The Dining Philosophers

Important 

Five introspective and introverted philosophers are sitting at a circular table. In front of each philosopher is a plate of food. Afork (or a chopstick) lies between each philosopher, one by the philosopher’s left hand and one by the right hand. A philosopher cannot eat until he or she has both forks in hand. Forks are picked up one at a time. If a fork is unavailable, the philosopher simply waits for the fork to be freed. When a philosopher has two forks, he or she eats a few bites and then returns both forks to the table. If a philosopher cannot obtain both forks for a long time, he or she will starve. Is there an algorithm that will ensure that no philosophers starve?

This is another concurrency classic, and although it may seem quite contrived - in the real world no one would starve because each philosopher would simply ask the adjacent philosophers for their forks - it accurately reflects real-world concurrency issues involving multiple shared resources. The point of the problem is to see whether you understand the concept of deadlock and know how it avoid it.

Start by trying a few simple tests to determine when deadlock happens and what you can do to avoid it. It won’t take you long to figure out that deadlock occurs quite readily. Consider the following implementation in which each philosopher picks up the forks in the same order, left followed by right:

 public class DiningPhilosophers {     // Each "fork" is just an Object we synchronize on     private Object[]      forks;     private Philosopher[] philosophers;     // Prepare the forks and philosophers     private DiningPhilosophers( int num ){         forks = new Object[ num ];         philosophers = new Philosopher[ num ];         for( int i = 0; i < num; ++i ){             forks[i] = new Object();             philosophers[i] = new Philosopher( i, i, ( i + 1 ) % num );         }     }     // Start the eating process     public void startEating() throws InterruptedException {         for( int i = 0; i < philosophers.length; ++i ){         philosophers[i].start();     }     // Suspend the main thread until the first philosopher     // stops eating, which will never happen -- this keeps     // the simulation running indefinitely     philosophers[0].join(); } // Entry point for simulation public static void main( String[] args ){     try {         DiningPhilosophers d = new DiningPhilosophers( 5 );         d.startEating();     }     catch( InterruptedException e ){     } } // Each philosopher runs in its own thread. private class Philosopher extends Thread {     private int id;     private int fork1;     private int fork2;     Philosopher( int id, int fork1, int fork2 ){         this.id = id;         this.fork1 = fork1;         this.fork2 = fork2;     }     public void run() {         status( "Ready to eat using forks " + fork1 +                 " and " + fork2 );         pause(); // pause to let others get ready         while( true ){             status( "Picking up fork " + fork1 );             synchronized( forks[ fork1 ] ){                 status( "Picking up fork " + fork2 );                 synchronized( forks[ fork2 ] ){                     status( "Eating" );                 }             }         }     }     private void pause(){         try {             sleep( 200 );         }         catch( InterruptedException e ){             // do nothing         }    }     private void status( String msg ){         System.out.println( "Philosopher " + id +                             ": " + msg );         }     } }

This application deadlocks when all philosophers have simultaneously picked up their left fork: Because no right fork is available to any philosopher, no philosopher can eat.

One solution is to add a timeout to the waiting: If a philosopher is not able to eat within a predetermined amount of time after acquiring the first fork, then the philosopher drops the fork and tries again. The flaw with this solution is that it’s possible for one or more philosophers to starve because they never acquire both forks. This is referred to as livelock.

The best solution requires a very simple change to the application. Instead of having all the philosophers pick up the left fork first, have one of the philosophers pick up the right fork first:

 // Prepare the forks and philosophers private DiningPhilosophers( int num ){     forks = new Object[ num ];     philosophers = new Philosopher[ num ];     for( int i = 0; i < num; ++i ){         forks[i] = new Object();         int fork1 = i;         int fork2 = ( i + 1 ) % num;          if( i == 0 ){             philosophers[0] = new Philosopher( 0, fork2, fork1 );         } else {             philosophers[i] = new Philosopher( i, fork1, fork2 );         }     } }

This one change to the fork pickup order is enough to break the deadlock and ensure that forks are always available to enable hungry philosophers to eat.