4.3.4. Dinning Philosophers

Application

The dining philosophers problem represents a situation that can occur in large communities of processes that share a sizeable pool of resources.

Five philosophers (the tasks) spend their time thinking and eating spaghetti. They eat at a round table with five individual seats. To eat, each philosopher needs two forks (the resources). There are five forks on the table, one to the left and one to the right of each seat. When a philosopher can not grab both forks, he sits and waits. Eating takes random time, then the philosopher puts the forks down and leaves the dining room. After spending some random time thinking about the nature of the universe, he again becomes hungry, and the circle repeats itself.

A Philosopher needs both the fork on his left and on his right to eat. The forks are shared with the neighbors on either side.

It can be observed that a straightforward solution, when forks are implemented by semaphores, is exposed to deadlock. There exist two deadlock states when all five philosophers are sitting at the table holding one fork each. One deadlock state is when each philosopher has grabbed the fork left of him, and another is when each has the fork on his right.

Here is a basic monitor based solution:

import threading

class Philosopher_table(Object):
    def __init__(self):
        # Each fork is available to start
        self.forks = [True, True, True, True, True]
        self.monitor = threading.Condition()

    def _can_eat(self, n):
        if self.forks[n] and self.forks[(n+1)%5]:
            return True
        else:
            return False

    def get_forks(n):
        self.monitor.acquire()
        while not self._can_eat(n):
            self.monitor.wait()
        self.forks[n] = False
        self.forks[(n+1)%5] = False
        self.monitor.release()

    def put_forks(n):
        self.monitor.acquire()
        self.forks[n] = True
        self.forks[(n+1)%5] = True
        self.monitor.notifyAll()
        self.monitor.release()

The above solution uses threading.Condition.notifyAll() to signal all other philosophers that are waiting. A more complex, but perhaps better, solution might be to have a mutual exclusion lock for the set of forks and a monitor for each philosopher and signal (notify) only the philosophers to the left and right when the forks are returned.