Mutex — implementation using hardware atomics (test-and-set, CAS)

4.2.15 · Coding › Operating Systems

WHY kyu hume hardware ki zarurat hai?

Intuition Software akela kyun fail karta hai

Socho lock ek boolean hai. "Obvious" lock kuch aisa lagta hai:

while (lock == true) { }   // wait
lock = true;               // grab it

Yeh do alag machine operations hain: ek read aur ek write. CPU threads ko beech mein switch kar sakta hai.

Thread A lock == false padhta hai → set karne wala tha.
Context switch → Thread B bhi lock == false padhta hai → lock = true set karta hai, andar jaata hai.
Thread A resume hota hai, lock = true set karta hai, woh bhi andar jaata hai.

Dono critical section ke andar hain. Mutual exclusion toot gayi. Bug invisible lagti hai kyunki code sequentially dikhta hai — lekin read aur write ek saath glue nahi hain.

Fix yeh hai: ek single CPU instruction jo old value read kare AUR new value ek atomic, uninterruptible step mein likhe, bus lock ke saath taaki koi aur core beech mein ghus na sake.

WHAT hai ek atomic instruction?

test-and-set: lock ko scratch se derive karo

Definition test-and-set semantics

test_and_set(addr) yeh kaam karta hai ek atomic unit ke roop mein:

old = *addr;
*addr = 1;
return old;

HOW TAS se spinlock banao

Formula TAS spinlock

acquire(lock):
    while (test_and_set(&lock) == 1)   // spin while it WAS already 1
        ;                              // (someone else holds it)
release(lock):
    lock = 0;

WHY yeh correct hai. test_and_set hamesha lock = 1 set karta hai. Return value batati hai ki woh pehle kya tha:

Agar old value 0 thi → lock free tha, aur humne abhi ise claim kar liya. Loop exit karta hai → humara hai.
Agar old value 1 thi → koi pehle se hold kar raha tha; humne ise phir se 1 set kar diya (harmless, woh already 1 tha) aur spin karte rahe.

"Check" (read old) aur "claim" (write 1) ab ek indivisible action hain, toh upar wali race ho hi nahi sakti. Read aur write ke beech koi window nahi hai jahan koi doosra thread ghus sake.

compare-and-swap (CAS): zyada powerful primitive

Definition CAS semantics

compare_and_swap(addr, expected, new) atomically karta hai:

if (*addr == expected) { *addr = new; return true; }
else                   { return false; }

Kuch hardware bool ki jagah old value return karta hai (CMPXCHG). Same idea hai.

Formula CAS spinlock

acquire(lock):
    while (!compare_and_swap(&lock, 0, 1))   // try to flip 0 -> 1
        ;
release(lock):
    lock = 0;   // or CAS(&lock, 1, 0)

WHY CAS > TAS. TAS sirf ek boolean manipulate kar sakta hai. CAS tumhe kehne deta hai "X ko tabhi change karo jab woh wahi value ho jo maine last dekhi thi." Yeh lock-free data structures (counters, stacks, queues) enable karta hai, sirf mutexes nahi. Yeh AtomicInteger.compareAndSet, std::atomic::compare_exchange, etc. ki foundation hai.

Figure — Mutex — implementation using hardware atomics (test-and-set, CAS)

Worked examples

Worked example Example 1 — do threads TAS par race karte hain, sirf ek jeetata hai

lock = 0. Threads A aur B dono "same time" par acquire call karte hain.

Hardware atomics ko serialize karta hai: ek waqt mein sirf EK test_and_set execute hoti hai. Yeh step kyun? Bus lock guarantee karta hai ki RMWs interleave nahi ho sakti.
Maan lo A ka TAS pehle chalta hai: old 0 return karta hai, lock=1 set karta hai. A loop se bahar → lock uska hai. Kyun? old==0 matlab woh free tha.
B ka TAS aage chalta hai: old 1 return karta hai, lock=1 set karta hai. B 1 dekhta hai → spin karta rehta hai. Kyun? old==1 matlab A ke paas already tha.
A release call karta hai → lock=0. B ka agla TAS 0 return karta hai → B andar jaata hai. Kyun? Ab free ho gaya, B ise jeet leta hai. Result: mutual exclusion hold hoti hai; har waqt exactly ek thread andar hota hai.

Worked example Example 2 — CAS ke saath atomic counter increment (lock-free)

Goal: ek shared counter ko bina mutex ke increment karo.

do {
    old = counter;            // read snapshot
    new = old + 1;            // compute
} while (!CAS(&counter, old, new));   // commit only if unchanged

old read karo. Kyun? CAS ko compare karne ke liye ek "expected" value chahiye.
old se new compute karo. Kyun? Hum optimistically kaam karte hain, maante hue ki koi interference nahi hai.
CAS tabhi commit karta hai jab counter still old ke barabar ho. Kyun? Agar kisi doosre thread ne beech mein change kiya, toh hamara new stale hai → CAS fail hoti hai → hum fresh read ke saath retry karte hain. Result: koi lock nahi, koi deadlock nahi; contention mein threads bas loop retry karte hain.

Worked example Example 3 — Test-and-Test-and-Set (ek optimization)

Plain TAS spinning bus ko atomic writes se hammer karta hai. Behtar:

acquire(lock):
    while (true) {
        while (lock == 1) ;            // spin on a CHEAP read (cached)
        if (test_and_set(&lock) == 0)  // only do the expensive atomic when it looks free
            return;
    }

Inner loop ek plain read par spin karta hai — local cache mein rehta hai, koi bus traffic nahi. Kyun? Atomic RMW doosre cores ki cache lines invalidate karta hai; reading bahut sasta hai.
Sirf jab lock free lagta hai tabhi hum atomic TAS try karte hain. Kyun? High contention mein cache-line bouncing kam karta hai. Result: same correctness, bahut kam bus contention.

Common mistake Common errors ko steel-man karna

"Spinlock = busy waiting = hamesha bura." Sahi lagta hai kyunki spinning CPU jalata hai. Fix: multi-core par, agar critical section chota hai, toh spinning tez hoti hai sleeping se (koi context-switch cost nahi). Real mutexes thodi der spin karte hain, phir so jaate hain. Expected wait time ke hisaab se choose karo.
"volatile flag ke liye kaafi hai." Sahi lagta hai — volatile compiler caching rok deta hai. Fix: volatile read-modify-write ko atomic nahi banata aur koi memory ordering guarantees nahi deta. Tumhe phir bhi hardware atomic chahiye.
"Release ko bas lock = 0 chahiye, ordering matter nahi karta." Sahi lagta hai — yeh ek write hai. Fix: tumhe ek memory barrier chahiye taaki critical section ke andar ke writes unlock se pehle visible hon. Acquire ko acquire-barrier chahiye, release ko release-barrier chahiye.
CAS ke saath ABA problem. Sahi lagta hai: "value wapas A par hai, toh kuch change nahi hua." Fix: ho sakta hai A→B→A gaya ho. CAS nahi bata sakta. Lock-free structures ke liye version/tag counters (double-width CAS) use karo.

Flashcards

Why can't a plain while(lock){} lock=1 implement a mutex?

lock ka read aur write do alag instructions hain; beech mein context switch do threads ko dono "free" dekhne deta hai aur dono andar aa jaate hain — mutual exclusion toot jaati hai.

What does test_and_set(addr) do atomically?

addr par old value read karta hai, *addr = 1 set karta hai, old value return karta hai — sab ek indivisible step mein.

In a TAS spinlock, what does a returned old value of 0 mean?

Lock free tha aur tumne abhi ise acquire kar liya; spin loop se bahar niklo.

What does compare_and_swap(addr, expected, new) do?

Atomically: agar *addr == expected ho, toh *addr = new set karo aur true return karo; warna chhod do aur false return karo.

Why is CAS more powerful than test-and-set?

CAS write ko current value ke expected value se match hone par condition karta hai, lock-free data structures enable karta hai; TAS sirf ek boolean flip karta hai.

What is the ABA problem?

Ek CAS succeed ho jaati hai kyunki value expected ke barabar hai, lekin woh actually beech mein A→B→A change ho chuki thi; CAS intermediate change detect nahi kar sakta. Version tags se fix karo.

Why does Test-and-Test-and-Set reduce bus traffic?

Yeh saste cached read par spin karta hai aur expensive atomic RMW sirf tab karta hai jab lock free lagta ho, cache-line bouncing se bachata hai.

Is busy-wait spinning always bad?

Nahi — bahut chote critical sections ke liye multi-core par, spinning context-switch overhead se bachata hai aur sleeping se tez hota hai.

Why is volatile insufficient for a lock flag?

Yeh compiler caching toh rok deta hai lekin atomic read-modify-write ya memory-ordering guarantees nahi deta.

What memory ordering does acquire/release need?

Acquire ko acquire barrier chahiye (koi baad wala op usse pehle na move ho); release ko release barrier chahiye (koi pehle wala op uske baad na move ho) taaki critical-section writes unlock se pehle visible hon.

Recall Feynman: 12-saal ke bacche ko explain karo

Socho ek bathroom hai aur darwaze par ek sign hai jo kehta hai FREE ya BUSY. Agar do bacche sign ko ek hi pal dekhein, dono FREE dekhte hain aur dono barge in karte hain — chaos. Trick: ek jadui darwaze ka handle jo, ek snap mein, sign dekhta bhi hai AUR use BUSY kar deta hai, phir batata hai sign pehle kya keh raha tha. Agar FREE keh raha tha, tum andar aa gaye. Agar BUSY keh raha tha, koi tumse pehle aa gaya — bahar ruko. Kyunki dekhna aur flip karna ek saath hota hai bina kisi gap ke, do bacche kabhi dono nahi jeet sakte. Woh jadui handle "test-and-set" hai. Ek fancier handle ("CAS") sign ko BUSY tabhi karta hai jab woh exactly FREE ho — jo tumhe bina full lock ke shared cheezein safely change karne deta hai.

Connections

Critical Section Problem — woh race jise yeh solve karta hai
Spinlock vs Blocking Mutex — wait karte waqt kya karna hai
Memory Barriers and Ordering — lock ko cores ke across visible banana
Lock-Free Data Structures — CAS par built
Semaphores — higher-level counting synchronization
Cache Coherence (MESI) — kyun atomics cache-line bouncing cause karte hain
Deadlock — mutual exclusion kya lead kar sakta hai