The Problem with Low-Level Solutions

Peterson's Solution and hardware instructions like test_and_set work — but they have a serious problem: busy-waiting. A process trying to enter the Critical Section loops continuously, burning CPU cycles while doing absolutely no useful work. On a lightly loaded system this is wasteful; on a heavily loaded system, it actively hurts the throughput of other processes.

More importantly, low-level solutions are error-prone at scale. Writing correct CompareAndSwap loops across a large codebase is fragile. We need a cleaner, higher-level abstraction. That abstraction is the Semaphore.

---

What is a Semaphore?

A Semaphore is a synchronization tool invented by Edsger Dijkstra in 1965. It is an integer variable, accessible only through two atomic, indivisible standard operations:

• wait(S) — also written as P(S) (from Dutch: Probeer, "to test")
• signal(S) — also written as V(S) (from Dutch: Verhoog, "to increment")

No other operation — not direct assignment, not reading — is permitted on a semaphore from outside these two operations. This restriction is what makes them safe.

The Classic (Busy-Wait) Definitions

1// wait(S): Decrement S. If S goes negative, spin until it becomes non-negative.
2wait(S) {
3    while (S <= 0) {
4        // busy-wait: do nothing, keep checking
5    }
6    S--;
7}
8
9// signal(S): Increment S, making a unit of the resource available.
10signal(S) {
11    S++;
12}

Critical Rule: The test of S <= 0 and the decrement S-- inside wait(), and the increment S++ inside signal(), must execute atomically — as single, uninterruptible units. The OS guarantees this through hardware support.

---

Two Types of Semaphores

1. Binary Semaphore (Mutex Lock)

• Integer value is restricted to 0 or 1 only.
• Initialized to 1 (unlocked).
• Provides mutual exclusion: only one process can be in the Critical Section.
• When value is 1 → lock is free. When value is 0 → lock is held.

2. Counting Semaphore

• Integer value ranges over an unrestricted non-negative domain.
• Initialized to the number of available instances of a resource.
• Controls access to a resource with multiple identical instances (e.g., 5 database connections, 3 printers).

---

Usage Pattern 1: Mutual Exclusion

1// Shared: semaphore mutex = 1;    (initialized to 1 = "one slot available")
2
3// Structure for EVERY process Pi:
4do {
5    wait(mutex);        // ENTRY: Acquire the lock. If already 0, spin/block.
6
7    /* ── CRITICAL SECTION ── */
8    /* Access shared resource  */
9
10    signal(mutex);      // EXIT: Release the lock. Increment back to 1.
11
12    /* ── REMAINDER SECTION ── */
13} while (true);

How it works: The semaphore starts at 1. The first process to call wait(mutex) decrements it to 0 and enters the CS. Any subsequent process calling wait(mutex) finds it at 0 and waits. When the first process calls signal(mutex), it goes back to 1, and a waiting process can now enter.

---

Usage Pattern 2: Process Ordering (Synchronization)

Semaphores can also enforce execution order — guaranteeing that Statement $S_2$ in Process $P_2$ only executes after Statement $S_1$ in Process $P_1$ has completed.

1// Shared: semaphore synch = 0;    (initialized to 0 = "event not yet occurred")
2
3// Process P1:                     // Process P2:
4    S1;                                wait(synch);  // Block until P1 signals
5    signal(synch);  // "S1 is done"    S2;           // Now safe to run

If $P_2$ reaches wait(synch) before $P_1$ has executed $S_1$, it blocks (semaphore is 0). When $P_1$ finishes $S_1$ and calls signal(synch), the semaphore becomes 1, and $P_2$ unblocks and runs $S_2$. Order is guaranteed regardless of scheduling.

Blocking Semaphores: Eliminating Busy-Waiting

The busy-wait versions of wait() and signal() are called spinlocks. They are acceptable only in very specific scenarios (very short CS durations, multiprocessor systems where spinning is cheaper than a context switch). For all other cases, we use blocking semaphores.

The Key Insight: Sleep Instead of Spin

Rather than wasting CPU cycles in a loop, a blocked process should relinquish the CPU and be placed in a waiting queue. It is woken up (moved back to the Ready Queue) when the resource becomes available.

The Semaphore Data Structure

1typedef struct {
2    int value;              // The semaphore counter
3    struct process *list;   // Queue of processes waiting on this semaphore
4} semaphore;

Blocking wait() and signal() Definitions

1// wait(S): If no resource is available, block the calling process.
2wait(semaphore *S) {
3    S->value--;
4    if (S->value < 0) {
5        // Add this process to S->list (the waiting queue)
6        add(S->list, current_process);
7        block();    // Suspend the process: remove from CPU, move to Blocked state
8    }
9}
10
11// signal(S): Release a resource; wake up a waiting process if any.
12signal(semaphore *S) {
13    S->value++;
14    if (S->value <= 0) {
15        // There are still processes waiting (value was negative before increment)
16        process *P = remove(S->list);   // Pick one process from the queue
17        wakeup(P);                      // Move P from Blocked to Ready state
18    }
19}

Interpreting the value:

• S->value > 0 → Resources are available. Value = number of available units.
• S->value == 0 → No resources available, no one is waiting.
• S->value < 0 → No resources available, and |S->value| processes are sleeping in the queue.

---

The Deadlock Danger with Semaphores

Semaphores are powerful but require discipline. A common programmer error is acquiring two semaphores in opposite order in different processes:

1// Shared: semaphore S = 1, Q = 1;
2
3// Process P0:                  // Process P1:
4    wait(S);                        wait(Q);
5    wait(Q);                        wait(S);   // ← DEADLOCK risk here
6    /* ... CS ... */                /* ... CS ... */
7    signal(S);                      signal(Q);
8    signal(Q);                      signal(S);

How deadlock happens:

Both processes are now permanently blocked, each holding one semaphore and waiting for the other's. This is a deadlock. Neither can proceed. Neither can release what the other needs.

The fix: Always acquire semaphores in the same, consistent global order across all processes.

---

Monitors: Synchronization Without the Risk

Semaphores work, but they put the burden of correctness entirely on the programmer. A single misplaced wait() or forgotten signal() causes a deadlock or race condition that is nearly impossible to debug. For complex systems, we need a safer abstraction: the Monitor.

What is a Monitor?

A Monitor is a high-level programming language construct (an Abstract Data Type) that encapsulates:

1. Shared data — the variables that need protection.
2. Procedures — the only functions through which the shared data can be accessed.
3. Synchronization — automatic mutual exclusion enforced by the language/runtime.

The golden rule of monitors: Only one process may be active (executing inside a monitor procedure) at any given time. This is enforced automatically by the compiler — the programmer does not write any lock/unlock code.

1monitor BankAccount {
2    // Shared data — only accessible via the procedures below
3    int balance = 0;
4
5    // Procedure: only one process can run this at a time — automatically
6    procedure deposit(int amount) {
7        balance = balance + amount;
8    }
9
10    procedure withdraw(int amount) {
11        balance = balance - amount;
12    }
13}

Any process that calls deposit() or withdraw() is automatically serialized. No semaphores, no wait(), no signal() needed for basic mutual exclusion.

---

Condition Variables: Waiting Inside a Monitor

Sometimes a process inside a monitor needs to wait for a specific condition before continuing (e.g., waiting for a buffer to have items). Since it holds the monitor lock, it can't just spin — that would block everyone else forever. Condition variables solve this.

A condition variable x supports exactly two operations:

1x.wait();
2// Suspends the calling process.
3// Automatically RELEASES the monitor lock so others can enter.
4// The process is placed in a queue associated with condition x.
5
6x.signal();
7// Resumes exactly ONE process waiting on condition x.
8// If no process is waiting, this is a NO-OP (nothing happens — unlike signal() on a semaphore!).
9// The resumed process must wait until the signaling process exits the monitor.

---

Semaphore vs. Monitor: A Comparison