Worked examples — Synchronization primitives (locks, barriers)

6.1.8 · D3 · Hardware › Parallelism & Multicore › Synchronization primitives (locks, barriers)

Ye page parent topic ka practice arena hai. Parent ne machinery banayi thi: locks, Test-and-Set / Compare-and-Swap, spin-lock cost formulas, aur reusable barriers. Yahaan hum un machines ko har possible case se guzarte hain, taaki koi bhi scenario tumhe surprise na kare.

Shuru karne se pehle, ek ek-line refresher un symbols ka jo hum reuse karenge, taaki kuch bhi bina samjhe use na ho:

Recall Symbols jo hum parent se inherit karte hain (click to expand)

• $N$ ::: total number of threads jo ek lock ke liye contend kar rahe hain ya barrier par aa rahe hain.
• $T_c$ ::: critical-section hold time — ek thread kitni der lock rakhta hai (seconds mein).
• $W_{avg}=T_c/2$ ::: ek single holder ke peeche ek arrival ka expected wait.
• $W_{queue\text{-}avg}=\frac{(N-1)T_c}{2}$ ::: $N$-deep FIFO queue mein positions par average mean wait.
• $t_{spin}$ ::: ek spin-loop iteration ka time (ek failed Test-and-Set attempt).
• $E_{instruction}$ ::: ek instruction execute karne ki energy cost.
• TAS ::: Test-and-Set — atomically ek flag read karta hai aur use 1 set karta hai, purani value return karta hai.
• CAS ::: Compare-and-Swap — new tabhi likhta hai jab location abhi bhi expected ke equal ho.

---

Scenario matrix

Is topic ke har problem mein in cells mein se ek mein fit hoti hai. Har cell ek alag tarah ka trap hai. Neeche ke examples mein har ek ke saath uska cell label hai — milke ye poora grid cover karte hain.

#	Cell class	Kya vary karta hai	Example
A	Race baseline — koi lock nahi	interleaving order	Ex 1
B	Lock cost, low contention	chhota $N$	Ex 2
C	Lock cost, high contention	bada $N$, queue wait	Ex 3
D	Degenerate: $N=1$	zero contention	Ex 4
E	Spin energy waste	$T_c/t_{spin}$ ratio	Ex 5
F	CAS success vs failure	expected match karta hai ya nahi	Ex 6
G	Barrier reuse race	generation counter	Ex 7
H	Barrier limiting case: ek slow thread	straggler dominate karta hai	Ex 8
I	Real-world word problem	formula mein translate karo	Ex 9
J	Exam twist: deadlock ordering	do locks, do threads	Ex 10

---

Cell A — bina lock ke race

Forecast: padhne se pehle andaza lagao — kya final value hamesha 2 hogi? Hamesha 1? Ya depend karti hai?

1. Har thread ko 3 atomic steps mein tod lo. Thread 1 = $L_1,A_1,S_1$ (Load, Add, Store); Thread 2 = $L_2,A_2,S_2$. Ye step kyun? Parent ne dikhaya tha ki hardware counter = counter+1 ko ek action ke roop mein nahi chalata — ye teen steps hain. Correctness step level par rehti hai.
2. Sahi result (2) ke liye zaroori hai ki ek thread ka store doosre thread ke load se pehle ho. Yani $S_1$ se pehle $L_2$, ya $S_2$ se pehle $L_1$. Ye step kyun? Agar ek thread doosre ke store ke baad read kare, to use updated value milti hai aur vo uske upar add karta hai.
3. Lost update (final = 1) tab hota hai jab dono loads PEHLE store se aage ho jaate hain, jaise $L_1{L}_2{A}_1{A}_2{S}_1{S}_2$. Ye step kyun? Dono 0 read karte hain, dono 1 compute karte hain, dono 1 likhte hain → ek increment gayab ho gaya.
4. Seedha count karo. 20 order-preserving interleavings enumerate karo aur har ek simulate karo. Safe condition (ek store doosre thread ke load se pehle aata hai) 16 interleavings mein hold karti hai; baaki 4 lossy hain (final = 1). Ye step kyun? Symmetry se argue karne ke bajaye (jisme galti hona aasaan hai), hum har ordering simulate karte hain — wohi mechanical check jo =VERIFY= block mein reproduce hoti hai.

Verify: Do 3-step sequences ke order-preserving interleavings ki sankhya $\left(\genfrac{}{}{0ex}{}{6}{3}\right)=20$ hai. Direct simulation se 16 safe (final value 2) aur 4 lossy (final value 1) milte hain. To answer hamesha 2 nahi hai — 20 mein se 4 orderings mein galat ho jaata hai (20% waqt).

---

Cells B, C, D — spin-lock waiting time

Forecast: 40? 20? 80?

1. Pehchano ki ye "ek holder ke peeche ek arrival" hai. $W_{avg}=T_c/2$ use karo. Ye step kyun? Parent ka formula: uniformly-random arrival average par hold interval ke aadhe remaining waqt ka wait karta hai.
2. Substitute karo: $W_{avg}=40/2=20\mu s$.

Verify: Units: $\mu s/2=\mu s$. ✓ 40 ka aadha 20 hai. ✓

Forecast: kya mean $T_c/2$ ke equal hoga, ya $N$ ke saath scale karega?

1. Last thread uske aage ke sabhi 4 threads ka wait karta hai. $W_{last}\approx (N-1)T_c=4\times 40=160\mu s$. Ye step kyun? FIFO mein, position $k$ apne aage ke $k-1$ full critical sections ka wait karta hai.
2. Positions $0,1,2,3,4$ par average karo: $W_{queue\text{-}avg}=\frac{(N-1)T_c}{2}=\frac{4\times 40}{2}=80\mu s$. Ye step kyun? Arithmetic run $0,T_c,2T_c,\dots$ ka mean $(N-1)T_c/2$ hai. Ye Ex 2 ke $T_c/2$ se alag quantity hai — parent ki warning dekho.

Verify: $W_{queue\text{-}avg}=80$, aur $W_{last}=160=2\times 80$ (mean ek uniform run ke maximum ka aadha hota hai). ✓ Ex 2 ke $20\mu s$ se contrast karo: $N$ ko 2 se 5 karne par mean wait $4\times$ badh gayi. Isi liye blocking locks matter karte hain (dekho Deadlock and livelock aur Thread scheduling).

Neeche ki figure yahi example draw ki hui hai. Har blue bar us thread ka wait hai jo us queue position par baitha hai: holder (position 0) kuch nahi wait karta, aur har ek step peeche jane par ek aur full critical section ($+40\mu s$) add hoti hai, to bars $0,40,80,120,160$ tak chadh jaati hain. Red bar sabse bure position wala (last) thread hai jo poore $160\mu s$ wait karta hai. Yellow dashed line mean $80\mu s$ hai — aur notice karo ki ye sabse unchi bar ke exactly beech mein aati hai, jo geometric reason hai ki queue average $(N-1)T_c/2$ ke equal kyun hota hai: evenly-spaced run ka mean hamesha uske maximum ka aadha hota hai. Bars ko left-to-right padhne se tumhe wo linear growth dikhti hai jo high contention ko punish karti hai.

Forecast: zero wait? ya phir bhi kuch cost?

1. Contention wait: $N=1$ ke saath koi doosra holder nahi hai, isliye $W_{queue\text{-}avg}=\frac{(N-1)T_c}{2}=\frac{0\cdot T_c}{2}=0$. Ye step kyun? $N=1$ queue formula mein plug karne par 0 milta hai — degenerate boundary formula ko sanity-check karta hai.
2. Lekin lock free nahi hai: ek single TAS instruction abhi bhi execute hoti hai (ek atomic read-modify-write) aur release par ek store. Ye step kyun? Uncontended bhi, ek atomic op ek coherence transaction force karta hai (line ko exclusive state mein lao). Ye "uncontended lock overhead" hai.

Verify: $(1-1)\cdot 40/2=0$. ✓ Zero waiting, non-zero instruction cost — dono statements consistent hain.

---

Cell E — spinning se barbad energy

Forecast: milli-joules? nano-joules? $N$ ke saath kaise scale karta hai?

1. Har waiting thread ke spin iterations count karo: $\frac{T_c}{t_{spin}}=\frac{40}{0.1}=400$ iterations ek hold ke dauraan. Ye step kyun? Poore hold ke dauraan spin karne wala thread har $t_{spin}$ mein ek instruction burn karta hai.
2. $(N-1)$ waiters se multiply karo: total iterations $=400\times (5-1)=1600$. Ye step kyun? 4 waiters mein se har ek spin karta hai; holder nahi karta.
3. Energy per instruction se multiply karo: $E_{waste}=\frac{T_c}{t_{spin}}(N-1)E_{instruction}=1600\times 2\text{nJ}=3200\text{nJ}=3.2\mu J$.

Verify: $\frac{40}{0.1}\cdot 4\cdot 2=3200$. ✓ Units: $(\mu s/\mu s)\cdot 1\cdot \text{nJ}=\text{nJ}$. ✓ $N-1$ ke saath linearly grow karta hai — spinning ke upar blocking locks ka parent ka motivation.

---

Cell F — CAS success vs failure

Forecast: kya B ka swap succeed karega?

1. A ki call: kya actual (7) expected (7) ke equal hai? Haan → new=9 likho. CAS purana actual = 7 return karta hai. Memory ab 9 hai. Ye step kyun? CAS sirf match par likhta hai aur hamesha jo usne dekha wo return karta hai. A ne 7 dekha, isliye swap kiya.
2. B ki call: kya actual (9) expected (7) ke equal hai? Nahi → koi write nahi. CAS actual = 9 return karta hai. Memory 9 hi rehti hai. Ye step kyun? B ka expected stale hai — duniya uske neeche badal gayi. Ye CAS failure case hai; ek real lock-free loop re-read karta aur expected=9 ke saath retry karta.

Verify: A 7 return karta hai, memory→9 (match branch). B 9 return karta hai, memory 9 rehti hai (no-match branch). CAS matrix ke dono cells (match / no-match) cover ho gaye. ✓ Retry loops is par kaise build karte hain uske liye Atomic operations dekho.

---

Cells G, H — barriers

Barrier examples se pehle, do symbols jo hum trace ke andar use karenge:

Recall Barrier symbols for Ex 7 (click to expand)

• threshold ::: barrier trip count — total number of threads $N$ jo gate khulne se pehle arrive karne chahiye. Yahaan $\text{threshold}=3$.
• my_gen ::: barrier ke current generation ki ek per-thread local copy, jo thread ke arrive karne ke waqt record ki jaati hai, taaki wo apna episode agle se alag pehchan sake.
• generation ::: barrier ka shared phase counter; last-in thread ise increment karta hai current episode ke liye gate kholne ke liye.
• count ::: current generation mein kitne threads arrive kar chuke hain (gate khulne par 0 par reset hoti hai).

Forecast: do full phases ke baad generation kya hoga?

1. Phase 0 start: generation=0, count=0. Threads arrive karte hain: har ek my_gen=0 record karta hai, phir count $1\to 2\to 3$ hota hai. Ye step kyun? Har barrier_wait lock ke andar count increment karta hai aur my_gen = us generation ko record karta hai jisme wo hai.
2. 3rd thread threshold trip karta hai: count == threshold (3) → generation=1 set karo, count=0 reset karo, broadcast karo. Ye step kyun? Last-in thread gate kholti hai aur generation advance karti hai. Waiters jagte hain aur check karte hain: unka my_gen(0) != generation(1) → wo aage badhte hain.
3. Phase 1: ek fast thread loop back karta hai, my_gen=1 record karta hai, count $1\to 2\to 3$ hota hai; last-in generation=2 set karta hai, count=0 reset karta hai. Ye step kyun? Kyunki phase-1 threads ne my_gen=1 record kiya tha, ek stale phase-0 wakeup galti se unhe satisfy nahi kar sakta — generation check episodes alag karta hai. Yahi wo exact race hai jisme parent ka "sirf count = 0 reset karo" version fail kiya tha.

Verify: Do phases ke baad, generation = 2 aur count = 0. Har phase ne generation exactly 1 se advance kiya aur count ko 0 par chhoda reuse ke liye taiyar. ✓

Forecast: kya release time average arrival hai, ya max?

1. Barrier sirf tab release hoti hai jab LAST thread arrive kare. Release time $=\max (\text{arrival times})=100\mu s$. Ye step kyun? Definition: koi bhi thread tab tak aage nahi badhta jab tak sab $N$ arrive na kar lein — sabse slow dictate karta hai.
2. Idle time = early threads par (release − unki arrival) ka sum. Teen threads mein se har ek $100-0=100\mu s$ wait karta hai: total $=3\times 100=300\mu s$. Ye step kyun? Har early thread apni arrival se release tak blocked baitha rehta hai.

Verify: Release $=100\mu s$ (max, mean 25 nahi). Idle $=300\mu s$. ✓ Lesson: barriers sirf utni fast hain jitna slowest thread — load-balanced Parallel algorithms ka motivation.

Neeche ki figure ye example ek timeline par dikhati hai, har thread ka ek row hai. Teen green dots $t=0$ par punctual arrivals hain; red dot $t=100\mu s$ par land karne wala straggler hai. Yellow bars idle stretches hain — har punctual thread arrive karne ke waqt se block ho jaata hai jab tak blue dashed release line $100\mu s$ par na aa jaye, isliye har yellow bar $100\mu s$ lamba hai. Pedagogical punch: teen barabar yellow bars ($100+100+100$) add karo aur tum aankhon se $300\mu s$ total idle padhte ho, aur tum dekhte ho ki release line set karne wala single red straggler hai — average arrival nahi. Ye hi "ek barrier apne slowest thread ki speed se chalti hai" ka poora point hai.

---

Cell I — real-world word problem

Forecast: microseconds? milliseconds? kaunsa formula — $T_c/2$ ya queue wala?

1. Cell identify karo: 50 contenders queueing = high-contention FIFO (cell C machinery). Ye step kyun? Ye Ex 3 word problem ke roop mein dress kiya hua hai — $W_{queue\text{-}avg}$ choose karo, single-arrival $T_c/2$ nahi.
2. Average wait: $W_{queue\text{-}avg}=\frac{(N-1)T_c}{2}=\frac{49\times 2}{2}=49\mu s$. Ye step kyun? 50 requests ke FIFO line mein, ek typical request middle position par baithti hai; sab positions par mean $(N-1)T_c/2$ hai — wohi queue formula jo Ex 3 mein prove hua, ab $N=50$ ke saath.
3. Worst request: $W_{last}=(N-1)T_c=49\times 2=98\mu s$. Ye step kyun? Sabse badkismat request bilkul last mein hai, apne aage ke sab $N-1=49$ critical sections ka wait karte hue — arithmetic run ka top, mean ka exactly double.

Verify: $49\times 2/2=49\mu s$ average, aur $49\times 2=98\mu s$ worst case $=2\times 49$. ✓ Units $\mu s$ mein. ✓ Real lesson: high $N$ par, ek single global lock sab kuch serialize kar deta hai — isi liye real servers account ko shard karte hain ya per-account locks use karte hain (ek consistency vs throughput trade-off).

---

Cell J — exam twist: lock ordering se deadlock

Forecast: kya ye hamesha complete ho sakta hai, ya hang hoga?

1. Deadly interleaving dhundo: A ko L1 milta hai, B ko L2 milta hai. Ab A L2 ka wait karta hai (B ke paas hai), B L1 ka wait karta hai (A ke paas hai). Ye step kyun? Har ek ek lock hold karta hai aur doosre par hamesha ke liye block ho jaata hai — classic circular-wait cycle.
2. Confirm karo ki sabhi chaar Coffman conditions hold karti hain: mutual exclusion (locks), hold-and-wait (A L1 hold karta hai, L2 chahta hai), no preemption (held lock cheen nahi sakte), circular wait (A→L2→B→L1→A). Ye step kyun? Deadlock ke liye chaaon ki zaroorat hai; yahaan sab dikhayi deti hain, isliye hang possible hai (har run par guaranteed nahi — sirf bad interleaving par).
3. Fix — global lock ordering: har thread ko same order mein locks acquire karne do, jaise hamesha L1 pehle, phir L2. Ye step kyun? Agar A aur B dono acquire(L1); acquire(L2) karte hain, to koi circular wait nahi ban sakta — jo bhi pehle L1 lega wo agle L2 le lega. Ye cycle condition tod deta hai.

Verify: Ordered acquisition ke saath, "hold-and-wait cycle" $A\to L2\to B\to L1\to A$ impossible hai kyunki dono pehle L1 request karte hain. ✓ Deep-dive Deadlock and livelock mein continue hoti hai.

---

Recall Self-test (right side chhupao)

Bina lock ke do increments 0 se final value range ::: ya to 1 (lost update, 20 mein se 4 orderings mein) ya 2 (safe, 20 mein se 16 mein) $W_{queue\text{-}avg}$ for $N=5,T_c=40\mu s$ ::: $80\mu s$ $N=5$ threads mein se last ka wait ::: $160\mu s$ Barrier release time = arrival times ka ? ::: max (slowest thread) Stale expected ke saath CAS ::: koi write nahi, current value return karta hai, caller retry karta hai Do-lock deadlock ka fix ::: global lock ordering (har jagah same order)