Critical section — mutual exclusion, progress, bounded waiting

WHAT is a critical section?

Definition Critical Section (CS)

A critical section is the segment of code where a process/thread accesses a shared resource (shared variable, file, device) that must not be accessed by more than one process at the same time.

Each process has the structure:

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? Because concurrent unsynchronized access creates a race condition — the final result depends on the unlucky interleaving of instructions.

Worked example The classic race

Two threads run count++ on shared count (initially 5). At the machine level count++ is three instructions:

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

A bad 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

Two increments, but count ends at 6, not 7. One update was lost. Why this step? Because the load/modify/store of B sneaked in between A's load and store — both read the stale 5.

The THREE requirements (WHY each exists)

DERIVING a correct lock from scratch

We build up, fixing each broken attempt (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 holds exactly one value.
❌ Progress fails: if it's P0's turn but P0 is busy in its remainder (not wanting CS), P1 is blocked even though CS is free. 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 holds.
❌ Deadlock: both set flag = true simultaneously, then both spin forever. Progress fails.

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

Formula Peterson's Algorithm (2 processes)

Derived by merging the good half of each attempt: keep an intent flag AND a turn that breaks ties by yielding.

// 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

Sketch proof of correctness of Peterson's:

Mutual exclusion: For both to be inside, both passed the while. P_i passed means flag[j]==false OR turn==i. Since flag[i]=flag[j]=true (both want in), it reduces to turn==i for P_i and turn==j for P_j — impossible, turn is one value. ⇒ both can't enter.
Progress: A waiting P_i is stuck only while flag[j] && turn==j. If P_j doesn't want CS, flag[j]=false → P_i enters. So a free CS is never blocked. ✅
Bounded waiting: When P_j exits and re-enters, it sets turn=i, so P_i (whose turn==i now) is guaranteed in next. Bound = 1. ✅

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

Hardware help — atomic instructions

Software (Peterson) assumes loads/stores are atomic and ordered. Real CPUs give atomic read-modify-write primitives so we don't have to.

Formula

test_and_set (atomic)

bool test_and_set(bool *target) {
    bool old = *target;   //  these two steps
    *target = true;       //  happen atomically
    return old;
}

Lock usage:

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

✅ Mutual exclusion (atomicity). ❌ No bounded waiting by itself — a process can be repeatedly beaten. Add a fair waiting queue to restore bounded waiting.

Worked example: which property fails?

Worked example Diagnose this code

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

Q: which condition breaks? A: Mutual exclusion! Steps 1 and 2 are not atomic. Both can pass while(lock) (lock false), then both set lock=true and enter together. Why this step? The gap between checking and setting is the race window — the whole reason test_and_set exists.

Flashcards

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

Mutual exclusion, progress, bounded waiting.

Define mutual exclusion.

If one process is in its CS, no other process may be in its CS at the same time.

Define progress.

When no process is in its CS, the decision of who enters next cannot be postponed indefinitely, and only contending (non-remainder) processes participate.

Define bounded waiting.

There is a finite bound on how many times other processes enter their CS after a process requests entry but before it is granted.

What is a race condition?

When the outcome depends on the order/timing (interleaving) of concurrent accesses to shared data.

Why does strict alternation (turn only) fail?

It violates progress — a process must wait its turn even when the other doesn't want the CS.

Why does the two-flag attempt deadlock?

Both set their flag true, then each waits forever for the other's flag to clear.

The key trick in Peterson's algorithm?

Set turn = other (yield), so the last writer of turn waits — breaking ties deterministically.

Peterson's wait condition?

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

What does test_and_set return and do?

Atomically returns the old value of the lock and sets it to true.

Why does plain test_and_set lack bounded waiting?

A process can be repeatedly overtaken; add a fair queue to bound waiting.

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

Check and set are not atomic — both processes can enter the CS together (ME fails).

Bounded-waiting bound for n processes with FCFS?

n − 1.

Recall Feynman: explain to a 12-year-old

There's one toy and two kids. Rules so nobody cries:

Only one kid plays with the toy at a time (mutual exclusion).
If a kid wants the toy and nobody is using it, they get it — no silly "wait, it's not your turn" when the turn-kid left the room (progress).
Nobody has to wait forever — after a few rounds it's your turn for sure (bounded waiting). Peterson's trick is the polite kid rule: "I want it, but you go first." Since both say "you first," whoever says it last actually waits, and the other plays — and they take clean turns.

Connections

Race conditions
Peterson's algorithm
Semaphores — higher-level synchronization built on these guarantees
Mutex locks and Spinlocks
Test-and-Set and Compare-and-Swap — atomic hardware primitives
Deadlock — what progress prevents at entry; broader resource version elsewhere
Starvation and Fairness — what bounded waiting prevents
Producer-Consumer problem / Dining Philosophers — applications

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, critical section matlab code ka woh hissa jahan tum koi shared cheez (shared variable, file) ko touch karte ho. Agar do threads ek saath usko chhute hain bina rule ke, to race condition ban jaati hai — jaise count++ do baar chala par result sirf ek baar badha, kyun ki dono ne purana (stale) value padh liya. Isliye humein synchronization chahiye.

Iske liye teen rules zaroori hain. Mutual exclusion: ek time pe sirf ek hi process andar (safety). Progress: agar andar koi nahi hai aur kisi ko jaana hai, to bina wajah ke rok nahi sakte — door free hai to kisi na kisi ko milna chahiye (liveness). Bounded waiting: koi process hamesha ke liye wait na kare, dusre log limited baar hi aage ja sakte hain (fairness). Yaad rakho: Me, Please, Briefly.

Solution banate waqt galtiyan samjho: sirf turn use karo to strict alternation ban jaata hai aur progress fail (agar dusra busy nahi hai tab bhi tum atke ho). Sirf flag use karo to dono ek saath flag true kar ke deadlock. Peterson's algorithm dono ka achha part jodta hai: flag[i]=true (mujhe jaana hai) phir turn=j (par pehle tum jao). Trick yeh hai ki jo turn last me likhta hai wahi wait karta hai — isliye tie hamesha clean tut-ta hai, koi deadlock nahi, mutual exclusion bhi pakka.

Real CPUs me hum test_and_set jaisa atomic instruction use karte hain taaki "check karo aur set karo" ek hi step me ho — warna while(lock); lock=true; me beech ka gap me dono ghus jaate hain. Exam me yaad rakho: test_and_set akela bounded waiting nahi deta, uske liye ek fair queue add karni padti hai. Bas yeh teen rules aur Peterson ka logic clear ho jaye, to topic ho gaya solid.

Test yourself — Operating Systems

Connections