Dining philosophers: Tanenbaum's solution

Allen B. Downey1



One of the best known solutions is the one that appears in Tanenbaum's popular operating systems textbook. For each philosopher there is a state variable that indicates whether the philosopher is thinking, eating, or waiting to eat ("hungry") and a semaphore that indicates whether the philosopher can start eating. Here are the variables:
state = ['thinking'] * 5 
sem = [Semaphore(0) for i in range(5)] 
mutex = Semaphore(1)
The initial value of state is a list of 5 copies of 'thinking'. sem is a list of 5 semaphores with the initial value 0. Here is the code:
def getfork(i): 
    mutex.wait()
    state[i] = 'hungry' 
    test(i)
    mutex.signal()
    sem[i].wait()
 
def putfork(i):
    mutex.wait()
    state[i] = 'thinking' 
    test(right(i))
    test(left(i))
    mutex.signal()
 
def test(i):
    if state[i] == 'hungry' and 
       state (left (i)) != 'eating' and
       state (right (i)) != 'eating': 
        state[i] = 'eating' 
        sem[i].signal()
The test function checks whether the ith philosopher can start eating, which he can if he is hungry and neither of his neighbors are eating. If so, the test signals semaphore i.
There are two ways a philosopher gets to eat. In the first case, the philosopher executes get_forks, finds the forks available, and proceeds immediately. In the second case, one of the neighbors is eating and the philosopher blocks on its own semaphore. Eventually, one of the neighbors will finish, at which point it executes test on both of its neighbors. It is possible that both tests will succeed, in which case the neighbors can run concurrently. The order of the two tests doesn't matter.
In order to access state or invoke test, a thread has to hold mutex. Thus, the operation of checking and updating the array is atomic. Since a philosopher can only proceed when we know both forks are available, exclusive access to the forks is guaranteed.
No deadlock is possible, because the only semaphore that is accessed by more than one philosopher is mutex, and no thread executes wait while holding mutex.
But again, starvation is tricky. Unfortunately, this solution is not starvation-free. Gingras demonstrated that there are repeating patterns that allow a thread to wait forever while other threads come and go.
Imagine that we are trying to starve Philosopher 0. Initially, 2 and 4 are at the table and 1 and 3 are hungry. Imagine that 2 gets up and 1 sits down; then 4 gets up and 3 sits down. Now we are in the mirror image of the starting position.
If 3 gets up and 4 sits down, and then 1 gets up and 2 sits down, we are back where we started. We could repeat the cycle indefinitely and Philosopher 0 would starve.
So, Tanenbaum's solution doesn't satisfy all the requirements.

Footnotes:

1Excerpted from "The Little Book of Semaphores" by Allen Downey. Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.1 or any later version published by the Free Software Foundation; this book contains no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. You can obtain a copy of the GNU Free Documentation License from www.gnu.org or by writing to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.