Philosophers at a Table

Creating a deadlock-free semaphore-based implementation of the dining philosopher problem isn't particularly difficult. All you need to do is implement a chopstick pickup order that does not allow deadlock. The method we used (although you could just as easily do the opposite) is to have each philosopher pick up their even-numbered chopstick first, then their odd-numbered chopstick afterwards. This guarantees that, regardless of the number of philosophers n at the table (as long as there're two chopsticks, smartass), at least one will be able to eat at any point, with a maximum of n / 2 (rounded down) being able to eat at once.

I initially thought (and indeed said in my report) that the condition we were seeing, where only one of five philosophers was able to eat, was a consequence of there being an odd number of philosophers. While I was correct that the odd number had an important part in what we were seeing, the problem was more general than I thought. This diagram of an eight-philosopher table shows the worst case scenario for an even number of philosophers:



What's happening here is as follows:
1. Philosopher 0 picks up chopsticks 0 and 1, and begins eating
2. Philosopher 1 picks up chopstick 2, and blocks on chopstick 1
3. Philosopher 2 blocks on chopstick 2
4. Philosopher 7 blocks on chopstick 0

In this order (or a few variations of it), one philosopher has managed to prevent three others in a cluster from eating. The exact same method can be used to block three others, while a total of two philosophers eat; this is the worst-case scenario for this table.

You can draw it out for yourself (I drew it on paper, along with several other sizes, but don't feel like making more diagrams online) and prove that it's possible for a minimum of two philosophers to eat at a table with only six philosophers. This is logical: one philosopher can only block three others, leaving three chopsticks available; one of the last two philosophers will be able to eat.

So, four philosophers is too few (for two philosophers to eat), six is enough, but what about five? This was the classic case, and the one we implemented. What happened is this, shown in words and figure:



1. Philosopher 1 picks up chopsticks 2 and 1, and begins eating
2. Philosopher 2 blocks on chopstick 2
3. Philosopher 0 picks up chopstick 0, and blocks on chopstick 1
4. Philosopher 4 picks up chopstick 4, and blocks on chopstick 0
5. Philosopher 3 blocks on chopstick 4

As you can see, the problem is that one philosopher (#4) has two even-numbered chopsticks (#4 and #0), meaning that regardless of the order in which he tries to pick them up, it's gonna screw up the ordering. In fact, what happens is that this allows an additional philosopher to block on one eating philosopher, bringing the total in the cluster to five - the number of philosophers at the table.

Oh, and for those keeping score, the minimum number of philosophers that are able to eat at any time appears to be (n + 2) / 4.