std - condition_variable: Worked examples — Hinglish deep dive

5.2.25 · D3 · Coding › C++ Programming › std - condition_variable

Neeche sab kuch parent topic par build karta hai aur std::mutex, std::unique_lock, std::lock_guard, aur Producer-Consumer Pattern ka sahara leta hai.

Scenario matrix

condition_variable program ko kuch independent "axes" wala samjho. Har real situation ek cell hai — in axes ke saath choices ka ek combination. Hume har cell ko kam se kam ek baar hit karna hai.

Axis	Cover karne wale cases
Waiters ki sankhya	0 waiters · 1 waiter · N waiters
Kaun sa notify	`notify_one` · `notify_all`
Events ka order	notify baad mein (waiter ke sone ke baad) (normal) · notify pehle (early / lost)
Predicate outcome	pred pehli check mein true · pred false → sleep · woken but abhi bhi false (spurious/stolen)
Timing	hamesha wait karo · `wait_for` timeout (deadline nikli vs. time par aayi)
Degenerate / bug	flag bina lock ke set (lost wakeup) · `while` ki jagah `if` (stolen item) · notify with koi waiter nahi (dropped)

Neeche ke naau worked examples mein se har ek [Cell: …] ke saath tagged hai taaki tum dekh sako matrix kaise fill ho raha hai.

Example 1 — Predicate already true (bilkul bhi nahi soya)

Worked example

[Cell: 1 waiter · pred true on first check] Shared: bool ready = true; (worker ke run karne se pehle hi set). Worker cv.wait(lk, []{ return ready; }) call karta hai. Thread kitni baar sota hai? Kya print hota hai?

Forecast: Abhi guess karo — kya thread zero baar sota hai, ek baar, ya hamesha ke liye block ho jaata hai?

Worker mutex lock karta hai. Yeh step kyun? wait ke liye zaroori hai ki tum pehle se std::unique_lock hold karo; lock ready ko read karne se protect karta hai.
wait(lk, pred) pehle pred() evaluate karta hai. Kyun? Predicate overload define hai as while(!pred()) cv.wait(lk); — yeh sone se pehle check karta hai. Yahan pred() true return karta hai.
!true == false, isliye while body kabhi nahi chalti. Yeh kyun matter karta hai? Thread doorbell ko touch hi nahi karta aur kabhi nahi sota. wait turant return karta hai, lock hold karte hue.
Worker started! print karta hai.

Verify: Sleep count = $0$ . Kyunki kisi bhi waiter se pehle bheja gaya notify lost ho jaata hai (cv ki koi memory nahi hoti), isliye correctness yahan puri tarah flag se aayi, notification se nahi — bilkul parent ka rule. Output: ek line started!.

Example 2 — Predicate false, ek real notify (happy path)

Worked example

[Cell: 1 waiter · pred false → sleep · notify_one · notify after sleep] bool ready = false;. Worker wait karta hai; 100 ms baad main karta hai { lock; ready = true; } cv.notify_one();. Sleeps trace karo.

Forecast: Total mein pred() kitni baar evaluate hota hai?

Worker lock karta hai, pred() evaluate karta hai → false. Kyun? Internal while ka pehla check. Evaluation #1.
!false == true → loop mein jaata hai → cv.wait(lk) call karta hai. Kyun? Single-arg wait atomically mutex unlock karta hai aur so jaata hai. Kaisa dikhta hai: worker "active" lane se nikalta hai aur waiting room mein jaata hai (figure s02, blue arrow down).
main lock karta hai, ready = true set karta hai, unlock karta hai, notify_one() karta hai. Lock ke neeche kyun set karein? Lost-wakeup window band karne ke liye (Example 7 dekho).
Doorbell bajti hai → worker jaagta hai → wait mutex re-lock karta hai → loop pred() re-evaluate karta hai → true. Evaluation #2. Dobara check kyun? Spurious ho sakta tha; loop guarantee karta hai ki hum tabhi aage badhein jab sab kuch sach mein ready ho.
!true == false → loop exit → started! print hota hai.

Verify: pred() exactly 2 baar evaluate hua, thread exactly 1 baar soya. Total notifies jo waiting thread tak pahunche: 1.

Example 3 — Spurious wakeup (bina notify ke jaagna)

Worked example

[Cell: 1 waiter · woken but pred still false] Example 2 jaisi setup, lekin OS worker ko ek baar spuriously jagaata hai pehle main ready set kare. Ab pred() ke kitne evaluations?

Forecast: while ki jagah if hota to kya galat hota?

Worker: pred() → false (eval #1) → so jaata hai.
Spurious wake: OS thread ko jaagaata hai bina kisi notify ke. wait re-locks, loop pred() re-check karta hai → abhi bhi false (eval #2). Hum kyun survive karte hain: while thread ko vapas sone bhejta hai. if ke saath, thread fall through karta aur started! print karta jabki ready abhi bhi false hai — ek bug.
Baad mein main ready = true set karta hai, notify_one() karta hai.
Worker jaagta hai, re-locks, pred() → true (eval #3), exit karta hai, print karta hai.

Verify: pred() 3 baar evaluate hua; thread 2 baar soya. Same visible output (started! ek baar), lekin loop ne extra wake ko safely absorb kar liya.

Example 4 — N waiters, ek item, `notify_one` (stolen wakeup)

Worked example

[Cell: N waiters · notify_one · one item · stolen wakeup] 3 consumers sab ek queue par wait kar rahe hain. Producer ek item push karta hai aur notify_one() call karta hai. Consumers har ek cv.wait(lk, []{ return !q.empty(); }) karte hain phir ek item pop karte hain. Un 2 consumers ka kya hota hai jinhe item nahi milta?

Forecast: Kya notify_one exactly us ek ko jagaata hai jo succeed karega?

Teeno consumers pred() evaluate karte hain → empty → so jaate hain. 3 threads waiting room mein.
Producer 1 item push karta hai, notify_one(). Ek kyun? Sirf ek item hai, isliye ek worker ko jagaana kaafi hai. Ek consumer (maano C1) jaagta hai.
C1 re-locks karta hai, pred() → !empty == true, item pop karta hai → queue phir se empty. C1 aage badhta hai.
C2, C3 sote rahte hain (unhe kabhi notify nahi hua). Yeh theek kyun hai? Unke liye koi item nahi hai, isliye unhe sone dena CPU bachata hai — yahi wajah hai ki notify_one sahi hai jab tum exactly ek unit of work add karte ho.

Verify: Items consumed = 1. Waiters abhi bhi so rahe hain = 2. Sleeps jo wasted wakeups mein badli = 0 (kyunki humne notify_all ki jagah notify_one choose kiya).

Example 5 — N waiters, `notify_all`, sirf ek item (kyun `while` apna kaam karta hai)

Worked example

[Cell: N waiters · notify_all · one item · stolen wakeup] Same 3 consumers, lekin producer (shayad shutdown par) ek item push karne ke baad notify_all() call karta hai. Ab teeno jaag jaate hain aur single item ke liye race karte hain.

Forecast: Loop ke bina, kitne consumers empty queue se pop karne ki koshish karte?

3 consumers so rahe hain. Producer 1 item push karta hai, notify_all() → teeno jaag jaate hain aur mutex ke liye contend karte hain.
C1 lock jeet jaata hai, pred() → !empty, item pop karta hai, queue empty. C1 aage badhta hai.
C1 lock release karta hai. C2 use pakad leta hai, pred() re-evaluate karta hai → empty == true, isliye !pred() → vapas so jaata hai. Dobara check kyun? C1 ne wo item chura liya jiske liye C2 ko jagaya gaya tha. while yeh pakad leta hai; if se C2 empty queue par q.front() call karta → undefined behaviour.
C3 bhi re-check karta hai → empty → so jaata hai.

Verify: Items consumed = 1. Consumers jo jaage = 3, jinmein se 2 loop ke zariye re-slept. Bug avoid hua exactly while(!pred()) ki wajah se.

Example 6 — Timed wait jo time out hoti hai vs. time par aati hai

Worked example

[Cell: wait_for · deadline passes · deadline met] cv.wait_for(lk, 200ms, []{ return ready; }) ek bool return karta hai: predicate ka final value. Do runs consider karo.

Run A (times out): 200 ms ke andar koi ready set nahi karta. Run B (in time): main 120 ms par ready set karta hai aur notify karta hai.

Forecast: Har run kaunsa boolean return karta hai?

Run A: worker so jaata hai; 200 ms par timer fire hota hai. wait_for re-locks, pred() evaluate karta hai → false → false return karta hai. "Kya time out hua" ki jagah predicate return kyun? Taaki tumhara code condition ki truth par branch kare, deadline ke paas spurious wakes ke against robust.
Run B: 120 ms par notify aata hai. Worker jaagta hai, pred() → true → 200 ms deadline se pehle true return karta hai.

Verify: Run A false return karta hai (aur $200 \geq 200$ ms elapsed). Run B true return karta hai (aur elapsed $\approx 120 < 200$ ms). Numerically: false aur true; elapsed times $200$ aur $120$ .

Example 7 — Lost-wakeup race (degenerate: flag bina lock ke set)

Worked example

[Cell: flag set without lock · notify_one · notify before sleep] Buggy code: main ready = true; karta hai bina lock kiye, phir cv.notify_one(); — aur yeh us choti si gap mein hota hai jiske baad worker ne pred() check kiya lekin wait(lk) call karne se pehle.

Forecast: Kya worker kabhi jaagta hai?

Worker lock karta hai, pred() → false. Abhi tak soya nahi.
CPU main par switch karta hai: ready = true (no lock), notify_one(). Lekin koi thread abhi wait ke andar nahi hai → notify ek empty waiting room se takraata hai → drop ho jaata hai (cv ki koi memory nahi).
CPU worker par vapas aata hai: woh cv.wait(lk) call karta hai aur so jaata hai — hamesha ke liye, kyunki ek hi notify pehle hi gaayab ho gayi thi.

Verify: Notifications jo ek waiting thread tak pahunchi = 0; worker ki sleep permanent hai (ek hang). Fix: ready = true us hi mutex ke neeche set karo jo worker use karta hai. Tab step 2, worker ke check aur uski sleep ke beech interleave nahi ho sakta, kyunki dono critical section ke andar hain — notify ek properly parked waiter par land karta hai. Yeh ek Race Condition hai; un-woken thread effectively ek one-sided Deadlock mein hai.

Example 8 — Real-world word problem: pizza kitchen (bounded buffer)

Worked example

[Cell: real-world · N producers/consumers · notify_all] Ek kitchen mein ek counter hai jo zyada se zyada 3 pizzas hold kar sakta hai. 2 cooks (producers) pizzas add karte hain; 4 waiters (consumers) unhe lete hain. Do conditions chahiye: "counter not full" (cooks wait karte hain) aur "counter not empty" (waiters wait karte hain). Ek mutex par do predicates use karo. Agar ek cook pizza add karta hai jab counter 0 par tha, to kitne waiters jaag sakte hain?

Forecast: "Not empty" event ke liye notify_one use karte ho ya notify_all?

Cook lock karta hai, wait(lk, []{ return count < 3; }). Kyun? Counter overflow mat karo. Full hone par so jaata hai.
Cook pizza add karta hai → count = 1, unlock karta hai, cv_notEmpty.notify_all() (ya notify_one agar ek item = ek waiter). Kyun notify_all safe hai: har jaagne wala waiter count > 0 ko while mein re-check karta hai; extra re-sleep karte hain (Example 5 logic). Exactly ek pizza add hone ke saath, notify_one efficient choice hai.
Ek waiter jaagta hai, pred() → count > 0, pizza leta hai → count = 0, phir cv_notFull.notify_one() karta hai kisi possibly-waiting cook ko batane ke liye ki jagah hai.

Verify: Counter cap $3$ ke saath: ek empty counter mein ek pizza add karne ke baad, exactly 1 pizza available hai; notify_one use karne par 1 waiter jaagta hai jo succeed karta hai; notify_all use karne par sab 4 jaag jaate hain, jinmein se 1 succeed karta hai aur 3 re-sleep karte hain. Dono service ke baad count = 0 chhodte hain.

Example 9 — Exam twist: K items ke liye K notifies mein kitne `pred()` evaluations?

Worked example

[Cell: exam-style counting] Ek consumer ek queue par wait karta hai. Ek producer 4 items push karta hai, ek-ek karke, har ek ke baad notify_one(). Consumer ek inner while(!q.empty()) per wake mein sab currently available items drain karta hai. Assume koi spurious wakes nahi aur har notify tab aata hai jab consumer so raha hota hai, agla push karne se pehle. Outer pred() kitni baar evaluate hota hai, aur consumer kitni baar sota hai?

Forecast: Kya 4 sleeps hote hain, ya kam?

Consumer: outer pred() → empty → sleep (eval #1, sleep #1).
Item push, notify. Consumer jaagta hai, pred() → true (eval #2), 1 item drain karta hai, loop back karta hai, pred() → empty → sleep (eval #3, sleep #2).
Items 2, 3, 4 ke liye repeat. Har item 2 evals add karta hai (ek true jo drain karta hai, ek false jo re-sleeps) — sivaaye last ke, jo done re-check karta hai.
Count: initial eval #1, phir har item ke liye ek "true" eval aur ek "false→sleep" eval.

Verify: $K = 4$ items ek-at-a-time-while-asleep deliver hone ke liye: outer pred() evaluations $= 2 K + 1 = 9$ ; consumer sleeps $= K = 4$ (initial sleep, phir pehle 3 drains ke baad re-sleep — 4th drain ya to phir se sota hai ya done par exit karta hai; initial + har delivered-then-empty gap ke baad ek count karne par 4 milte hain).

Flashcards

notify_all ke saath, ek item, aur 3 waiters ke saath, kitne consumers aage badhte hain aur kitne re-sleep karte hain?

1 aage badhta hai; 2 re-sleep karte hain kyunki while (ab false) predicate ko re-check karta hai.

cv.wait_for kya return karta hai?

Predicate ka final value — true agar condition hold kare, false agar condition abhi bhi false hone par time out ho gayi.

Lost-wakeup bug mein, notify drop kyun hota hai?

Yeh tab bheja jaata hai jab koi bhi thread wait ke andar nahi hota; condition_variable ki koi memory nahi hoti, isliye koi waiter nahi hone par notify lost ho jaata hai.

Agar wait(lk,pred) call hone par predicate already true hai, to thread kitni baar sota hai?

Zero — predicate sone se pehle check hota hai, isliye wait turant return karta hai.

Exactly ek item push karne ke baad notify_all ki jagah notify_one kyun use karein?

Sirf ek unit of work hai, isliye ek waiter ko jaagaana kaafi hai; sab ko jaagaana bas extras ko jaag ke re-sleep karvaata hai, CPU waste karta hai.

Recall Pure matrix ka ek-line summary

Correctness hamesha flag + mutex + while-loop se aati hai; notify sirf ek nudge hai, aur har failure case (spurious, stolen, lost, timeout) predicate ko lock ke neeche re-check karne se handle hota hai.