Critical section — mutual exclusion, progress, bounded waiting

4.2.14 · Coding › Operating Systems

WHAT is a critical section?

Definition Critical Section (CS)

Critical section code ka woh segment hai jahan ek process/thread shared resource (shared variable, file, device) access karta hai, jise ek waqt mein ek se zyada process access nahi kar sakti.

Har process ki structure aisi hoti hai:

while (true) {
    entry_section      // ask permission
    CRITICAL SECTION   // touch shared data
    exit_section       // release permission
    remainder_section  // do other (non-shared) work
}

WHY do we need it? Kyunki concurrent unsynchronized access se race condition create hoti hai — final result instructions ke unlucky interleaving par depend karta hai.

Worked example Classic race

Do threads count++ run karte hain shared count par (initially 5). Machine level par count++ teen instructions hai:

R1 = count      // load
R1 = R1 + 1     // add
count = R1      // store

Ek buri interleaving:

Thread A	Thread B	count
R1=count (5)		5
	R2=count (5)	5
R1=R1+1 (6)		5
	R2=R2+1 (6)	5
count=R1 (6)		6
	count=R2 (6)	6

Do increments hue, lekin count 6 par khatam hota hai, 7 par nahi. Ek update lost ho gaya. Why this step? Kyunki B ka load/modify/store A ke load aur store ke beech ghus gaya — dono ne stale 5 read ki.

The THREE requirements (WHY each exists)

DERIVING a correct lock from scratch

Hum step-by-step build karte hain, har tute hue attempt ko fix karte hue (Steel-man your mistakes).

Attempt 1 — single `turn` variable (strict alternation)

turn = 0
// Process i (i = 0 or 1)
while (turn != i) ;   // entry: busy-wait
   CS
turn = 1 - i          // exit: hand over

✅ Mutual exclusion: turn exactly ek value hold karta hai.
❌ Progress fails: agar P0 ki turn hai lekin P0 apne remainder mein busy hai (CS nahi chahta), toh P1 block ho jaata hai chahe CS free ho. Forced alternation = no progress.

Attempt 2 — `flag[]` (intent flags)

flag[i] = true        // "I want in"
while (flag[j]) ;     // wait while other wants in
   CS
flag[i] = false

✅ Mutual exclusion hold karta hai.
❌ Deadlock: dono simultaneously flag = true set kar lete hain, phir dono forever spin karte hain. Progress fail.

Attempt 3 — Peterson's solution (combine intent + courtesy)

Formula Peterson's Algorithm (2 processes)

Dono attempts ke good half ko merge karke derive kiya: intent flag rakho AUR ek turn jo ties ko yielding se break karta hai.

// shared:  bool flag[2] = {false,false};  int turn;
// Process i, other = j
flag[i] = true;        // 1. I want to enter
turn   = j;            // 2. but you go first (courtesy)
while (flag[j] && turn == j) ;   // 3. wait only if j wants AND it's j's turn
    CRITICAL SECTION
flag[i] = false;       // 4. I'm done

Peterson's correctness ka sketch proof:

Mutual exclusion: Dono ke andar hone ke liye, dono while se pass hue hote. P_i pass hua matlab flag[j]==false OR turn==i. Kyunki flag[i]=flag[j]=true (dono chahte hain), yeh reduce hota hai turn==i P_i ke liye aur turn==j P_j ke liye — impossible, turn ek value hai. ⇒ dono enter nahi kar sakte.
Progress: Ek waiting P_i sirf tab stuck hai jab flag[j] && turn==j. Agar P_j CS nahi chahta, flag[j]=false → P_i enter karta hai. Toh ek free CS kabhi blocked nahi hoti. ✅
Bounded waiting: Jab P_j exit karke re-enter karta hai, woh turn=i set karta hai, toh P_i (jiska ab turn==i hai) next mein guaranteed andar jaata hai. Bound = 1. ✅

Figure — Critical section — mutual exclusion, progress, bounded waiting

Hardware help — atomic instructions

Software (Peterson) assume karta hai ki loads/stores atomic aur ordered hain. Real CPUs atomic read-modify-write primitives dete hain taki hume yeh manually na karna pade.

Formula

test_and_set (atomic)

bool test_and_set(bool *target) {
    bool old = *target;   //  yeh do steps
    *target = true;       //  atomically hote hain
    return old;
}

Lock usage:

while (test_and_set(&lock)) ;   // spin until we read 'false'
    CS
lock = false;

✅ Mutual exclusion (atomicity). ❌ Akele bounded waiting nahi — ek process ko baar baar beat kiya ja sakta hai. Bounded waiting restore karne ke liye fair waiting queue add karo.

Worked example: which property fails?

Worked example Is code ko diagnose karo

// both processes
while (lock) ;     // 1. wait if locked
lock = true;       // 2. take lock
   CS
lock = false;

Q: kaun si condition break hoti hai? A: Mutual exclusion! Steps 1 aur 2 atomic nahi hain. Dono while(lock) pass kar sakte hain (lock false), phir dono lock=true set karke saath andar ghus jaate hain. Why this step? Checking aur setting ke beech ka gap race window hai — yahi wajah hai ki test_and_set exist karta hai.

Flashcards

What are the three requirements of a critical-section solution?

Mutual exclusion, progress, bounded waiting.

Define mutual exclusion.

Agar ek process apni CS mein hai, toh koi doosri process us waqt apni CS mein nahi ho sakti.

Define progress.

Jab koi process CS mein nahi hoti, to yeh decision ki agli kaun enter kare indefinitely postpone nahi ho sakta, aur sirf contending (non-remainder) processes participate karti hain.

Define bounded waiting.

Ek finite bound hota hai ki kitni baar doosri processes apni CS enter kar sakti hain jab ek process entry request kar chuki ho lekin usse grant abhi nahi hua.

What is a race condition?

Jab outcome shared data ke concurrent accesses ke order/timing (interleaving) par depend kare.

Why does strict alternation (turn only) fail?

Progress violate hoti hai — ek process ko tab bhi apni turn ka wait karna padta hai jab doosre ko CS nahi chahiye.

Why does the two-flag attempt deadlock?

Dono apna flag true set kar lete hain, phir har ek doosre ka flag clear hone ka forever wait karta hai.

The key trick in Peterson's algorithm?

turn = other set karo (yield karo), taki turn ka last writer wait kare — ties deterministically break hoti hain.

Peterson's wait condition?

while (flag[j] && turn == j);

What does test_and_set return and do?

Atomically lock ki old value return karta hai aur use true set kar deta hai.

Why does plain test_and_set lack bounded waiting?

Ek process ko baar baar overtake kiya ja sakta hai; bound karne ke liye fair queue add karo.

Why is while(lock); lock=true; unsafe?

Check aur set atomic nahi hain — dono processes CS mein saath enter kar sakti hain (ME fail).

Bounded-waiting bound for n processes with FCFS?

n − 1.

Recall Feynman: explain to a 12-year-old

Ek toy hai aur do bacche. Rules taaki koi na roye:

Sirf ek baccha ek waqt mein toy se khelega (mutual exclusion).
Agar koi baccha toy chahta hai aur koi use nahi kar raha, toh use mil jaaye — yeh silly "wait, it's not your turn" wali baat nahi jab turn-baccha room se chala gaya (progress).
Kisi ko forever wait nahi karna padega — kuch rounds ke baad apni turn pakki hai (bounded waiting). Peterson ka trick polite bacche ka rule hai: "Main chahta hoon, lekin tum pehle jao." Kyunki dono kehte hain "tum pehle," jo last mein kehta hai woh actually wait karta hai, aur doosra khelta hai — aur woh clean turns lete hain.

Connections

Race conditions
Peterson's algorithm
Semaphores — in guarantees par built higher-level synchronization
Mutex locks aur Spinlocks
Test-and-Set and Compare-and-Swap — atomic hardware primitives
Deadlock — jo progress entry par rokta hai; broader resource version alag jagah
Starvation and Fairness — jo bounded waiting rokta hai
Producer-Consumer problem / Dining Philosophers — applications