CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 5 of 7 · 2 min read

Two fixes

The circular wait is the cause, so the fixes break the circle. Two are standard.

Fix 1: order the forks. Number the forks 0 to 4, and let every philosopher pick up the lower-numbered of the two forks first. Four philosophers take the left one first as before. The last, whose left fork is 4 and right fork is 0, takes fork 0 first. The circle is broken: there cannot be a cycle of waits, since every wait goes from a lower to a higher number.

int first = left, second = right;
if (left > right) { first = right; second = left; }    /* lowest-numbered fork first */
pthread_mutex_lock(&fork[first]);
pthread_mutex_lock(&fork[second]);

Fix 2: limit the number at the table. A counting semaphore with the value 4 lets at most four philosophers try for forks at once. With five forks and at most four philosophers, at least one of them can always get two forks (page 5).

sem_wait(&seats);                      /* at most 4 at the table */
/* pick up both forks, eat, put them down */
sem_post(&seats);

Both were tested for 2 seconds (the same program, with the same pauses):

Version Meals in 2 s Meals per philosopher Stuck?
Left fork first 0 0, 0, 0, 0, 0 Yes
Lowest fork first 2,088 465, 680, 745, 766, 466 No
At most 4 at the table 1,580 472, 473, 472, 472, 472 No

In plain words: Both fixes prevent the deadlock, and they differ in other ways. The ordering fix produced more meals and treated the philosophers unevenly (466 to 766, nearly a factor of two). The seat limit produced fewer meals, with nearly perfectly equal shares (472 or 473). Which is better depends on the aim: total throughput, or fairness. Neither has a built-in guarantee against starvation. The seat-limit run suggests that the semaphore queue serves the philosophers evenly.

The ordering idea is the one that matters in practice. When code needs several locks, always take them in one global order, as the account transfer of page 3 did by ordering on the address.

Resource ordering

Resource ordering is a deadlock-prevention technique in which all resources (locks) are given a fixed global order and every thread acquires the ones it needs strictly in increasing order, so that a circular chain of waits cannot form.

Example: each philosopher takes the lower-numbered fork first, so the philosopher between forks 4 and 0 takes fork 0 before fork 4.

Check yourself: 1. Why does ordering remove the circle? 2. Why is it enough to let four philosophers sit? 3. Which fix gave the more equal shares in the test?