Solution: Bounded Buffer… — Producer-Consumer Pattern | OneNoughtOne

0/105

System Design (LLD)Concurrency Patterns

Producer-Consumer Pattern

LevelIntermediate

Duration90 mins

TopicConcurrency Patterns

2 / 4

Solution: Bounded Buffer with Synchronization

The Classic Solution

The solution to the Producer-Consumer problem has been studied and refined for over 50 years, since Edsger Dijkstra first formalized it in 1965. The bounded buffer with proper synchronization remains the gold standard because it elegantly solves every challenge we identified in the previous page. The core insight of the solution is deceptively simple: use counting to track available slots and items, and use condition variables to efficiently wait for those counts to change . This combination prevents race conditions, handles rate mismatches, avoids deadlock, and ensures fairness. In this page, we'll build this solution from first principles, understanding not just what to implement but why each component is necessary. By the end, you'll be able to implement correct Producer-Consumer systems and recognize when existing implementations are flawed.

What You Will Learn

This page covers the canonical bounded buffer solution: understanding semaphores and condition variables, implementing the classic two-semaphore solution, handling edge cases correctly, and ensuring both correctness and efficiency.

The Bounded Buffer Concept

A bounded buffer is a fixed-capacity data structure that sits between producers and consumers. Its bounded nature is critical—it prevents unbounded memory growth when producers are faster than consumers, and its fixed size allows us to reason precisely about its state. The Key Invariants A correctly implemented bounded buffer maintains these invariants at all times: 0 \leq item_count \leq capacity : The buffer never has negative items and never exceeds its capacity available_slots + item_count = capacity : The sum of empty slots and filled slots equals total capacity FIFO ordering (typically): Items are consumed in the order they were produced The State Space At any moment, a bounded buffer is in one of three states:

Bounded Buffer States
State	Condition	Producer Action	Consumer Action
Empty	item_count = 0	Can produce immediately	Must wait for items
Partial	0 < item_count < capacity	Can produce immediately	Can consume immediately
Full	item_count = capacity	Must wait for space	Can consume immediately

Why Bounded? The boundedness is not merely a practical constraint—it's essential for correctness: Backpressure : When the buffer fills, producers are forced to slow down, preventing memory exhaustion Latency Control : Items don't wait indefinitely in the buffer; the maximum wait time is bounded Resource Predictability : Memory usage is constant and predictable, essential for systems programming Fairness Enablement : Bounded waiting allows fairness guarantees that unbounded buffers cannot provide

Choosing Buffer Size

Buffer size is a crucial design decision. Too small: producers block excessively, reducing throughput. Too large: high memory usage, increased latency, delayed backpressure. The optimal size depends on production/consumption rate variance. A common heuristic: buffer enough to absorb brief rate spikes without excessive memory use.

Understanding Semaphores

The classic solution to the Producer-Consumer problem uses semaphores, a synchronization primitive invented by Dijkstra. A semaphore is essentially a non-negative integer counter with two atomic operations. Semaphore Operations wait() (also called P, down, or acquire): If counter > 0: decrement counter and return immediately If counter = 0: block until counter becomes positive, then decrement and return signal() (also called V, up, or release): Increment counter by 1 If any threads are blocked waiting, wake one up Why Semaphores Work Semaphores solve the Producer-Consumer problem because they encode counting into the synchronization primitive. Instead of checking "is buffer full?" and then acting (which creates a race), we atomically "try to decrement the empty-slot counter and block if it's already zero."

semaphore-concept.ts
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
// Conceptual Semaphore Implementation (not production-ready)
class Semaphore {
    private permits: number;
    private waitQueue: Array<() => void> = [];
    
    constructor(initialPermits: number) {
        if (initialPermits < 0) throw new Error("Permits cannot be negative");
        this.permits = initialPermits;
    }
    
    /**
     * Acquire a permit (wait/P/down)
     * Blocks if no permits are available
     */
    async acquire(): Promise<void> {
        // In a real implementation, this entire method is atomic
        if (this.permits > 0) {
            this.permits--;
            return;
        }
        
        // No permits available - block until signaled
        return new Promise<void>((resolve) => {
            this.waitQueue.push(resolve);
        });
    }
    
    /**
     * Release a permit (signal/V/up)
     * Wakes one waiting thread if any
     */
    release(): void {
        this.permits++;
        
        // Wake one waiting thread if any
        const waiter = this.waitQueue.shift();
        if (waiter) {
            this.permits--;  // Give the permit to the waiter
            waiter();
        }
    }
    
    /**
     * Check available permits (for debugging only)
     */
    availablePermits(): number {
        return this.permits;
    }
}
 
// Usage:
// Semaphore with 3 permits = 3 threads can acquire simultaneously
// 4th thread blocks until one releases

Two Types of Semaphores

•Binary Semaphore (Mutex) — Initialized to 1, allows only one thread at a time. Used for mutual exclusion. Similar to a lock.
•Counting Semaphore — Initialized to n, allows n threads concurrently. Used to limit access to a finite pool of resources. Essential for Producer-Consumer.

The Two-Semaphore Solution

The classic Producer-Consumer solution uses three semaphores: empty (counting): Tracks available slots for producers (initialized to buffer capacity) full (counting): Tracks available items for consumers (initialized to 0) mutex (binary): Protects buffer access to ensure only one thread modifies at a time The brilliance of this design is that semaphores elegantly encode both counting and waiting. Producers wait on empty (no slots) and signal full (added an item). Consumers wait on full (no items) and signal empty (freed a slot).

classic-producer-consumer.ts
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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
/**
 * Classic Producer-Consumer with Semaphores
 * 
 * This implementation is correct, deadlock-free, and handles
 * all the edge cases we discussed in the problem page.
 */
class BoundedBuffer<T> {
    private buffer: T[] = [];
    private readonly capacity: number;
    
    // Semaphores for coordination
    private empty: Semaphore;  // Counts empty slots (producer waits)
    private full: Semaphore;   // Counts filled slots (consumer waits)
    private mutex: Semaphore;  // Mutual exclusion for buffer access
    
    constructor(capacity: number) {
        this.capacity = capacity;
        
        // Initially: all slots are empty, no items
        this.empty = new Semaphore(capacity);  // capacity empty slots
        this.full = new Semaphore(0);          // 0 items
        this.mutex = new Semaphore(1);         // Binary for mutual exclusion
    }
    
    /**
     * Producer: Add item to buffer
     * 
     * Order of operations is CRITICAL:
     * 1. Wait for empty slot (blocks if buffer full)
     * 2. Acquire mutex (protect buffer modification)
     * 3. Add item to buffer
     * 4. Release mutex
     * 5. Signal that item is available
     */
    async produce(item: T): Promise<void> {
        // Step 1: Wait for an empty slot
        // This blocks if buffer is full (empty count is 0)
        await this.empty.acquire();
        
        // Step 2: Lock the buffer
        // This ensures only one producer/consumer modifies buffer
        await this.mutex.acquire();
        
        try {
            // Step 3: Add item (protected by mutex)
            this.buffer.push(item);
        } finally {
            // Step 4: Release mutex (always, even on error)
            this.mutex.release();
        }
        
        // Step 5: Signal that an item is available
        // This wakes a waiting consumer, if any
        this.full.release();
    }
    
    /**
     * Consumer: Remove item from buffer
     * 
     * Mirror of producer, with opposite semaphores:
     * 1. Wait for item (blocks if buffer empty)
     * 2. Acquire mutex (protect buffer modification)
     * 3. Remove item from buffer
     * 4. Release mutex
     * 5. Signal that slot is available
     */
    async consume(): Promise<T> {
        // Step 1: Wait for an item
        // This blocks if buffer is empty (full count is 0)
        await this.full.acquire();
        
        // Step 2: Lock the buffer
        await this.mutex.acquire();
        
        let item: T;
        try {
            // Step 3: Remove item (protected by mutex)
            item = this.buffer.shift()!;
        } finally {
            // Step 4: Release mutex (always, even on error)
            this.mutex.release();
        }
        
        // Step 5: Signal that a slot is available
        // This wakes a waiting producer, if any
        this.empty.release();
        
        return item;
    }
}
 
// Usage Example:
const buffer = new BoundedBuffer<string>(10);
 
// Producer thread
async function producer(id: number) {
    for (let i = 0; i < 100; i++) {
        const item = `Item ${i} from Producer ${id}`;
        await buffer.produce(item);
        console.log(`Producer ${id} added: ${item}`);
    }
}
 
// Consumer thread
async function consumer(id: number) {
    while (true) {
        const item = await buffer.consume();
        console.log(`Consumer ${id} processed: ${item}`);
        // Process the item...
    }
}

Order of Semaphore Operations Matters!

The order of wait operations (empty before mutex for producers, full before mutex for consumers) is CRITICAL. Reversing them causes deadlock! If a producer acquires mutex first and then waits on empty, and a consumer needs mutex to release empty, neither can proceed.

Why This Solution is Correct

Let's verify that the semaphore solution satisfies all the correctness requirements we established:

Correctness Verification
Requirement	How Solution Satisfies It
Mutual Exclusion	The mutex semaphore ensures only one thread modifies the buffer at any time. All buffer operations are wrapped in mutex acquire/release.
Buffer Bounds Respected	Producers can only proceed after acquiring an 'empty' permit—impossible if buffer is full. Consumers can only proceed after acquiring a 'full' permit—impossible if buffer is empty.
No Deadlock	The order of semaphore operations prevents circular wait. Threads wait on counting semaphores BEFORE acquiring mutex, never holding mutex while waiting for capacity/items.
No Starvation	Semaphore implementations typically use FIFO ordering for waiters. Each release wakes the longest-waiting thread, ensuring bounded wait times.
Correct Signaling	Producers release 'full' after adding an item, waking waiting consumers. Consumers release 'empty' after removing, waking waiting producers.

The Invariant Preservation Proof We can prove correctness by showing that the invariant empty + full = capacity is always maintained: Initially: empty = capacity, full = 0 empty + full = capacity ✓ After produce(): empty decremented by 1 (acquired) full incremented by 1 (released) Net change: empty + full unchanged ✓ After consume(): full decremented by 1 (acquired) empty incremented by 1 (released) Net change: empty + full unchanged ✓ Since the invariant holds initially and every operation preserves it, it always holds. This proves: Buffer never overflows: full \leq capacity (since full = capacity - empty \leq capacity) Buffer never underflows: full \geq 0 (semaphore count can't go negative)

The Power of Invariants

Reasoning about concurrent code is notoriously difficult. Invariant-based proofs provide confidence that code is correct. When writing concurrent code, always identify the invariants and verify that every operation preserves them.

The Condition Variable Alternative

While semaphores provide an elegant solution, many modern languages and frameworks use condition variables instead. Condition variables offer a more general mechanism for waiting on arbitrary conditions, not just counting. How Condition Variables Work A condition variable is always used with a lock/mutex. It provides: wait(lock) : Atomically release lock and block until signaled; re-acquire lock before returning notify() / signal() : Wake one waiting thread notifyAll() / broadcast() : Wake all waiting threads The key advantage: you can wait on any boolean condition, not just counter values.

condition-variable-solution.ts
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
import java.util.LinkedList;
import java.util.Queue;
import java.util.concurrent.locks.*;
 
/**
 * Producer-Consumer with Condition Variables
 * 
 * This is often preferred in Java because it allows
 * separate conditions for producers and consumers.
 */
public class BoundedBuffer<T> {
    private final Queue<T> buffer = new LinkedList<>();
    private final int capacity;
    
    private final Lock lock = new ReentrantLock();
    private final Condition notFull = lock.newCondition();   // For producers
    private final Condition notEmpty = lock.newCondition();  // For consumers
    
    public BoundedBuffer(int capacity) {
        this.capacity = capacity;
    }
    
    /**
     * Producer: Add item, wait if buffer is full
     */
    public void produce(T item) throws InterruptedException {
        lock.lock();
        try {
            // WHILE loop, not IF - guard against spurious wakeups
            while (buffer.size() == capacity) {
                // Buffer is full, wait for consumer to make room
                notFull.await();  // Atomically release lock and wait
            }
            
            buffer.add(item);
            
            // Signal consumers that an item is available
            notEmpty.signal();
        } finally {
            lock.unlock();
        }
    }
    
    /**
     * Consumer: Remove item, wait if buffer is empty
     */
    public T consume() throws InterruptedException {
        lock.lock();
        try {
            // WHILE loop, not IF - guard against spurious wakeups
            while (buffer.isEmpty()) {
                // Buffer is empty, wait for producer to add item
                notEmpty.await();  // Atomically release lock and wait
            }
            
            T item = buffer.poll();
            
            // Signal producers that space is available
            notFull.signal();
            
            return item;
        } finally {
            lock.unlock();
        }
    }
    
    /**
     * Non-blocking try methods with timeout
     */
    public boolean tryProduce(T item, long timeout, TimeUnit unit) 
            throws InterruptedException {
        lock.lock();
        try {
            while (buffer.size() == capacity) {
                if (!notFull.await(timeout, unit)) {
                    return false;  // Timed out
                }
            }
            buffer.add(item);
            notEmpty.signal();
            return true;
        } finally {
            lock.unlock();
        }
    }
}

Always Use WHILE, Never IF

When waiting on a condition variable, ALWAYS use a while loop, not an if statement. Reason: Spurious wakeups can occur (thread wakes without notify), and multiple threads might wake but only one condition is satisfied. The while loop re-checks the condition after waking.

Semaphores vs Condition Variables

•Semaphores — Best when counting resources (permits, slots, items). Simpler mental model. Harder to get wrong.
•Condition Variables — Best when waiting on complex conditions. More flexible. Separate conditions for different waiters. Preferred in most modern code.
•Trade-off — Semaphores encode the count into the mechanism; condition variables require manual counting but allow arbitrary conditions.

Built-in Blocking Queues

In practice, you rarely implement Producer-Consumer from scratch. Modern languages provide blocking queue data structures that encapsulate the entire pattern, thoroughly tested and optimized.

blocking-queues.ts
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
import java.util.concurrent.*;
 
// Java provides several BlockingQueue implementations:
 
// 1. ArrayBlockingQueue - Bounded, array-backed
BlockingQueue<String> arrayQueue = new ArrayBlockingQueue<>(100);
 
// 2. LinkedBlockingQueue - Optionally bounded, linked-node
BlockingQueue<String> linkedQueue = new LinkedBlockingQueue<>(100);
BlockingQueue<String> unboundedQueue = new LinkedBlockingQueue<>();
 
// 3. PriorityBlockingQueue - Priority ordering
BlockingQueue<Task> priorityQueue = new PriorityBlockingQueue<>();
 
// 4. SynchronousQueue - No capacity, direct handoff
BlockingQueue<String> syncQueue = new SynchronousQueue<>();
 
// Usage - All blocking operations built-in:
 
// Producer
arrayQueue.put("item");           // Blocks if full
arrayQueue.offer("item");         // Returns false if full
arrayQueue.offer("item", 5, TimeUnit.SECONDS);  // Blocks with timeout
 
// Consumer
String item = arrayQueue.take();  // Blocks if empty
String item2 = arrayQueue.poll(); // Returns null if empty
String item3 = arrayQueue.poll(5, TimeUnit.SECONDS);  // Blocks with timeout
 
// Complete Producer-Consumer with BlockingQueue:
BlockingQueue<Order> orderQueue = new ArrayBlockingQueue<>(1000);
 
// Producer thread
new Thread(() -> {
    while (running) {
        Order order = receiveOrder();
        orderQueue.put(order);  // Blocks if queue full
    }
}).start();
 
// Consumer thread
new Thread(() -> {
    while (running) {
        Order order = orderQueue.take();  // Blocks if queue empty
        processOrder(order);
    }
}).start();

Use the Standard Library

In production code, ALWAYS use your language's built-in blocking queue implementations. They are battle-tested, optimized, and handle edge cases you might miss. Custom implementations are for learning or when you need specialized behavior not provided by standard libraries.

Edge Cases and Refinements

A production-ready bounded buffer must handle several edge cases beyond the basic implementation:

Critical Edge Cases

•Graceful Shutdown — When the system shuts down, waiting threads must be woken and allowed to terminate. Use poison pills, interrupt, or explicit shutdown flags.
•Timeout Handling — Threads shouldn't wait forever. Implement timeouts that allow threads to check for shutdown, report starvation, or take alternative action.
•Exception Safety — If an exception occurs between semaphore operations, the invariant may be violated. Use try-finally to ensure cleanup.
•Null/Empty Items — Decide whether null items are allowed. If not, validate inputs. If yes, ensure consumers can distinguish null-from-empty.
•Monitoring — Expose metrics: current size, producer wait time, consumer wait time, throughput. Essential for production debugging.

production-buffer.ts
Java
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
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
 
/**
 * Production-ready bounded buffer with graceful shutdown
 */
public class ProductionBuffer<T> {
    private final BlockingQueue<T> buffer;
    private final AtomicBoolean shutdown = new AtomicBoolean(false);
    
    // Metrics
    private final AtomicLong producedCount = new AtomicLong(0);
    private final AtomicLong consumedCount = new AtomicLong(0);
    private final AtomicLong producerWaitTimeNs = new AtomicLong(0);
    private final AtomicLong consumerWaitTimeNs = new AtomicLong(0);
    
    public ProductionBuffer(int capacity) {
        this.buffer = new ArrayBlockingQueue<>(capacity);
    }
    
    /**
     * Produce with timeout and shutdown awareness
     */
    public boolean produce(T item, long timeout, TimeUnit unit) 
            throws InterruptedException {
        if (shutdown.get()) {
            throw new IllegalStateException("Buffer is shutdown");
        }
        
        long startTime = System.nanoTime();
        try {
            boolean success = buffer.offer(item, timeout, unit);
            if (success) {
                producedCount.incrementAndGet();
            }
            return success;
        } finally {
            producerWaitTimeNs.addAndGet(System.nanoTime() - startTime);
        }
    }
    
    /**
     * Consume with timeout and shutdown awareness
     */
    public T consume(long timeout, TimeUnit unit) 
            throws InterruptedException {
        long startTime = System.nanoTime();
        try {
            T item = buffer.poll(timeout, unit);
            if (item != null) {
                consumedCount.incrementAndGet();
            }
            return item;  // null means timeout
        } finally {
            consumerWaitTimeNs.addAndGet(System.nanoTime() - startTime);
        }
    }
    
    /**
     * Graceful shutdown - wake all waiting threads
     */
    public void shutdown() {
        shutdown.set(true);
        // Insert poison pills to wake consumers
        // Or use interrupt on all producer/consumer threads
    }
    
    public boolean isShutdown() {
        return shutdown.get();
    }
    
    // Metrics for monitoring
    public int getCurrentSize() { return buffer.size(); }
    public long getProducedCount() { return producedCount.get(); }
    public long getConsumedCount() { return consumedCount.get(); }
    public long getAverageProducerWaitNs() {
        long produced = producedCount.get();
        return produced > 0 ? producerWaitTimeNs.get() / produced : 0;
    }
}

System Design (LLD)Concurrency Patterns

Producer-Consumer Pattern

LevelIntermediate

Duration90 mins

TopicConcurrency Patterns

2 / 4

Solution: Bounded Buffer with Synchronization

The Classic Solution

The solution to the Producer-Consumer problem has been studied and refined for over 50 years, since Edsger Dijkstra first formalized it in 1965. The bounded buffer with proper synchronization remains the gold standard because it elegantly solves every challenge we identified in the previous page. The core insight of the solution is deceptively simple: use counting to track available slots and items, and use condition variables to efficiently wait for those counts to change . This combination prevents race conditions, handles rate mismatches, avoids deadlock, and ensures fairness. In this page, we'll build this solution from first principles, understanding not just what to implement but why each component is necessary. By the end, you'll be able to implement correct Producer-Consumer systems and recognize when existing implementations are flawed.

What You Will Learn

This page covers the canonical bounded buffer solution: understanding semaphores and condition variables, implementing the classic two-semaphore solution, handling edge cases correctly, and ensuring both correctness and efficiency.

The Bounded Buffer Concept

A bounded buffer is a fixed-capacity data structure that sits between producers and consumers. Its bounded nature is critical—it prevents unbounded memory growth when producers are faster than consumers, and its fixed size allows us to reason precisely about its state. The Key Invariants A correctly implemented bounded buffer maintains these invariants at all times: 0 \leq item_count \leq capacity : The buffer never has negative items and never exceeds its capacity available_slots + item_count = capacity : The sum of empty slots and filled slots equals total capacity FIFO ordering (typically): Items are consumed in the order they were produced The State Space At any moment, a bounded buffer is in one of three states:

Bounded Buffer States
State	Condition	Producer Action	Consumer Action
Empty	item_count = 0	Can produce immediately	Must wait for items
Partial	0 < item_count < capacity	Can produce immediately	Can consume immediately
Full	item_count = capacity	Must wait for space	Can consume immediately

Why Bounded? The boundedness is not merely a practical constraint—it's essential for correctness: Backpressure : When the buffer fills, producers are forced to slow down, preventing memory exhaustion Latency Control : Items don't wait indefinitely in the buffer; the maximum wait time is bounded Resource Predictability : Memory usage is constant and predictable, essential for systems programming Fairness Enablement : Bounded waiting allows fairness guarantees that unbounded buffers cannot provide

Choosing Buffer Size

Buffer size is a crucial design decision. Too small: producers block excessively, reducing throughput. Too large: high memory usage, increased latency, delayed backpressure. The optimal size depends on production/consumption rate variance. A common heuristic: buffer enough to absorb brief rate spikes without excessive memory use.

Understanding Semaphores

The classic solution to the Producer-Consumer problem uses semaphores, a synchronization primitive invented by Dijkstra. A semaphore is essentially a non-negative integer counter with two atomic operations. Semaphore Operations wait() (also called P, down, or acquire): If counter > 0: decrement counter and return immediately If counter = 0: block until counter becomes positive, then decrement and return signal() (also called V, up, or release): Increment counter by 1 If any threads are blocked waiting, wake one up Why Semaphores Work Semaphores solve the Producer-Consumer problem because they encode counting into the synchronization primitive. Instead of checking "is buffer full?" and then acting (which creates a race), we atomically "try to decrement the empty-slot counter and block if it's already zero."

semaphore-concept.ts
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
// Conceptual Semaphore Implementation (not production-ready)
class Semaphore {
    private permits: number;
    private waitQueue: Array<() => void> = [];
    
    constructor(initialPermits: number) {
        if (initialPermits < 0) throw new Error("Permits cannot be negative");
        this.permits = initialPermits;
    }
    
    /**
     * Acquire a permit (wait/P/down)
     * Blocks if no permits are available
     */
    async acquire(): Promise<void> {
        // In a real implementation, this entire method is atomic
        if (this.permits > 0) {
            this.permits--;
            return;
        }
        
        // No permits available - block until signaled
        return new Promise<void>((resolve) => {
            this.waitQueue.push(resolve);
        });
    }
    
    /**
     * Release a permit (signal/V/up)
     * Wakes one waiting thread if any
     */
    release(): void {
        this.permits++;
        
        // Wake one waiting thread if any
        const waiter = this.waitQueue.shift();
        if (waiter) {
            this.permits--;  // Give the permit to the waiter
            waiter();
        }
    }
    
    /**
     * Check available permits (for debugging only)
     */
    availablePermits(): number {
        return this.permits;
    }
}
 
// Usage:
// Semaphore with 3 permits = 3 threads can acquire simultaneously
// 4th thread blocks until one releases

Two Types of Semaphores

•Binary Semaphore (Mutex) — Initialized to 1, allows only one thread at a time. Used for mutual exclusion. Similar to a lock.
•Counting Semaphore — Initialized to n, allows n threads concurrently. Used to limit access to a finite pool of resources. Essential for Producer-Consumer.

The Two-Semaphore Solution

The classic Producer-Consumer solution uses three semaphores: empty (counting): Tracks available slots for producers (initialized to buffer capacity) full (counting): Tracks available items for consumers (initialized to 0) mutex (binary): Protects buffer access to ensure only one thread modifies at a time The brilliance of this design is that semaphores elegantly encode both counting and waiting. Producers wait on empty (no slots) and signal full (added an item). Consumers wait on full (no items) and signal empty (freed a slot).

classic-producer-consumer.ts
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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
/**
 * Classic Producer-Consumer with Semaphores
 * 
 * This implementation is correct, deadlock-free, and handles
 * all the edge cases we discussed in the problem page.
 */
class BoundedBuffer<T> {
    private buffer: T[] = [];
    private readonly capacity: number;
    
    // Semaphores for coordination
    private empty: Semaphore;  // Counts empty slots (producer waits)
    private full: Semaphore;   // Counts filled slots (consumer waits)
    private mutex: Semaphore;  // Mutual exclusion for buffer access
    
    constructor(capacity: number) {
        this.capacity = capacity;
        
        // Initially: all slots are empty, no items
        this.empty = new Semaphore(capacity);  // capacity empty slots
        this.full = new Semaphore(0);          // 0 items
        this.mutex = new Semaphore(1);         // Binary for mutual exclusion
    }
    
    /**
     * Producer: Add item to buffer
     * 
     * Order of operations is CRITICAL:
     * 1. Wait for empty slot (blocks if buffer full)
     * 2. Acquire mutex (protect buffer modification)
     * 3. Add item to buffer
     * 4. Release mutex
     * 5. Signal that item is available
     */
    async produce(item: T): Promise<void> {
        // Step 1: Wait for an empty slot
        // This blocks if buffer is full (empty count is 0)
        await this.empty.acquire();
        
        // Step 2: Lock the buffer
        // This ensures only one producer/consumer modifies buffer
        await this.mutex.acquire();
        
        try {
            // Step 3: Add item (protected by mutex)
            this.buffer.push(item);
        } finally {
            // Step 4: Release mutex (always, even on error)
            this.mutex.release();
        }
        
        // Step 5: Signal that an item is available
        // This wakes a waiting consumer, if any
        this.full.release();
    }
    
    /**
     * Consumer: Remove item from buffer
     * 
     * Mirror of producer, with opposite semaphores:
     * 1. Wait for item (blocks if buffer empty)
     * 2. Acquire mutex (protect buffer modification)
     * 3. Remove item from buffer
     * 4. Release mutex
     * 5. Signal that slot is available
     */
    async consume(): Promise<T> {
        // Step 1: Wait for an item
        // This blocks if buffer is empty (full count is 0)
        await this.full.acquire();
        
        // Step 2: Lock the buffer
        await this.mutex.acquire();
        
        let item: T;
        try {
            // Step 3: Remove item (protected by mutex)
            item = this.buffer.shift()!;
        } finally {
            // Step 4: Release mutex (always, even on error)
            this.mutex.release();
        }
        
        // Step 5: Signal that a slot is available
        // This wakes a waiting producer, if any
        this.empty.release();
        
        return item;
    }
}
 
// Usage Example:
const buffer = new BoundedBuffer<string>(10);
 
// Producer thread
async function producer(id: number) {
    for (let i = 0; i < 100; i++) {
        const item = `Item ${i} from Producer ${id}`;
        await buffer.produce(item);
        console.log(`Producer ${id} added: ${item}`);
    }
}
 
// Consumer thread
async function consumer(id: number) {
    while (true) {
        const item = await buffer.consume();
        console.log(`Consumer ${id} processed: ${item}`);
        // Process the item...
    }
}

Order of Semaphore Operations Matters!

The order of wait operations (empty before mutex for producers, full before mutex for consumers) is CRITICAL. Reversing them causes deadlock! If a producer acquires mutex first and then waits on empty, and a consumer needs mutex to release empty, neither can proceed.

Why This Solution is Correct

Let's verify that the semaphore solution satisfies all the correctness requirements we established:

Correctness Verification
Requirement	How Solution Satisfies It
Mutual Exclusion	The mutex semaphore ensures only one thread modifies the buffer at any time. All buffer operations are wrapped in mutex acquire/release.
Buffer Bounds Respected	Producers can only proceed after acquiring an 'empty' permit—impossible if buffer is full. Consumers can only proceed after acquiring a 'full' permit—impossible if buffer is empty.
No Deadlock	The order of semaphore operations prevents circular wait. Threads wait on counting semaphores BEFORE acquiring mutex, never holding mutex while waiting for capacity/items.
No Starvation	Semaphore implementations typically use FIFO ordering for waiters. Each release wakes the longest-waiting thread, ensuring bounded wait times.
Correct Signaling	Producers release 'full' after adding an item, waking waiting consumers. Consumers release 'empty' after removing, waking waiting producers.

The Invariant Preservation Proof We can prove correctness by showing that the invariant empty + full = capacity is always maintained: Initially: empty = capacity, full = 0 empty + full = capacity ✓ After produce(): empty decremented by 1 (acquired) full incremented by 1 (released) Net change: empty + full unchanged ✓ After consume(): full decremented by 1 (acquired) empty incremented by 1 (released) Net change: empty + full unchanged ✓ Since the invariant holds initially and every operation preserves it, it always holds. This proves: Buffer never overflows: full \leq capacity (since full = capacity - empty \leq capacity) Buffer never underflows: full \geq 0 (semaphore count can't go negative)

The Power of Invariants

Reasoning about concurrent code is notoriously difficult. Invariant-based proofs provide confidence that code is correct. When writing concurrent code, always identify the invariants and verify that every operation preserves them.

The Condition Variable Alternative

While semaphores provide an elegant solution, many modern languages and frameworks use condition variables instead. Condition variables offer a more general mechanism for waiting on arbitrary conditions, not just counting. How Condition Variables Work A condition variable is always used with a lock/mutex. It provides: wait(lock) : Atomically release lock and block until signaled; re-acquire lock before returning notify() / signal() : Wake one waiting thread notifyAll() / broadcast() : Wake all waiting threads The key advantage: you can wait on any boolean condition, not just counter values.

condition-variable-solution.ts
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
import java.util.LinkedList;
import java.util.Queue;
import java.util.concurrent.locks.*;
 
/**
 * Producer-Consumer with Condition Variables
 * 
 * This is often preferred in Java because it allows
 * separate conditions for producers and consumers.
 */
public class BoundedBuffer<T> {
    private final Queue<T> buffer = new LinkedList<>();
    private final int capacity;
    
    private final Lock lock = new ReentrantLock();
    private final Condition notFull = lock.newCondition();   // For producers
    private final Condition notEmpty = lock.newCondition();  // For consumers
    
    public BoundedBuffer(int capacity) {
        this.capacity = capacity;
    }
    
    /**
     * Producer: Add item, wait if buffer is full
     */
    public void produce(T item) throws InterruptedException {
        lock.lock();
        try {
            // WHILE loop, not IF - guard against spurious wakeups
            while (buffer.size() == capacity) {
                // Buffer is full, wait for consumer to make room
                notFull.await();  // Atomically release lock and wait
            }
            
            buffer.add(item);
            
            // Signal consumers that an item is available
            notEmpty.signal();
        } finally {
            lock.unlock();
        }
    }
    
    /**
     * Consumer: Remove item, wait if buffer is empty
     */
    public T consume() throws InterruptedException {
        lock.lock();
        try {
            // WHILE loop, not IF - guard against spurious wakeups
            while (buffer.isEmpty()) {
                // Buffer is empty, wait for producer to add item
                notEmpty.await();  // Atomically release lock and wait
            }
            
            T item = buffer.poll();
            
            // Signal producers that space is available
            notFull.signal();
            
            return item;
        } finally {
            lock.unlock();
        }
    }
    
    /**
     * Non-blocking try methods with timeout
     */
    public boolean tryProduce(T item, long timeout, TimeUnit unit) 
            throws InterruptedException {
        lock.lock();
        try {
            while (buffer.size() == capacity) {
                if (!notFull.await(timeout, unit)) {
                    return false;  // Timed out
                }
            }
            buffer.add(item);
            notEmpty.signal();
            return true;
        } finally {
            lock.unlock();
        }
    }
}

Always Use WHILE, Never IF

When waiting on a condition variable, ALWAYS use a while loop, not an if statement. Reason: Spurious wakeups can occur (thread wakes without notify), and multiple threads might wake but only one condition is satisfied. The while loop re-checks the condition after waking.

Semaphores vs Condition Variables

•Semaphores — Best when counting resources (permits, slots, items). Simpler mental model. Harder to get wrong.
•Condition Variables — Best when waiting on complex conditions. More flexible. Separate conditions for different waiters. Preferred in most modern code.
•Trade-off — Semaphores encode the count into the mechanism; condition variables require manual counting but allow arbitrary conditions.

Built-in Blocking Queues

In practice, you rarely implement Producer-Consumer from scratch. Modern languages provide blocking queue data structures that encapsulate the entire pattern, thoroughly tested and optimized.

blocking-queues.ts
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
import java.util.concurrent.*;
 
// Java provides several BlockingQueue implementations:
 
// 1. ArrayBlockingQueue - Bounded, array-backed
BlockingQueue<String> arrayQueue = new ArrayBlockingQueue<>(100);
 
// 2. LinkedBlockingQueue - Optionally bounded, linked-node
BlockingQueue<String> linkedQueue = new LinkedBlockingQueue<>(100);
BlockingQueue<String> unboundedQueue = new LinkedBlockingQueue<>();
 
// 3. PriorityBlockingQueue - Priority ordering
BlockingQueue<Task> priorityQueue = new PriorityBlockingQueue<>();
 
// 4. SynchronousQueue - No capacity, direct handoff
BlockingQueue<String> syncQueue = new SynchronousQueue<>();
 
// Usage - All blocking operations built-in:
 
// Producer
arrayQueue.put("item");           // Blocks if full
arrayQueue.offer("item");         // Returns false if full
arrayQueue.offer("item", 5, TimeUnit.SECONDS);  // Blocks with timeout
 
// Consumer
String item = arrayQueue.take();  // Blocks if empty
String item2 = arrayQueue.poll(); // Returns null if empty
String item3 = arrayQueue.poll(5, TimeUnit.SECONDS);  // Blocks with timeout
 
// Complete Producer-Consumer with BlockingQueue:
BlockingQueue<Order> orderQueue = new ArrayBlockingQueue<>(1000);
 
// Producer thread
new Thread(() -> {
    while (running) {
        Order order = receiveOrder();
        orderQueue.put(order);  // Blocks if queue full
    }
}).start();
 
// Consumer thread
new Thread(() -> {
    while (running) {
        Order order = orderQueue.take();  // Blocks if queue empty
        processOrder(order);
    }
}).start();

Use the Standard Library

In production code, ALWAYS use your language's built-in blocking queue implementations. They are battle-tested, optimized, and handle edge cases you might miss. Custom implementations are for learning or when you need specialized behavior not provided by standard libraries.

Edge Cases and Refinements

A production-ready bounded buffer must handle several edge cases beyond the basic implementation:

Critical Edge Cases

•Graceful Shutdown — When the system shuts down, waiting threads must be woken and allowed to terminate. Use poison pills, interrupt, or explicit shutdown flags.
•Timeout Handling — Threads shouldn't wait forever. Implement timeouts that allow threads to check for shutdown, report starvation, or take alternative action.
•Exception Safety — If an exception occurs between semaphore operations, the invariant may be violated. Use try-finally to ensure cleanup.
•Null/Empty Items — Decide whether null items are allowed. If not, validate inputs. If yes, ensure consumers can distinguish null-from-empty.
•Monitoring — Expose metrics: current size, producer wait time, consumer wait time, throughput. Essential for production debugging.

production-buffer.ts
Java
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
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
 
/**
 * Production-ready bounded buffer with graceful shutdown
 */
public class ProductionBuffer<T> {
    private final BlockingQueue<T> buffer;
    private final AtomicBoolean shutdown = new AtomicBoolean(false);
    
    // Metrics
    private final AtomicLong producedCount = new AtomicLong(0);
    private final AtomicLong consumedCount = new AtomicLong(0);
    private final AtomicLong producerWaitTimeNs = new AtomicLong(0);
    private final AtomicLong consumerWaitTimeNs = new AtomicLong(0);
    
    public ProductionBuffer(int capacity) {
        this.buffer = new ArrayBlockingQueue<>(capacity);
    }
    
    /**
     * Produce with timeout and shutdown awareness
     */
    public boolean produce(T item, long timeout, TimeUnit unit) 
            throws InterruptedException {
        if (shutdown.get()) {
            throw new IllegalStateException("Buffer is shutdown");
        }
        
        long startTime = System.nanoTime();
        try {
            boolean success = buffer.offer(item, timeout, unit);
            if (success) {
                producedCount.incrementAndGet();
            }
            return success;
        } finally {
            producerWaitTimeNs.addAndGet(System.nanoTime() - startTime);
        }
    }
    
    /**
     * Consume with timeout and shutdown awareness
     */
    public T consume(long timeout, TimeUnit unit) 
            throws InterruptedException {
        long startTime = System.nanoTime();
        try {
            T item = buffer.poll(timeout, unit);
            if (item != null) {
                consumedCount.incrementAndGet();
            }
            return item;  // null means timeout
        } finally {
            consumerWaitTimeNs.addAndGet(System.nanoTime() - startTime);
        }
    }
    
    /**
     * Graceful shutdown - wake all waiting threads
     */
    public void shutdown() {
        shutdown.set(true);
        // Insert poison pills to wake consumers
        // Or use interrupt on all producer/consumer threads
    }
    
    public boolean isShutdown() {
        return shutdown.get();
    }
    
    // Metrics for monitoring
    public int getCurrentSize() { return buffer.size(); }
    public long getProducedCount() { return producedCount.get(); }
    public long getConsumedCount() { return consumedCount.get(); }
    public long getAverageProducerWaitNs() {
        long produced = producedCount.get();
        return produced > 0 ? producerWaitTimeNs.get() / produced : 0;
    }
}

Solution: Bounded Buffer with Synchronization

The Classic Solution

The Bounded Buffer Concept

The Key Invariants

The State Space

Why Bounded?

Understanding Semaphores

Semaphore Operations

Why Semaphores Work

The Two-Semaphore Solution

Why This Solution is Correct

The Invariant Preservation Proof

The Condition Variable Alternative

How Condition Variables Work

Built-in Blocking Queues

Edge Cases and Refinements

There’s more to understand.

Solution: Bounded Buffer with Synchronization

The Classic Solution

The Bounded Buffer Concept

The Key Invariants

The State Space

Why Bounded?

Understanding Semaphores

Semaphore Operations

Why Semaphores Work

The Two-Semaphore Solution

Why This Solution is Correct

The Invariant Preservation Proof

The Condition Variable Alternative

How Condition Variables Work

Built-in Blocking Queues

Edge Cases and Refinements

There’s more to understand.