dining philosophers problem.txt

dining philosophers problem

    }

  void PickUpSticks()
    {
      for(boolean gotem=false;!gotem;) 
        {
          painter.drawFirstGrab(myNum); 
          rightHand=rightStick.grabStick(); 

          painter.drawSecondGrab(myNum); 
          if(rightHand==Chopstick.gold) 
            { 
              painter.drawGoldGrab(myNum); 

              rightStick.dropStick(rightHand); 
              leftHand=leftStick.grabStick(); 
              if(leftHand==Chopstick.gold) 
                { 
                  leftStick.dropStick(leftHand); 
                  continue;  /* gold stick went around table */
                } 
              rightHand=rightStick.grabStick(); 
              painter.drawGoldGrab(myNum); 
            } 
          else leftHand=leftStick.grabStick();

          painter.drawSecondGrab(myNum); 
          painter.drawFirstGrab(myNum); 
          gotem=true; 
        }
    }

  void eat()
    {
      painter.drawEat(myNum);
      try {sleep((int)(EatTime*Math.random()));} 
      catch (InterruptedException e) {}
      painter.drawEat(myNum);
    }

  void PutDownSticks()
    {/* swap sticks and put them down */
      rightStick.dropStick(leftHand); 
      leftStick.dropStick(rightHand); 
    }
} 

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

The class Philosopher is used to start the threads for the Dining Philosophers applet. The class has the following five methods: 

public void run()  This method defines the philosophers actions. Each philosopher thinks, waits to pick up its chopsticks, eats, returns the chopsticks, and repeats the cycle. 
void think()  This method is where the philosopher thinks. The thinking image is drawn and the philosopher sleeps for a random amount of time. 
void PickUpSticks()  In this method, the philosopher picks up the chopsticks in a way that is fair and avoids deadlocks. 
void eat()  This method is where the philosopher eats. The eating image is drawn and the philosopher sleeps for a random amount of time. 
void PutDownSticks()  In this method, the philosopher returns the sticks. The chopsticks are switched when they are put down so that the gold stick is not always in the same place. 
All of the synchronization is done in the Chopstick class. There is one instance of this class for each chopstick on the table. The class is used by the philosophers when they want to pick up or return a chopstick. The three states of the chopstick are represented by the variable stickHolder: noStick means the chopstick is gone, wood means this is the wooden stick, and gold means this is the golden stick. stickHolder is an instance variable. More than one philosopher may be trying to get/drop it at once, so there is a danger of data corruption. The methods of this class are synchronized to ensure that stickHolder does not get corrupted (see Listing 16.7). 


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

Listing 16.7. The class Chopstick. 

class Chopstick extends Object
{
  final static int noStick=0;
  final static int wood=1;
  final static int gold=2;
  ScenePainter painter;
  int stickHolder;
  int myNum;

  public Chopstick(int stick, ScenePainter p, int n) 
    {
      painter=p;
      myNum=n;
      dropStick(stick);
    }

  synchronized int grabStick()
    {
      int Thuy;

      if(stickHolder==noStick)
        try {wait();} catch (InterruptedException e) {}
      painter.drawStick(myNum,stickHolder); 
      Thuy=stickHolder;
      stickHolder=noStick;
      return Thuy;
    }

  synchronized void dropStick(int stick)
    {
      stickHolder=stick;
      painter.drawStick(myNum,stickHolder); 
      notify();
    }
} 

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

The class Chopstick is used to synchronize the threads in the Dining Philosophers applet. The class has the following two methods: 

synchronized int grabStick()  Philosophers (threads) will come into this method when they attempt to get a stick. If the stick is there, the method gives the stick to the philosopher. If the stick has already been taken by its neighbor, the philosopher waits for the stick to be returned. 
synchronized void dropStick()  The philosophers use this method to return the sticks. If the other philosopher is waiting for this chopstick, it is woken. 
The class ScenePainter is used by the philosophers to paint their state. If a philosopher starts eating, puts down a stick, or does anything else, it calls methods in this class. The states of philosophers (for example, eating or waiting for a stick) are represented by different shapes. When a philosopher starts thinking, it calls drawThink(myNum) to draw the philosopher in its thinking state. Then, when it is done thinking, it calls drawThink(myNum) again to erase the philosopher. All of the methods in this class are called in pairs. The first call draws a state and the second erases it. 


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

Listing 16.8. The class ScenePainter. 

class ScenePainter extends Object
{
  int sX1[], sY1[], sX2[], sY2[], pX[], pY[];
  final int xOffset=150, yOffset=150, Tscale=70;
  final int rg=2, rEating=15, rThinking=8, rFirst=7; 
  final int rSecond=3, rGold=5;
  Graphics G;
  Component C;

  public ScenePainter(Graphics g, Component c, int numPhils) 
    {
      int i;
      pX  = new int[numPhils]; pY  = new int[numPhils];
      sX1 = new int[numPhils]; sY1 = new int[numPhils];
      sX2 = new int[numPhils]; sY2 = new int[numPhils];
      double arc=Math.PI/numPhils; 

      G=g; C=c;

      for(i=0;i<numPhils;i++) 
        {
          pX[i]= (int)(xOffset+   Tscale*Math.cos(i*2*arc));
          pY[i]= (int)(yOffset+   Tscale*Math.sin(i*2*arc));
          sX1[i]=(int)(xOffset+   Tscale*Math.cos(i*2*arc+arc));
          sY1[i]=(int)(yOffset+   Tscale*Math.sin(i*2*arc+arc));
          sX2[i]=(int)(xOffset+.7*Tscale*Math.cos(i*2*arc+arc)); 
          sY2[i]=(int)(yOffset+.7*Tscale*Math. sin(i*2*arc+arc));
        }
      G.setColor(Color.white);
      G.setXORMode(Color.blue); 
    }

  void drawStick(int num, int stick)
    {
      G.drawLine(sX1[num],sY1[num],sX2[num],sY2[num]); 
      if(stick==Chopstick.gold) 
        G.fillOval(sX1[num]-rg,sY1[num]-rg,rg+rg,rg+rg); 
      C.repaint();
    }

  void drawEat(int num)
    {
      fillCircle(num,rEating);
    }

  void drawThink(int num)
    {
      fillCircle(num,rThinking); 
    }

  void drawFirstGrab(int num)
    {
      fillSquare(num,rFirst);
    } 

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

The class ScenePainter is used to draw the state of all the philosophers in the Dining Philosophers applet. 

public ScenePainter(Graphics, Component, int)  The constructor for this class calculates the position of each philosopher and chopstick. 
void drawStick(num, stick)  This method draws/erases the chopstick specified by num. A stick is represented by drawing a line between the two philosophers that may use it. If stick is the gold chopstick, a small circle is added to the end of the chopstick. 
void drawEat(num)  This method draws/erases the philosopher specified by num in its eating state. A large circle represents the eating state. 
void drawThink(num)  This method draws/erases a small circle that represents a philosopher in its thinking state. 
void drawFirstGrab(num)  This method draws/erases a small square. The method is called when the philosopher tries to grab the first stick. 
void drawSecondGrab(num)  This method erases/draws a smaller square inside the square drawn by drawFirstGrab(num). The method is called after the philosopher already has one chopstick and is trying to grab the second. A philosopher in this state is represented by a small hollow square. 
void drawGoldGrab(num)  This method is called if the first stick the philosopher picked up is the gold stick. It is only called after both drawFirstGrab(num) and drawSecondGrab(num) have been called. A philosopher in this state is represented by a small hollow square with a tiny circle in the middle. 
Summary 
Threads are the life in an applet. Some threads are created by the system, but others are started in the applet. Threads can be started to remove some of the burden from a system thread, or to start its own line of execution. 

This chapter contained several applets that started threads. The examples showed specific uses of threads that can be expanded to general use. Most threading problems can be solved by using slight variations of the first two examples. These examples have threads that do not communicate with other threads. If threads need to communicate with each other, care must be taken to avoid data corruption. The third example shows data corruption and the steps that must be taken to avoid it. The forth example shows how two threads can be synchronized so that they can do things in the right order. The final example, the Dining Philosophers, shows many of the subtle problems in a multithreaded environment. If threads in an applet compete for common resources, a deadlock can occur unless care is taken to avoid it. The examples in this chapter are just that, examples. The reader is encouraged to experiment with them, tweak some of the parameters, add more threads, but most of all, have fun.