Process Synchronization — Critical Section, Peterson's, Semaphores & Monitors
Press Next → or use ← → arrow keys
The Story That Explains Synchronization
The withdrawal should have been one indivisible step. Because it wasn't, the result depends on who wrote last — a race condition.
A race condition occurs when the final state of shared data depends on the exact interleaving of concurrent operations. The outcome is non-deterministic — right sometimes, wrong other times — which makes these the hardest bugs to catch.
Watch a Race Condition Happen
counter++ and counter-- each compile to read, modify, write. If
both read the old value (5) before either writes, the second write overwrites the first. One update simply
vanishes. A single shared variable, three machine instructions, and the result is corrupt.
The Critical-Section Problem
Code splits into four regions: an entry section that requests access, the critical section that touches shared data, an exit section that releases, and the remainder. The whole game is making the entry gate guarantee that only one process is in the red block at a time.
Three Requirements of a Correct Solution
A solution that gives mutual exclusion but lets a process wait forever fails bounded waiting. One that's fair but occasionally lets two processes in fails mutual exclusion. A correct answer satisfies all three at once.
A First Attempt — And Why It Fails
// Strict alternation with a shared turn variable int turn = 0; // whose turn is it (0 or 1) // Process P0 // Process P1 while (turn != 0) ; while (turn != 1) ; // CRITICAL SECTION // CRITICAL SECTION turn = 1; turn = 0;
Strict alternation forces P0, P1, P0, P1… forever. If P0 finishes and doesn't want to enter again, P1 still can't proceed until P0 takes another turn — which never comes. A process is blocked by another that isn't even interested. That violates progress.
Peterson's Solution — The Two-Process Answer
// Pi wants in; j = 1 − i flag[i] = true; // (1) I want to enter turn = j; // (2) but I let YOU go first while (flag[j] && turn == j); // (3) wait if other wants in AND it's their turn // ... CRITICAL SECTION ... flag[i] = false; // (4) done — you can go
Each process raises its own flag to signal intent, then politely sets turn to the
other. Whoever set turn last yields — so exactly one proceeds. Peterson's satisfies all
three requirements for two processes, using only shared memory, no special hardware.
Hardware Support — Atomic Instructions
Software locks are fiddly. Modern CPUs provide atomic read-modify-write instructions that can't be interrupted halfway — the hardware foundation every lock is built on.
// Spinlock built on Test-and-Set do { while (TestAndSet(&lock)) ; // spin until we get the lock // ... CRITICAL SECTION ... lock = false; // release } while (true);
Semaphores — Dijkstra's Elegant Answer
A semaphore is just an integer touched only through two atomic operations — wait() (P) and signal() (V).
wait(S) { signal(S) { while (S <= 0) ; S = S + 1; S = S − 1; } }
Binary Semaphore in Action
PA calls wait(mutex): the value drops 1→0 and PA enters. PB calls
wait(mutex) but the value is 0, so it blocks in the queue. When PA calls
signal(mutex), PB is woken and takes the key. Mutual exclusion, guaranteed.
Producer–Consumer With Three Semaphores
semaphore mutex = 1, empty = N, full = 0; // PRODUCER // CONSUMER wait(empty); wait(full); wait(mutex); wait(mutex); // add item // remove item signal(mutex); signal(mutex); signal(full); signal(empty);
mutex guards the buffer (mutual exclusion); empty counts free slots so the producer
blocks when full; full counts items so the consumer blocks when empty. Order matters —
always take the counting semaphore before the mutex, or you can deadlock.
Semaphore Pitfalls
signal() and the resource is never released — every waiter blocks forever.signal() before wait(), or double-waiting, silently breaks mutual exclusion.Semaphores are correct only if every programmer uses them perfectly, everywhere. One misplaced call anywhere in a large codebase can corrupt data or freeze the system — and the bug may appear only once in a million runs. That fragility is exactly what monitors were invented to fix.
Monitors — Language-Level Synchronization
A monitor bundles shared data with the procedures that touch it, and the compiler guarantees
only one process is active inside at a time — you never call wait/signal by hand. Inside, a
condition variable lets a process sleep until a predicate holds (notEmpty.wait())
and be woken by another (notEmpty.signal()). Java's synchronized is a monitor.
Semaphore vs Monitor
| Feature | Semaphore | Monitor |
|---|---|---|
| Level | Low-level OS primitive | High-level language construct |
| Mutual exclusion | Manual — call wait/signal | Automatic — enforced by compiler |
| Signal semantics | Remembered (increments the count) | Lost if no one is waiting |
| Programmer effort | High — easy to bug | Low — structured |
| Error-prone | Yes (deadlock, forgot signal) | Much less so |
| Support | OS syscall / library | Built-in (Java synchronized, C# lock) |
| Best for | Kernel code, resource counting | Application code, structured concurrency |
A semaphore's signal() is remembered — signal now, a later wait() still succeeds.
A condition variable's signal() is stateless — if nobody is waiting, it's lost.
That's why monitor code always re-checks the condition in a while loop, never an if.
Eight Rules for Synchronization
while.From Race Conditions to Reliable Concurrency
From the race condition that starts it all, through the critical-section requirements, Peterson's software solution, atomic hardware, semaphores and monitors — you can reason about any concurrency problem and pick the right tool to keep shared data safe.
Apply these tools to the classic problems — readers–writers and dining philosophers — then study deadlock: how it arises and how to prevent, avoid, or detect it.
🔐 End of tutorial · Press ← to review, or click Restart