Process Synchronization in Operating Systems: Semaphores, Critical Sections and Worked Examples

A concurrent program can be correct inside each process and still produce a wrong result. The scheduler may interleave ordinary read, compute and write steps in an unsafe order. Two processes updating a shared x = 5 can leave it holding 10, when the only defensible answers are 18 and 14. Getting that right takes three things: a rule for what a correct critical section must guarantee, a primitive that enforces the rule, and the arithmetic to predict a semaphore value after an exact schedule. All three sit in the Operating Systems block of GATE CS preparation.

1. Why process synchronization is needed

Concurrency is overlapping progress, not necessarily simultaneous execution; one CPU can interleave processes. Shared state can make the result timing-dependent. This defect is a race condition, and code accessing the shared resource is a critical section.

Let shared integer x = 5. Process P1 runs x = x + 4, while P2 runs x = x * 2. Each statement expands into read, compute and write steps. Suppose P1 reads 5 and computes 9; P2 reads 5 and computes 10; P1 writes 9; then P2 writes 10. The final value is 10, so P1's update is lost. If P1 writes last, 9 is possible.

The serial outcomes are (5 + 4) * 2 = 18 for P1 then P2, and (5 * 2) + 4 = 14 for P2 then P1. Neither is uniquely correct. The compound updates need a defined atomic ordering.

2. The critical-section contract: safety and progress

Code using shared data follows entry section -> critical section -> exit section -> remainder section. A solution must satisfy three requirements:

1. Mutual exclusion: at most one process is in the critical section. This is the safety property.

2. Progress: when no process is inside the critical section, the choice of who enters next cannot be postponed indefinitely, and a process that does not want to enter takes no part in that choice.

3. Bounded waiting: after a request, there is a bound on how many times other processes may enter first. Progress and bounded waiting are the liveness properties.

Peterson's two-process pattern is an exam model under atomic reads and writes plus sequential consistency. P0 sets flag[0] = true, sets turn = 1, then waits while flag[1] && turn == 1; P1 is symmetric. Do not treat it as production application code. Atomic hardware instructions such as test-and-set or compare-and-swap can implement locks, while ordinary check-then-set is racy. Atomicity alone does not guarantee bounded waiting, because queueing policy decides who is woken. The three-requirement argument for Peterson's is worked line by line in Process Synchronization and Semaphores: A Worked Trace.

3. Choosing among mutexes, spinlocks, semaphores and monitors

Choose by what you are counting: one exclusive holder means a mutex, N interchangeable units such as three buffer slots mean a counting semaphore, and shared state whose operations and wait predicates should travel together means a monitor. A spinlock pays only when blocking would cost more than the wait, so short uncontended sections on a multiprocessor, never a wait on I/O. A binary semaphore has values 0 and 1, but does not necessarily carry mutex ownership semantics. Here wait(S) atomically acquires a permit or blocks; signal(S) atomically releases one or wakes a waiter. Two counting conventions are in use. Dijkstra's original wait decrements first, so the value can go negative and its magnitude is the number of blocked processes. The non-negative convention stops at 0 and parks the caller in a queue instead, and every trace here uses that form. Read the initial value from the resource rather than the convention: a capacity-3 buffer starts at mutex = 1, empty = 3 and full = 0 either way.

4. Worked example: bounded buffer with exact semaphore values

Take a buffer of capacity 3, initially [_, _, _], with empty = 3, full = 0 and mutex = 1. A producer uses wait(empty); wait(mutex); insert item; signal(mutex); signal(full). A consumer uses wait(full); wait(mutex); remove item; signal(mutex); signal(empty). The counting semaphores enforce capacity and availability. The mutex protects the buffer data structure while it changes.

Trace the completed operations:

• Producer P_A inserts A: [A, _, _], so (empty, full, mutex) = (2, 1, 1).

• P_B inserts B: [A, B, _], so the state is (1, 2, 1).

• P_C inserts C: [A, B, C], so the state is (0, 3, 1).

• P_D calls wait(empty) and blocks because empty = 0. It has not entered or acquired mutex.

Consumer C_1 now takes one full permit, so full changes from 3 to 2. It acquires mutex, removes A, releases mutex, then signals empty, changing empty from 0 to 1. The waiting P_D claims that permit, so empty returns to 0. It then acquires mutex, inserts D, releases mutex and signals full, taking full from 2 to 3.

The final buffer is [B, C, D] and (empty, full, mutex) = (0, 3, 1). Across the consume-then-resume sequence, the permit flow is exactly full: 3 -> 2 -> 3 and empty: 0 -> 1 -> 0.

5. Classical synchronization problems and what each teaches

In readers-writers, every update of readCount is protected by a small counter mutex. Start with readCount = 0. R1 sets readCount = 1; the first reader locks the shared resource against writers. R2 sets readCount = 2 and reads concurrently. Writer W1 waits. When R1 leaves, readCount = 1, so W1 still waits. When R2 leaves, readCount = 0; the last reader releases the resource, and W1 may write. Under reader preference, a continuing stream of new readers can starve writers.

Producer-consumer teaches capacity plus mutual exclusion. Readers-writers teaches controlled sharing plus fairness. Dining philosophers exposes circular resource acquisition. With philosophers P0 to P4 and forks F0 to F4, deadlock can arise if every Pi holds Fi and waits for F(i+1) mod 5. Two remedies are to let at most four philosophers compete at once, or impose one global fork order and always acquire the lower-numbered fork first.

6. Deadlock, starvation, busy waiting and semaphore traps

Common errors include wrong initial values, reversing wait and signal, missing a signal on one path, and assuming unstated fairness. If a producer waits for mutex before empty, it can hold mutex while blocked on a full buffer. The consumer cannot acquire mutex to remove an item and free a slot, so the system deadlocks.

7. How GATE-style questions and interviews test synchronization

IIT Guwahati's GATE 2026 CS syllabus lists concurrency and synchronization, followed by deadlock, inside Operating System. The paper runs MCQ, MSQ and NAT formats, so one trace can be asked three ways: pick the single reachable final value, pick every reachable final value, or type in the semaphore value after a stated schedule. For the marks split and what has actually been asked, work through the official GATE 2026 question papers and answer keys.

Practice usually asks you to:

1. enumerate possible final values under an interleaving;

2. test mutual exclusion, progress and bounded waiting;

3. calculate semaphore or buffer states after an exact schedule;

4. detect deadlock or starvation from resource acquisition.

For a quick check, after A, B and C fill the capacity-3 buffer, a fourth producer cannot pass wait(empty) because empty = 0. The KnowledgeGate practice bank carries over 200 questions on process synchronization. Place the topic inside the wider Operating Systems for GATE map, then attempt it against the clock in the GATE Test Series. In an interview, state the invariant before you name a primitive: at most one thread may mutate the buffer, and a producer blocks while empty = 0. Then pick the mutex and counting semaphores that enforce it.

8. Short version and the next step

Use five checks: identify shared state, isolate the smallest critical section, state the invariant, initialise each primitive from the resource meaning, and test hostile interleavings plus failure paths. Here, an unprotected update can finish at 10, not either serial result 18 or 14. The capacity-3 buffer finishes as [B, C, D] with (empty, full, mutex) = (0, 3, 1). If you want that reasoning drilled across the whole GATE CS syllabus, the plan already built is GATE Guidance by Sanchit Sir.