Synchronization primitives (locks, barriers)

6.1.8 · Hardware › Parallelism & Multicore

The fundamental problem: Race conditions

Jab multiple threads concurrently execute hoti hain, unke operations interleave ho sakte hain unpredictable tareekon se. Yeh simple increment dekho:

// Thread 1 aur Thread 2 dono execute karte hain:
counter = counter + 1;

Hardware level par, yeh ban jaata hai:

LOAD counter memory se register mein
ADD 1 register mein
STORE register wapas memory mein

Agar dono threads simultaneously execute hon, toh hum dekh sakte hain:

Thread 1 LOAD (reads 0)
Thread 2 LOAD (reads 0)
Thread 1 ADD (computes 1)
Thread 2 ADD (computes 1)
Thread 1 STORE (writes 1)
Thread 2 STORE (writes 1)

Result: counter = 1, 2 nahi! Yeh hai lost update problem.

Figure — Synchronization primitives (locks, barriers)

Locks (Mutual Exclusion)

Derivation: Lock ko first principles se banana

Ek sahi lock ki requirements:

Mutual exclusion: Critical section mein sirf ek thread
Progress: Agar koi thread lock nahi rakh rahi, toh ek waiting thread eventually usse acquire kar le
Bounded waiting: Lock acquire karne ka wait karne wali thread ko forever wait nahi karna chahiye (fairness)

Attempt 1: Simple flag (BROKEN)

bool lock = false;
 
acquire() {
    while (lock == true) { /* spin */ }
    lock = true;
}
 
release() {
    lock = false;
}

Yeh kyun fail hota hai: Do threads dono lock == false dekh sakti hain, dono while loop pass kar sakti hain, aur dono lock = true set kar sakti hain. Koi mutual exclusion nahi!

Attempt 2: Test-and-Set (Hardware atomic instruction)

Modern CPUs atomic read-modify-write instructions provide karte hain. Test-and-Set (TAS):

// Hardware yeh EK atomic instruction ke roop mein provide karta hai
int TestAndSet(int *ptr) {
    int old = *ptr;
    *ptr = 1;
    return old;
}

Atomic kyun? CPU ka cache coherence protocol ensure karta hai ki TAS operation ke dauran koi doosra core is memory location ko access nahi kar sakta.

Ab hamaara lock:

typedef struct {
    int flag;  // 0 = free, 1 = held
} lock_t;
 
void acquire(lock_t *lock) {
    while (TestAndSet(&lock->flag) == 1) {
        // Spin: koshish karte raho
    }
}
 
void release(lock_t *lock) {
    lock->flag = 0;
}

Correctness ki derivation:

Mutual exclusion: TAS exactly EK thread ko 0 (old value) return karta hai jab flag 0 tha. Baaki sab ko 1 milta hai aur woh spin karte hain.
Progress: Jab release() flag=0 set karta hai, next TAS succeed karega.
Bounded waiting: Guarantee nahi—ek thread forever spin kar sakti hai agar unlucky ho.

Formula Spin lock overhead

Agar $N$ threads ek lock ke liye contend kar rahi hain jo $T_{c}$ time ke liye hold hai, average wait time per waiting thread: $W_{a v g} = \frac{T _{c}}{2}$ Kyun? Ek waiting thread current holder ke critical section ke dauran kisi random point par arrive karti hai. Average mein usse remaining critical-section time ka aadha wait karna padta hai, yaani $T_{c} /2$ (uniform random arrival within hold interval assume karte hue). Saare contenders par total wait: $(N - 1)$ threads holder ke peeche queue mein hain, aur har ek ko apne aage ke saare critical sections complete hone tak FIFO order mein wait karna padta hai, last thread $\approx (N - 1) \cdot T_{c}$ wait karti hai. Toh queue positions par average hai: $W_{q u e u e - a v g} = \frac{( N - 1 ) \cdot T _{c}}{2}$ Note karo yeh do alag quantities hain: $W_{a v g} = T_{c} /2$ ek holder ke peeche per-arrival expected wait hai; $W_{q u e u e - a v g}$ ek $N$ -deep FIFO queue par mean hai. Energy cost: Spinning CPU cycles waste karta hai. Agar har spin iteration $t_{s p in}$ leta hai aur lock $T_{c}$ ke liye held hai: $E_{w a s t e} = \frac{T _{c}}{t _{s p in}} \cdot (N - 1) \cdot E_{in s t r u c t i o n}$ Contention ke saath yeh growth blocking locks ko motivate karti hai.

Attempt 3: Compare-and-Swap (CAS) - Zyada general

int CompareAndSwap(int *ptr, int expected, int new) {
    int actual = *ptr;
    if (actual == expected)
        *ptr = new;
    return actual;
}

CAS zyada powerful hai—lock-free data structures implement kar sakta hai. Lock implementation behavior mein TAS jaisi hi hai.

Blocking locks: CPU waste mat karo

Spin locks single-core ya oversubscribed systems par wasteful hote hain. Solution: Lock unavailable hone par CPU yield karo.

void acquire(lock_t *lock) {
    while (TestAndSet(&lock->flag) == 1) {
        yield();  // OS call: CPU doosri thread ko do
    }
}

Aur bhi achha: Ek wait queue use karo. Jab lock unavailable ho, thread park() call kare (so jaye), aur release karne wali thread ek waiting thread par unpark() call kare.

Worked example Lock usage pattern

lock_t mutex;
int shared_counter = 0;
// Thread function
void increment() {
    acquire(&mutex);
    // Critical section
    shared_counter = shared_counter + 1;
    release(&mutex);
}

Yeh step kyun?

acquire: Ensure karta hai ki sirf HUM shared_counter modify kar rahe hain
Critical section: Woh dangerous code jo shared state access karta hai
release: Doosri threads ko proceed karne do

Common mistake: Error paths mein release bhool jaana → deadlock!

Barriers (Synchronization points)

Derivation: Barrier banana

Requirements:

Saari $N$ threads ko barrier tak pahunchna chahiye
Koi thread tab tak proceed nahi karti jab tak sab pahunch na jayein
Multiple phases ke liye reusable (back-to-back barriers mein safely kaam karna chahiye)

Naive barrier (BROKEN reuse ke liye)

// DANGER: count reset karna aur ek CV use karna kaafi nahi hai
void barrier_wait(barrier_t *b) {
    lock(&b->lock);
    b->count++;
    if (b->count == b->threshold) {
        b->count = 0;          // reset
        broadcast(&b->cv);
    } else {
        wait(&b->cv, &b->lock); // doosron ka wait karo
    }
    unlock(&b->lock);
}

Common mistake "count = 0 reset karna" akele barrier reuse kyun todta hai

Intuition: "Last thread counter reset karti hai aur sabko jagaati hai, toh next time ke liye ready hai." Complete lagta hai. Reality: Ek fast thread jo abhi wake up hui hai woh pichle phase ki slow thread ke schedule hone se pehle hi agle phase ke liye barrier_wait dobara call kar sakti hai. Fast thread count increment karti hai, aur ab slow thread ka wakeup aur naye phase ka count uljh jaata hai—kuch threads atak jaati hain, ya ek thread bina sab ke pahunche barrier se nikal jaati hai. Yeh classic barrier reuse race hai. Fix: Ek generation (phase) counter add karo. Har thread wait karne se pehle current generation record karti hai, aur sirf tab proceed karti hai jab generation actually advance ho—na ki sirf jab CV signal ho. Yeh har barrier episode ko logically distinct banata hai.

Correct reusable barrier (generation counter ke saath)

typedef struct {
    int count;          // IS generation mein kitne pahunche hain
    int threshold;      // Threads ki total sankhya (N)
    int generation;     // Phase / episode counter
    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);   // internal lock ZAROOR initialize karo
    cond_init(&b->cv);     // condition variable ZAROOR initialize karo
}
 
void barrier_wait(barrier_t *b) {
    lock(&b->lock);
    int my_gen = b->generation;   // yaad rakho main kis episode ka hoon
 
    b->count++;
    if (b->count == b->threshold) {
        // Last thread: barrier kholo aur NEW generation shuru karo
        b->generation++;   // phase advance karo -> purane aur naye ko alag karo
        b->count = 0;      // next use ke liye reset karo
        broadcast(&b->cv);
    } else {
        // Tab tak wait karo jab tak generation actually change na ho.
        // Looping spurious wakeups AUR reuse race dono se bachata hai.
        while (my_gen == b->generation) {
            wait(&b->cv, &b->lock);
        }
    }
    unlock(&b->lock);
}

Yeh kyun kaam karta hai:

Lock count/generation protect karta hai: Atomic increment aur comparison.
Generation counter: Ek naya-woken fast thread jo next phase ke liye re-enter karti hai uska my_gen alag hota hai, isliye woh pichle episode ke wait ko accidentally satisfy ya interfere nahi kar sakti.
while loop (if nahi): Thread tab tak nahi nikalti jab tak generation sach mein advance na ho, isliye spurious wakeups aur reuse races dono handle hote hain.
Init function: lock_init aur cond_init required hain—uninitialized mutex/CV undefined behavior hai.

Barrier ke types

Blocking barrier: Threads so jaati hain (upar wala example)
Spinning barrier: Threads spin-wait karti hain (bahut chote phases ke liye useful)
Tree barrier: $N ≫ 1$ ke liye hierarchical wake-up (notification time $O (N)$ se $O (lo g N)$ ho jaata hai)

Worked example Matrix computation mein Barrier

double A[N][N], B[N][N];
barrier_t sync;
 
void compute_phase() {
    int tid = get_thread_id();
    // Phase 1: A par compute karo, B mein write karo
    for (int i = tid * CHUNK; i < (tid+1) * CHUNK; i++) {
        for (int j = 0; j < N; j++) {
            B[i][j] = some_function(A[i][j]);
        }
    }
    
    barrier_wait(&sync);  // SAARI threads ko Phase 1 finish karna chahiye
    
    // Phase 2: Ab B read karna safe hai, A mein write karo
    for (int i = tid * CHUNK; i < (tid+1) * CHUNK; i++) {
        for (int j = 0; j < N; j++) {
            A[i][j] = another_function(B[i][j]);
        }
    }
}

Yahan barrier kyun? Phase 2 B se read karta hai, jo Phase 1 write karta hai. Barrier ke bina, Thread 1 Phase 2 shuru kar sakti hai jab Thread 2 abhi Phase 1 mein hai, aur purane/partial B values read kar sakti hai. Aur kyunki WAHI barrier object ek outer loop ke kai iterations mein reuse hota hai, generation counter essential hai.

Hardware support for synchronization

Modern CPUs provide karte hain:

Atomic instructions: TAS, CAS, Fetch-and-Add, Load-Linked/Store-Conditional
Memory barriers: Cores ke across loads/stores ki ordering enforce karte hain
Cache coherence: Lock variables consistent rakhta hai (MESI protocol)

Common mistake Memory ordering bhool jaana

Trap: Modern CPUs par stores reorder ho sakte hain. Memory barriers ke bina, doosri thread dekh sakti hai:

data = 42;      // Store 1
flag = true;    // Store 2 (release lock)

flag=true lekin data abhi bhi uninitialized!

Fix: Release operations mein ek store barrier hota hai (ensure karta hai ki saare prior stores pehle complete hon). Acquire operations mein ek load barrier hota hai (ensure karta hai ki subsequent loads saare prior stores dekh sakein).

Advanced: Lock-free algorithms

Kya hum sirf atomic CAS use karke locks se poori tarah bach sakte hain?

void lock_free_increment(int *counter) {
    int old, new;
    do {
        old = *counter;
        new = old + 1;
    } while (CompareAndSwap(counter, old, new) != old);
}

Kaise kaam karta hai:

Current value read karo
Naya value compute karo
CAS: agar *counter abhi bhi old ke equal hai, new mein update karo
Agar CAS fail ho (doosri thread ne badla), retry karo

Advantage: No blocking, hamesha progress
Disadvantage: High contention → bahut saare retries → wasted work

Recall Ek 12-saal ke bachche ko explain karo

Socho ek bathroom mein ek toilet hai. Agar lock nahi hai, toh do log ek saath andar aa sakte hain—awkward! Ek lock ek simple system ki tarah hai: "Agar darwaza unlocked hai, main usse lock karta hoon aur andar jaata hoon. Jab kaam ho jaaye, unlock kar deta hoon." Test-and-Set ek magic door handle ki tarah hai jo ek instant mein, check bhi karta hai ki unlock hai ya nahi AUR lock bhi kar deta hai agar hai. Koi in dono actions ke beech ghus nahi sakta.

Ek barrier ek field trip ki tarah hai jahan teacher kehti hai, "Hum sab 3 baje bus par milenge—jab tak sab nahi aa jaate, koi nahi chadhega." Agar tum jaldi aa jaao, wait karo. Jab last banda aa jaye, teacher chillati hai "All aboard!" aur sab saath chadhte hain. Aur agli baar phir trip chalane ke liye, teacher ek "Day number" rakhti hai taaki ek fast bachcha jo utar chuka hai galti se aaj ki roll call mein count na ho.

Connections

Cache coherence protocols – MESI ensure karta hai ki lock variables cores ke across consistent rahein
Memory consistency models – Loads/stores ki legal orderings define karte hain; synchronization order enforce karta hai
Thread scheduling – Blocking locks ko OS scheduler ki zaroorat hoti hai threads ko park/unpark karne ke liye
Deadlock and livelock – Galat lock ordering deadlock cause karta hai; lock-free algorithms livelock kar sakte hain
Parallel algorithms – Barriers bulk-synchronous parallel (BSP) model enable karte hain
Atomic operations – Hardware primitives jo lock implementation possible banate hain

#flashcards/hardware

Race condition kya hota hai?

Jab multiple threads shared data ko concurrently access karti hain aur result unke operations ki unpredictable interleaving par depend karta hai, jo galat results deta hai.

Ek sahi lock ko kaunsi teen guarantees deni chahiye?

1) Mutual exclusion (critical section mein sirf ek thread), 2) Progress (agar lock free hai, ek waiting thread eventually usse acquire kar le), 3) Bounded waiting (koi thread forever wait nahi kare).

Ek simple flag (check-then-set) lock ke roop mein kyun fail hota hai?

Check aur set alag operations hain. Do threads dono "free" dekh sakti hain, dono check pass kar sakti hain, aur dono flag set kar sakti hain, mutual exclusion violate kar ke. Atomic read-modify-write chahiye.

Test-and-Set (TAS) atomically kya karta hai?

Memory location ka purana value read karta hai, usse 1 set karta hai, aur purana value return karta hai—sab ek indivisible hardware operation ke roop mein.

Spin lock kya hota hai aur yeh wasteful kab hota hai?

Ek lock jahan threads ek loop mein repeatedly check (spin) karti hain jab tak lock free na ho. Wasteful hota hai jab wait time lamba ho, ya single-core systems par jahan spinning thread lock holder ko run karne se rokti hai.

Spin lock ke liye, ek thread ka expected wait jo EK holder ke peeche arrive karti hai, uniform arrival assume karte hue, kya hota hai?

Lagbhag

T_{c} /2

— critical-section hold time ka aadha. (

(N - 1) \cdot T_{c} /2

figure ek

N

-deep FIFO queue par average hai.)

Parallel programming mein barrier kya hota hai?

Ek synchronization point jahan

N

threads sab ko pahunchna hota hai pehle ki koi bhi proceed kar sake, ensuring phase completion before moving to the next phase.

Lock aur barrier mein kya key difference hai?

Lock mutual exclusion ensure karta hai (critical section mein ek time par ek thread). Barrier ensure karta hai ki saari threads ek synchronization point par pahunchen pehle ki koi proceed kare (ordering/phasing).

Ek reusable barrier ko generation/phase counter kyun use karna chahiye?

Iske bina, ek fast thread jo ek barrier se wake up hui hai next phase mein loop kar sakti hai aur count increment kar sakti hai pehle ki pichle phase ki slow thread run ho, dono episodes ko tangle kar ke aur correctness todke. Generation counter har barrier episode ko distinct banata hai aur waiters ko loop karne deta hai jab tak generation actually advance na ho.

barrier_init ko lock_init aur cond_init kyun call karna chahiye?

Uninitialized mutex ya condition variable use karna undefined behavior hai; internal synchronization objects ko barrier use karne se pehle initialize karna zaroori hai.

Compare-and-Swap (CAS) kya hota hai?

Ek atomic instruction jo ek memory location ko expected value se compare karti hai aur, agar match kare, usse new value mein update kar deti hai. Actual value found return karta hai, lock-free algorithms ke liye retry loops allow karta hai.

Lock-free algorithms ka locks ke upar kya advantage hota hai?

Woh system-wide progress guarantee karte hain chahe individual threads delayed ya preempted hon, deadlock aur priority inversion avoid karte hain. Lekin, contention mein high retry overhead suffer kar sakte hain.