# Semaphores in Depth — Value Numericals, Bounded Buffer in Python, Readers-Writers and Dining Philosophers

Source: https://skills101.in/learn/operating-systems/os-semaphores-classic-problems — Skills101 free tutorial (Operating Systems). Updated 2026-11-21.

Lesson 4 introduced race conditions, mutexes and semaphores. This lesson goes one level deeper: what a semaphore does **inside**, the numerical questions built on it, and complete solutions to the classic problems — with programs you can run.

## 1. A semaphore with a blocked queue

The simple definition "wait blocks while S is 0" would make a waiting process loop and burn CPU (a **busy wait** or **spinlock**). Operating systems instead keep a **queue of blocked processes** inside the semaphore:

- **wait(S)**: S = S − 1. If S is now **negative**, put the caller in the queue and block it.
- **signal(S)**: S = S + 1. If S is still **≤ 0**, someone is waiting — remove one process from the queue and wake it.

In this (textbook) version, a **negative value tells you how many processes are blocked**: S = −2 means two are waiting.

Example: an office has **2 printers**, so S starts at 2. Four jobs A, B, C, D arrive.

![Table of semaphore S starting at 2: A and B wait and get printers (S 1, then 0); C and D wait and block (S −1, −2, queue C, D); A signals and C wakes (S −1); B signals and D wakes (S 0)](https://skills101.in/learn-img/operating-systems/semaphore-queue.svg)

The same thing as a program:

```python
from collections import deque

class Semaphore:
    def __init__(self, value):
        self.value = value
        self.queue = deque()

    def wait(self, who):                 # also called P() or down()
        self.value -= 1
        if self.value < 0:
            self.queue.append(who)       # no instance free: block
            return f"{who} blocks"
        return f"{who} gets a printer"

    def signal(self, who):               # also called V() or up()
        self.value += 1
        if self.value <= 0:
            woken = self.queue.popleft() # hand the instance to a waiter
            return f"{who} releases, {woken} wakes up"
        return f"{who} releases"

s = Semaphore(2)
steps = [("wait", "A"), ("wait", "B"), ("wait", "C"), ("wait", "D"), ("signal", "A"), ("signal", "B")]
for op, who in steps:
    msg = getattr(s, op)(who)
    print(f"{op}({who}) -> S = {s.value:2}  queue = {list(s.queue)}  ({msg})")
```

```text
wait(A) -> S =  1  queue = []  (A gets a printer)
wait(B) -> S =  0  queue = []  (B gets a printer)
wait(C) -> S = -1  queue = ['C']  (C blocks)
wait(D) -> S = -2  queue = ['C', 'D']  (D blocks)
signal(A) -> S = -1  queue = ['D']  (A releases, C wakes up)
signal(B) -> S =  0  queue = []  (B releases, D wakes up)
```

In a real OS, wait and signal must themselves be **atomic** — the kernel disables interrupts or uses a hardware instruction such as test-and-set while it changes S and the queue.

## 2. Semaphore value numericals

Each wait subtracts 1 and each signal adds 1, so the final value does not depend on the order:

**Final S = initial + (number of signals) − (number of waits)**

| Question | Working | Answer |
|---|---|---|
| S = 10; 6 wait and 4 signal operations. Final S? | 10 − 6 + 4 | **8** |
| S = 7; 20 waits and 15 signals. Final S? | 7 − 20 + 15 | **2** |
| S = 0; 5 waits, then 2 signals. How many processes are still blocked? | 0 − 5 + 2 = −3 | **3** |

A related question: "a counting semaphore starts at x; after 8 waits and 3 signals it is 1. Find x." → x − 8 + 3 = 1 → **x = 6**.

## 3. What can an unprotected counter end up as?

Two threads both run `x = x + 1` on a shared x = 0. The CPU does this in three steps — **load** x into a register, **add** 1, **store** it back — and the threads can be interleaved between any two steps. This program tries **every** interleaving and collects the possible final values:

```python
from itertools import combinations

def run(order, steps):
    x = 0
    reg = {"A": 0, "B": 0}           # each thread's private register
    pos = {"A": 0, "B": 0}
    for t in order:
        op = steps[pos[t]]
        pos[t] += 1
        if op == "load":
            reg[t] = x
        elif op == "add":
            reg[t] += 1
        else:                         # store
            x = reg[t]
    return x

def all_results(increments):
    steps = ["load", "add", "store"] * increments
    n = len(steps)
    results = set()
    for a_slots in combinations(range(2 * n), n):   # every interleaving
        order = ["A" if i in a_slots else "B" for i in range(2 * n)]
        results.add(run(order, steps))
    return sorted(results)

print("each thread does x = x + 1 once:  ", all_results(1))
print("each thread does x = x + 1 twice: ", all_results(2))
```

```text
each thread does x = x + 1 once:   [1, 2]
each thread does x = x + 1 twice:  [2, 3, 4]
```

The "expected" answers are 2 and 4, but **lost updates** make smaller values possible: both threads load the same old value, and one store overwrites the other. Wrapping the increment in wait(mutex) … signal(mutex) leaves only the correct answer.

## 4. Producer–consumer that really runs

Python's `threading.Semaphore` has `acquire()` (= wait) and `release()` (= signal). Here a producer makes items 1 to 10, the buffer holds at most 3, and a consumer takes them out:

```python
import threading

N = 3                                   # buffer slots
buffer = []
mutex = threading.Semaphore(1)          # protects the buffer
empty = threading.Semaphore(N)          # free slots
full = threading.Semaphore(0)           # filled slots
largest = 0
eaten = []

def producer():
    global largest
    for item in range(1, 11):
        empty.acquire()                 # wait(empty)
        with mutex:
            buffer.append(item)
            largest = max(largest, len(buffer))
        full.release()                  # signal(full)

def consumer():
    for _ in range(10):
        full.acquire()                  # wait(full)
        with mutex:
            eaten.append(buffer.pop(0))
        empty.release()                 # signal(empty)

threads = [threading.Thread(target=producer), threading.Thread(target=consumer)]
for t in threads:
    t.start()
for t in threads:
    t.join()
print("consumed in order:", eaten)
print("buffer never held more than", N, "items:", largest <= N)
```

```text
consumed in order: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
buffer never held more than 3 items: True
```

The two threads interleave differently on every run, yet the output is always the same — that is what correct synchronisation means. Each semaphore has one job: `empty` stops the producer when the buffer is full, `full` stops the consumer when it is empty, and `mutex` stops them from changing the list at the same moment.

## 5. Peterson's solution (two processes, no special hardware)

```text
flag[i] = true          // I want to enter
turn = j                // but you may go first
while (flag[j] and turn == j) { }   // wait
    ... critical section ...
flag[i] = false
```

Both processes set `turn` to the **other** one; whoever wrote last waits. It satisfies all three rules — mutual exclusion, progress and bounded waiting. It is taught because it is a neat proof, but on modern CPUs that reorder memory operations it needs memory barriers to be correct, so real code uses hardware atomic instructions instead.

## 6. Readers–writers (readers first)

Many readers may read together; a writer needs the data alone. Two semaphores, `rw = 1` and `m = 1`, and a counter `readers = 0`:

```text
Writer:                 Reader:
  wait(rw)                wait(m)
  ... write ...           readers = readers + 1
  signal(rw)              if readers == 1: wait(rw)    // first reader locks writers out
                          signal(m)
                          ... read ...
                          wait(m)
                          readers = readers - 1
                          if readers == 0: signal(rw)  // last reader lets writers in
                          signal(m)
```

Only the **first** reader waits on `rw` and only the **last** releases it. The weakness: a steady stream of readers can **starve** writers. "Writers-first" versions fix that at the cost of more semaphores.

## 7. Dining philosophers

![Five philosophers P0 to P4 around a table with five forks F0 to F4 between them; each needs both neighbouring forks, and if everyone takes the left fork first they deadlock](https://skills101.in/learn-img/operating-systems/dining-philosophers.svg)

If every philosopher does `wait(left fork)` then `wait(right fork)`, all five can take their left fork at the same instant and wait for ever — all four deadlock conditions hold. Correct fixes, each breaking one condition:

| Fix | Condition broken |
|---|---|
| Allow at most **4** philosophers at the table (a counting semaphore set to 4) | circular wait — at least one can get both forks |
| **Asymmetric**: odd philosophers take left first, even ones right first | circular wait |
| Pick up **both forks or neither** (check inside a critical section) | hold and wait |

## Common mistakes

- Thinking the final semaphore value depends on the order of waits and signals — it does not.
- Swapping `wait(empty)` and `wait(mutex)` in the producer: a producer holding the mutex while the buffer is full blocks the consumer for ever.
- Forgetting the `readers` counter needs its own mutex.
- Believing the deadlock-free dining philosophers solutions also prevent **starvation** — they do not automatically.

## Quick recap

- wait: S −= 1, block if S < 0. signal: S += 1, wake one if S ≤ 0. Negative S = number blocked.
- Final value = initial + signals − waits.
- Unprotected `x = x + 1` in two threads can lose updates.
- Bounded buffer: empty = N, full = 0, mutex = 1, and the order of waits matters.
- Readers-writers: first reader locks, last reader unlocks. Dining philosophers: break circular wait or hold-and-wait.


Practice quiz and free certificate: https://skills101.in/learn/operating-systems/os-semaphores-classic-problems