Synchronization primitives (locks, barriers): Question bank

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

Definition Is page par use hone wale symbols (ek baar, shuru mein define kiye gaye)

Kisi bhi trap se pehle, yahan bataya gaya hai ki har ek ka kya matlab hai — sab kuch ek single lock ya barrier episode par measure kiya gaya hai:

$N$ = contending threads ki sankhya (barrier ke liye, un participants ki sankhya jo sab ko pahunchna zaroori hai).
$T_{c}$ = critical-section hold time: winning thread lock ko release karne se pehle kitni der rakhta hai.
$t_{s p in}$ = one spin iteration ka time (ek Test-and-Set attempt jo fail hota hai aur loop karta hai).
$E_{in s t r u c t i o n}$ = energy cost of executing one instruction (roughly, ek spin attempt).
$W_{a v g}$ = ek thread ka expected wait jo random moment par ek current holder ke peeche aata hai.
$W_{q u e u e - a v g}$ = $N$ -deep FIFO queue mein saari positions par averaged mean wait.
$E_{w a s t e}$ = spinning threads dwara wait karte waqt jalaya gaya total energy.

Shuru karne se pehle un teen concepts ki picture dekhein jo yeh bank test karta hai — woh batata hai ki har trap kahan rehta hai.

Figure — Synchronization primitives (locks, barriers)

Atomic read-modify-write, visually

True ya false — justify karein

Simple flag lock (check lock == true, phir set lock = true) mutual exclusion guarantee karta hai.

False — do threads check aur set ke beech ke gap mein dono false read kar sakti hain (upar figure mein red gap), dono loop se nikal sakti hain, aur dono true likh sakti hain. Check-and-set ek indivisible step nahi hai.

Test-and-Set (TAS) isliye kaam karta hai kyunki compiler read aur write ko ek saath reorder karta hai.

False — yeh isliye kaam karta hai kyunki hardware read-modify-write ko ek atomic instruction banata hai, cache coherence protocol dwara enforce kiya gaya, kisi compiler trick ki wajah se nahi.

Ek atomic Test-and-Set akela critical section mein shared data ko protect karne ke liye kaafi hai.

False — atomicity acquire ko race karne se rokti hai, lekin memory fence ke bina CPU protected loads/stores ko lock ke baahir reorder kar sakta hai. Aapko acquire/release ordering bhi chahiye (dekhein Memory consistency models).

Spinlock hamesha blocking lock se kam CPU cycles waste karta hai.

False — spinning tab sasta hota hai jab hold time bahut chhota ho aur cores idle hon. Single core ya oversubscribed system par, spinning usi CPU ko jalata hai jishe lock-holder ko finish karne ke liye chahiye, cheezein aur kharab kar deta hai.

Compare-and-Swap (CAS) woh sab kar sakta hai jo Test-and-Set kar sakta hai, plus aur bhi.

True — CAS ek expected value carry karta hai, toh yeh current state ke basis par conditionally update kar sakta hai, lock-free structures enable karta hai; TAS hamesha blindly 1 likhta hai, toh sirf ek plain lock bana sakta hai.

Ek correct lock bounded waiting guarantee karta hai (koi thread forever wait nahi karta).

False — TAS spinlock mutual exclusion aur progress deta hai lekin bounded waiting nahi; ek unlucky thread har race haar sakta hai aur indefinitely spin kar sakta hai. Fairness ke liye ticket ya queue jaise extra machinery chahiye.

Jab barrier mein last thread broadcast call karti hai, count = 0 reset karna barrier ko reusable banane ke liye kaafi hai.

False — ek woken fast thread next phase mein loop kar sakti hai aur count increment kar sakti hai pehle ki previous phase ki ek slow thread run kare, dono episodes ko tangle kar deti hai. Phases ko distinct rakhne ke liye aapko ek generation counter chahiye.

Barrier aur lock ek hi problem solve karte hain.

False — lock mutual exclusion enforce karta hai (ek waqt mein ek thread andar); barrier rendezvous enforce karta hai (sab

N

threads ko pahunchna chahiye pehle ki koi jaaye). Bilkul alag goals hain.

Agar lock release ho jaaye lekin koi thread wait nahi kar rahi, toh release wasted work hai.

False — releasing sirf flag ko free set karti hai (ya kisi ko unpark nahi karti); yeh sasta hai aur zaroori hai taaki next acquirer succeed kare. Koi waste nahi hai, bas koi wake karne wala nahi hai.

park() / unpark() blocking locks saari busy-waiting eliminate kar dete hain.

Mostly true, lekin ek chhoti si window hai jahan ek thread sone ka decide karti hai jab hi unpark aa jaata hai (lost-wakeup problem). Guard hai wake-up predicate par loop karna — neeche pattern dekhein.

Lost-wakeup guard aur barrier generations, code mein

Definition Generation counter (ek reusable barrier actually kaise banta hai)

Ek generation (ya phase) sirf ek integer hai jo count karta hai ki barrier kitni baar poori tarah se khul chuka hai. Har thread sone se pehle iska snapshot leta hai aur tabhi jaata hai jab snapshot match nahi karta — proof ki ek poora naya episode shuru hua hai, koi stray wakeup nahi.

typedef struct {
    int   count;       // arrived in THIS generation
    int   threshold;   // = N, total participants
    int   generation;  // phase counter, starts at 0
    lock_t lock; cond_t cv;
} barrier_t;
 
void barrier_init(barrier_t *b, int n){
    b->count = 0; b->threshold = n; b->generation = 0;
    lock_init(&b->lock); cond_init(&b->cv);
}
 
void barrier_wait(barrier_t *b){
    lock(&b->lock);
    int my_gen = b->generation;      // snapshot MY episode
    if (++b->count == b->threshold){ // I am the last to arrive
        b->generation++;             // open a NEW episode
        b->count = 0;                // reset for reuse
        broadcast(&b->cv);
    } else {
        // loop on a PREDICATE, not a bare wait -> guards lost/spurious wakeups
        while (my_gen == b->generation)
            wait(&b->cv, &b->lock);
    }
    unlock(&b->lock);
}

while (my_gen == b->generation) loop park ke liye lost-wakeup guard jaise hi shape ka hai: wakeup ke baad hamesha condition re-test karein, wakeup par kabhi trust mat karein.

Error dhundhein

acquire(&mutex);
if (error) return;        // <-- kya galat hai?
shared_counter++;
release(&mutex);

Bug dhundhein.

Early return release ko skip kar deta hai, toh lock hamesha ke liye held rehta hai → deadlock. Critical section ke andar har error path ko pehle lock release karna chahiye.

void acquire(lock_t *l){ while(l->flag==1){} l->flag=1; }

Yeh kyun broken hai jabki yeh "checks then sets" karta hai?

Check aur set do alag operations hain; ek doosri thread gap mein ghus sakti hai. Yeh ek single atomic Test-and-Set / CAS hona chahiye, do plain memory accesses nahi.

if (b->count == b->threshold) { broadcast(&b->cv); }
else { wait(&b->cv, &b->lock); }   // no loop

wait ke surrounding loop ke bina kya khatre hai?

Ek spurious wakeup (ya pichli generation ka ek stale broadcast) thread ko tab bhi wake kar sakta hai jab condition abhi bhi false ho. while loop ke bina jo generation re-check kare, thread bahut jaldi aage badh jaata hai.

barrier_t b;
b.count = 0; b.threshold = 4;   // then straight to barrier_wait

Kya bhool gaye?

Internal lock aur condition variable kabhi initialize nahi kiye gaye (lock_init / cond_init), aur generation 0 set nahi kiya gaya. Uninitialized lock use karna undefined behaviour hai.

// mutex with NO ownership tracking:
release(lock_t *l){ l->flag = 0; }   // any thread may call this

Thread B, thread A dwara held lock par release call karta hai. Kya toot jaata hai, aur real mutexes isse kaise rokate hain?

flag = 0 lock ko free karta hai jabki A abhi bhi apne critical section mein hai, toh ek teesri thread enter kar sakti hai — mutual exclusion silently break ho jaati hai. Real mutexes ek owner id store karte hain aur non-owner se release (ya double-release) reject karte hain, isse corruption ki jagah error bana dete hain.

Kya E_waste = (T_c / t_spin) · (N−1) · E_instruction ek error hai?

Nahi — yeh ek correct estimate hai. Spins count karein:

T_{c}

tak held lock mein har spin

t_{s p in}

cost karti hai toh

T_{c} / t_{s p in}

spins per waiter deta hai, times

(N - 1)

waiters, times

E_{in s t r u c t i o n}

per spin. Yeh yahan hai yeh dikhane ke liye ki energy waste contention ke saath badhti hai

(N - 1)

, jo blocking locks prefer karne ka asli reason hai.

Why questions

Test-and-Set sirf flag set karne ki bajaye old value kyun return karta hai?

Old value se thread yeh jaanta hai ki usne lock acquire kiya (old 0 tha) ya der se pahuncha (old 1 tha). Return value ke bina atomically winner aur loser mein koi fark nahi kar sakte.

Barrier ko wait karne se pehle my_gen = b->generation kyun yaad rakhna padta hai?

Taaki waiter "barrier actually meri next phase mein advance hua" aur "kisi ne CV signal kiya" mein fark kar sake. Yeh tabhi aage badhta hai jab generation sach mein change ho, sirf wake hone par nahi.

Atomic instructions ke liye cache coherence kyun matter karta hai?

Atomic read-modify-write cores ke across indivisible dikhna chahiye; coherence protocol ek core ko operation ki duration ke liye cache line ki exclusive ownership deta hai, toh koi doosra core mid-operation mein value observe ya alter nahi kar sakta.

Hum fence aur atomic instruction dono kyun chahte hain — kya atomicity kaafi nahi hai?

Atomicity acquire ko indivisible banati hai, lekin surrounding loads/stores ki ordering ke baare mein kuch nahi kehti. Fence compiler/CPU ko protected accesses ko lock ke baahir move karne se rokta hai (dekhein Memory consistency models).

W_{a v g} = T_{c} /2

(per arrival) aur

W_{q u e u e - a v g} = (N - 1) T_{c} /2

mein kya fark hai?

W_{a v g}

randomly-timed arrival ke liye ek current holder ke peeche expected wait hai (average mein, uske hold ke halfway par).

W_{q u e u e - a v g}

saari

N

FIFO queue positions par wait average karta hai, jahan baad ki positions unke aage ke har critical section ka wait karti hain.

Spinning kabhi blocking se better kyun ho sakti hai?

Agar lock ek context switch se kam time ke liye held hai, toh briefly spinning mahenga sleep/wake round-trip avoid karti hai. Isliye kuch systems adaptive/spin-then-block locks use karte hain.

generation advance karna bhoolna (sirf count reset karna) testing mein kabhi kabhi kyun "work" karta lagta hai?

Low contention mein threads itni jaldi loop back nahi karte ki reuse race trigger ho, toh bug chhup jaata hai. Yeh tabhi surface karta hai jab ek fast thread next barrier tak pahunch jaata hai pehle ki previous wali ki ek slow thread kare — timing jo stress tests expose karti hai lekin casual runs miss kar deti hain.

Edge cases

threshold = 1 wala barrier kya karta hai?

Single thread pahunchti hai, turant count == threshold hit karta hai, generation advance karta hai, aur seedha nikal jaati hai — ek no-op barrier, jo correct behaviour hai.

threshold = 0 wala barrier kya karta hai?

Koi thread count ko increment karke kabhi equal to 0 nahi bana sakti (pehli arrival count = 1 > 0 set karti hai), toh == test ke saath barrier kabhi fire nahi karta aur koi bhi arrival hang ho jaati hai — ek degenerate input jise ek robust barrier_init reject karna chahiye (ya treat karna chahiye jaise "immediately fires, sabko through jaane deta hai").

Agar aap ek lock release karein jo kabhi acquire nahi hua?

Flag 0 (free) par force ho jaata hai, toh jo thread abhi andar critical section mein hai woh protected nahi rahi — ek aur thread ab enter kar sakti hai. Yeh silently mutual exclusion todta hai jab tak mutex ownership track nahi karta.

Do threads ek hi exact waqt par do cores par acquire call karti hain. Kaun jeetta hai?

Coherence protocol do atomic operations ko cache line par serialize karta hai, toh exactly ek TAS old 0 padhta hai aur doosra 1 padhta hai. Hardware level par ties impossible hain.

Zero threads kabhi barrier_wait call nahi karti. Barrier kis state mein hai?

Yeh count = 0, generation = 0 par raha karti hai, forever wait karti hai — harmless. Barrier tabhi "fire" karta hai jab

N

-wi thread pahunche; koi arrival nahi toh kuch block nahi hota aur kuch leak nahi hota.

Ek thread ek phase ke liye barrier_wait call karti hai, lekin

N

threads mein se ek crash ho gayi aur kabhi nahi pahunchi.

Barrier kabhi threshold reach nahi karta, toh har pahunchi thread forever wait karti hai → permanent stall. Barriers assume karti hain ki saare

N

participants alive hain; missing participants hang cause karte hain (ek liveness failure, dekhein Deadlock and livelock).

Recall Aage badhne se pehle self-check

Ek-line trap jise main abhi bhi justify nahi kar sakta ::: Us item ka answer dobara padhein aur parent note ke code mein trace karein, phir ek ghante mein apne aap ko re-test karein.