Deadlock

The Producer-Consumer Relationship

There are cases where two or more running threads share resources and also depend on each other to update the resources. This is typified in the producer-consumer relationship where a producer thread produces a resource that a consumer thread consumes. Synchronizing each thread’s access to the resource can prevent race conditions but some mechanism is still needed for the threads to communicate with each other. Looking at it from the consumer’s point of view, if the consumer needs to consume a resource that the producer has net yet produced, then the consumer must wait until it is notified that the resource has been produced. Looking at it from the producer’s point of view, if storage is limited and the producer has temporarily stopped producing because there is no more room, then the producer will need to be notified when the consumer has consumed some of the storage.

In PiPanel1 (example 16.8), as you may remember, a producer thread kept producing digits and calling handleDigit() every time a new digit was produced. The handleDigit() method consumed the digits by calling displayDigit() which displayed them in a JTextArea. This was not a producer-consumer relationship because the call to displayDigit() was issued from the producer thread itself. In other words, the producer was its own consumer, making it a logical impossibility for it to produce a digit unless the previous digit had been consumed.

In PiPanelProdCons (example 16.20), we will separate out the consumer functionality into a separate thread to create a true producer-consumer relationship. First, take a look at DefaultDigitHolder.java (example 16.19) which implements DigitHolder (example 16.18). PiPanelProdCons will use an instance of DefaultDigitHolder as the storage facility for a single digit. The producer thread will store digits into it and the consumer thread will retrieve digits from it. Notice that whenever store() is called, the previously stored digit value will be overwritten by the new value. DefaultDigitHolder has a storage capacity of one digit.

Example 16.20: chap16.prodcons.PiPanelProdCons.java

 1      package chap16.prodcons; 2 3      import java.awt.BorderLayout; 4 5      import javax.swing.JFrame; 6 7      import chap16.pi.PiPanel1; 8 9      public class PiPanelProdCons extends PiPanel1 { 10       private DigitHolder holder; 11 12       public PiPanelProdCons(DigitHolder holder) { 13         this.holder = holder; 14         startConsumer(); 15       } 16       private void startConsumer() { 17         Thread consumerThread = new Thread() { 18           public void run() { 19             while (true) { 20               int digit = holder.retrieve(); 21               displayDigit(digit); 22             } 23           } 24         }; 25         consumerThread.start(); 26       } 27       //called constantly by producer thread 28       protected void handleDigit(int digit) { 29         holder.store(digit); 30       } 31       public static void main(String[] arg) { 32         JFrame f = new JFrame(); 33         f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); 34         DigitHolder holder = null; 35         if (arg.length > 0) { 36           if ("bad".equals(arg[0])) { 37             holder = new BadDigitHolder(); 38           } else if ("good".equals(arg[0])) { 39             holder = new GoodDigitHolder(); 40           } 41         } 42         if (holder == null) { 43           holder = new DefaultDigitHolder(); 44         } 45         f.getContentPane().add(new PiPanelProdCons(holder), BorderLayout.CENTER); 46         f.getContentPane().add(new chap16.clock.ClockPanel1(), BorderLayout.NORTH); 47         f.pack(); 48         f.show(); 49       } 50     }

Example 16.19: chap16.prodcons.DefaultDigitHolder.java

 1      package chap16.prodcons; 2 3      public class DefaultDigitHolder implements DigitHolder { 4        private int digit; 5 6        public void store(int digit) { 7          this.digit = digit; 8        } 9        public int retrieve() { 10         return digit; 11       } 12     }

Example 16.18: chap16.prodcons.DigitHolder

 1     package chap16.prodcons; 2 3     public interface DigitHolder { 4       public void store(int digit); 5       public int retrieve(); 6     }

PiPanelProdCons extends PiPanel1. It overrides handleDigit() to store the digit in a DigitHolder thereby removing the consumer functionality from the producer thread. PiPanelProdCons’s constructor creates and starts a consumer thread that continuously (and rapidly) retrieves digits from the DigitHolder and calls displayDigit(). The displayDigit() method, as we remember from PiPanel1, appends to the JTextArea whatever digit the consumer gives it. This is a true consumer-producer relationship in that the producer keeps producing and the consumer keeps consuming. Unfortunately, there is no coordination between the two.

PiPanelProdCons can run in three modes: “default”, “good” and “bad” depending on its command line arguments. These modes specify whether to use an instance of DefaultDigitHolder itself or a particular subclass of it. The absence of command-line arguments will cause PiPanelProdCons to use an instance of DefaultDigitHolder.

Try to predict what will happen when the program uses a DefaultDigitHolder. Remember that the consumer thread will be started by PiPanelProdCons’s constructor so it will be running before the press of the “Play” button has even started the producer thread. When you think you know what will happen, run the program and find out. Make sure you press the Pause/Play button at least once to start the producer thread.

Use the following commands to compile and run the examples. From the directory containing the src folder:

  javac –d classes -sourcepath src src/chap16/prodcons/PiPanelProdCons.java  java –cp classes chap16.prodcons.PiPanelProdCons

Were you surprised by the results? Since it’s a lot quicker to consume a digit of pi than it is to produce it, the consumer thread is able to get and display the most recent digit many times before the producer thread is able to produce the next digit. Running PiPanelProdCons using a DefaultDigitHolder simply highlights the need to coordinate the producer and consumer threads’ activities.

Example 16.21,  BadDigitHolder.java tries, unsuccessfully, to fix the problem by synchronizing DefaultDigitHolder’s store and retrieve methods. The synchronization is successful, as far as it goes, in preventing more than one thread from storing simultaneously or retrieving simultaneously. Furthermore, because both methods synchronize on the same object, it even prevents one thread from storing while another is retrieving. Unfortunately, it does nothing further to coordinate the producer and consumer threads’ activities. Run the program again with a command line argument of “bad” to use BadDigitHolder and to verify that synchronization alone will not be enough in this case.

Example 16.21: chap16.prodcons.BadDigitHolder.java

 1        package chap16.prodcons; 2 3        public class BadDigitHolder extends DefaultDigitHolder { 4          public synchronized void store(int digit) { 5            super.store(digit); 6          } 7          public synchronized int retrieve() { 8            return super.retrieve(); 9          } 10      }

Use the following command to execute the example. From the directory containing the src folder:

      java –cp classes chap16.prodcons.PiPanelProdCons bad

The real problem to be solved is that the consumer thread needs to be notified when the producer thread has produced a digit, and the producer thread needs to be notified when the consumer thread has consumed a digit. The Object class itself defines five methods that can be used to achieve an inter-thread notification mechanism. These methods, listed in table 16-10, are useful when threads need to wait on conditions that are set by other threads.

Method Name and Purpose

public final void wait() throws InterruptedException

Causes the current thread to wait for another thread to call notify() or notifyAll() on this same object.

public final void wait(long timeout) throws InterruptedException

Causes the current thread to wait no longer than the specified time for another thread to call notify() or notifyAll() on this same object.

public final void wait(long timeout, int nanos) throws InterruptedException

Causes the current thread to wait no longer than the specified time for another thread to call notify() or notifyAll() on this same object.

public final void notify()

Wakes up one thread (chosen by the JVM) that is waiting for this object’s lock.

public final void notifyAll()

Wakes up all threads that are waiting for this object’s lock. They will still have to compete as usual for ownership of the lock.

A thread that attempts to invoke these methods on an object will throw an IllegalMonitorStateException unless that thread owns the object’s lock. (Being a subclass of RuntimeException, IllegalMonitorStateException need not be declared or caught.) Invoking wait() on an object causes the current thread to give up ownership of the object’s lock and to suspend execution until another thread invokes either interrupt() on the waiting thread or notify() or notifyAll() on the object for which the thread is waiting. If a thread invokes the notifyAll() method on an object, then all threads that are waiting for that object are woken. If a thread invokes notify() on an object, the scheduler chooses just one thread to wake up from among the threads waiting for that object. Waiting threads are woken with an InterruptedEx-ception which they may handle however they choose. In the case of the timed wait() methods, a waiting thread will automatically exit the wait state if the specified time passes without a notification or interruption.

In example 16.22, GoodDigitHolder solves the producer-consumer coordination through the use of the wait() and notify() methods in conjunction with the boolean field, haveDigit, which indicates whether a digit was most recently retrieved or stored. If a digit was most recently stored, then haveDigit will be true, meaning that a digit is available for consumption. If a digit was most recently retrieved, then haveDigit will be false, meaning than a new digit will need to be stored before one is available for consumption. Because of the way the while loops are constructed, a thread that is waiting to store a digit will repeatedly wait until haveDigit is false. Conversely, a thread that is waiting to retrieve a digit will repeatedly wait until haveDigit is true.

Example 16.22: chap16.prodcons.GoodDigitHolder

 1      package chap16.prodcons; 2 3      public class GoodDigitHolder extends DefaultDigitHolder { 4        private boolean haveDigit = false; 5 6        public synchronized void store(int digit) { 7          while (haveDigit) { 8            try { 9              wait(); 10           } catch (InterruptedException e) {} 11         } 12         super.store(digit); 13         haveDigit = true; 14         notify(); 15       } 16       public synchronized int retrieve() { 17         while (!haveDigit) { 18           try { 19             wait(); 20           } catch (InterruptedException e) {} 21         } 22         haveDigit = false; 23         notify(); 24         return super.retrieve(); 25       } 26     }

Notice in lines 9 and 14 that the object upon which GoodDigitHolder invokes wait() and notify() is the GoodDigitHolder instance itself. Since these invocations occur within methods that are synchronized on the GoodDigitHolder instance, an IllegalMonitorStateException will not be thrown.

Use the following command to execute the example. From the directory containing the src folder:

      java –cp classes chap16.prodcons.PiPanel2 good

If this all seems clear to you, great. But in case it isn’t, we’ll look at what’s happening in greater detail. First, we’ll look at things from the consumer’s point of view. If the consumer thread calls retrieve() when haveDigit is false, it means that the producer has not yet stored another digit. The consumer will enter the wait state from which it will not exit until it is either notified or interrupted. When it does exit wait(), it will have reacquired the lock and it will again check the loop condition (possibly causing it to repeat the waiting process). Consequently, the consumer thread will not exit the while loop unless haveDigit is true (meaning that a new digit has been produced). When, if ever, haveDigit becomes true, it will set haveDigit to false, the stored digit will be returned and any threads waiting for the lock will be notified that this might be a good time to wake up and try again. In particular, if the producer thread is waiting, it will wake up and discover that it is now safe to store another digit. Figure 16-13 shows what might happen if haveDigit is false when the consumer thread calls retrieve().

Figure 16-13: Consumer Thread Waits

Now let’s look at things from the producer’s point of view. If the producer thread calls store() when haveDigit is true, it means that the consumer has not yet retrieved the most recently stored digit. The producer will enter the wait state from which it will not exit until it is either notified or interrupted. When it does exit wait(), it will have reacquired the lock and it will again check the loop condition (possibly causing it to repeat the waiting process). Consequently, the producer thread will not exit the while loop unless haveDigit is false (meaning that the most recently stored digit has been consumed). When, if ever, haveDigit becomes false, it will set haveDigit to true, the newly produced digit will be stored and any threads waiting for the lock will be notified that this might be a good time to wake up and try again. In particular, if the consumer thread is waiting, it will wake up and discover that it is now safe to retrieve a digit. Figure 16-14 shows what might happen if haveDigit is true when the producer thread calls store().

Figure 16-14: Producer Thread Waits

Earlier in the chapter in PiPanel1 (example 16.8), the Swing event thread needed to notify a paused producer thread whenever the user pressed the “Play” button. PiPanel1 used sleep() and interrupt() to effect this notification, but wait() and notify() are more appropriate. PiPanel2 (example 16.22) extends PiPanel1 solely to re-implement pauseImpl() and playImpl() using wait() and notify(). In order for wait() and notify() to work together, a single object on which to synchronize needs to be chosen. Any object including the PiPanel2 instance itself could work, but in this case using the PiPanel2 instance wouldn’t be a good idea. If PiPanel1 were ever modified to perform some synchronization on itself, there could be unintended implications on previously written subclasses (such as PiPanel2) that were also using “this” for their own synchronization. For this reason, we choose to synchronize pauseImpl() and playImpl() on an object known only to PiPanel2.

Example 16.23: chap16.prodcons.PiPanel2.java

 1      package chap16.prodcons; 2 3      import chap16.pi.PiPanel1; 4 5      public class PiPanel2 extends PiPanel1 { 6        private Object lock = new Object(); 7 8        protected void pauseImpl() { 9          synchronized (lock) { 10           try { 11             lock.wait(); 12           } catch (InterruptedException e) {} 13         } 14       } 15       protected void playImpl() { 16         synchronized (lock) { 17           lock.notify(); 18         } 19       } 20     }

Use the following commands to compile and excecute the example. From the directory containing the src folder:

      javac –d classes -sourcepath src src/chap16/prodcons/PiPanel2.java      java –cp classes chap16.prodcons.PiPanel2

Quick Review

In a producer-consumer relationship a producer thread produces something that a consumer thread consumes and neither thread makes an effort to coordinate with the other. Coordination is handled instead by the object they both access. The wait() and notify() methods of Object can be used to negotiate the coordination between inter-dependent threads.