AdvancedOperating Systems · Lesson 14 of 17 · Updated ·
Semaphores in Depth — Value Numericals, Bounded Buffer in Python, Readers-Writers and Dining Philosophers
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.
The same thing as a program:
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})")
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:
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))
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:
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)
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)
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:
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
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)andwait(mutex)in the producer: a producer holding the mutex while the buffer is full blocks the consumer for ever. - Forgetting the
readerscounter 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 + 1in 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.