The Critical Section Problem & Semaphores

When multiple processes share common storage (RAM, files, global variables) and access it concurrently, the final outcome depends on the exact execution order of interleaving instructions. This bug is a Race Condition.

To prevent race conditions, the code region that accesses shared resources is designated as the Critical Section (CS). A valid solution to the Critical Section problem MUST satisfy three mandatory criteria:

1. Mutual Exclusion (Safety): If process Pᵢ is executing in its critical section, no other processes can be executing in their critical sections.

2. Progress (Liveness): If no process is in its CS and some processes wish to enter, only processes not in their remainder sections can participate in deciding who enters next, and this selection cannot be postponed indefinitely.

3. Bounded Waiting (Fairness/Starvation-freedom): There must exist a bound on the number of times other processes are allowed to enter their critical sections after a process has requested entry, preventing starvation.

Can software alone guarantee mutual exclusion without special hardware instructions? In 1981, Gary L. Peterson devised a classic algorithmic solution for two processes, alternating between their critical and remainder sections.

Consider two processes, P_0 and P_1. Let the current process be P_i and the other process be P_j (where j = 1 - i). Peterson's algorithm shares two variables:

• boolean flag[2]; (where flag[i] = true indicates that process P_i is ready to enter its critical section).

• int turn; (indicates whose turn it is to enter the critical section).

The Algorithm Structure for Process P_i: ``c flag[i] = true; // 1. Declare intent: I want to enter turn = j; // 2. Be polite: Offer priority to the other process while (flag[j] && turn == j); // 3. Busy-wait while other wants in AND has turn / CRITICAL SECTION / flag[i] = false; // 4. Exit: Release claim / REMAINDER SECTION / ``

Proof of Correctness:

1. Mutual Exclusion Guaranteed: For both processes to be in the CS simultaneously, both flag[0] and flag[1] must be true, and turn 0 AND turn 1 must hold simultaneously. Since turn is a scalar variable that can only hold one value at a time, at least one process was blocked in the while loop.

2. Progress Guaranteed: If P_j is not in its CS and has no desire to enter (flag[j] == false), the while condition for P_i immediately evaluates to false, allowing P_i to enter without delay. If both try to enter concurrently, turn will be set to either 0 or 1 by whichever write executes last, permitting the other process to enter immediately.

3. Bounded Waiting Guaranteed: A process waits at most one critical section entry of the other process. Once P_j exits, it resets flag[j] = false, freeing P_i.

While Peterson's algorithm works for two processes, scaling software synchronization to N processes introduces significant complexity and CPU-burning busy-waiting. In 1965, Edsger Dijkstra introduced the Semaphore.

A semaphore S is an integer variable that, apart from initialization, is accessed only through two standard atomic hardware/kernel operations: wait() (P-operation) and signal() (V-operation).

Atomic Definition of wait(S): ``c wait(S) { S = S - 1; if (S < 0) { // add this process to semaphore's waiting queue block(); } } ``

Atomic Definition of signal(S): ``c signal(S) { S = S + 1; if (S <= 0) { // remove a process P from the waiting queue wakeup(P); } } ``

Crucially, the modification to S and the test must execute atomically (uninterruptibly) — guaranteed by the OS kernel disabling interrupts on uniprocessors or using hardware spinlocks (test_and_set) on multiprocessors.