Semaphore and the Dining-Philosophers Solution Using Monitors

A semaphore is a classic synchronization primitive used in operating systems to coordinate concurrent activities and protect critical sections.2 Conceptually, a semaphore is an integer-like abstract object manipulated only through atomic operations such as $wait$ and $signal$ (also written as $P$ and $V$), where $wait$ may block a process when the resource is unavailable, and $signal$ may wake a blocked process when the resource becomes available.2

Semaphores are widely used for two related purposes: mutual exclusion and coordination. A binary semaphore behaves much like a mutex and can enforce one-at-a-time access, while a counting semaphore tracks multiple identical resources.2 However, semaphores are low-level and error-prone because they are often global objects separate from the shared state they protect; incorrect ordering of $wait$/$signal$ calls can lead to deadlock, missed intent, or difficult-to-debug race conditions.

A monitor is a higher-level abstraction that groups shared data, procedures, and synchronization rules together.2 Inside a monitor, only one thread is active at a time, which gives implicit mutual exclusion. To express waiting for logical conditions, monitors are extended with condition variables such as $x.wait()$ and $x.signal()$.2 This distinction matters: a condition variable does not “remember” a prior signal if no thread was waiting, unlike a semaphore operation that changes stored state.2

The Dining Philosophers problem illustrates why synchronization design matters.2 Five philosophers alternate between thinking and eating, and each needs two adjacent chopsticks to eat. A naive strategy can create circular waiting, causing deadlock if each philosopher picks up one chopstick and waits forever for the other. The monitor-based solution avoids this by allowing a philosopher to enter the eating state only when both neighbors are not eating, using per-philosopher condition variables and shared state transitions.2

Footnotes

1. Semaphore (programming) - Wikipedia - Overview of semaphore semantics, wait/signal behavior, and synchronization role. ↩ ↩² ↩³

2. Semaphores in Process Synchronization - GeeksforGeeks - Introductory explanation of semaphores in process synchronization. ↩

3. Lecture 6: Semaphores and Monitors - UC San Diego - Operating-systems lecture notes comparing locks, semaphores, monitors, and condition variables. ↩ ↩² ↩³ ↩⁴ ↩⁵

4. Dining Philosophers, Monitors, and Condition Variables - University of Colorado Boulder - Detailed lecture notes with monitor-based Dining Philosophers pseudocode and condition-variable semantics. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶

5. Condition Variables & Monitors - Virginia Tech - Explanation of condition-variable semantics, monitor behavior, and fairness considerations. ↩

6. Lecture 4: Monitors - Dublin City University - Notes clarifying differences between monitor condition variables and semaphores. ↩

7. Dining-Philosophers Solution Using Monitors - GeeksforGeeks - Summary of the monitor solution, philosopher states, and deadlock-avoidance logic. ↩ ↩² ↩³

What a Semaphore Is

Formally, a semaphore supports two atomic operations:2

$$wait(S): \begin{cases} S \leftarrow S - 1 \\ \text{if resource unavailable, block caller} \end{cases}$$ $$signal(S): \begin{cases} S \leftarrow S + 1 \\ \text{if threads are waiting, wake one} \end{cases}$$

In operating-systems teaching material, semaphores are described as high-level synchronization mechanisms that block waiting threads instead of forcing them to spin continuously, making them more suitable than raw spinlocks for longer waits. They can be used to solve bounded-buffer, readers-writers, and signaling problems, but they have drawbacks: they mix mutual exclusion and scheduling logic, are not naturally tied to the protected data, and are therefore more prone to programmer mistakes.

A monitor improves structure by bundling the state and the operations on that state into one protected module.2 Inside a monitor, synchronization becomes state-oriented: instead of manually counting resources everywhere, code checks whether a condition on shared state is true, and waits if it is not.2 This approach is especially natural for the Dining Philosophers problem because the relevant condition is not “how many chopsticks exist,” but “whether both neighboring philosophers are not eating.”2

Footnotes

1. Semaphore (programming) - Wikipedia - Overview of semaphore semantics, wait/signal behavior, and synchronization role. ↩

2. Lecture 6: Semaphores and Monitors - UC San Diego - Operating-systems lecture notes comparing locks, semaphores, monitors, and condition variables. ↩ ↩² ↩³ ↩⁴

3. Dining Philosophers, Monitors, and Condition Variables - University of Colorado Boulder - Detailed lecture notes with monitor-based Dining Philosophers pseudocode and condition-variable semantics. ↩ ↩² ↩³

4. Lecture 4: Monitors - Dublin City University - Notes clarifying differences between monitor condition variables and semaphores. ↩

5. Dining-Philosophers Solution Using Monitors - GeeksforGeeks - Summary of the monitor solution, philosopher states, and deadlock-avoidance logic. ↩

Why the Dining Philosophers Problem Is Hard

The problem models a system of competing processes sharing adjacent limited resources. Each philosopher alternates between thinking and eating, but to eat, philosopher $i$ must hold both the left and right chopsticks. The correctness requirements are:

1. Safety: adjacent philosophers must not eat simultaneously.2
2. Deadlock freedom: the system must avoid circular wait where everyone holds one resource and waits forever.
3. Starvation freedom: no philosopher should be postponed indefinitely under a fair scheduling discipline.

A naive semaphore-like resource acquisition pattern can fail because each philosopher may independently grab one chopstick first, satisfying hold-and-wait and circular-wait conditions. The monitor solution instead reasons over philosopher states:

• $THINKING$
• $HUNGRY$
• $EATING$2

The key invariant is that philosopher $i$ may enter $EATING$ only if both neighbors are not $EATING$.2 This eliminates the need to model chopsticks explicitly; the state array is sufficient because a philosopher eating implies both adjacent chopsticks are logically in use.2

Footnotes

1. Dining-Philosophers Solution Using Monitors - GeeksforGeeks - Summary of the monitor solution, philosopher states, and deadlock-avoidance logic. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷

2. Dining Philosophers, Monitors, and Condition Variables - University of Colorado Boulder - Detailed lecture notes with monitor-based Dining Philosophers pseudocode and condition-variable semantics. ↩ ↩² ↩³ ↩⁴

3. CS170 Lecture Notes -- Thinking and Eating - UC Santa Barbara - Notes explaining the state-based monitor solution and why explicit chopstick tracking is unnecessary. ↩

Monitor Pseudocode

The textbook-style monitor solution is commonly written as follows:2

1monitor DiningPhilosophers
2{
3    enum { THINKING, HUNGRY, EATING } state[5];
4    condition self[5];
5
6    int left(int i)  { return (i + 4) % 5; }
7    int right(int i) { return (i + 1) % 5; }
8
9    void test(int i) {
10        if (state[i] == HUNGRY &&
11            state[left(i)] != EATING &&
12            state[right(i)] != EATING) {
13            state[i] = EATING;
14            self[i].signal();
15        }
16    }
17
18    void pickup(int i) {
19        state[i] = HUNGRY;
20        test(i);
21        if (state[i] != EATING)
22            self[i].wait();
23    }
24
25    void putdown(int i) {
26        state[i] = THINKING;
27        test(left(i));
28        test(right(i));
29    }
30}

Each philosopher executes the following loop:2

1while (true) {
2    think();
3    DiningPhilosophers.pickup(i);
4    eat();
5    DiningPhilosophers.putdown(i);
6}

This algorithm relies on two monitor principles. First, monitor procedures execute with implicit mutual exclusion, so updates to $state[]$ are serialized.2 Second, condition variables allow a philosopher to sleep until another philosopher changes the relevant shared state.2

Footnotes

1. Dining Philosophers, Monitors, and Condition Variables - University of Colorado Boulder - Detailed lecture notes with monitor-based Dining Philosophers pseudocode and condition-variable semantics. ↩ ↩² ↩³ ↩⁴

2. Dining-Philosophers Solution Using Monitors - GeeksforGeeks - Summary of the monitor solution, philosopher states, and deadlock-avoidance logic. ↩ ↩²

3. Lecture 6: Semaphores and Monitors - UC San Diego - Operating-systems lecture notes comparing locks, semaphores, monitors, and condition variables. ↩

4. Condition Variables & Monitors - Virginia Tech - Explanation of condition-variable semantics, monitor behavior, and fairness considerations. ↩

Why the Monitor Algorithm Works

The monitor solution is considered deadlock-free because no philosopher is allowed to partially acquire only one chopstick; eating begins only when both adjacent resources are effectively available.2 That breaks the classic circular-wait scenario that causes deadlock in naive approaches. The monitor also ensures mutual exclusion over the shared state array, so race conditions in state transitions are prevented.2

A useful correctness argument is based on invariants:

• If $state[i] = EATING$, then $state[left(i)] \neq EATING$ and $state[right(i)] \neq EATING$.2
• Only one monitor procedure manipulates $state[]$ at a time.
• A hungry philosopher waits only when its eligibility predicate is false.2

When philosopher $i$ finishes eating and calls $putdown(i)$, the algorithm immediately tests both neighbors.2 This is important because it localizes responsibility: only the neighboring philosophers could have been blocked by philosopher $i$'s eating. If one of them is hungry and both of its neighbors are now not eating, it can be signaled to proceed.2

Starvation is subtler. The classic monitor formulation is deadlock-free, and under fair signaling and scheduling assumptions it is often presented as starvation-resistant in teaching contexts, but starvation freedom can depend on implementation semantics and scheduling policy.2 In practice, fairness strategies such as FIFO condition queues or explicit aging may be added if strict starvation-freedom guarantees are required.

Footnotes

1. Dining Philosophers, Monitors, and Condition Variables - University of Colorado Boulder - Detailed lecture notes with monitor-based Dining Philosophers pseudocode and condition-variable semantics. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷ ↩⁸

2. Dining-Philosophers Solution Using Monitors - GeeksforGeeks - Summary of the monitor solution, philosopher states, and deadlock-avoidance logic. ↩ ↩² ↩³ ↩⁴ ↩⁵

3. Lecture 6: Semaphores and Monitors - UC San Diego - Operating-systems lecture notes comparing locks, semaphores, monitors, and condition variables. ↩

4. Condition Variables & Monitors - Virginia Tech - Explanation of condition-variable semantics, monitor behavior, and fairness considerations. ↩ ↩²

5. CS170 Lecture Notes -- Thinking and Eating - UC Santa Barbara - Notes explaining the state-based monitor solution and why explicit chopstick tracking is unnecessary. ↩

Summary Comparison

The central conceptual progression is:

For the Dining Philosophers problem, monitors provide a more declarative solution than plain semaphores. Instead of counting forks directly, the algorithm maintains shared logical state and suspends philosophers until the predicate for safe eating becomes true.3 This makes the reasoning clearer: the algorithm enforces the invariant that no two adjacent philosophers are in the $EATING$ state at the same time.2

Footnotes

1. Lecture 6: Semaphores and Monitors - UC San Diego - Operating-systems lecture notes comparing locks, semaphores, monitors, and condition variables. ↩ ↩²

2. Semaphore (programming) - Wikipedia - Overview of semaphore semantics, wait/signal behavior, and synchronization role. ↩

3. Dining Philosophers, Monitors, and Condition Variables - University of Colorado Boulder - Detailed lecture notes with monitor-based Dining Philosophers pseudocode and condition-variable semantics. ↩ ↩² ↩³

4. Condition Variables & Monitors - Virginia Tech - Explanation of condition-variable semantics, monitor behavior, and fairness considerations. ↩

5. Dining-Philosophers Solution Using Monitors - GeeksforGeeks - Summary of the monitor solution, philosopher states, and deadlock-avoidance logic. ↩ ↩²

6. CS170 Lecture Notes -- Thinking and Eating - UC Santa Barbara - Notes explaining the state-based monitor solution and why explicit chopstick tracking is unnecessary. ↩