.. _philosophers:

Dinning Philosophers
^^^^^^^^^^^^^^^^^^^^^

.. sidebar:: 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.

.. figure:: philosophers.jpg
   :align: center

   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 :term:`semaphore`\ s, 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 :term:`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 :meth:`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.