OS Notes
HubFunctions of Operating SystemsHistory of Operating SystemsObjectives of Operating SystemsTypes of Operating Systems — Operating SystemsWhat is an Operating SystemThe Booting ProcessThe KernelOperating System ServicesOperating System StructureSystem CallsUser Mode vs Kernel ModeContext SwitchingInterprocess Communication (IPC)MultithreadingProcess Control Block (PCB)Introduction to ProcessesProcess SchedulingProcess StatesThreadsCritical Section ProblemDining Philosophers ProblemMonitorsMutex LocksProducer-Consumer ProblemReaders-Writers ProblemSemaphoresIntroduction to Process SynchronizationBanker\Deadlock AvoidanceDeadlock DetectionIntroduction to DeadlocksDeadlock PreventionDeadlock RecoveryNecessary Conditions for DeadlockResource Allocation GraphContiguous Memory AllocationDemand PagingMemory Management IntroductionPage Replacement AlgorithmsPagingSegmentationThrashingVirtual Memory — Operating SystemsDisk Scheduling - I/O OptimizationDisk Structure - Physical OrganizationRAID - Redundant Array of Independent DisksSecondary Storage - Persistent StorageStorage Virtualization - Abstract StorageSwap Space Management - Virtual MemoryDirectory StructureFile Allocation MethodsFile ConceptsFile ProtectionFile System ImplementationFile System IntroductionFree Space ManagementDevice DriversDisk Scheduling AlgorithmsDMA - Direct Memory AccessInterruptsI/O HardwareI/O SoftwareCPU Scheduling Interview QuestionsLinux Interview QuestionsMemory Management Interview QuestionsOperating System CheatsheetOperating System Interview Questions — Operating SystemsAndroid Operating System — Operating SystemsEmbedded OS Case StudyiOS Operating System — Operating SystemsLinux ArchitectureWindows ArchitectureGlossary of Terms — Operating SystemsImportant Formulas — Operating SystemsQuick Revision Notes — Operating SystemsRecommended Books — Operating SystemsFCFS Scheduling - First Come First ServedMultilevel Feedback Queue SchedulingMultilevel Queue SchedulingPriority SchedulingRound Robin SchedulingScheduling Algorithm ComparisonCPU Scheduling ConceptsSJF Scheduling - Shortest Job FirstCloud Operating Systems - Architecture and ImplementationDistributed Operating Systems - Design and ConceptsEmbedded Operating Systems - Real-time and Resource-ConstrainedMobile Operating Systems - Android, iOS, and WindowsNetwork Operating Systems - NOS ArchitectureReal-Time Operating SystemsVirtualization - Containers and Virtual MachinesAdvanced Virtualization - Full and Para-virtualizationBasic Linux Commands - Command Line UsageLinux File System - ext4 and othersLinux Introduction - OS OverviewPermissions and Security - Linux SecurityProcess Management in Linux - Process ControlShell Scripting - Bash ProgrammingUser Management - Users and GroupsBankerCPU Scheduling Simulator ProjectMini Operating System ProjectPage Replacement SimulatorShell Scripting ProjectsAccess Control - Permission ModelsAuthentication - User VerificationAuthorization - Access ControlMalware and Threats - Security ThreatsOS Security Basics - Threats and ControlsProtection Mechanisms - Security ImplementationSecurity Best Practices - OS Hardening
The classic producer-consumer (bounded buffer) synchronization problem — solutions using semaphores, mutex locks, and monitors with complete code examples.
Introduction
The producer-consumer problem is one of the most important and frequently occurring synchronization problems in computing. A producer process generates data and places it in a buffer. A consumer process takes data from the buffer and uses it. They must synchronize so that the producer does not add data to a full buffer and the consumer does not try to remove data from an empty buffer.
This pattern appears everywhere: a web server producing log entries while a logger consumes them, a keyboard driver producing keystrokes while the terminal application consumes them, a video decoder producing frames while the display driver consumes them.
Problem Statement
- A shared buffer of size N exists between producer and consumer processes
- The producer generates items and places them in the buffer
- The consumer removes items from the buffer and processes them
- The producer must wait if the buffer is full
- The consumer must wait if the buffer is empty
- Access to the buffer must be mutually exclusive (only one modifies at a time)
Example
Producer → [Buffer: slot1 | slot2 | ... | slotN] → Consumer
Three synchronization needs:
1. Mutual exclusion on buffer access
2. Producer blocks when buffer is full (count == N)
3. Consumer blocks when buffer is empty (count == 0)
Solution Using Semaphores
Example
#include <semaphore.h>
#include <pthread.h>
#define BUFFER_SIZE 10
int buffer[BUFFER_SIZE];
int in = 0, out = 0;
sem_t mutex; // Binary semaphore for mutual exclusion (init = 1)
sem_t empty; // Counting semaphore: empty slots (init = BUFFER_SIZE)
sem_t full; // Counting semaphore: full slots (init = 0)
void *producer(void *arg) {
while (1) {
int item = produce_item();
sem_wait(&empty); // Wait for an empty slot (decrement empty count)
sem_wait(&mutex); // Enter critical section
buffer[in] = item;
in = (in + 1) % BUFFER_SIZE;
sem_post(&mutex); // Exit critical section
sem_post(&full); // Signal that one more slot is full
}
}
void *consumer(void *arg) {
while (1) {
sem_wait(&full); // Wait for a full slot (decrement full count)
sem_wait(&mutex); // Enter critical section
int item = buffer[out];
out = (out + 1) % BUFFER_SIZE;
sem_post(&mutex); // Exit critical section
sem_post(&empty); // Signal that one more slot is empty
consume_item(item);
}
}
int main() {
sem_init(&mutex, 0, 1);
sem_init(&empty, 0, BUFFER_SIZE);
sem_init(&full, 0, 0);
pthread_t prod, cons;
pthread_create(&prod, NULL, producer, NULL);
pthread_create(&cons, NULL, consumer, NULL);
pthread_join(prod, NULL);
pthread_join(cons, NULL);
return 0;
}
Why the Order of sem_wait Matters
CRITICAL: The order sem_wait(&empty) then sem_wait(&mutex) is essential. If reversed:
c example
// WRONG ORDER — causes deadlock!
sem_wait(&mutex); // Got mutex
sem_wait(&empty); // Buffer full! Block... but still hold mutex!
// Consumer cannot acquire mutex to remove items
// → DEADLOCKAlways wait on the counting semaphore (condition check) BEFORE the mutex (critical section entry).
Solution Using Mutex + Condition Variables
Example
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t not_full = PTHREAD_COND_INITIALIZER;
pthread_cond_t not_empty = PTHREAD_COND_INITIALIZER;
int buffer[BUFFER_SIZE];
int count = 0, in = 0, out = 0;
void *producer(void *arg) {
while (1) {
int item = produce_item();
pthread_mutex_lock(&mutex);
while (count == BUFFER_SIZE)
pthread_cond_wait(¬_full, &mutex); // Wait + release mutex atomically
buffer[in] = item;
in = (in + 1) % BUFFER_SIZE;
count++;
pthread_cond_signal(¬_empty); // Wake consumer
pthread_mutex_unlock(&mutex);
}
}
void *consumer(void *arg) {
while (1) {
pthread_mutex_lock(&mutex);
while (count == 0)
pthread_cond_wait(¬_empty, &mutex);
int item = buffer[out];
out = (out + 1) % BUFFER_SIZE;
count--;
pthread_cond_signal(¬_full); // Wake producer
pthread_mutex_unlock(&mutex);
consume_item(item);
}
}
Multiple Producers and Consumers
The semaphore solution naturally supports multiple producers and multiple consumers. The mutex ensures only one thread modifies the buffer at a time, while the counting semaphores track available slots regardless of how many producers or consumers exist.
Real-World Applications
| Application | Producer | Consumer | Buffer |
|---|---|---|---|
| Print spooling | Applications | Printer driver | Print queue |
| Web server | Network listener | Worker threads | Request queue |
| Video streaming | Decoder | Display driver | Frame buffer |
| Logging | Application threads | Log writer | Log buffer |
| Keyboard input | Keyboard driver | Application | Key buffer |
Real-World Analogy
The producer-consumer problem is like a sushi conveyor belt restaurant. The chef (producer) places sushi plates on the belt (buffer). Customers (consumers) take plates off. If the belt is full, the chef waits. If the belt is empty, customers wait. Only one person can place or take a plate at each position at a time (mutual exclusion). The belt has finite capacity (bounded buffer).
Key Takeaways
- The producer-consumer problem requires three types of synchronization: mutual exclusion, full-buffer blocking, and empty-buffer blocking
- The semaphore solution uses three semaphores: mutex (mutual exclusion), empty (available slots), full (occupied slots)
- Order of semaphore operations is critical — always wait on counting semaphore before mutex
- Condition variables with mutex provide an equivalent modern solution
- The pattern appears universally in systems: queues, buffers, pipelines
- Multiple producers and consumers are handled naturally by the same synchronization structure
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Producer-Consumer Problem.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Operating Systems topic.
Search Terms
operating-systems, operating systems, operating, systems, process, synchronization, producer, consumer
Related Operating Systems Topics
Continue learning this concept
Process SynchronizationCritical Section ProblemDeep dive into the critical section problem — requirements, software solutions (Peterson\Process SynchronizationDining Philosophers ProblemThe classic dining philosophers problem — problem statement, naive solution showing deadlock, correct solutions using semaphores, monitors, and resource hierarchy.Process SynchronizationReaders-Writers ProblemThe readers-writers synchronization problem — first readers-writers problem (readers preference), second variant (writers preference), and starvation-free solutions.Process SynchronizationMonitorsUnderstanding monitors as a high-level synchronization construct — encapsulation, condition variables, wait and signal operations, and comparison with semaphores.Process SynchronizationMutex LocksUnderstanding mutex locks for mutual exclusion — acquire and release operations, spinlocks vs blocking mutexes, recursive mutexes, and practical mutex usage patterns.Process SynchronizationSemaphoresComplete guide to semaphores — counting and binary semaphores, wait() and signal() operations, implementation, usage patterns, and solving synchronization problems with semaphores.