dining philosophers problem.txt

dining philosophers problem

The Dining Philosophers Problem
The Dining Philosophers problem is a classic concurrent programming problem. In the problem, a philosopher only does two things, think and eat. A philosopher thinks for a while, and then gets hungry. Then it eats until it gets full, and then starts thinking again. Each philosopher is so involved in its own thinking or eating that it's oblivious to anything else. The problem has five philosophers that are sitting at a table. Between neighboring philosophers there is a single chop stick. A philosopher must have both the stick on its right and the stick on its left in order for it to eat. Obviously, no two neighboring philosophers can be eating at the same time. The philosophers cannot disturb each other. If a philosopher wants to start eating and its neighbor has one of the sticks, the philosopher must wait until the stick becomes available. To solve the problem, an algorithm must be designed to let all of the philosophers eat. 

A simple algorithm for the philosophers could be: 

Think Get right chopstick
Get left chopstick
Eat
Drop left chopstick
Drop right chopstick
Repeat

There is one very serious problem with this algorithm. Suppose that each philosopher picks up the right chopstick at the same time. When they try to get the left stick, it won't be there. The neighbor to the left has it. All of the philosophers starve to death with a chopstick in one hand and food on the table. This is known as a deadlock. 

Deadlocks
Deadlocks are always a danger in multithreaded environments. A deadlock has occurred because 

Each thread needed exclusive use of the chopsticks. 
One thread is not allowed to take a chopstick from its neighbor. 
Each thread is waiting while holding a chopstick that another thread is waiting for. 
All deadlocks in any problem have the same reasons for deadlocking. Instead of waiting for chopsticks, they are waiting for some other resource or resources. If only one of the conditions can be broken, a deadlock will not occur. 

The first condition is usually hard to break. In the previous algorithm this could done by allowing philosophers to share a chopstick, but that isn't really possible. Sometimes threads need exclusive use of a resource. Things like the instance of a class or a socket may require that only one thread may use it at once. 

The second condition can sometimes be used to avoid deadlocks. If a philosopher was allowed to take a chopstick from its neighbor, there would not be a deadlock. However, if the philosophers keep taking sticks from each other, they may never get a chance to take a bite. Some problems can be solved by allowing resource stealing. It depends on the resource and the problem. 

If the deadlock cannot be avoided with the other conditions, it should be avoided by breaking the third condition. The philosophers can avoid a deadlock if there is a special chopstick that they aren't allowed to hold while they are waiting for the second chopstick. They are allowed to eat with the special stick, but they can't just hold it. An algorithm should not be too strict, otherwise the resources may be underused. For example, an algorithm could be made that only allows one philosopher to eat at once. Obviously, there would be no deadlocks, but a philosopher may have to wait longer before it can eat. 

A Solution to the Dining Philosophers Problem
There are many solutions to the Dining Philosophers problem. One solution follows. 

One of the chopsticks is marked as gold, while the rest are wood. No philosopher is allowed to hold the gold stick without eating. This prevents the philosophers from deadlocking. The philosophers picks up one chopstick then the other. If the gold stick is picked up first, it is put down and the other stick is picked up. It is possible that in the time between putting down the gold chopstick and picking up the other chopstick, all the other philosophers will have eaten and moved the gold chopstick all the way around the table, so when the philosopher picks up the other chopstick, it too is the gold chopstick. If this happens, the philosopher starts over. The solution is as follows: 

Think 
Pick up right chopstick 
If right chopstick is gold 
Drop right chopstick 
Pick up left chopstick 
If left chopstick is gold 
       Start over 
Pick up right chopstick 
Else 
Pick up left chopstick 
Eat 
Switch chopsticks in hands 
Drop right chopstick 
Drop left chopstick 
Repeat 
The chopsticks are switched when the philosopher puts down the chopsticks. This allows the philosophers equal chances to eat. Otherwise, the philosopher to the left of the gold chopstick would be disadvantaged. 

The philosophers may interfere with each other when they try to pick up a chopstick. A critical region is used to ensure that one philosopher can pick up or put down a chopstick. If one philosopher is picking up or putting down a stick, its neighbor is not allowed to touch the stick. What if a philosopher enters the critical section to get a chopstick, but the chopstick is not there? The philosopher must wait until the stick returns. This is done by a special wait in the critical section. The philosopher releases its lock and waits in the critical section. This allows the other philosopher to enter the critical section to return the chopstick. After the chopstick is returned, the waiting philosopher is woken up. After awakening, the philosopher reacquires the lock and continues executing. At any one time there can be only one philosopher running in the critical section, but it is OK if another philosopher is also sleeping in the critical section. 

Java's wait() and notify() 
Java has three wait() and two notify() methods that aid in synchronizing threads. The wait() methods cause the thread to pause in the critical region. While paused, the thread releases its lock. It must get the lock again before it starts executing again. The notify() methods wake up threads that have called wait(). Calling notify() when no wait() has been called has no effect. The methods shown below are in the Object class and can only be called in a synchronized block or method. 

public final void wait()  This method causes the thread to wait forever until a notify() or notifyAll() is called. The thread releases its lock on the critical regions so that other threads may enter. 
public final void wait(long m)  This method causes the thread to wait m milliseconds for a notify() or notifyAll() to be called. After the time is expired, the thread tries to resume execution. However, it must first reobtain the lock for the critical region. Another thread may have entered the critical section while the thread was waiting. 
public final void wait(long m, int n)  This method is similar to the previous one except that it waits for m milliseconds plus n nanoseconds. 
public final void notify()  This method wakes up a thread that has previously called wait(). The thread that was waiting has to get the lock before it can resume execution. It has to wait until the current thread leaves the critical region. Only one thread that has called wait() is woken up. It is not guaranteed that the first thread that called wait() is the first one woken up. 
public final void notifyAll()  This method wakes up all the threads that have called wait(). Each waiting thread has to get the lock for the critical region before it resumes. There can still be only one thread running in the critical section at once. 
Dining Philosophers Example
The Dining Philosophers applet uses four classes: the ones shown in Listings 16.5, 16.6, 16.7, and 16.8. The first class, DiningPhilosophers, extends the Applet class. The structure of this class is similar to the first example. Philosopher threads are created when the applet is initialized. They are suspended if the user leaves the page and resumed if the user returns. However, unlike the first example, no threads are created in this class. The Dining Philosophers example can be seen in Figure 16.5. 

Figure 16.5 : The Dining Philosophers example. 


--------------------------------------------------------------------------------

Listing 16.5. The class DiningPhilosophers. 

public class DiningPhilosophers extends Applet
{
  final int numPhils=5;

  Image offImage;        /* off screen image      */
  Graphics offGraphics;  /* Graphics for offImage */
  Philosopher Phil[] = new Philosopher[numPhils];
  Chopstick Stick[] = new Chopstick[numPhils];
  ScenePainter painter;

  public void init()
    {
      int i;

      offImage=createImage(400,300); 
      offGraphics=offImage.getGraphics(); 
      painter=new ScenePainter(offGraphics,this,numPhils); 

      for(i=0;i<numPhils;i++) 
        Stick[i]=new Chopstick (i==0 ? Chopstick.gold :
                                       Chopstick.wood, 
                                painter,i); 
      for(i=0;i<numPhils;i++) 
        Phil[i]= new Philosopher(Stick[i],Stick[(i+1)%numPhils], 
                                 painter,i); 
     }

  public void start()
    {
      int i;
      for(i=0;i<numPhils;i++) 
        Phil[i].resume(); 
    }

  public void stop()
    {
      int i;
      for(i=0;i<numPhils;i++) 
        Phil[i].suspend(); 
    }

  public void destroy()
    {
      int i;
      for(i=0;i<numPhils;i++) 
        {
          Phil[i].resume(); 
          Phil[i].stop(); 
        }
    }

  public void paint(Graphics g)
    {
      g.drawImage(offImage,0,0,null); 
    }

  public void update(Graphics Dijkstra)
    {
      paint(Dijkstra);
    }
} 

--------------------------------------------------------------------------------

The class DiningPhilosophers has six methods and is similar to the InfiniteThreadExample. 

public void init()  This method initializes the applet. It creates five instances of the classes Chopstick and Philosopher. One of the Chopstick classes is created as a gold chopstick, the rest are wood. Each Philosopher can reach two Chopsticks. On the right is Chopstick i, and on the left is Chopstick i+1 mod 5. 
public void start()  This method resumes philosopher execution. 
public void stop()  This method suspends philosopher execution. 
public void destroy()  This method kills the philosophers. 
public void paint()/update()  These two methods paint the state of the philosophers. 
Each philosopher at the table is its own thread. The thread is created in the class Philosopher by extending Thread. The methods in the class control the philosopher's life of thinking and eating. Initially, the philosopher is thinking. After some time, the philosopher picks up the two chopsticks next to it and starts eating. It calls methods in the Chopstick class (see Listing 16.7) to get the chopsticks. The philosopher also paints its state by calling methods in the ScenePainter class (see Listing 16.8). 


--------------------------------------------------------------------------------

Listing 16.6. The class Philosopher. 

class Philosopher extends Thread
{
  final int ThinkTime=5000, EatTime=3000;
  Chopstick rightStick,leftStick;
  ScenePainter painter;
  int rightHand,leftHand;
  int myNum;

  public Philosopher(Chopstick right, Chopstick left, 
                     ScenePainter p, int n)
    {
      painter=p;
      myNum=n;
      rightStick=right;
      leftStick=left;
      start();
    }

  public void run()
    {
      for(;;)
        {
          think(); 
          PickUpSticks(); 
          eat(); 
          PutDownSticks(); 
        }
    }

  void think()
    {
      painter.drawThink(myNum); 
      try {sleep((int)(ThinkTime*Math.random()));} 
      catch (InterruptedException e) {}
      painter.drawThink(myNum);