Classic problems — Producer-Consumer, Readers-Writers (three variants), Dining Philosophers
0. Toolbox: what a semaphore actually is
1. Producer–Consumer (Bounded Buffer)
Deriving the solution from scratch
We have THREE invariants to protect, so we need THREE counters/locks:
- "Is there room?" → we must count empty slots. Start with
Nempties. - "Is there data?" → we must count full slots. Start with
0fulls. - "Only one at a time touches the buffer" → a mutex.
empty = N # counting semaphore: free slots
full = 0 # counting semaphore: filled slots
mutex = 1 # binary: protect buffer
Producer: Consumer:
loop: loop:
item = produce() wait(full) # is data there?
wait(empty) # room? wait(mutex) # lock buffer
wait(mutex) # lock item = remove()
insert(item) signal(mutex) # unlock
signal(mutex)# unlock signal(empty) # one slot freed
signal(full) # +1 data consume(item)2. Readers–Writers (three variants)
The trick: writers need an exclusive lock wrt. Readers share it — but only the first reader locks wrt and only the last reader unlocks it. We track the count with readcount, protected by its own mutex.
Variant 1 — Reader-priority (the textbook default)
wrt = 1; mutex = 1; readcount = 0
Writer: Reader:
wait(wrt) wait(mutex)
...write... readcount += 1
signal(wrt) if readcount==1: wait(wrt) # first reader locks writers out
signal(mutex)
...read...
wait(mutex)
readcount -= 1
if readcount==0: signal(wrt) # last reader lets writers in
signal(mutex)Variant 2 — Writer-priority
Once a writer is waiting, no NEW reader may start; queued writers go first.
Add readtry (blocks new readers when a writer waits) and a writecount mirror.
wrt=1; rmutex=1; wmutex=1; readtry=1; readcount=0; writecount=0
Reader: Writer:
wait(readtry) wait(wmutex)
wait(rmutex) writecount+=1
readcount+=1 if writecount==1: wait(readtry) # block new readers
if readcount==1: wait(wrt) signal(wmutex)
signal(rmutex) wait(wrt)
signal(readtry) ...write...
...read... signal(wrt)
wait(rmutex) wait(wmutex)
readcount-=1 writecount-=1
if readcount==0: signal(wrt) if writecount==0: signal(readtry) # release readers
signal(rmutex) signal(wmutex)Now readers can starve instead. We traded one starvation for the other.
Variant 3 — Fair / no-starvation (FIFO)
Add an entry queue semaphore that every process passes through, so order of arrival is roughly preserved.
wrt=1; mutex=1; queue=1; readcount=0
Reader: Writer:
wait(queue) wait(queue)
wait(mutex) wait(wrt)
readcount+=1 signal(queue) # release next waiter early
if readcount==1: wait(wrt) ...write...
signal(mutex) signal(wrt)
signal(queue)
...read...
(exit as Variant 1)| Variant | Priority | Who can starve? |
|---|---|---|
| 1 | Readers | Writers |
| 2 | Writers | Readers |
| 3 | Fair (FIFO) | Nobody |
3. Dining Philosophers
The naïve solution and its disease
fork[i] = 1 for all i # each fork is a binary semaphore
Philosopher i:
wait(fork[i]) # left
wait(fork[(i+1)%5]) # right
eat
signal(fork[i]); signal(fork[(i+1)%5])Fixes (break ONE Coffman condition)
Active Recall
Recall Why must Producer-Consumer take the resource semaphore
before the mutex? If you grab the mutex first then block on a full/empty resource semaphore, you sleep holding the lock the other party needs to make progress → deadlock. Resource-first, mutex-second.
Recall In Readers-Writers Variant 1, what single line causes writer starvation?
if readcount==0: signal(wrt) — as long as a fresh reader arrives before readcount reaches 0, the writer never gets wrt.
Recall Why does limiting Dining Philosophers to 4 prevent deadlock?
Pigeonhole: 4 philosophers can hold at most 8 fork-requests over 5 forks, so at least one gets both forks and frees the system.
Recall Feynman: explain to a 12-year-old
Producer-Consumer: a baker (producer) puts cakes on a shelf with N spaces; a kid (consumer) eats them. The baker waits if the shelf is full; the kid waits if it's empty. Two tokens — "empty spaces" and "cakes ready" — keep them in sync, and a "one-person-at-a-time" rule stops them bumping hands. Readers-Writers: lots of people can read a poster on a wall at once, but only one person can repaint it, and not while anyone's reading. Dining Philosophers: five friends share five forks in a circle. If everyone grabs the left fork at the same second, nobody can grab a right fork and they all sit hungry forever. Telling one friend "grab right first" breaks the stalemate.
Flashcards
What are the three semaphores in bounded-buffer Producer-Consumer and their init values?
empty=N (free slots), full=0 (filled slots), mutex=1 (buffer lock).Why must wait(empty) come before wait(mutex) in the producer?
What invariant always holds in the bounded buffer?
In Readers-Writers, what does readcount track and what protects it?
mutex so increments/decrements are atomic.Which reader locks out writers and which lets them back in?
wait(wrt); the LAST reader (readcount==0) does signal(wrt).Variant 1 vs 2 vs 3 of Readers-Writers — who starves?
How does Variant 3 achieve fairness?
queue turnstile semaphore every process passes through, preserving arrival order (FIFO).State the four Coffman conditions for deadlock.
Why does the naïve "left-then-right" Dining Philosophers deadlock?
Three fixes for Dining Philosophers and which condition each breaks?
Why exactly 4 (not 3) philosophers allowed in Fix B?
Difference between mutex and counting semaphore?
Connections
- Semaphores and Mutexes — the primitive tools used here
- Deadlock — Coffman conditions — formal basis for Dining Philosophers fixes
- Starvation and Fairness — Readers-Writers variants
- Monitors and Condition Variables — higher-level alternative encoding of these problems
- Race Conditions and Critical Sections — what the mutex defends
- pthread_rwlock and Condition Variables — real-world Readers-Writers
Concept Map
Hinglish (regional understanding)
Intuition Hinglish mein samjho
Ye teen problems concurrency ke "starter pack" hain — har ek tumhe ek alag bug sikhati hai. Producer-Consumer mein ek banda items banata hai aur shelf (buffer of size N) pe rakhta hai, dusra utha ke use karta hai. Yahan teen semaphore use karte hain: empty=N (kitni jagah khaali hai), full=0 (kitne items ready hain), aur mutex=1 (ek time pe sirf ek hi buffer ko chhuye). Sabse bada rule: pehle resource semaphore (wait(empty) ya wait(full)) lo, phir mutex — warna agar buffer full hai aur tum mutex hold karke so gaye to dusra banda kabhi lock nahi le payega aur deadlock ho jayega.
Readers-Writers mein ek shared cheez ko bahut saare log ek saath padh sakte hain (read mein koi conflict nahi), lekin likhne wala (writer) akela hi chahiye. Trick simple hai: pehla reader aata hai to writer ko lock kar deta hai (wait(wrt)), aur aakhri reader nikalte waqt writer ko wapas chhod deta hai. Iska teen variant hai — V1 readers ko priority deta hai (writer bhookha mar sakta hai = starvation), V2 writer ko priority (reader starve), aur V3 ek queue turnstile laga ke FIFO fairness deta hai taaki koi bhi forever wait na kare.
Dining Philosophers mein 5 dost circle mein baithe hain, beech mein 5 forks. Khaane ke liye dono forks chahiye. Agar sab ek saath apna LEFT fork utha lein, to sabke paas ek-ek fork hai aur right fork padosi ke paas — sab atke, koi nahi kha sakta. Ye circular wait hai, classic deadlock. Fix simple: ek banda ko bolo "tu pehle RIGHT utha", ya sirf 4 logon ko table pe baithne do (pigeonhole se ek banda ko dono fork mil hi jayenge), ya dono forks ek saath atomically utha. Yaad rakho: Producer = race, Readers = starvation, Dining = Deadlock.