MULTI THREADING

What Is a Thread?

A thread executes a series of instructions. Every line of code that is executed is done so by a thread. Some threads can run for the entire life of the applet, while others are alive for only a few milliseconds. A thread also creates a new thread or kills an existing one. Threads run in methods or constructors. The methods and constructors themselves are lifeless. The threads go into the methods and follow their instructions. Methods and constructors reside in the computer's memory. Figure 16.1 shows threads, constructors, and methods in a typical applet.
The applet methods start(), paint(), and so on are all called by underlying threads. These threads are created by the Web browser. When there is a mouse click or arepaint() has been called, the underlying thread calls the appropriate thread in the applet. While the threads are running in the applet methods, they cannot do anything else. If the applet holds these threads too long, it locks up the browser. If an applet needs to do something that will take some time in one of its methods, it should start a new thread. Some specific uses for threads are listed below:

• Long initiations.  Threads are used in applets that may take a while to initialize. The applet may need to do something like wait for an image to be loaded. A thread is used so that the system thread can handle other events.
• Repetitive or timed tasks.  Threads are used to do tasks that happen repetitively. A common example of this is found in animations. Every few milliseconds a new frame is shown. A thread displays a frame, sleeps for a while, and then repeats the process.
• Asynchronous events.  Threads are used to handle events. An example of this is a mouse click. If the user clicks the mouse, a new thread is created to render a new frame in an image.
• Multiple tasks.  Threads are used to do more than one thing at once. One thread controls an animation, while another does a computation.

The Thread Class

The class java.lang.Thread is used to create and control threads. To create a thread, a new instance of this class must be created. However, the thread does not start running right away. Thread.start() must be called to actually make the thread run. When Thread.start() is called, the thread begins executing in the run() method of the target class. A new Thread class always starts running the public void run() method of a class. There are two ways to create a thread:

• Extend the Thread class.  With this technique the new class inherits from the class Thread. The thread can start running in the class's run method.
• Implement the Runnable interface.  This technique is probably more common than extending the Thread class. It is not necessary to define a new class to run the thread. If a thread is to start running in the applet, it must use the Runnable interface. The applet cannot inherit from both the Thread and Applet classes. An applet with the Runnable interface must have a run() method for the thread to start.

There isn't much difference between the two approaches. Both extending the Thread class and implementing the Runnable interface have the same functionality. The interface approach must be used if the thread is to actually start in the applet class. But if the thread is going to be running in its own class, it may be more convenient to extend the Thread class. Examples of both approaches are in this chapter.
The Thread class has seven constructors. All of them create a new thread. The thread does not start running until Thread.start() is called. When Thread.start() is called, the new thread starts running in the run() method of an object. The constructors are the following:

Thread()
Thread(Runnable)
Thread(ThreadGroup)
Thread(String)
Thread(ThreadGroup,String)
Thread(Runnable,String)
Thread(ThreadGroup,Runnable,String)

The constructors can use three possible parameters:

• String  The name of the new thread is the parameter String. A thread can get its name by calling Thread.getName().
• ThreadGroup  The new thread will belong to the group specified by the parameter ThreadGroup. A ThreadGroup can be used to organize a thread.
• Runnable  The Runnable parameter is an object that has implemented the Runnable interface. The thread will start executing in the run() method of the Runnableparameter when Thread.start() has been called.

There are many methods in the Thread class. Some of them, such as destroy(), don't seem to have been implemented yet, and may never be. Some of the methods that control the thread execution are the following:

• start()  This method starts the thread. It starts executing in the run() method of its Runnable target that was set when the constructor was called. This method can be called only once.
• suspend()  This method suspends the execution of the thread. It remains suspended until resume() is called.
• resume()  This method resumes the execution of a suspended thread. It has no effect on a thread that is not suspended.
• stop()  This method stops and kills a running thread. Currently, the thread does not stop unless it is running. If it is suspended, it does not die until it starts running again. However, this may be fixed someday.
• sleep(int m)/sleep(int m,int n)  The thread sleeps for m milliseconds, plus n nanoseconds.

Simple Thread Examples

Listing 16.1 shows how to start, stop, suspend, and resume threads. It uses the Runnable interface. Threads like this are useful for things like controlling animation sequences or repeatedly playing audio samples. This example uses a thread that counts and prints a string every second. The thread starts when the applet is initialized. It continues to run until the user leaves the page. If the user returns to the page (and all is well), the thread continues from where it left off. This allows applets to retain their states while the user is away.

---

import java.lang.Thread;

import java.applet.Applet;

public class InfiniteThreadExample extends Applet implements Runnable
{
  Thread myThread;

  public void init()
    {
      System.out.println("in init() -- starting thread.");
      myThread= new Thread(this);
      myThread.start();
    }

  public void start()
    {
      System.out.println("in start() -- resuming thread.");
      myThread.resume();
    }

  public void stop()
    {
      System.out.println("in stop() -- suspending thread.");
      myThread.suspend();
    }

  public void destroy()
    {
      System.out.println("in destroy() -- stoping thread.");
      myThread.resume();
      myThread.stop();
    }

  public void run()
    {
      int i=0;
      for(;;)
        {
          i++;
          System.out.println("At " + i + " and counting!");
          try {myThread.sleep(1000);}
          catch (InterruptedException e ) {}
        }
    }
}

---

SimpleThreadExample Output

The output of InfiniteThreadExample is shown here. The applet ran for nine seconds until it was stopped.

in init() -- starting thread.
At 1 and counting!
in start() -- resuming thread.
At 2 and counting!
At 3 and counting!
At 4 and counting!
At 5 and counting!
At 6 and counting!
At 7 and counting!
At 8 and counting!
At 9 and counting!
in stop() -- suspending thread.
in destroy() -- stoping thread.

The applet has only five methods:

• public void init()  The thread is initialized and is started in this method. In this example, the constructor Thread takes the argument this. When theThread.start() method is called, the thread looks for a public void run() method in the this object.
• public void start()  When this method is called by the system, the thread resumes execution. If the thread is already running, this method has no effect.
• public void stop()  This method suspends the thread.
• public void destroy()  This method stops the thread. Thread.stop() stops and kills the thread. However, it only kills a thread that is running, soThread.resume() is called beforehand.
• public void run()  This is where the thread actually starts running. This example has an infinite loop that prints a string and then sleeps for a second. Long running threads should sleep every once in a while to give other threads a chance to run. If not, the system may not even get a chance to paint the applet.

When Are the Methods in InfiniteThreadExample Called?

Unfortunately, its not always possible to know exactly when or if the methods are called. It can vary from browser to browser, or even by how the user has the browser configured. Netscape 3.0 calls init() and then calls start() the first time the applet is loaded. If the user leaves the page with the applet, stop() is called. Returning to the applet calls start(), but it is possible that init() may be the first called. It depends on whether or not the applet is still residing in memory. If it is, then only start() is called; otherwise, both init() and start() are called again.
The method destroy() is called before the applet is removed from memory. All threads should be destroyed at this time so that its resources can be used by other applets. The browsers can only handle so many threads. If the user visits too many applets that don't clean up after themselves, the browser may crash. Generally, threads should be suspended when the user leaves the page and killed when the applet is destroyed. It is possible to leave threads running while the user is visiting other pages, but the user may not appreciate it.
Listing 16.2 shows how to use threads to handle events. When an event that existing threads shouldn't take the time to handle happens in the applet, a new thread is spawned to handle that event. After the event is handled, the new thread quietly dies. Listing 16.2 uses threads to handle mouse clicks. Each thread draws a blue target, as you can see in Figure 16.2. Methods such as mouseDown() or mouseUp() are called by threads external to the applet. While the thread is running in the applet, no other mouse movements are detected. Keeping the external thread may not just affect the applet, but possibly the whole browser. Generally, these methods should be returned as soon as possible. If it is necessary to do a long computation or wait for something else, a new thread should be started. By starting a new thread, the external thread can return almost immediately.

import java.applet.Applet;

import java.awt.*;

public class FiniteThreadExample extends Applet
{
  Image offImage;        /* off screen image      */
  Graphics offGraphics;  /* Graphics for offImage */

  public void init()
    {
      offImage=createImage(400,300);
      offGraphics=offImage.getGraphics();
    }

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

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

  public boolean mouseDown(Event e, int x, int y)
    {
      new DrawTarget(this,x,y,offGraphics);
      return true;
    }
}

class DrawTarget extends Thread
{
  int xPos,yPos;        /* position of the target */
  Applet myMaster;      /* who to repaint         */
  Graphics offGraphics; /* Graphics to draw on    */

  public DrawTarget(Applet a, int x, int y, Graphics g)
    {
      xPos=x; yPos=y;
      myMaster=a;
      offGraphics=g;
      start();
    }

  public void run()
    {
      int i;  /* i is direction the circles are moving */
      int r;  /* r is the radius of the current circle */

      offGraphics.setColor(Color.white);
      offGraphics.setXORMode(Color.blue);
      for(r=0,i=10;i>-20;i-=20)      /* i=(10,-10)             */
        for(r+=i;(r<90)&&(r>0);r+=i) /* r=(10,20...80,80,70...10) */
          {
            offGraphics.fillOval(xPos-r,yPos-r,2*r,2*r);
            myMaster.repaint();
            try {sleep(200);}
            catch (InterruptedException e) {}
          }
    }
}

---

The class FiniteThreadExample is used to paint the applet, to catch the mouse clicks, but not to start the threads. The applet uses a class that extends the Thread class to start new threads. The class FiniteThreadExample has four methods shown below that sets up things, handles the painting, and catches the mouse clicks:

• public void init()  This method creates an image and gets a Graphics context for that image.
• public void paint(Graphics)  This method paints the Image offImage on the screen.
• public void update(Graphics)  This method isn't really necessary. It overrides update(Graphics) in java.awt.Component, and is used to reduce flickering.
• public boolean mouseDown(Event, int, int)  This method is called when there is a mouse click in the applet. It creates a new instance of the classDrawTarget. DrawTarget is defined in the next class.

DrawTarget is where the threads are created to draw the targets. DrawTarget inherits properties from java.lang.Thread and has a single constructor and method, which are listed below:

• public DrawTarget(Applet a, int x, int y, Graphics g)  The constructor copies the parameters to instance variables and starts the thread. Applet is needed so the run method can tell the applet to repaint. The integers x and y are the coordinates of target. Graphics is the graphics context on which the targets are drawn. The thread is started by simply calling start().
• public void run()  This method is where the thread starts and draws the targets. It is called sometime after start() is called in the constructor. The method first sets offGraphics to XOR-Mode. In this mode, if something is drawn on something previously drawn, it reverts back to its original color. Next, the thread enters the nested for loops. Each iteration draws a circle, asks the applet to repaint, and sleeps for 200ms. The radius of the circle is varied from 10 to 80, and then from 80 back to 10. The thread dies on its own after it exits the loops, so there is no need to call stop().

Problems with Multithreading

Listing 16.3 shows how data can be corrupted in a multithreaded environment. If more than one thread manipulates shared variables or objects at the same time, corruption may result. Instance variables are shared between threads. If one is modified by a thread, the change affects the other threads. Method variables are unique for each threads. Each Thread has its own copy. Listing 16.3 uses 2 classes, ProblemThreadExample and CorruptedDataExample. The class ProblemThreadExample extends theApplet class. It has two methods, which are listed after Listing 16.3.

---

import java.lang.*;

import java.applet.Applet;

public class ProblemThreadExample extends Applet
{
  CorruptedDataExample CDE;

  public void start()
    {
      int i;

      CDE=new CorruptedDataExample();
      for(i=0;i<20;i++)  /* start 20 threads */
        new Thread(CDE,new String("booThread"+i)).start();
    }

  public void stop()
    {
      CDE.stopThreads();
    }
}

class CorruptedDataExample extends Object implements Runnable
{
  int num=0;  /* num will be corrupted  */

  public void run()
    {
      int i=0;
      for(;;)
        {
          for(i=0;i<1000;i++)
            {
              num=num+10;
              num=num-10;
            }

          try {Thread.sleep(10000);}
          catch (InterruptedException e ) {}
          System.out.println(Thread.currentThread().getName()+
                     " sees the number: " + num);
        }
    }

  void stopThreads()
    {
      Thread tArray[];
      int numThreads;

      numThreads=Thread.activeCount();
      tArray=new Thread[numThreads];
      Thread.enumerate(tArray);
      for(int i=0;i
      if(tArray[i].getName().startsWith("booThread"))
        tArray[i].stop();
    }
}

---

• public void start()  This method gets a new instance of the CorruptedDataExample class and starts 20 threads. Each thread has an individual name that is from "booThread0" to "booThread19". The threads start running in CorruptedDataExample's run method.
• public void stop()  This method calls stopThreads() in CorruptedDataExample. The class CorruptedDataExample does not guard against corruption of its instance variable num. The class has two methods, which are as follows:
• public void run()  This method has an infinite loop that shows how data can be corrupted by multiple threads. Twenty threads are executed in this loop at the same time. The loop does the following:
• Adds 10 then -10 to num 1000 times
• Sleeps
• Prints a string that contains num
• The first step is the cause of the corruption. It serves no purpose other than illustrating how data is corrupted.
• void stopThreads()  All of the booThreads are stopped in this method. A list of threads is fetched. All of the threads that have names that begin with booThreadare stopped.

The following is the ProblemThreadExample output:

booThread0 sees the number: 0
booThread1 sees the number: 0
booThread2 sees the number: 0
booThread3 sees the number: 0
booThread4 sees the number: 10
booThread6 sees the number: 10
booThread7 sees the number: 10
booThread8 sees the number: 10
booThread9 sees the number: 10
booThread10 sees the number: 0
booThread11 sees the number: 0
booThread12 sees the number: 0
booThread13 sees the number: 0
booThread5 sees the number: 0
booThread14 sees the number: 0
booThread15 sees the number: 0
booThread16 sees the number: 0
booThread17 sees the number: 0
booThread18 sees the number: 0
booThread19 sees the number: 0
booThread0 sees the number: 0
booThread1 sees the number: 0
booThread3 sees the number: 0
booThread4 sees the number: 0
booThread6 sees the number: 0
booThread8 sees the number: 0
booThread9 sees the number: 0
booThread2 sees the number: 0
booThread7 sees the number: 0
booThread10 sees the number: 10
booThread11 sees the number: 0
booThread12 sees the number: -10
booThread13 sees the number: -10
booThread5 sees the number: -10
booThread14 sees the number: -10
booThread16 sees the number: -10
booThread17 sees the number: -10
booThread18 sees the number: -10
booThread19 sees the number: -10

What Goes Wrong?

The first step in the infinite loop would have no ill effect in a single-threaded environment. It simply adds and then subtracts 10 to a variable with the net result being no change. However, in a multithreaded environment, the operations can interfere with each other. You can see one scenario in the following steps in which two threads try to add 10 at the same time.

Step	Thread A	Thread B	num
1.	Atmp num		0
2.	Atmp Atmp+10		0
3.		Btmp num	0
4.		Btmp Btmp+10	0
5.		num Btmp	10
.	.	.	.
.	.	.	.
.	.	.	.
10.	num Atmp		10

Two num=num+10; operations have been executed, but the value of num has only increased by 10. The problem here is that Thread A was interrupted in the middle of its operation before it could save its results. Threads A and B have added 10 to the same number.
This type of problem is somewhat rare, but should not be ignored. In the previous example, 10 is added and subtracted 1000 times in 20 threads, and the problem still did not occur that often. The bad thing about these types of bugs is that they can be extremely difficult to find. Imagine that num is the index of an array. The problem may not show up until long after num has been corrupted. Generally, these bugs are not reproducible, so they are hard to catch. In some ways the problem is amplified in Java because Java is expected to run on so many platforms. On some systems, num=num+10 may be an atomic operation (cannot be interrupted). In this case, everything works fine. A developer may create an applet on such a system thinking that everything is fine, but it may not work when someone from a different system views the applet. Data corruption can also be more common with other data types. Integer operations are simple compared to many others. Arrays or other data structures can take much longer to process so it is much more likely to be corrupted.

Thread Names and Current Threads

In Listing 16.3, the threads are given names. They are named booThread0 through booThread19 when they are created by the constructor Thread(Runnable,String). The names can be used to identify the threads. The thread names are printed along with num in the run() method of CorruptedDataExample. The Thread methodcurrent.Thread() is called to get a reference to the currently running thread.
The names are also used to stop the threads. A reference is needed for each thread so that stop() can be called to kill it. Thread.enumerate(Thread[]) gets a reference to every thread in this group. Some of these threads are the booThreads, but they may be others. The other threads should not be killed. Before each thread is killed it is checked to see if its name starts with booThread.

Java's synchronized

A way to prevent data from being corrupted by multiple threads is to prevent the interruption of critical regions. Critical regions are places like num=num+10 above, where only one thread should be running at once. Java's synchronized can be used to ensure that only one thread is in a critical region at once. When the thread enters a synchronized code block, it tries to get a lock on that region. While the thread is in the critical region, no other thread can enter the critical region. If a thread tries to enter and the code is already locked, the thread has to wait for the other thread to leave the critical region. Listing 16.3 can be fixed by synchronizing the access to num. The run()method in CorruptedDataExample can be modified to the following:

  public void run()
    {
      int i=0;
      int tmp;       /*new*/
      for(;;)
        {
          for(i=0;i<1000;i++)
            {
                synchronized (this)  /*new*/
                {
                  num=num+10;
                  num=num-10;
                }
            }

          try {Thread.sleep(10000);}
          catch (InterruptedException e ) {}
          synchronized (this)                    /*new*/
          {tmp=num;}                             /*new*/
          System.out.println(Thread.currentThread().getName()+
                     " sees the number: " + tmp); /*new*/
        }
    }

The following lines make up a protected critical region:

            synchronized (this)
        {
          num=num+10;
          num=num-10;
        }

synchronized (this) ensures that only one thread can be in the following code block. The argument this tells the thread to use the lock for this this object.
The variable num is also referenced when the string is printed. The new code is as follows:

      synchronized (this)                                 /*new*/
      {tmp=num;}                                           /*new*/
      System.out.println(currentThread().getName()+
                 " sees the number: " + tmp);     /*new*/

A critical region is used to copy num to temporary storage. The string is then printed using the temporary storage. It would have been possible to synchronize the print line directly, but it would cut performance because the print line does many other things that have nothing to do with referencing num. All the threads waiting to enter the critical region will needlessly wait longer while the print line is executed. Generally, the synchronized blocks should be as small as possible while still protecting the critical region.
You may also think that the other variables in the run method, i and tmp, also need to be synchronized, but it's not necessary. Both i and tmp are method variables so each running thread has its own private copy. There are 20 i's and tmp's but there is only one num.

Synchronizing Threads

Listing 16.4 can be seen in Figure 16.3. This example shows how synchronized can be used to control critical regions. There are two synchronized methods:drawRoundTarget() and drawSquareTarget(). If a thread is in a synchronized method, no other thread can be in any synchronized method that uses the same lock. This example draws only one square or circle at a time. The seven methods of the SynchronizedThreadExample applet are shown after Listing 16.4.

import java.applet.Applet;

import java.awt.*;

public class SynchronizedThreadExample extends Applet
implements Runnable
{
  Image offImage;        /* off screen image      */
  Graphics offGraphics;  /* Graphics for offImage */
  Thread Thr1, Thr2;     /* threads               */

  public void start()
    {
      offImage=createImage(400,300);
      offGraphics=offImage.getGraphics();
      offGraphics.setColor(Color.white);
      offGraphics.setXORMode(Color.blue);
      Thr1=new Thread(this);  Thr1.start();
      Thr2=new Thread(this);  Thr2.start();
    }

  public void stop()
    {
      Thr1.stop();
      Thr2.stop();
    }

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

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

  public void run()
    {
      for(;;)
        {
          drawRoundTarget();
          drawSquareTarget();
        }
    }

  synchronized void drawRoundTarget()
    {
      for(int r=0,i=10;i>-20;i-=20)  /* i=(10,-10)                */
        for(r+=i;(r<90)&&(r>0);r+=i) /* r=(10,20...80,80,70...10) */
          {
            offGraphics.fillOval(200-r,150-r,2*r,2*r);
            repaint();
            try {Thread.currentThread().sleep(200);}
            catch (InterruptedException e) {}
          }
    }

  synchronized void drawSquareTarget()
    {
      int i,r;
      for(r=0,i=10;i>-20;i-=20)      /* i=(10,-10)                */
        for(r+=i;(r<90)&&(r>0);r+=i) /* r=(10,20...80,80,70...10) */
          {
            offGraphics.fillRect (200-r,150-r,2*r,2*r);
            repaint();
            try {Thread.currentThread().sleep(250);}
            catch (InterruptedException e) {}
          }
    }
}

The methods of the SynchronizedThreadExample applet are as follows:

• public void start()/stop()  The threads are started and stopped in these methods.
• public void paint/update(Graphics)  These methods paint the applet.
• public void run()  Both threads start executing in this method. It is an infinite loop that draws round and then square targets.
• synchronized void drawRoundTarget()  This method is synchronized. Only one thread can be inside drawing circles.
• synchronized void drawSquareTarget()  This method is like drawRoundTarget, but draws squares instead of circles.

Multiple Locks

What if two locks are needed?
The current applet only allows one target to be drawn at a time, be it round or square. Suppose that you want the applet to draw a round and a square target at the same time; you would need two locks for two independent critical regions. The problem is that each object has only one lock. Creating separate classes for drawRoundTarget()and drawSquareTarget() could solve the problem, but it may not be convenient. A better way is to create new objects, and to use their locks to control the methods. This is done by modifying Listing 16.4 as follows:

       .             
       .             
       .             
  Object RoundSync,SquareSync;              /*new*/

  public void start()
    {
       .            .
       .            .
       .            .
      RoundSync=new Object();               /*new*/
      SquareSync=new Object();              /*new*/
      Thr1=new Thread(this);  Thr1.start();
      Thr2=new Thread(this);  Thr2.start();
    }

  void drawRoundTarget()
    {
      synchronized (RoundSync)              /*new*/
        {
          for(int r=0,i=10;i>-20;i-=20)
             .            .
             .            .
             .            .
        }
    }

   void drawSquareTarget()
    {
      synchronized (SquareSync)             /*new*/
        {
          for(r=0,i=10;i>-20;i-=20)
             .            .
             .            .
             .            .
        }
    }
}

Two new Objects are created: RoundSync and SquareSync. The Objects don't actually do anything themselves, but their locks are used when drawing the targets. The instances of Object are obtained in the start method. synchronized (RoundSync) is put in front of the for loops in the drawRoundTarget() method anddrawSquareTarget() is modified similarly. When a thread tries to execute the body of the target drawing methods, it first has to get a lock. drawRoundTarget() gets a lock from the object RoundSync and drawSquareTarget() gets a lock from SquareSync(). After these modifications have been made, the drawRoundTarget() anddrawSquareTargets() methods do not block each other. The applet draws round and square targets at the same time. But it is not able to draw two round targets or two square targets at the same time. Figure 16.4 shows the results of the modifications.
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.

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.

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
        Stick[i]=new Chopstick (i==0 ? Chopstick.gold :
                                       Chopstick.wood,
                                painter,i);
      for(i=0;i
        Phil[i]= new Philosopher(Stick[i],Stick[(i+1)%numPhils],
                                 painter,i);
     }

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

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

  public void destroy()
    {
      int i;
      for(i=0;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 theChopstick 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).

---

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);
    }

  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).

---

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.

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
        {
          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) anddrawSecondGrab(num) have been called. A philosopher in this state is represented by a small hollow square with a tiny circle in the middle.