Why Classic Problems?

These three problems are not just textbook exercises. They are abstract models of real synchronization challenges:

Mastering these means you understand the pattern, not just the code. Any synchronization problem you encounter in practice will map to one of these three.

---

Problem 1: The Bounded-Buffer (Producer/Consumer) Problem

Setup

A fixed-size buffer (pool) of n slots sits between a Producer process and a Consumer process:

• The Producer generates items and places them into the buffer.
• The Consumer picks items from the buffer and uses them.

The constraints:

1. The Producer must wait if the buffer is full (no empty slots to fill).
2. The Consumer must wait if the buffer is empty (no items to consume).
3. Only one process can manipulate the buffer at a time (mutual exclusion).

The Three Semaphores

1semaphore mutex = 1;    // Binary semaphore: ensures mutual exclusion on buffer access
2semaphore empty = n;    // Counting semaphore: counts empty slots. Init = n (all slots empty)
3semaphore full  = 0;    // Counting semaphore: counts full slots. Init = 0 (buffer starts empty)

Intuition:

• mutex is the buffer's lock — only one hand in the cookie jar at a time.
• empty tracks "how many spots can the Producer still fill?" Starts at n.
• full tracks "how many items can the Consumer take?" Starts at 0.

Full Implementation

1// ── PRODUCER PROCESS ────────────────────────────────────────────────────────
2do {
3    /* ... produce an item into 'next_produced' ... */
4
5    wait(empty);        // Decrement empty slots. If 0, BLOCK — buffer is full.
6    wait(mutex);        // Acquire exclusive access to the buffer.
7
8    /* ── CRITICAL SECTION ──────────────────────── */
9    add next_produced to buffer;
10    /* ─────────────────────────────────────────── */
11
12    signal(mutex);      // Release buffer access.
13    signal(full);       // Increment full slots — Consumer can now consume one more.
14
15} while (true);
16
17
18// ── CONSUMER PROCESS ────────────────────────────────────────────────────────
19do {
20    wait(full);         // Decrement full slots. If 0, BLOCK — buffer is empty.
21    wait(mutex);        // Acquire exclusive access to the buffer.
22
23    /* ── CRITICAL SECTION ──────────────────────── */
24    remove an item from buffer into 'next_consumed';
25    /* ─────────────────────────────────────────── */
26
27    signal(mutex);      // Release buffer access.
28    signal(empty);      // Increment empty slots — Producer can now produce one more.
29
30    /* ... consume the item in 'next_consumed' ... */
31
32} while (true);

The Buffer as a Circular Queue

Critical exam point — Order of wait() calls matters! In the Producer, wait(empty) must come before wait(mutex). If you reverse the order (acquire mutex first, then wait for empty), the Producer could hold the mutex while blocking on empty. The Consumer would then block on wait(mutex) trying to free up a slot — deadlock.

Problem 2: The Readers-Writers Problem

Setup

A shared data object (imagine a database table) is accessed by two classes of processes:

• Readers — only read data; they don't modify it.
• Writers — modify data; they need exclusive access.

The key insight: Multiple readers can safely read simultaneously (reading is non-destructive), but a writer must have completely exclusive access — no other reader or writer may be active while a writer is writing.

First Readers-Writers Problem (Readers Priority)

In this version, if a reader is in the CS, new readers arriving can immediately join — writers must wait until all readers are done.

Variables:

1semaphore rw_mutex = 1;   // Exclusive access for writers (and the first/last reader)
2semaphore mutex   = 1;    // Protects read_count — only one thread updates it at a time
3int       read_count = 0; // How many readers are currently reading

Full Implementation:

1// ── READER PROCESS ───────────────────────────────────────────────────────────
2do {
3    // ENTRY
4    wait(mutex);            // Protect read_count modification
5    read_count++;
6    if (read_count == 1) {  // First reader? Grab the rw_mutex to block writers.
7        wait(rw_mutex);
8    }
9    signal(mutex);          // Release read_count lock
10
11    /* ── READ the shared data ── */
12
13    // EXIT
14    wait(mutex);            // Protect read_count modification
15    read_count--;
16    if (read_count == 0) {  // Last reader? Release rw_mutex so writers can proceed.
17        signal(rw_mutex);
18    }
19    signal(mutex);
20
21} while (true);
22
23
24// ── WRITER PROCESS ───────────────────────────────────────────────────────────
25do {
26    wait(rw_mutex);         // Request exclusive access. Block until ALL readers are done.
27
28    /* ── WRITE to the shared data ── */
29
30    signal(rw_mutex);       // Release exclusive access.
31
32} while (true);

The Logic — Why the First/Last Reader Pattern?

• The first reader to arrive locks rw_mutex — blocking any writer from starting.
• All subsequent readers can freely join without touching rw_mutex (they just increment read_count).
• When the last reader exits, it releases rw_mutex — allowing a waiting writer to proceed.
• This is elegant: the reader group collectively holds one "team lock."

The Starvation Risk: If readers arrive in a continuous stream, read_count never drops to 0, rw_mutex is never released, and writers wait indefinitely. This is the classic starvation of writers in the First RW Problem.

Second Readers-Writers Problem (Writers Priority): The roles are reversed — once a writer requests access, no new readers may start. Existing readers finish, and the writer gets in. This prevents writer starvation but can starve readers instead.

Modern Solution — Reader-Writer Locks (RWLocks): Modern operating systems (POSIX, Linux, Windows) implement this pattern natively:

1pthread_rwlock_t rwlock;
2pthread_rwlock_rdlock(&rwlock);    // Acquire read lock (multiple allowed)
3pthread_rwlock_wrlock(&rwlock);    // Acquire write lock (exclusive)
4pthread_rwlock_unlock(&rwlock);    // Release either lock

Problem 3: The Dining Philosophers Problem

The Setup

Five philosophers sit around a circular table. Between each adjacent pair of philosophers lies a single fork (chopstick). To eat, a philosopher needs both forks — the one on their left and the one on their right. A philosopher alternates between thinking (not using any forks) and eating (holding both adjacent forks).

The challenge: Design a solution where no philosopher starves and no deadlock occurs.

---

The Naive (Deadlock-Prone) Approach

The obvious approach: each philosopher picks up the left fork first, then the right fork.

1// Shared: semaphore fork[5] = {1, 1, 1, 1, 1};  (all forks available)
2
3// Philosopher i:
4do {
5    wait(fork[i]);          // Pick up LEFT fork
6    wait(fork[(i+1) % 5]); // Pick up RIGHT fork
7
8    /* ... EAT ... */
9
10    signal(fork[i]);          // Put down LEFT fork
11    signal(fork[(i+1) % 5]); // Put down RIGHT fork
12
13    /* ... THINK ... */
14} while (true);

The Deadlock Scenario: Suppose all 5 philosophers get hungry simultaneously. Each picks up their left fork at the same time. Now each philosopher holds one fork and is waiting for the right fork — which is held by the next philosopher. A circular wait has formed:

P0 waits for Fork 1 (held by P1) → P1 waits for Fork 2 (held by P2) → P2 waits for Fork 3 (held by P3) → P3 waits for Fork 4 (held by P4) → P4 waits for Fork 0 (held by P0)

Deadlock. All five philosophers will starve to death.

---

Semaphore-Based Fixes

Fix 1: Allow at most 4 Philosophers to sit simultaneously. Use a counting semaphore initialized to 4. Only 4 philosophers can "sit down" at any time. With only 4 philosophers and 5 forks, at least one philosopher can always acquire both forks.

1semaphore seats = 4;   // Only 4 can try to eat at once
2
3// Philosopher i:
4do {
5    wait(seats);                   // Must get a seat first
6    wait(fork[i]);
7    wait(fork[(i+1) % 5]);
8    /* ... EAT ... */
9    signal(fork[(i+1) % 5]);
10    signal(fork[i]);
11    signal(seats);                 // Free up a seat
12    /* ... THINK ... */
13} while (true);

Fix 2: Asymmetric Solution.

• Odd-numbered philosophers pick left fork first, then right.
• Even-numbered philosophers pick right fork first, then left. This breaks the symmetry that causes circular wait.

---

The Correct Monitor Solution (Tanenbaum's State Machine)

The most elegant and exam-canonical solution uses a monitor to track each philosopher's state explicitly.

1monitor DiningPhilosophers {
2
3    // State machine: each philosopher is in one of 3 states
4    enum { THINKING, HUNGRY, EATING } state[5];
5
6    // Condition variable for each philosopher to wait on
7    condition self[5];
8
9    // ── INITIALIZATION ──────────────────────────────────────────────────────
10    // Called once at startup
11    initialization_code() {
12        for (int i = 0; i < 5; i++) {
13            state[i] = THINKING;
14        }
15    }
16
17    // ── PICKUP: Called when Philosopher i wants to eat ───────────────────────
18    procedure pickup(int i) {
19        state[i] = HUNGRY;          // Announce: "I am hungry, I want to eat."
20        test(i);                     // Check if I can eat right now.
21        if (state[i] != EATING) {   // If test() didn't set me to EATING...
22            self[i].wait();         // ...I must wait until a neighbor wakes me up.
23        }
24    }
25
26    // ── PUTDOWN: Called when Philosopher i finishes eating ───────────────────
27    procedure putdown(int i) {
28        state[i] = THINKING;        // I am done eating; I'm back to thinking.
29
30        // Check if my LEFT neighbor (i-1) can now eat
31        test((i + 4) % 5);
32
33        // Check if my RIGHT neighbor (i+1) can now eat
34        test((i + 1) % 5);
35    }
36
37    // ── TEST: Check if Philosopher i can start eating ────────────────────────
38    procedure test(int i) {
39        // I can eat only if:
40        //  1. I am HUNGRY (I actually want to eat)
41        //  2. My LEFT neighbor is NOT eating
42        //  3. My RIGHT neighbor is NOT eating
43        if (state[i] == HUNGRY &&
44            state[(i + 4) % 5] != EATING &&
45            state[(i + 1) % 5] != EATING)
46        {
47            state[i] = EATING;      // Grant permission to eat.
48            self[i].signal();       // Wake up philosopher i if it's sleeping on self[i].
49        }
50    }
51
52} // end monitor
53
54
55// ── PHILOSOPHER i's MAIN LOOP (outside the monitor) ─────────────────────────
56do {
57    /* ... THINK ... */
58
59    DiningPhilosophers.pickup(i);
60
61    /* ... EAT ... */
62
63    DiningPhilosophers.putdown(i);
64
65} while (true);

Why this solution is correct:

• No Deadlock: A philosopher only eats if both neighbors are not eating. The state check prevents the circular wait condition from ever forming.
• No Starvation (of a specific type): If a philosopher is HUNGRY, one of their neighbors will eventually call putdown() and then call test(i) to wake them. However, note that this solution could still theoretically allow a philosopher to starve if both neighbors are constantly alternating eating — a more sophisticated solution would add an aging mechanism.
• Mutual Exclusion: The monitor guarantees only one procedure executes at a time, so state[] is never modified by two philosophers simultaneously.