Visual walkthrough — Synchronization primitives (locks, barriers)

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

Poore note mein, thread ka matlab hai "ek worker jo instructions ki ek list follow kar raha hai". Shared variable ek memory mein number hai jo ek se zyada worker read aur write kar sakte hain. Shuru karne ke liye bas itni hi vocabulary chahiye.

Step 1 — Do workers, ek number

KYA. Do workers, T1 aur T2, ko imagine karo. Dono same chhoti si job run karna chahte hain: shared number counter lo aur use ek bada karo. C mein yeh innocent line hai counter = counter + 1.

KYUN. Bug dekhne se pehle, humein sabse simple possible situation chahiye jahan bug exist kar sake: sabse chhoti shared cheez (ek number) jise sabse chhoti bheed (do workers) touch kare.

PICTURE.

Beech mein red box dekho — woh counter hai, abhi value $0$ hold kar raha hai. Dono arrows (T1 left se, T2 right se) uski taraf point kar rahe hain. Abhi kuch galat nahi hai, kyunki humne nahi dekha ki "add one" ka matlab asliyat mein kya hai.

Step 2 — "Add one" chhup ke teen steps hai

KYA. CPU ek single motion mein memory location mein ek nahi jod sakta. Usse yeh karna hoga:

1. LOAD — memory se counter ko ek private scratch space (register) mein copy karo.
2. ADD — us private copy mein $1$ jodo.
3. STORE — private copy ko wapas memory mein likho.

KYUN. Yahi poore lesson ka core hai. Bug sirf sub-steps ke beech ghus sakta hai. Agar "add one" sach mein ek indivisible act hota, toh ghusne ke liye koi gap nahi hoti. Isliye hamen gaps expose karni hogi.

Har worker ka apna register hota hai, apne chhote box ki tarah draw kiya gaya. "Register" ka matlab hai "worker ka private notepad — koi aur use read nahi kar sakta."

PICTURE.

Teeno stacked bars teen sub-steps hain. Notice karo ki shared counter (red) beech mein hai, lekin har worker ka register (sides par black boxes) private hai. Dashed lines gaps hain — woh khatarnak moments jahan CPU ek worker ko pause karke doosre ko run kar sakta hai.

Step 3 — Bura interleaving, frame by frame

KYA. Worst-case ordering run karte hain. Time niche ki taraf flow karta hai. Mein har instant par har worker ki value mark karta hoon.

$\underset{r_1=0}{\underbrace{\text{T1 LOAD}}}\to \underset{r_2=0}{\underbrace{\text{T2 LOAD}}}\to \underset{r_1=1}{\underbrace{\text{T1 ADD}}}\to \underset{r_2=1}{\underbrace{\text{T2 ADD}}}\to \underset{\text{counter}=1}{\underbrace{\text{T1 STORE}}}\to \underset{\text{counter}=1}{\underbrace{\text{T2 STORE}}}$

Terms left to right padhne par: $r_1$ T1 ka private register hai, $r_2$ T2 ka private register hai. Dono LOAD karte hain jab counter abhi bhi $0$ dikhata hai, isliye dono stale value $0$ copy karte hain. Dono apne notepad par $1$ reach karne ke liye ADD karte hain. Dono $1$ STORE karte hain. Do increments hue, lekin counter $1$ par khatam hua, $2$ par nahi.

KYUN. Yeh hai lost update: ek worker ki write doosre ki write ko silently overwrite kar deti hai. Parent note is exact failure ka naam deta hai — yahan hum woh timeline dekhte hain jo ise produce karta hai.

PICTURE.

Red STORE arrows follow karo: T2 ka store T1 ke store ke upar land karta hai. T1 ka poora increment gayab ho gaya. Jo value hum expect karte the ($2$, dashed) woh kabhi reach nahi hoti.

Step 4 — Naive fix, aur yeh bhi kyun toot jaata hai

KYA. Obvious idea: number ko ek flag se guard karo. "Agar flag free kahe, toh use held karo, phir apna kaam karo." Code mein:

while (lock == true) { /* spin */ }   // wait while held
lock = true;                          // claim it

KYUN. Hum mutual exclusion enforce karne ki koshish kar rahe hain — ek fancy phrase jiska matlab hai ek time par sirf ek worker danger zone ke andar. Danger zone (LOAD-ADD-STORE) ko critical section kehte hain.

Lekin check-then-set khud do steps hai — flag padhna, phir flag likhna — beech mein ek gap ke saath. Toh wahi bimari ek level upar dobara aati hai.

$\underset{\text{"it’s free!"}}{\underbrace{\text{T1 reads flag}=false}}\to \underset{\text{"it’s free!"}}{\underbrace{\text{T2 reads flag}=false}}\to \underset{\text{enters}}{\underbrace{\text{T1 sets }true}}\to \underset{\text{enters}}{\underbrace{\text{T2 sets }true}}$

Dono ne false dekha, dono andar chale gaye. Mutual exclusion khatam.

PICTURE.

"Read flag" aur "set flag" ke beech red gap wahi crack hai Step 2 se, bas alag costume mein. Ek gap ko doosra gap add karke fix nahi kar sakte.

Step 5 — Test-and-Set: read aur write ko saath chipkana

KYA. Hardware hume ek instruction deta hai jo old value read karta hai aur new value likhta hai beech mein koi gap ke bina — indivisible. Ise Test-and-Set (TAS) kehte hain:

int TestAndSet(int *ptr) {
    int old = *ptr;   // read the old value
    *ptr = 1;         // write 1 (claim it)
    return old;       // hand back what was there before
}

Term by term: ptr flag ka address hai; old woh hai jo flag mein pehle tha jab humne use touch kiya; hum unconditionally 1 daalte hain; hum old return karte hain taki caller jaane ki unhone isse flip kiya ya nahi.

YEH TOOL KYUN. Humein ek operation chahiye jo scheduler se split nahi ho sakta. TAS sabse chhota aisa tool hai: yeh read-then-write ko ek atomic beat mein collapse karta hai. "Atomic" ka matlab literally uncuttable hai — koi doosra worker mid-instruction mein nahi ghus sakta, kyunki cache coherence protocol exactly ek core ko us memory line ki exclusive ownership deta hai puri duration ke liye.

Lock, TAS use karke:

void acquire(lock_t *lock) {
    while (TestAndSet(&lock->flag) == 1) { /* spin */ }
}
void release(lock_t *lock) { lock->flag = 0; }

Yeh mutual exclusion kyun deta hai? Jab flag $0$ ho (free) aur kai workers race karte hain, TAS ek at a time run hota hai atomic ki definition se. Pehle worker ka TAS old = 0 dekhta hai (darwaza khula tha) — woh andar jaata hai. Har baad ke worker ka TAS ab old = 1 dekhta hai (kisi ne pehle se $1$ daal diya) — unhe $1$ wapas milta hai aur woh spin karte rehte hain.

PICTURE.

Red block single unbreakable beat hai. Exactly ek arrow (T1) old = 0 ke saath emerge hota hai aur enter karta hai; T2 ka TAS $1$ return karta hai aur loop karta hai. Step 4 se compare karo — gap gone hai.

Step 6 — Degenerate cases (koi gap unshown mat chhodo)

KYA AUR KYUN. Ek derivation tabhi trustworthy hai jab woh corners mein survive kare. Chaar corners:

• Ek worker, koi contention nahi ($N=1$): TAS $0$ padhta hai, $0$ return karta hai, instantly enter karta hai. Koi spinning nahi. Cost ek atomic instruction hai. Sahi aur sasta.
• Lock aane par pehle se held hai: TAS $1$ padhta hai, $1$ return karta hai, aap spin karo. Jab holder release call karta hai ($0$ likhta hai), aapka agla TAS $0$ padhta hai aur aap enter karte ho. Yeh progress guarantee hai.
• Do workers bilkul same instant par release/acquire karte hain: Overlap karna impossible hai — TAS aur release mein store dono same memory line par act karte hain, aur coherence unhe serialise karta hai. Ek ordering jiti hai; doosra simply updated value dekhta hai.
• Bhula hua release: flag hamesha ke liye $1$ rehta hai, har future acquirer hamesha ke liye spin karta hai. Yeh self-inflicted deadlock hai — lock sahi hai, program buggy hai.

PICTURE.

Chaar mini-timelines, ek per corner. Red element flag karta hai jo har corner ko distinct banata hai: akela entry, release ke baad successful retry, serialised clash, aur bhule hue release ka never-ending spin.

Ek-picture summary

Ek canvas par poori journey: gap villain hai (Steps 2–4), aur atomic beat (red) hero hai jo use hata deta hai (Step 5). Naive flag = gap moved, removed nahi. TAS = gap glued shut → exactly ek winner.

Related: Atomic operations · Cache coherence protocols · Memory consistency models · Deadlock and livelock · Thread scheduling · Parallel algorithms