Classic Synchronisation Problems
By the end of this lesson you will be able to write semaphore solutions for the three classic synchronisation problems, explain where each one can go wrong, and test them in a small Python simulation.
These three problems are not puzzles for their own sake. Each is a model of a pattern you meet in real software: a queue between two stages, a shared record that many read and few update, and a group of tasks that each need several resources. Learn them once and you will recognise them everywhere.
The tiny kernel we will use
All three simulations use the same small round-robin kernel from the semaphores lesson. Processes are Python generators that yield ("P", sem) or yield ("V", sem). Any other request just uses up a turn, which lets us make a process "slow". If every remaining process is blocked, the kernel reports a deadlock.
from collections import deque
class Sem:
def __init__(self, v): self.v, self.q = v, deque()
def run(procs):
ready, blocked = deque(procs.items()), 0
while ready:
name, g = ready.popleft()
try:
op, arg = next(g)
except StopIteration:
continue
if op == "P":
arg.v -= 1
if arg.v < 0:
arg.q.append((name, g)); blocked += 1; continue
elif op == "V":
arg.v += 1
if arg.v <= 0:
ready.append(arg.q.popleft()); blocked -= 1
ready.append((name, g))
print("DEADLOCK: everyone is blocked" if blocked else "all done")Each runnable example below includes this code at the top, so it runs on its own.
1. Producer-consumer (bounded buffer)
A producer makes items and puts them in a buffer with room for N items. A consumer takes them out. The producer must wait when the buffer is full, and the consumer must wait when it is empty.
Picture the serving counter between the kitchen and the dining hall in a South Indian tiffin centre. It holds only two plates. The cook places plates; the waiter carries them away. If the counter is full, the cook waits. If it is empty, the waiter waits.
Three semaphores solve it:
empty, starting atN: counts free slots.full, starting at 0: counts filled slots.mutex, starting at 1: makes sure only one process changes the buffer at a time.
Step 1: run it. The waiter is slower than the cook, so you will see the buffer fill up.
from collections import deque
class Sem:
def __init__(self, v): self.v, self.q = v, deque()
def run(procs):
ready, blocked = deque(procs.items()), 0
while ready:
name, g = ready.popleft()
try:
op, arg = next(g)
except StopIteration:
continue
if op == "P":
arg.v -= 1
if arg.v < 0:
arg.q.append((name, g)); blocked += 1; continue
elif op == "V":
arg.v += 1
if arg.v <= 0:
ready.append(arg.q.popleft()); blocked -= 1
ready.append((name, g))
print("DEADLOCK: everyone is blocked" if blocked else "all done")
N = 2 # buffer holds 2 plates
buffer = deque()
empty, full, mutex = Sem(N), Sem(0), Sem(1)
def producer(): # the cook
for dish in ["idli", "dosa", "vada", "upma", "poha"]:
if len(buffer) == N:
print("cook waits: buffer full")
yield ("P", empty) # wait for a free slot
yield ("P", mutex)
buffer.append(dish); print(f"cook put {dish:5} buffer={list(buffer)}")
yield ("V", mutex)
yield ("V", full) # one more full slot
def consumer(): # the waiter
for _ in range(5):
yield ("P", full) # wait for a full slot
yield ("P", mutex)
dish = buffer.popleft(); print(f"waiter took {dish:5} buffer={list(buffer)}")
yield ("V", mutex)
yield ("V", empty) # one more free slot
for _ in range(3):
yield ("serve", None) # walking to the table takes time
run({"cook": producer(), "waiter": consumer()})cook put idli buffer=['idli'] waiter took idli buffer=[] cook put dosa buffer=['dosa'] cook put vada buffer=['dosa', 'vada'] waiter took dosa buffer=['vada'] cook put upma buffer=['vada', 'upma'] cook waits: buffer full waiter took vada buffer=['upma'] cook put poha buffer=['upma', 'poha'] waiter took upma buffer=['poha'] waiter took poha buffer=[] all done
Step 2: check the rules. The buffer never holds more than 2 plates, and the waiter never takes from an empty counter.
The classic trap: if the producer does P(mutex) before P(empty), then a producer that finds the buffer full goes to sleep while holding mutex. The consumer can never get mutex to empty the buffer, and both wait for ever. Always wait on the counting semaphore first, then the mutex.
2. Readers-writers
Many processes share a record, such as a train timetable. Readers only look at it, so any number can read together. A writer changes it, so a writer needs the record completely to itself.
The first readers-writers solution uses:
rw, starting at 1: held by a writer, or by the group of readers as a whole.read_count: how many readers are inside.mutex, starting at 1: protectsread_count.
The first reader to arrive locks rw; the last reader to leave unlocks it. Readers in between just walk in.
from collections import deque
class Sem:
def __init__(self, v): self.v, self.q = v, deque()
def run(procs):
ready, blocked = deque(procs.items()), 0
while ready:
name, g = ready.popleft()
try:
op, arg = next(g)
except StopIteration:
continue
if op == "P":
arg.v -= 1
if arg.v < 0:
arg.q.append((name, g)); blocked += 1; continue
elif op == "V":
arg.v += 1
if arg.v <= 0:
ready.append(arg.q.popleft()); blocked -= 1
ready.append((name, g))
print("DEADLOCK: everyone is blocked" if blocked else "all done")
rw, mutex = Sem(1), Sem(1) # rw: the timetable itself; mutex protects read_count
read_count = 0
def reader(name):
global read_count
yield ("P", mutex)
read_count += 1
if read_count == 1:
yield ("P", rw) # first reader locks out writers
yield ("V", mutex)
print(f"{name} reading (readers inside: {read_count})")
yield ("read", None)
yield ("read", None)
yield ("P", mutex)
read_count -= 1
print(f"{name} done reading")
if read_count == 0:
yield ("V", rw) # last reader lets writers in
yield ("V", mutex)
def writer(name, arrives_after):
for _ in range(arrives_after):
yield ("travel", None) # the writer shows up a little later
print(f"{name} wants to write")
yield ("P", rw)
print(f"{name} WRITING alone")
yield ("write", None)
print(f"{name} done writing")
yield ("V", rw)
run({"R1": reader("R1"), "R2": reader("R2"), "W1": writer("W1", 3), "R3": reader("R3")})R1 reading (readers inside: 2) W1 wants to write R2 reading (readers inside: 3) R3 reading (readers inside: 3) R1 done reading R2 done reading R3 done reading W1 WRITING alone W1 done writing all done
Three readers share the timetable, while W1 waits until the last reader leaves. (The count printed is how many readers are inside at that moment.) This version favours readers: if new readers keep arriving, the writer can starve. The second readers-writers problem flips the preference so that a waiting writer blocks new readers. Real libraries offer read-write locks (pthread_rwlock_t on Linux, SRWLOCK on Windows) with fairer rules.
3. Dining philosophers
Five philosophers sit at a round table. Between each pair lies one fork, so there are five forks. A philosopher alternates between thinking and eating, and needs both neighbouring forks to eat.
The obvious solution is: pick up the left fork, then the right fork, eat, put both down. Each fork is a semaphore starting at 1. Step 1: run it, and then run the fixed version.
from collections import deque
class Sem:
def __init__(self, v): self.v, self.q = v, deque()
def run(procs):
ready, blocked = deque(procs.items()), 0
while ready:
name, g = ready.popleft()
try:
op, arg = next(g)
except StopIteration:
continue
if op == "P":
arg.v -= 1
if arg.v < 0:
arg.q.append((name, g)); blocked += 1; continue
elif op == "V":
arg.v += 1
if arg.v <= 0:
ready.append(arg.q.popleft()); blocked -= 1
ready.append((name, g))
print("DEADLOCK: everyone is blocked" if blocked else "all done")
def philosopher(i, forks, smart):
left, right = i, (i + 1) % 5
first, second = (right, left) if smart and i % 2 else (left, right)
yield ("P", forks[first])
yield ("P", forks[second])
print(f"Ph{i} eats with forks {first} and {second}")
yield ("V", forks[second])
yield ("V", forks[first])
for smart in (False, True):
print("Odd philosophers pick right fork first:" if smart else "Everyone picks left fork first:")
forks = [Sem(1) for _ in range(5)]
run({f"Ph{i}": philosopher(i, forks, smart) for i in range(5)})Everyone picks left fork first: DEADLOCK: everyone is blocked Odd philosophers pick right fork first: Ph0 eats with forks 0 and 1 Ph3 eats with forks 4 and 3 Ph1 eats with forks 2 and 1 Ph4 eats with forks 4 and 0 Ph2 eats with forks 2 and 3 all done
Step 2: understand the deadlock. In the first run, every philosopher picks up their left fork in their first turn. Now every fork is taken, and everyone waits for a right fork that their neighbour holds. Nobody can ever eat.
Common fixes:
- Asymmetry: odd-numbered philosophers pick the right fork first, as in the second run. The circle of waiting is broken.
- Limit the table: allow at most four philosophers to sit at once (a counting semaphore starting at 4). At least one of them can always get two forks.
- Both or nothing: pick up both forks only if both are free, checked inside a monitor.
This problem models any set of tasks that each need several locks, such as bank transfers that must lock two accounts. You will study the general theory in Deadlocks & How to Prevent Them.
Common mistakes
- Swapping
P(empty)andP(mutex)in the producer. Sleeping while holding the mutex deadlocks the system. - Forgetting that the first readers-writers solution can starve writers. Exams ask which side starves.
- Thinking the "limit to four" fix also guarantees fairness. It prevents deadlock, but a particular philosopher can still be unlucky.
Key points
- Producer-consumer uses
empty(N),full(0) andmutex(1), and waits on the counting semaphore before the mutex. - Readers-writers lets many readers share but gives a writer exclusive access; the first version can starve writers.
- Naive dining philosophers deadlocks when everyone holds one fork and waits for the next.
- Asymmetric ordering, limiting diners, or taking both forks at once prevents that deadlock.
- These patterns model real pipelines, shared records and multi-lock operations.
Exercise
In the producer-consumer simulation, swap the order of yield ("P", empty) and yield ("P", mutex) in the producer (and remove the two "waits" lines above them). Run it and explain the result. Then also remove the waiter's three "serve" steps and run it again. What changed?
Show solution
def producer():
for dish in ["idli", "dosa", "vada", "upma", "poha"]:
yield ("P", mutex) # WRONG ORDER
yield ("P", empty)
buffer.append(dish); print(f"cook put {dish:5} buffer={list(buffer)}")
yield ("V", mutex)
yield ("V", full)cook put idli buffer=['idli'] waiter took idli buffer=[] cook put dosa buffer=['dosa'] cook put vada buffer=['dosa', 'vada'] waiter took dosa buffer=['vada'] cook put upma buffer=['vada', 'upma'] DEADLOCK: everyone is blocked
The buffer is full, so the cook sleeps on empty while still holding mutex. The waiter then blocks on mutex and can never free a slot. Without the "serve" steps the waiter keeps up, the buffer never fills, and the program finishes with all done: the bug is still there, it just stays hidden. Bugs that appear only with certain timings are the most dangerous kind.
Quick Quiz
1. In the bounded-buffer solution, what is the initial value of the semaphore full?
At the start no slot is full, so a consumer must wait until a producer signals full.
2. In the first readers-writers solution, who can starve?
A stream of overlapping readers can keep rw locked and the writer waits for ever.
3. Why does the naive dining philosophers solution deadlock?
A circular wait forms in which nobody can proceed.
4. Which change prevents deadlock in the dining philosophers problem?
Breaking the symmetry breaks the circular wait.
Learn Operating Systems with a mentor
Free lessons get you started. Our Computer Science Fundamentals training adds real projects and code reviews from working developers.
- Project-based learning
- Mentor code reviews
- Free counselling call