Difficulty: Advanced
Explain the readers-writers problem and the dining philosophers problem, and how each can be solved without deadlock or starvation.
These two problems are the remaining classics of synchronization, and each teaches a different lesson. Readers-writers teaches that not all access is equal: reading is safe to share, writing is not. Dining philosophers teaches how deadlock can arise from perfectly reasonable local behaviour. Let me take them in turn.
In the readers-writers problem, a shared data set (a database, a cache, a file) is accessed by readers, who only read, and writers, who modify. Any number of readers can safely access the data simultaneously, but a writer needs exclusive access, with no readers and no other writers present. The first solution, the readers-preference version, uses a counter readcount protected by a mutex, and a semaphore wrt for exclusive writing. The first reader to arrive locks wrt on behalf of all readers, and the last reader to leave unlocks it. Writers simply wait on wrt. This maximizes concurrency but can starve writers: if readers keep arriving in an overlapping stream, readcount never drops to zero. The second solution, writers-preference, blocks new readers when a writer is waiting; it protects writers but can starve readers. The third solution, a fair one, uses a turnstile semaphore that forces everyone through a queue in order. In practice this is packaged as a read-write lock, such as pthread_rwlock_t or Java's ReentrantReadWriteLock, which is worth using when reads greatly outnumber writes.
The dining philosophers problem, from Dijkstra, has five philosophers sitting around a circular table with a bowl of noodles, and a single chopstick between each pair of neighbours, so five chopsticks in total. A philosopher alternates between thinking and eating, and to eat needs both the left and right chopsticks. It models processes competing for multiple shared resources.
The naive solution, each philosopher picks up the left chopstick then the right, fails badly. If all five pick up their left chopstick simultaneously, each waits forever for the right one held by a neighbour: a circular wait, and hence deadlock. Even fixing deadlock can leave starvation, where one philosopher is unlucky forever.
There are several standard fixes, and each attacks a different Coffman condition. Limit the number of philosophers at the table to four using a counting semaphore, so at least one can always get two chopsticks; this prevents circular wait. Impose a resource ordering: number the chopsticks and always pick up the lower-numbered one first, so the last philosopher picks right before left; this breaks the cycle. Use an asymmetric strategy where odd philosophers pick left first and even philosophers pick right first. Or pick up both chopsticks atomically inside a critical section, or use a monitor with a state for each philosopher (thinking, hungry, eating) so that a philosopher may eat only if neither neighbour is eating. The monitor solution is deadlock-free, but a philosopher can still starve if the two neighbours alternate eating in an unlucky rhythm.
The most important idea to carry away is that resource ordering is the simplest and most general deadlock prevention technique in real code, for example always acquiring locks in a global order. The problem also connects to database transactions, where locking multiple rows in inconsistent order causes deadlocks.
When asked in an interview, do not merely recite the code. Identify the shared resources, the failure mode (deadlock or starvation), and which condition your fix removes.
import threading, time, random
N = 5
forks = [threading.Lock() for _ in range(N)]
def philosopher(i):
left, right = i, (i + 1) % N
first, second = min(left, right), max(left, right) # global order
for _ in range(3):
time.sleep(random.random() * 0.01) # think
with forks[first]:
with forks[second]:
print(f"philosopher {i} eating")
time.sleep(0.01)
ts = [threading.Thread(target=philosopher, args=(i,)) for i in range(N)]
for t in ts: t.start()
for t in ts: t.join()
print("done - no deadlock")Always taking the lower-numbered fork first breaks the circular wait, so the program cannot deadlock.
readers-writers, dining philosophers, starvation, deadlock avoidance, synchronization