Producer Consumer Problem - Learning Module

Loading content...

0/227

Semaphore Solution: The Complete Implementation

The Classic Semaphore Solution

Having examined the bounded buffer structure, the producer's algorithm, and the consumer's algorithm in isolation, we now synthesize them into the complete, classic solution. This solution, first described by Edsger Dijkstra in 1965, remains the canonical approach to the Producer-Consumer Problem—studied in every operating systems course and implemented in countless production systems.

The solution uses three semaphores working in concert:

empty — A counting semaphore tracking available buffer slots (initially N)
full — A counting semaphore tracking items waiting for consumption (initially 0)
mutex — A binary semaphore (mutex) providing mutual exclusion (initially 1)

Together, these semaphores guarantee mutual exclusion, prevent buffer overflow and underflow, avoid busy-waiting, and ensure progress for both producers and consumers.

What You Will Learn

By the end of this page, you will understand the complete semaphore solution's structure, why the ordering of semaphore operations is critical, how to trace execution through various scenarios, and how the solution handles edge cases. You'll see the solution in multiple programming languages and understand the design choices that make it both elegant and robust.

The Complete Semaphore Solution

Here is the complete, canonical semaphore solution to the Producer-Consumer Problem. Study this code carefully—every line is essential for correctness.

producer_consumer_complete.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
/*
 * The Classic Semaphore Solution to the Producer-Consumer Problem
 * 
 * This solution correctly handles:
 * - Mutual exclusion on buffer access
 * - Blocking when buffer is full (producers wait)
 * - Blocking when buffer is empty (consumers wait)
 * - Waking blocked threads when conditions change
 * - Multiple producers and multiple consumers
 */
 
#include <semaphore.h>
#include <pthread.h>
 
#define BUFFER_SIZE 10
 
// ========== SHARED DATA ==========
int buffer[BUFFER_SIZE];       // The bounded buffer (ring buffer)
int head = 0;                   // Write position for producers
int tail = 0;                   // Read position for consumers
 
// ========== SEMAPHORES ==========
sem_t empty;                    // Counts empty slots (initialized to BUFFER_SIZE)
sem_t full;                     // Counts full slots (initialized to 0)
sem_t mutex;                    // Binary semaphore for mutual exclusion (initialized to 1)
 
// Initialize the synchronization primitives
void init_buffer() {
    sem_init(&empty, 0, BUFFER_SIZE);  // N empty slots initially
    sem_init(&full, 0, 0);              // 0 items initially
    sem_init(&mutex, 0, 1);             // Mutex unlocked
}
 
// ========== PRODUCER ==========
void* producer(void* arg) {
    int item;
    
    while (1) {
        // Step 1: Produce item OUTSIDE critical section
        item = produce_item();
        
        // Step 2: Wait for an empty slot
        // BLOCKS if buffer is full (empty == 0)
        sem_wait(&empty);
        
        // Step 3: Acquire mutual exclusion
        // BLOCKS if another thread holds the mutex
        sem_wait(&mutex);
        
        // ========== CRITICAL SECTION START ==========
        // Step 4: Insert item into buffer
        buffer[head] = item;
        head = (head + 1) % BUFFER_SIZE;
        // ========== CRITICAL SECTION END ==========
        
        // Step 5: Release mutual exclusion
        sem_post(&mutex);
        
        // Step 6: Signal that an item is available
        // WAKES a blocked consumer if any
        sem_post(&full);
    }
    return NULL;
}
 
// ========== CONSUMER ==========
void* consumer(void* arg) {
    int item;
    
    while (1) {
        // Step 1: Wait for a full slot
        // BLOCKS if buffer is empty (full == 0)
        sem_wait(&full);
        
        // Step 2: Acquire mutual exclusion
        // BLOCKS if another thread holds the mutex
        sem_wait(&mutex);
        
        // ========== CRITICAL SECTION START ==========
        // Step 3: Remove item from buffer
        item = buffer[tail];
        tail = (tail + 1) % BUFFER_SIZE;
        // ========== CRITICAL SECTION END ==========
        
        // Step 4: Release mutual exclusion
        sem_post(&mutex);
        
        // Step 5: Signal that a slot is available
        // WAKES a blocked producer if any
        sem_post(&empty);
        
        // Step 6: Consume item OUTSIDE critical section
        consume_item(item);
    }
    return NULL;
}

Anatomy of the Solution:

Component	Type	Initial Value	Purpose
`empty`	Counting semaphore	N (buffer size)	Tracks available slots; producers wait on this
`full`	Counting semaphore	0	Tracks available items; consumers wait on this
`mutex`	Binary semaphore	1	Ensures only one thread modifies buffer at a time
`buffer[]`	Array	Undefined	The actual storage for items
`head`	Integer	0	Next write position (producer's index)
`tail`	Integer	0	Next read position (consumer's index)

The solution is remarkably concise—the core producer and consumer are each about 10 lines of code. Yet this simple structure correctly handles all the complexities of concurrent buffer access.

Why Operation Order Matters

The ordering of semaphore operations is critical for correctness. Changing the order can introduce deadlock or incorrect behavior. Let's examine why the specific ordering in our solution is necessary.

The Correct Producer Order:

1. wait(empty)   // First: acquire a slot
2. wait(mutex)   // Second: acquire exclusive access
3. [insert]      // Then: modify buffer
4. signal(mutex) // Fourth: release exclusive access
5. signal(full)  // Last: signal item available

The Correct Consumer Order:

1. wait(full)    // First: acquire an item
2. wait(mutex)   // Second: acquire exclusive access
3. [remove]      // Then: modify buffer
4. signal(mutex) // Fourth: release exclusive access
5. signal(empty) // Last: signal slot available

The Critical Rule: Always acquire counting semaphores BEFORE the mutex.

Deadlock with Wrong Ordering

What if the producer acquired mutex BEFORE empty?

wait(mutex)    // Acquire lock first
wait(empty)    // Then wait for slot — DEADLOCK POSSIBLE!

If the buffer is full, the producer blocks on wait(empty) WHILE HOLDING THE MUTEX. No consumer can acquire the mutex to remove an item and free a slot. The producer waits for a slot that will never become available. System halts.

Why the Correct Order Works:

Counting semaphores before mutex: By waiting on empty or full first, we only proceed if resources are available. We never block on a condition while holding a lock.
Mutex protects only the critical section: The mutex is held for the minimum necessary time—just for the buffer modification. This maximizes concurrency.
Signal mutex before counting semaphore: We release the mutex before signaling full/empty. If we signaled first, the awakened thread might immediately try to acquire the mutex we're still holding, causing unnecessary contention.

Trace: Correct Order with Full Buffer

Buffer: [■ ■ ■ ■ ■ ■ ■ ■ ■ ■]  (Full, empty=0, full=10)

Producer:                         Consumer:
---------                         ---------
wait(empty)                       
  → empty=0, BLOCKS waiting       
                                  wait(full)
                                    → full=10, becomes 9
                                  wait(mutex)
                                    → acquired
                                  [remove item]
                                  signal(mutex)
                                  signal(empty)
                                    → empty=0→1, WAKES producer!
Producer AWAKENED:
  → empty=1→0, proceeds
wait(mutex)
  → acquired
[insert item]
signal(mutex)
signal(full)
  → full=9→10

The producer correctly waits outside the mutex, is awakened when space becomes available, then proceeds.

Operation Order Comparison
Ordering	Result	Explanation
wait(counting) → wait(mutex)	✅ Correct	Block on condition OUTSIDE mutex; no deadlock possible
wait(mutex) → wait(counting)	❌ Deadlock	Block on condition WHILE holding mutex; counter-party can't proceed
signal(mutex) → signal(counting)	✅ Best practice	Release mutex first; awakened thread can proceed immediately
signal(counting) → signal(mutex)	✓ Correct but suboptimal	Works, but awakened thread blocks on mutex we still hold

Execution Trace: Normal Operation

Let's trace through a complete scenario with one producer and one consumer, starting from an empty buffer (N=5).

trace_normal.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
Initial State:
  buffer = [_, _, _, _, _]  (all slots empty)
  head = 0, tail = 0
  empty = 5, full = 0, mutex = 1
 
=== Step 1: Producer produces item A ===
Producer: item = produce_item()  → item = A
Producer: wait(empty)           → empty: 5→4, proceeds
Producer: wait(mutex)           → mutex: 1→0, acquired
Producer: buffer[0] = A         → buffer = [A, _, _, _, _]
Producer: head = 1              → head = 1
Producer: signal(mutex)         → mutex: 0→1
Producer: signal(full)          → full: 0→1
 
State after Step 1:
  buffer = [A, _, _, _, _]
  head = 1, tail = 0
  empty = 4, full = 1, mutex = 1
 
=== Step 2: Producer produces item B (concurrently) ===
Producer: item = produce_item()  → item = B
Producer: wait(empty)           → empty: 4→3, proceeds
Producer: wait(mutex)           → mutex: 1→0, acquired
Producer: buffer[1] = B         → buffer = [A, B, _, _, _]
Producer: head = 2              → head = 2
Producer: signal(mutex)         → mutex: 0→1
Producer: signal(full)          → full: 1→2
 
State after Step 2:
  buffer = [A, B, _, _, _]
  head = 2, tail = 0
  empty = 3, full = 2, mutex = 1
 
=== Step 3: Consumer removes item ===
Consumer: wait(full)            → full: 2→1, proceeds
Consumer: wait(mutex)           → mutex: 1→0, acquired
Consumer: item = buffer[0]      → item = A
Consumer: tail = 1              → tail = 1
Consumer: signal(mutex)         → mutex: 0→1
Consumer: signal(empty)         → empty: 3→4
Consumer: consume_item(A)       → processing A...
 
State after Step 3:
  buffer = [_, B, _, _, _]  (slot 0 is now "empty" conceptually)
  head = 2, tail = 1
  empty = 4, full = 1, mutex = 1
 
Invariant check: empty + full = 4 + 1 = 5 = N ✓

Key Observations from the Trace:

Semaphore values track resources faithfully: empty decreases as items are inserted, full increases. The inverse happens on removal.
The mutex serializes access: Only one thread modifies head/tail at a time.
FIFO order is preserved: Item A was inserted first and removed first.
Conservation law holds: empty + full = N at every step.
Conceptual vs physical state: Slot 0 still contains 'A' after removal, but it's logically "empty" (tail has advanced past it). The slot will be overwritten on the next producer cycle.

Ring Buffer Reuse

Notice that consumed slots aren't "cleared"—we just advance the tail pointer. The old data remains until overwritten by the next producer cycle. This is safe because (1) the slot isn't included in the active region (between tail and head), and (2) no thread will read from positions before tail.

Execution Trace: Edge Cases

Let's trace through critical edge cases: the buffer becoming full and becoming empty.

Case 1: Buffer Becomes Full (Producer Blocks)

trace_full.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
Initial State:
  buffer = [A, B, C, D, _]  (4 items)
  head = 4, tail = 0
  empty = 1, full = 4, mutex = 1
 
=== Producer inserts 5th item (E) ===
Producer: wait(empty)           → empty: 1→0, proceeds
Producer: wait(mutex)           → acquired
Producer: buffer[4] = E         → buffer = [A, B, C, D, E]
Producer: head = 0              → head = 0 (wrapped!)
Producer: signal(mutex)         → released
Producer: signal(full)          → full: 4→5
 
State: buffer FULL
  empty = 0, full = 5
  head = 0, tail = 0  (head "caught up" to tail)
 
=== Producer tries to insert 6th item (F) ===
Producer: wait(empty)           → empty = 0, BLOCKS! ←←←
   Producer is now in empty's wait queue
   
=== Consumer removes item ===
Consumer: wait(full)            → full: 5→4
Consumer: wait(mutex)           → acquired
Consumer: item = buffer[0]      → item = A
Consumer: tail = 1              → tail = 1
Consumer: signal(mutex)         → released
Consumer: signal(empty)         → empty: 0→1, WAKES PRODUCER!
 
=== Producer AWAKENED ===
Producer: (returns from wait(empty), empty is now 0 again after decrement)
Producer: wait(mutex)           → acquired
Producer: buffer[0] = F         → buffer = [F, B, C, D, E]
Producer: head = 1              → head = 1
Producer: signal(mutex)         → released
Producer: signal(full)          → full: 4→5
 
Final State:
  buffer = [F, B, C, D, E]
  head = 1, tail = 1
  empty = 0, full = 5  (buffer is full again)

Case 2: Buffer Becomes Empty (Consumer Blocks)

trace_empty.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
Initial State:
  buffer = [_, _, _, _, A]  (1 item at position 4)
  head = 0, tail = 4
  empty = 4, full = 1, mutex = 1
 
=== Consumer removes last item ===
Consumer: wait(full)            → full: 1→0, proceeds
Consumer: wait(mutex)           → acquired
Consumer: item = buffer[4]      → item = A
Consumer: tail = 0              → tail = 0 (wrapped!)
Consumer: signal(mutex)         → released
Consumer: signal(empty)         → empty: 4→5
 
State: buffer EMPTY
  empty = 5, full = 0
  head = 0, tail = 0  (they match, buffer empty)
 
=== Consumer tries to remove another item ===
Consumer: wait(full)            → full = 0, BLOCKS! ←←←
   Consumer is now in full's wait queue
 
=== Producer inserts item ===
Producer: item = produce_item()  → item = B
Producer: wait(empty)           → empty: 5→4
Producer: wait(mutex)           → acquired
Producer: buffer[0] = B         → buffer = [B, _, _, _, _]
Producer: head = 1              → head = 1
Producer: signal(mutex)         → released
Producer: signal(full)          → full: 0→1, WAKES CONSUMER!
 
=== Consumer AWAKENED ===
Consumer: (returns from wait(full), full is now 0 after decrement)
Consumer: wait(mutex)           → acquired
Consumer: item = buffer[0]      → item = B
Consumer: tail = 1              → tail = 1
Consumer: signal(mutex)         → released
Consumer: signal(empty)         → empty: 4→5
Consumer: consume_item(B)       → processing B...

The Wake-and-Decrement Dance

When a blocked thread is awakened by signal(), the semaphore value has already been incremented. The awakened thread then atomically decrements it as part of returning from wait(). So if empty was 0, signal() increments it to 1, and the awakened producer's wait() decrements it back to 0 as it returns. The net effect: producer proceeds, slot is now claimed.

Multiple Producers and Consumers

The solution naturally extends to multiple producers and multiple consumers. No code changes are required—the semaphores correctly coordinate any number of competing threads.

Why It Works with Multiple Producers:

Each producer decrements empty before inserting. If empty = 3 and 5 producers try to insert simultaneously, exactly 3 will pass wait(empty); the other 2 will block.
The mutex ensures only one producer modifies head at a time. Producers serialize through the critical section.
Each producer signals full after inserting. Consumers are correctly notified of each new item.

Why It Works with Multiple Consumers:

Each consumer decrements full before removing. If full = 3 and 5 consumers try to remove simultaneously, exactly 3 will pass wait(full); the other 2 will block.
The mutex ensures only one consumer modifies tail at a time. Consumers serialize through the critical section.
Each consumer signals empty after removing. Producers are correctly notified of each freed slot.

multi_trace.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
Scenario: 2 Producers (P1, P2), 2 Consumers (C1, C2), Buffer Size = 3
 
Initial: empty=3, full=0, mutex=1, buffer=[_,_,_]
 
Time    P1              P2              C1              C2
----    --              --              --              --
t1      wait(empty)                                     
        →3→2,proceed                                    
t2                      wait(empty)                     
                        →2→1,proceed                    
t3      wait(mutex)                                     
        →1→0,acquired                                   
t4                      wait(mutex)                     
                        →BLOCKS(P1 has it)              
t5      insert item A                                   
        head=0→1                                        
t6      signal(mutex)                                   
        →0→1                                            
t7                      (WAKES, acquires)               
                        →1→0,acquired                   
t8      signal(full)                                    
        →0→1                                            
t9                      insert item B                   wait(full)
                        head=1→2                        →1→0,proceed
t10                     signal(mutex)   wait(mutex)     
                        →0→1            BLOCKS          
t11                     signal(full)    (WAKES)         
                        →0→1            acquired        
t12                                     remove A        wait(full)
                                        tail=0→1        →1→0,proceed
t13                                     signal(mutex)   wait(mutex)
                                        →0→1            BLOCKS
t14                                     signal(empty)   
                                        →1→2            
t15                                     consume(A)      (WAKES)
                                                        acquired
t16                                                     remove B
                                                        tail=1→2
 
Final: empty=2, full=0, buffer=[_,_,_] (conceptually empty)
Both A and B were produced and consumed correctly.

Fairness Considerations:

With multiple producers/consumers, fairness becomes relevant:

FIFO semaphores: If the semaphore implementation uses FIFO queuing, threads are served in the order they blocked. A producer that blocked first gets the first free slot.
Priority inversion: If a low-priority consumer holds the mutex, a high-priority producer must wait. This is generally acceptable for short critical sections.
Starvation prevention: FIFO semaphores guarantee bounded waiting—no thread waits forever if resources eventually become available.

Performance with Many Threads:

As thread count increases, contention points become bottlenecks:

Mutex contention: All threads serialize through the mutex. With many threads, this limits throughput.
Semaphore contention: wait/signal operations involve atomic operations and potential context switches.

Optimizations for high-concurrency scenarios include lock-free structures, sharded buffers, or batch operations.

Scalability Limits

The classic solution, while correct, doesn't scale perfectly to many cores. With 100+ threads, mutex contention becomes significant. Production systems often use lock-free queues (e.g., disruptor pattern) or per-core buffers for extreme throughput requirements.

Implementation in Different Languages

The classic solution can be implemented in any language with semaphore support. Modern languages often provide higher-level abstractions that encapsulate this pattern.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
// Complete C implementation with POSIX threads
 
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>
 
#define BUFFER_SIZE 5
#define NUM_ITEMS 20
 
int buffer[BUFFER_SIZE];
int head = 0, tail = 0;
 
sem_t empty_sem, full_sem, mutex_sem;
 
void* producer(void* arg) {
    int id = *(int*)arg;
    for (int i = 0; i < NUM_ITEMS; i++) {
        int item = id * 100 + i;  // Unique item ID
        
        sem_wait(&empty_sem);     // Wait for empty slot
        sem_wait(&mutex_sem);     // Enter critical section
        
        buffer[head] = item;
        printf("Producer %d: inserted %d at position %d\n", id, item, head);
        head = (head + 1) % BUFFER_SIZE;
        
        sem_post(&mutex_sem);     // Exit critical section
        sem_post(&full_sem);      // Signal item available
        
        usleep(rand() % 1000);    // Simulate variable production time
    }
    return NULL;
}
 
void* consumer(void* arg) {
    int id = *(int*)arg;
    for (int i = 0; i < NUM_ITEMS; i++) {
        sem_wait(&full_sem);      // Wait for item
        sem_wait(&mutex_sem);     // Enter critical section
        
        int item = buffer[tail];
        printf("Consumer %d: removed %d from position %d\n", id, item, tail);
        tail = (tail + 1) % BUFFER_SIZE;
        
        sem_post(&mutex_sem);     // Exit critical section
        sem_post(&empty_sem);     // Signal slot available
        
        usleep(rand() % 2000);    // Simulate variable consumption time
    }
    return NULL;
}
 
int main() {
    sem_init(&empty_sem, 0, BUFFER_SIZE);
    sem_init(&full_sem, 0, 0);
    sem_init(&mutex_sem, 0, 1);
    
    pthread_t prod_threads[2], cons_threads[2];
    int ids[] = {1, 2};
    
    for (int i = 0; i < 2; i++) {
        pthread_create(&prod_threads[i], NULL, producer, &ids[i]);
        pthread_create(&cons_threads[i], NULL, consumer, &ids[i]);
    }
    
    for (int i = 0; i < 2; i++) {
        pthread_join(prod_threads[i], NULL);
        pthread_join(cons_threads[i], NULL);
    }
    
    sem_destroy(&empty_sem);
    sem_destroy(&full_sem);
    sem_destroy(&mutex_sem);
    
    return 0;
}

Language Abstractions

Notice how Go channels completely abstract away the semaphore mechanics. The channel IS the bounded buffer, and send/receive operations have the waiting and signaling built in. Understanding the underlying semaphore solution helps you understand what channels do internally and debug blocking issues.

Common Pitfalls and Mistakes

Even with a well-understood solution, implementation mistakes are common. Here are pitfalls to avoid:

Common Mistakes

•Wrong semaphore order — Acquiring mutex before the counting semaphore causes deadlock when buffer is full/empty.
•Forgetting to signal — Every wait() must have a matching signal(). If a thread forgets to signal, other threads block forever.
•Double wait or double signal — Calling wait() or signal() twice in a row breaks the semaphore invariants.
•Wrong initial values — empty should be N (not 0), full should be 0 (not N). Swapping these inverts the logic.
•Using wrong semaphore — Producer waiting on 'full' or consumer waiting on 'empty' inverts the blocking condition.
•Exception safety — If an exception is thrown between wait(mutex) and signal(mutex), the mutex is never released—deadlock.
•Modifying buffer outside mutex — Accessing buffer[head] or buffer[tail] without holding the mutex causes race conditions.
•Forgetting to update head/tail — Inserting without advancing head leaves stale data; removing without advancing tail re-reads items.

pitfall_examples.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// ❌ WRONG: Semaphore order reversed
void bad_producer() {
    wait(&mutex);     // Acquired mutex first
    wait(&empty);     // Now waiting for slot while holding mutex - DEADLOCK!
    // ...
}
 
// ❌ WRONG: Forgot to signal
void bad_consumer() {
    wait(&full);
    wait(&mutex);
    item = buffer[tail];
    tail = (tail + 1) % N;
    signal(&mutex);
    // Forgot signal(&empty)! Producers will eventually all block.
    consume(item);
}
 
// ❌ WRONG: Initial values swapped
sem_init(&empty, 0, 0);       // Should be N!
sem_init(&full, 0, BUFFER_SIZE);  // Should be 0!
// Consumers will proceed on empty buffer, producers will block on empty buffer
 
// ❌ WRONG: Using wrong semaphore
void confused_producer() {
    wait(&full);      // Producer waiting on full? Wrong!
    // Should be wait(&empty)
    // This blocks until items exist, not until space exists
}
 
// ✅ CORRECT: Exception-safe with RAII or try-finally
void safe_producer() {
    wait(&empty);
    wait(&mutex);
    try {
        buffer[head] = produce();
        head = (head + 1) % N;
    } finally {
        signal(&mutex);
    }
    signal(&full);
}

Debugging Deadlocks

If your program hangs, check: (1) Are all threads blocked on semaphores? (2) What are the semaphore values? If empty=0 and full=N (or vice versa) but threads are stuck, you likely have a signaling bug. If mutex is locked but no thread is in the critical section, you have an exception safety bug.

Summary: The Semaphore Solution Mastery

We've now seen the complete semaphore solution in full detail. Let's consolidate the key points:

Key Takeaways

•Three semaphores: empty (counting, init=N), full (counting, init=0), mutex (binary, init=1).
•Correct order: wait(counting) → wait(mutex) → [operation] → signal(mutex) → signal(counting).
•Why order matters: Acquiring mutex before counting semaphore causes deadlock when buffer is full/empty.
•Producer sequence: wait(empty) → wait(mutex) → insert → signal(mutex) → signal(full).
•Consumer sequence: wait(full) → wait(mutex) → remove → signal(mutex) → signal(empty).
•Conservation law: empty + full = N always holds.
•Multiple entities: Solution handles multiple producers and consumers without modification.
•Edge cases: Full buffer blocks producers; empty buffer blocks consumers; signals wake waiters.
•Exception safety: Ensure signals occur even if exceptions are thrown between waits.

What's Next:

The solution works—but how do we know it's correct? The final page of this module provides a rigorous correctness analysis. We'll formally prove that the semaphore solution satisfies mutual exclusion, prevents deadlock, avoids starvation, and preserves buffer invariants. This analysis completes our deep understanding of the Producer-Consumer Problem.

Page Complete

You now understand the complete semaphore solution—its structure, operation ordering, execution behavior, multi-language implementations, and common pitfalls. Next, we'll prove this solution correct using formal analysis techniques.