Semaphores & the Producer-Consumer Problem

Building an Operating System Kernel: Concurrency, I/O & Synchronization

Chapter 3 · Semaphores & the Producer-Consumer Problem

A mutex answers "can exactly one process touch this?" A semaphore answers a more general question: "can up to N processes touch this?" This chapter builds a real counting semaphore on top of Chapter 2's own mutex, applies it to the classic producer-consumer problem — and finds a genuine bug in the very first proper fix, one line that quietly undoes everything the semaphores were built to guarantee.

A Real Counting Semaphore, Built From Chapter 2's Own Mutex

class Semaphore:
    def __init__(self, mem, counter_paddr, lock_paddr, initial_value):
        self.mem = mem; self.counter_paddr = counter_paddr
        self.mutex = Mutex(mem, lock_paddr)   # the counter itself needs real protection
        self.mem.data[counter_paddr] = initial_value

    def try_acquire(self):
        if not self.mutex.try_acquire():
            return False
        if self.mem.data[self.counter_paddr] > 0:
            self.mem.data[self.counter_paddr] -= 1
            self.mutex.release()
            return True
        self.mutex.release()
        return False
    

Finding 1: Real, Verified Counting-Semaphore Correctness

Verified directly — exactly N permits, no more, no fewer

A semaphore with 3 permits: requesting 4 acquires in a row gives [True, True, True, False] — exactly 3 succeed, the 4th genuinely fails. A mutex generalizes cleanly: Semaphore(initial_value=1) behaves exactly like Chapter 2's own Mutex (verified in Exercise 1). After one release(), exactly one more acquire succeeds.

Finding 2: A Naive Bounded Buffer Overwrites Real, Unconsumed Data

A plausible first attempt at a bounded buffer: track a plain shared "count" byte, and check it before writing.

Verified directly — a real, produced item is silently overwritten before it's ever consumed

With exactly one real free slot left, two producers each independently read the same "there's room" count. Both write — to the same slot index. Producer A's real value, 111, is silently overwritten by producer B's 222. A plain, unsynchronized count tells each producer "there's room" independently, with no coordination about which slot is actually free.

Finding 3: A Real Bug — A Forgotten release() Shrinks the Buffer Forever

The real fix: two semaphores — empty (free slots, starts at capacity) and full (filled slots, starts at 0) — plus a mutex protecting the buffer's own indices. A first, careful-looking implementation:

def try_consume(self):
    if not self.full.try_acquire():
        return None
    if not self.buffer_mutex.try_acquire():
        self.full.release()
        return None
    value = self.mem.data[self.buf_paddrs[self.read_idx % self.capacity]]
    self.read_idx += 1
    self.buffer_mutex.release()
    return value   # empty.release() is missing here
    

Verified directly — the buffer permanently shrinks with every real consume

2 producers, 1 consumer, a real capacity-3 buffer, under real QUANTUM=1 preemption: after exactly 3 real consumes, empty.value() is stuck at 0 and full.value() is also 0 — the two should always sum to 3, but sum to 0. Every consume correctly reads its item and releases full, but never tells empty a slot just became free. The buffer effectively loses one real slot of capacity on every single consume, until both producers spin forever on a permit that can never be granted again.

Finding 4: The Real Fix — Release Both Directions

Verified directly — one missing line restored, full correctness under the same scheduler

Adding self.empty.release() right after the buffer mutex is released is the entire fix. Re-run under the identical QUANTUM=1 preemptive scheduler that broke both Finding 2 and Finding 3: every single item from both producers is consumed exactly once — none lost, none duplicated.

Where This Connects

This chapter's finding	What it connects to
A semaphore built on top of a mutex	Chapter 2's own `Mutex` — reused directly to protect the semaphore's own internal counter, the same shared-state problem one level up
One forgotten release() call silently breaking everything	Course 1 Chapter 8's own timer-reset bug — a single missing line, invisible until measured directly, quietly undoing an entire mechanism's own guarantee
Two semaphores that must both be honored correctly	Course 1 Chapter 6's own quota enforced on one code path but not another — a rule only holds if every relevant path is updated together
A buffer permanently shrinking rather than crashing	The reason this bug is dangerous — no exception, no crash, just a silent, permanent loss of real capacity that only shows up as unexplained starvation later

Hands-On Exercises

Exercise 1

Create a Semaphore with initial_value=1 and verify it behaves exactly like Chapter 2's own Mutex — exactly one acquirer at a time, correctly restored by release(). Explain why this isn't a coincidence.

📄 View solution

Exercise 2

Run a consumer with nothing ever produced for it, alongside a completely unrelated bystander process doing its own real work. Confirm the consumer's own repeated failed attempts never block the bystander's own progress, and explain why.

📄 View solution

Exercise 3

Run the real, fixed BoundedBuffer with a capacity of exactly 1 — the tightest possible bounded buffer. Confirm every item is still delivered correctly, and explain why the fix doesn't depend on the buffer having "room to spare."

📄 View solution

Chapter 3 Quick Reference

Semaphore: a real counting permit system built on top of a mutex protecting its own internal counter
A mutex is a semaphore: Semaphore(initial_value=1) is exactly Chapter 2's own Mutex, not a coincidence
Verified Finding 2 (bug): a plain shared "count" check overwrites real, unconsumed data under real interleaving
Verified Finding 3 (bug): a forgotten empty.release() call permanently shrinks the buffer's own real capacity, one consume at a time
Verified Finding 4 (fix): both semaphores — empty and full — must be released correctly on every path, or the buffer silently starves
Golden rule: two-permit coordination needs BOTH directions signaled correctly — releasing only one half of the pair is a silent, not a loud, failure
Next chapter: Deadlock: Causes, Detection & Prevention — what happens when multiple locks are acquired in the wrong order