Live coding puzzles question 175 of 180 mid
Solve the dining philosophers problem without deadlock.
- Give each philosopher a timeout and retry immediately
- Correct: Impose a global order on the forks, so one philosopher picks up in the opposite order and no cycle can form; or use a waiter semaphore allowing N-1 to eat
- Make eating synchronized on one lock
- Give each philosopher their own pair of forks
Five philosophers, five forks, everyone grabbing left then right: a perfect circular wait. The three standard fixes, and the Coffman condition each one breaks:
- Lock ordering: number the forks and always take the lower-numbered one first. The last philosopher then reaches right-then-left, which breaks the cycle. One line of change.
- A waiter: a
Semaphorewith four permits, so at most four philosophers sit down and someone can always eat. With one seat empty the cycle can never close, so this breaks circular wait, like ordering, without numbering anything. - tryLock with backoff: take the first fork,
tryLockthe second, and put the first down if it fails, retrying after a random delay. Breaks hold-and-wait, but needs the randomness or it becomes a livelock.
Say which you would ship: ordering, because it is deterministic and has no retry storms.