Process Synchronization in OS — Critical Section, Peterson's, Semaphores & Monitors

The Story That Explains Process Synchronization

Background — Why Concurrency Breaks Things

In a modern OS, multiple processes and threads run concurrently. On a uniprocessor, the scheduler rapidly switches between them, giving the illusion of parallelism. On a multicore machine, they may truly execute at the same instant. Both scenarios cause the same problem: the outcome depends on interleaving.

Consider a shared variable counter = 5. Producer wants counter++. Consumer wants counter--. Each compiles into three machine instructions:

🎮 Interactive — Watch the Race Unfold, Step by Step

The Critical-Section Problem

Galvin formalises the problem as follows. Each of n processes has a segment of code called a critical section, in which it accesses shared variables, modifies a common file, or updates shared data structures. When one process is executing in its critical section, no other process may execute in their critical section.

The Three Requirements

A First Attempt — And Why It Fails

Naive students often reach for a simple boolean lock. Let's see why every naive attempt breaks at least one of the three requirements.

Attempt 1 — Strict Alternation using turn

// Shared variable
int turn = 0;   // whose turn is it (0 or 1)

// Process P0                        Process P1
while (true) {                     while (true) {
    while (turn != 0);  // wait       while (turn != 1);
    // CRITICAL SECTION              // CRITICAL SECTION
    turn = 1;                        turn = 0;
    // remainder                     // remainder
}                                    }

Peterson's Solution — The Two-Process Answer

In 1981, Gary Peterson published an elegant software-only solution for two processes. It combines a shared turn variable and a shared flag[] array to signal intent. Peterson's algorithm satisfies all three requirements.

// Shared variables
int  turn;              // whose turn is it
boolean flag[2];        // flag[i] = true means Pi wants in

// Process Pi (i = 0 or 1, j = 1 − i)
while (true) {
    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 AND it's their turn

    // CRITICAL SECTION

    flag[i] = false;                       // (4) I'm done, you can go
    // remainder section
}

🎮 Interactive — Walk Through Peterson's Algorithm

Hardware Support — Atomic Instructions

Modern hardware provides atomic instructions that make locking easy. Two are especially famous.

The key property: these instructions execute indivisibly — the CPU guarantees no other core can interleave with them. This is enough to build a spinlock:

// Spinlock using TestAndSet
do {
    while (TestAndSet(&lock)) ;   // spin until we get the lock
    // CRITICAL SECTION
    lock = false;                  // release
    // remainder section
} while (true);

Semaphores — Dijkstra's Elegant Answer

In 1965, Edsger Dijkstra introduced the semaphore — an integer accessed only through two atomic operations: wait() (P) and signal() (V).

// The two atomic operations
wait(S) {                   signal(S) {
    while (S <= 0) ;              S = S + 1;
    S = S − 1;                }
}

🎮 Interactive — Semaphore Wait/Signal Sequence

semaphore mutex = 1;   // initialised to 1 → binary semaphore

// Every process does:
while (true) {
    wait(mutex);        // decrement; block if 0
    // CRITICAL SECTION
    signal(mutex);      // increment; wake one waiter if any
    // remainder
}

Bounded Buffer (Producer/Consumer) with Semaphores

A producer generates items and places them in a buffer of size N. A consumer removes them. We need three semaphores: mutex for the buffer, empty counting empty slots, full counting filled slots.

semaphore mutex = 1;         // mutual exclusion on buffer
semaphore empty = N;         // initially N empty slots
semaphore full  = 0;         // initially 0 filled slots

// PRODUCER                          // CONSUMER
while (true) {                     while (true) {
    // produce item                    wait(full);        // wait for item
    wait(empty);       // wait slot       wait(mutex);
    wait(mutex);                        // remove item
    // add item to buffer             signal(mutex);
    signal(mutex);                       signal(empty);    // slot free
    signal(full);      // item ready      // consume item
}                                    }

🎮 Interactive — Bounded Buffer of Size 4

Semaphore Pitfalls

Monitors — Language-Level Synchronization

In 1974, Per Brinch Hansen and Tony Hoare proposed the monitor: a high-level construct that automatically enforces mutual exclusion. All shared data and all operations on it are encapsulated in one module; only one process can be active inside a monitor at a time.

🎮 Interactive — Monitor with Condition Variables

Monitor Example — Bounded Buffer

monitor BoundedBuffer {
    int     buffer[N];
    int     count = 0;
    condition notFull, notEmpty;

    procedure insert(int item) {
        while (count == N)
            notFull.wait();          // wait until room in buffer
        buffer[count] = item;
        count++;
        notEmpty.signal();          // wake a consumer
    }

    procedure remove() returns int {
        while (count == 0)
            notEmpty.wait();         // wait until an item exists
        int item = buffer[--count];
        notFull.signal();           // wake a producer
        return item;
    }

    initialization { count = 0; }
}

In Java — Every Object Is a Monitor

public class BoundedBuffer<T> {
    private final Object[] buf;
    private int count = 0;

    public BoundedBuffer(int capacity) { buf = new Object[capacity]; }

    public synchronized void put(T item) throws InterruptedException {
        while (count == buf.length) wait();
        buf[count++] = item;
        notifyAll();
    }

    public synchronized T take() throws InterruptedException {
        while (count == 0) wait();
        T item = (T) buf[--count];
        notifyAll();
        return item;
    }
}

Comparison — Semaphore vs Monitor

Real-World Applications

Golden Rules — Process Synchronization