Classic problems — Producer-Consumer, Readers-Writers (three variants), Dining Philosophers

4.2.18 · Coding › Operating Systems

0. Toolbox: semaphore actually kya hota hai

1. Producer–Consumer (Bounded Buffer)

Solution ko scratch se derive karna

Humare paas teen invariants protect karne hain, isliye teen counters/locks chahiye:

"Kya room hai?" → hame empty slots count karne chahiye. N empties se shuru karo.
"Kya data hai?" → hame full slots count karne chahiye. 0 fulls se shuru karo.
"Ek hi time pe ek hi banda buffer touch kare" → ek 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 (teen variants)

Trick ye hai: writers ko exclusive lock wrt chahiye. Readers ise share karte hain — lekin sirf pehla reader wrt lock karta hai aur sirf aakhri reader ise unlock karta hai. Count ko readcount se track karte hain, jo apne mutex se protected hai.

Variant 1 — Reader-priority (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

Jab ek writer waiting ho, koi NEW reader start nahi ho sakta; queued writers pehle jaate hain. readtry add karo (jab writer wait karta hai to naye readers ko block karta hai) aur ek 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)

Ab readers starve kar sakte hain. Humne ek starvation dusri se trade kar li.

Variant 3 — Fair / no-starvation (FIFO)

Ek entry queue semaphore add karo jisse har process guzarti hai, taaki arrival order roughly preserve ho.

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	Kaun starve kar sakta hai?
1	Readers	Writers
2	Writers	Readers
3	Fair (FIFO)	Nobody

3. Dining Philosophers

Figure — Classic problems — Producer-Consumer, Readers-Writers (three variants), Dining Philosophers

Naïve solution aur uski bimari

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 (ek Coffman condition todo)

Active Recall

Recall Producer-Consumer kyun resource semaphore

pehle mutex se pehle leta hai? Agar pehle mutex pakdo phir full/empty resource semaphore pe block ho jao, to tum lock hold karte soye rahte ho jisko dusri party ko progress ke liye chahiye → deadlock. Resource-first, mutex-second.

Recall Readers-Writers Variant 1 mein kaun si single line writer starvation karti hai?

if readcount==0: signal(wrt) — jab tak koi fresh reader readcount ke 0 hone se pehle aa jaata hai, writer ko kabhi wrt nahi milta.

Recall Dining Philosophers ko 4 tak limit karna deadlock kyun prevent karta hai?

Pigeonhole: 4 philosophers 5 forks pe zyada se zyada 8 fork-requests hold kar sakte hain, to kam se kam ek ko dono forks milte hain aur system free hota hai.

Recall Feynman: ek 12-saal ke bacche ko explain karo

Producer-Consumer: ek baker (producer) N jagah wali shelf pe cakes rakhta hai; ek baccha (consumer) unhe khaata hai. Baker tab wait karta hai jab shelf full ho; baccha tab wait karta hai jab khali ho. Do tokens — "empty spaces" aur "cakes ready" — unhe sync mein rakhte hain, aur ek "ek-aadmi-at-a-time" rule unke haath takraane se bachata hai. Readers-Writers: bahut saare log ek wall pe poster ek saath padh sakte hain, lekin sirf ek banda use repaint kar sakta hai, aur tab nahi jab koi padh raha ho. Dining Philosophers: paanch dost ek circle mein paanch forks share karte hain. Agar har koi ek hi second mein left fork pakad le, to koi right fork nahi pakad sakta aur sab forever bhookhe baithe rahte hain. Ek dost ko "pehle right pakdo" kehna stalemate todo deta hai.

Flashcards

Bounded-buffer Producer-Consumer mein teen semaphores kaunse hain aur unki init values kya hain?

empty=N (free slots), full=0 (filled slots), mutex=1 (buffer lock).

Producer mein wait(empty) wait(mutex) se pehle kyun aana chahiye?

Warna producer full buffer pe block ho sakta hai mutex hold karte hue jo consumer ko chahiye → deadlock.

Bounded buffer mein kaun sa invariant hamesha hold karta hai?

empty + full = N (in-flight items count karte hue), wait/signal ke pairs se banaa conservation law.

Readers-Writers mein readcount kya track karta hai aur use kya protect karta hai?

Active readers ki sankhya; apne mutex se protected taaki increments/decrements atomic hon.

Kaun sa reader writers ko lock out karta hai aur kaun unhe wapas aane deta hai?

PEHLA reader (readcount==1) wait(wrt) karta hai; AAKHRI reader (readcount==0) signal(wrt) karta hai.

Readers-Writers Variant 1 vs 2 vs 3 — kaun starve karta hai?

V1 reader-priority → writers starve; V2 writer-priority → readers starve; V3 fair/FIFO → nobody.

Variant 3 fairness kaise achieve karta hai?

Ek single queue turnstile semaphore jisse har process guzarti hai, arrival order (FIFO) preserve karta hai.

Deadlock ke chaar Coffman conditions batao.

Mutual exclusion, hold-and-wait, no-preemption, circular wait — chaaronon zaroori hain.

Naïve "left-then-right" Dining Philosophers deadlock kyun karta hai?

Sab paanch ek saath left forks pakad lete hain → har koi apne neighbor ke paas held right fork ka wait karta hai → circular wait.

Dining Philosophers ke teen fixes aur har ek kaun si condition break karta hai?

(A) Asymmetric pickup order → circular wait break; (B) sirf 4 bithao → pigeonhole se hold-and-wait break; (C) atomic both-or-none pickup → hold-and-wait break.

Fix B mein exactly 4 (3 nahi) philosophers kyun allowed hain?

5 forks ke liye 4 contenders pigeonhole se guarantee karte hain ki kam se kam ek ko dono forks milte hain → progress; 4 maximum hai jo full cycle phir bhi prevent karta hai.

Mutex aur counting semaphore mein kya fark hai?

Mutex = binary (0/1) mutual exclusion ke liye; counting semaphore = N se init hota hai identical available resources count karne ke liye.

Connections

Semaphores and Mutexes — yahan use kiye gaye primitive tools
Deadlock — Coffman conditions — Dining Philosophers fixes ka formal basis
Starvation and Fairness — Readers-Writers variants
Monitors and Condition Variables — in problems ka higher-level alternative encoding
Race Conditions and Critical Sections — mutex kya defend karta hai
pthread_rwlock and Condition Variables — real-world Readers-Writers