MindView Inc.

Thinking in Java, 3rd ed. Revision 4.0


[ Viewing Hints ] [ Book Home Page ] [ Free Newsletter ]
[ Seminars ] [ Seminars on CD ROM ] [ Consulting ]

Previous Next Title Page Index Contents

13: Concurrency

Objects provide a way to divide a program into independent sections. Often, you also need to turn a program into separate, independently running subtasks.

Each of these independent subtasks is called a thread, and you program as if each thread runs by itself and has the CPU to itself. Some underlying mechanism is actually dividing up the CPU time for you, but in general, you don’t have to think about it, which makes programming with multiple threads a much easier task. Feedback

A process is a self-contained running program with its own address space. A multitasking operating system is capable of running more than one process (program) at a time, while making it look like each one is chugging along on its own, by periodically switching the CPU from one task to another. A thread is a single sequential flow of control within a process. A single process can thus have multiple concurrently executing threads. Feedback

There are many possible uses for multithreading, but in general, you’ll have some part of your program tied to a particular event or resource, and you don’t want that to hold up the rest of your program. So, you create a thread associated with that event or resource and let it run independently of the main program. Feedback

Concurrent programming is like stepping into an entirely new world and learning a new programming language, or at least a new set of language concepts. With the appearance of thread support in most microcomputer operating systems, extensions for threads have also been appearing in programming languages or libraries. In all cases, thread programming:

  1. Seems mysterious and requires a shift in the way you think about programming
  2. Looks similar to thread support in other languages, so when you understand threads, you understand a common tongue

And although support for threads can make Java a more complicated language, this isn’t entirely the fault of Java—threads are tricky. Feedback

Understanding concurrent programming is on the same order of difficulty as understanding polymorphism. If you apply some effort, you can fathom the basic mechanism, but it generally takes deep study and understanding in order to develop a true grasp of the subject. The goal of this chapter is to give you a solid foundation in the basics of concurrency so that you can understand the concepts and write reasonable multithreaded programs. Be aware that you can easily become overconfident, so if you are writing anything complex, you will need to study dedicated books on the topic. Feedback

Motivation

One of the most compelling reasons for concurrency is to produce a responsive user interface. Consider a program that performs some CPU-intensive operation and thus ends up ignoring user input and being unresponsive. The basic problem is that the program needs to continue performing its operations, and at the same time it needs to return control to the user interface so that the program can respond to the user. If you have a “quit” button, you don’t want to be forced to poll it in every piece of code you write in your program, and yet you want the quit button to be responsive, as if you were checking it regularly. Feedback

A conventional method cannot continue performing its operations and at the same time return control to the rest of the program. In fact, this sounds like an impossible thing to accomplish, as if the CPU must be in two places at once, but this is precisely the illusion that concurrency provides. Feedback

Concurrency can also be used to optimize throughput. For example, you might be able to do important work while you’re stuck waiting for input to arrive on an I/O port. Without threading, the only reasonable solution is to poll the I/O port, which is awkward and can be difficult. Feedback

If you have a multiprocessor machine, multiple threads may be distributed across multiple processors, which can dramatically improve throughput. This is often the case with powerful multiprocessor web servers, which can distribute large numbers of user requests across CPUs in a program that allocates one thread per request. Feedback

One thing to keep in mind is that a program with many threads must be able to run on a single-CPU machine. Therefore, it must also be possible to write the same program without using any threads. However, multithreading provides a very important organizational benefit, so that the design of your program can be greatly simplified. Some types of problems, such as simulation—a video game, for example—are very difficult to solve without support for concurrency. Feedback

The threading model is a programming convenience to simplify juggling several operations at the same time within a single program. With threads, the CPU will pop around and give each thread some of its time. Each thread has the consciousness of constantly having the CPU to itself, but the CPU’s time is actually sliced between all the threads. The exception to this is if your program is running on multiple CPUs, but one of the great things about threading is that you are abstracted away from this layer, so your code does not need to know whether it is actually running on a single CPU or many. Thus, threads are a way to create transparently scalable programs—if a program is running too slowly, it can easily be made faster by adding CPUs to your computer. Multitasking and multithreading tend to be the most reasonable ways to utilize multiprocessor systems. Feedback

Threading can reduce computing efficiency somewhat in single-CPU machines, but the net improvement in program design, resource balancing, and user convenience is often quite valuable. In general, threads enable you to create a more loosely-coupled design; otherwise, parts of your code would be forced to pay explicit attention to tasks that would normally be handled by threads. Feedback

Basic threads

The simplest way to create a thread is to inherit from java.lang.Thread, which has all the wiring necessary to create and run threads. The most important method for Thread is run( ), which you must override to make the thread do your bidding. Thus, run( ) is the code that will be executed “simultaneously” with the other threads in a program. Feedback

The following example creates five threads, each with a unique identification number generated with a static variable. The Thread’s run( ) method is overridden to count down each time it passes through its loop and to return when the count is zero (at the point when run( ) returns, the thread is terminated by the threading mechanism). Feedback

//: c13:SimpleThread.java
// Very simple Threading example.
import com.bruceeckel.simpletest.*;

public class SimpleThread extends Thread {
  private static Test monitor = new Test();
  private int countDown = 5;
  private static int threadCount = 0;
  public SimpleThread() {
    super("" + ++threadCount); // Store the thread name
    start();
  }
  public String toString() {
    return "#" + getName() + ": " + countDown;
  }
  public void run() {
    while(true) {
      System.out.println(this);
      if(--countDown == 0) return;
    }
  }
  public static void main(String[] args) {
    for(int i = 0; i < 5; i++)
      new SimpleThread();
    monitor.expect(new String[] {
      "#1: 5",
      "#2: 5",
      "#3: 5",
      "#5: 5",
      "#1: 4",
      "#4: 5",
      "#2: 4",
      "#3: 4",
      "#5: 4",
      "#1: 3",
      "#4: 4",
      "#2: 3",
      "#3: 3",
      "#5: 3",
      "#1: 2",
      "#4: 3",
      "#2: 2",
      "#3: 2",
      "#5: 2",
      "#1: 1",
      "#4: 2",
      "#2: 1",
      "#3: 1",
      "#5: 1",
      "#4: 1"
    }, Test.IGNORE_ORDER + Test.WAIT);
  }
} ///:~


The thread objects are given specific names by calling the appropriate Thread constructor. This name is retrieved in toString( ) using getName( ).

A Thread object’s run( ) method virtually always has some kind of loop that continues until the thread is no longer necessary, so you must establish the condition on which to break out of this loop (or, as in the preceding program, simply return from run( )). Often, run( ) is cast in the form of an infinite loop, which means that, barring some factor that causes run( ) to terminate, it will continue forever (later in the chapter you’ll see how to safely signal a thread to stop). Feedback

In main( ) you can see a number of threads being created and run. The start( ) method in the Thread class performs special initialization for the thread and then calls run( ). So the steps are: the constructor is called to build the object, it calls start( ) to configure the thread, and the thread execution mechanism calls run( ). If you don’t call start( ) (which you don’t have to do in the constructor, as you will see in subsequent examples), the thread will never be started. Feedback

The output for one run of this program will be different from that of another, because the thread scheduling mechanism is not deterministic. In fact, you may see dramatic differences in the output of this simple program between one version of the JDK and the next. For example, a previous JDK didn’t time-slice very often, so thread 1 might loop to extinction first, then thread 2 would go through all of its loops, etc. This was virtually the same as calling a routine that would do all the loops at once, except that starting up all those threads is more expensive. In JDK 1.4 you get something like the output from SimpleThread.java, which indicates better time-slicing behavior by the scheduler—each thread seems to be getting regular service. Generally, these kinds of JDK behavioral changes have not been mentioned by Sun, so you cannot plan on any consistent threading behavior. The best approach is to be as conservative as possible while writing threading code. Feedback

When main( ) creates the Thread objects, it isn’t capturing the references for any of them. With an ordinary object, this would make it fair game for garbage collection, but not with a Thread. Each Thread “registers” itself so there is actually a reference to it someplace, and the garbage collector can’t clean it up until the thread exits its run( ) and dies. Feedback

Yielding

If you know that you’ve accomplished what you need to in your run( ) method, you can give a hint to the thread scheduling mechanism that you’ve done enough and that some other thread might as well have the CPU. This hint (and it is a hint—there’s no guarantee your implementation will listen to it) takes the form of the yield( ) method. Feedback

We can modify the preceding example by yielding after each loop:

//: c13:YieldingThread.java
// Suggesting when to switch threads with yield().
import com.bruceeckel.simpletest.*;

public class YieldingThread extends Thread {
  private static Test monitor = new Test();
  private int countDown = 5;
  private static int threadCount = 0;
  public YieldingThread() {
    super("" + ++threadCount);
    start();
  }
  public String toString() {
    return "#" + getName() + ": " + countDown;
  }
  public void run() {
    while(true) {
      System.out.println(this);
      if(--countDown == 0) return;
      yield();
    }
  }
  public static void main(String[] args) {
    for(int i = 0; i < 5; i++)
      new YieldingThread();
    monitor.expect(new String[] {
      "#1: 5",
      "#2: 5",
      "#4: 5",
      "#5: 5",
      "#3: 5",
      "#1: 4",
      "#2: 4",
      "#4: 4",
      "#5: 4",
      "#3: 4",
      "#1: 3",
      "#2: 3",
      "#4: 3",
      "#5: 3",
      "#3: 3",
      "#1: 2",
      "#2: 2",
      "#4: 2",
      "#5: 2",
      "#3: 2",
      "#1: 1",
      "#2: 1",
      "#4: 1",
      "#5: 1",
      "#3: 1"
    }, Test.IGNORE_ORDER + Test.WAIT);
  }
} ///:~


By using yield( ), the output is evened up quite a bit. But note that if the output string is longer, you will see output that is roughly the same as it was in SimpleThread.java (try it—change toString( ) to put out longer and longer strings to see what happens). Since the scheduling mechanism is preemptive, it decides to interrupt a thread and switch to another whenever it wants, so if I/O (which is executed via the main( ) thread) takes too long, it is interrupted before run( ) has a chance to yield( ). In general, yield( ) is useful only in rare situations, and you can’t rely on it to do any serious tuning of your application. Feedback

Sleeping

Another way you can control the behavior of your threads is by calling sleep( ) to cease execution for a given number of milliseconds. In the preceding example, if you replace the call to yield( ) with a call to sleep( ), you get the following: Feedback

//: c13:SleepingThread.java
// Calling sleep() to wait for awhile.
import com.bruceeckel.simpletest.*;

public class SleepingThread extends Thread {
  private static Test monitor = new Test();
  private int countDown = 5;
  private static int threadCount = 0;
  public SleepingThread() {
    super("" + ++threadCount);
    start();
  }
  public String toString() {
    return "#" + getName() + ": " + countDown;
  }
  public void run() {
    while(true) {
      System.out.println(this);
      if(--countDown == 0) return;
      try {
        sleep(100);
      } catch (InterruptedException e) {
        throw new RuntimeException(e);
      }
    }
  }
  public static void
  main(String[] args) throws InterruptedException {
    for(int i = 0; i < 5; i++)
      new SleepingThread().join();
    monitor.expect(new String[] {
      "#1: 5",
      "#1: 4",
      "#1: 3",
      "#1: 2",
      "#1: 1",
      "#2: 5",
      "#2: 4",
      "#2: 3",
      "#2: 2",
      "#2: 1",
      "#3: 5",
      "#3: 4",
      "#3: 3",
      "#3: 2",
      "#3: 1",
      "#4: 5",
      "#4: 4",
      "#4: 3",
      "#4: 2",
      "#4: 1",
      "#5: 5",
      "#5: 4",
      "#5: 3",
      "#5: 2",
      "#5: 1"
    });
  }
} ///:~


When you call sleep( ), it must be placed inside a try block because it’s possible for sleep( ) to be interrupted before it times out. This happens if someone else has a reference to the thread and they call interrupt( ) on the thread (interrupt( ) also affects the thread if wait( ) or join( ) has been called for it, so those calls must be in a similar try block—you’ll learn about those methods later). Usually, if you’re going to break out of a suspended thread using interrupt( ) you will use wait( ) rather than sleep( ), so that ending up inside the catch clause is unlikely. Here, we follow the maxim “don’t catch an exception unless you know what to do with it” by re-throwing it as a RuntimeException. Feedback

You’ll notice that the output is deterministic—each thread counts down before the next one starts. This is because join( ) (which you’ll learn about shortly) is used on each thread, so that main( ) waits for the thread to complete before continuing. If you did not use join( ), you’d see that the threads tend to run in any order, which means that sleep( ) is also not a way for you to control the order of thread execution. It just stops the execution of the thread for awhile. The only guarantee that you have is that the thread will sleep at least 100 milliseconds, but it may take longer before the thread resumes execution, because the thread scheduler still has to get back to it after the sleep interval expires. Feedback

If you must control the order of execution of threads, your best bet is not to use threads at all, but instead to write your own cooperative routines that hand control to each other in a specified order. Feedback

Priority

The priority of a thread tells the scheduler how important this thread is. Although the order that the CPU attends to an existing set of threads is indeterminate, if there are a number of threads blocked and waiting to be run, the scheduler will lean toward the one with the highest priority first. However, this doesn’t mean that threads with lower priority aren’t run (that is, you can’t get deadlocked because of priorities). Lower priority threads just tend to run less often. Feedback

Here’s SimpleThread.java modified so that the priority levels are demonstrated. The priorities are adjusting by using Thread’s setPriority( ) method.

//: c13:SimplePriorities.java
// Shows the use of thread priorities.
import com.bruceeckel.simpletest.*;

public class SimplePriorities extends Thread {
  private static Test monitor = new Test();
  private int countDown = 5;
  private volatile double d = 0; // No optimization
  public SimplePriorities(int priority) {
    setPriority(priority);
    start();
  }
  public String toString() {
    return super.toString() + ": " + countDown;
  }
  public void run() {
    while(true) {
      // An expensive, interruptable operation:
      for(int i = 1; i < 100000; i++)
        d = d + (Math.PI + Math.E) / (double)i;
      System.out.println(this);
      if(--countDown == 0) return;
    }
  }
  public static void main(String[] args) {
    new SimplePriorities(Thread.MAX_PRIORITY);
    for(int i = 0; i < 5; i++)
      new SimplePriorities(Thread.MIN_PRIORITY);
    monitor.expect(new String[] {
      "Thread[Thread-1,10,main]: 5",
      "Thread[Thread-1,10,main]: 4",
      "Thread[Thread-1,10,main]: 3",
      "Thread[Thread-1,10,main]: 2",
      "Thread[Thread-1,10,main]: 1",
      "Thread[Thread-2,1,main]: 5",
      "Thread[Thread-2,1,main]: 4",
      "Thread[Thread-2,1,main]: 3",
      "Thread[Thread-2,1,main]: 2",
      "Thread[Thread-2,1,main]: 1",
      "Thread[Thread-3,1,main]: 5",
      "Thread[Thread-4,1,main]: 5",
      "Thread[Thread-5,1,main]: 5",
      "Thread[Thread-6,1,main]: 5",
      "Thread[Thread-3,1,main]: 4",
      "Thread[Thread-4,1,main]: 4",
      "Thread[Thread-5,1,main]: 4",
      "Thread[Thread-6,1,main]: 4",
      "Thread[Thread-3,1,main]: 3",
      "Thread[Thread-4,1,main]: 3",
      "Thread[Thread-5,1,main]: 3",
      "Thread[Thread-6,1,main]: 3",
      "Thread[Thread-3,1,main]: 2",
      "Thread[Thread-4,1,main]: 2",
      "Thread[Thread-5,1,main]: 2",
      "Thread[Thread-6,1,main]: 2",
      "Thread[Thread-4,1,main]: 1",
      "Thread[Thread-3,1,main]: 1",
      "Thread[Thread-6,1,main]: 1",
      "Thread[Thread-5,1,main]: 1"
    }, Test.IGNORE_ORDER + Test.WAIT);
  }
} ///:~


In this version, toString( ) is overridden to use Thread.toString( ), which prints the thread name (which you can set yourself via the constructor; here it’s automatically generated as Thread-1, Thread-2, etc.), the priority level, and the “thread group” that the thread belongs to. Because the threads are self-identifying, there is no threadNumber in this example. The overridden toString( ) also shows the countdown value of the thread. Feedback

You can see that the priority level of thread 1 is at the highest level, and all the rest of the threads are at the lowest level. Feedback

Inside run( ), 100,000 repetitions of a rather expensive floating-point calculation have been added, involving double addition and division. The variable d has been made volatile to ensure that no optimization is performed. Without this calculation, you don’t see the effect of setting the priority levels (try it: comment out the for loop containing the double calculations). With the calculation, you see that thread 1 is given a higher preference by the thread scheduler (at least, this was the behavior on my Windows 2000 machine). Even though printing to the console is also an expensive behavior, you won’t see the priority levels that way, because console printing doesn’t get interrupted (otherwise, the console display would get garbled during threading), whereas the math calculation can be interrupted. The calculation takes long enough that the thread scheduling mechanism jumps in and changes threads, and pays attention to the priorities so that thread 1 gets preference. Feedback

You can also read the priority of an existing thread with getPriority( ) and change it at any time (not just in the constructor, as in SimplePriorities.java) with setPriority( ).

Although the JDK has 10 priority levels, this doesn’t map well to many operating systems. For example, Windows 2000 has 7 priority levels that are not fixed, so the mapping is indeterminate (although Sun’s Solaris has 231 levels). The only portable approach is to stick to MAX_PRIORITY, NORM_PRIORITY, and MIN_PRIORITY when you’re adjusting priority levels. Feedback

Daemon threads

A “daemon” thread is one that is supposed to provide a general service in the background as long as the program is running, but is not part of the essence of the program. Thus, when all of the non-daemon threads complete, the program is terminated. Conversely, if there are any non-daemon threads still running, the program doesn’t terminate. There is, for instance, a non-daemon thread that runs main( ). Feedback

//: c13:SimpleDaemons.java
// Daemon threads don't prevent the program from ending.

public class SimpleDaemons extends Thread {
  public SimpleDaemons() {
    setDaemon(true); // Must be called before start()
    start();
  }
  public void run() {
    while(true) {
      try {
        sleep(100);
      } catch (InterruptedException e) {
        throw new RuntimeException(e);
      }
      System.out.println(this);
    }
  }
  public static void main(String[] args) {
    for(int i = 0; i < 10; i++)
      new SimpleDaemons();
  }
} ///:~


You must set the thread to be a daemon by calling setDaemon( ) before it is started. In run( ), the thread is put to sleep for a little bit. Once the threads are all started, the program terminates immediately, before any threads can print themselves, because there are no non-daemon threads (other than main( )) holding the program open. Thus, the program terminates without printing any output.

You can find out if a thread is a daemon by calling isDaemon( ). If a thread is a daemon, then any threads it creates will automatically be daemons, as the following example demonstrates: Feedback

//: c13:Daemons.java
// Daemon threads spawn other daemon threads.
import java.io.*;
import com.bruceeckel.simpletest.*;

class Daemon extends Thread {
  private Thread[] t = new Thread[10];
  public Daemon() {
    setDaemon(true);
    start();
  }
  public void run() {
    for(int i = 0; i < t.length; i++)
      t[i] = new DaemonSpawn(i);
    for(int i = 0; i < t.length; i++)
      System.out.println("t[" + i + "].isDaemon() = "
        + t[i].isDaemon());
    while(true)
      yield();
  }
}

class DaemonSpawn extends Thread {
  public DaemonSpawn(int i) {
    start();
    System.out.println("DaemonSpawn " + i + " started");
  }
  public void run() {
    while(true)
      yield();
  }
}

public class Daemons {
  private static Test monitor = new Test();
  public static void main(String[] args) throws Exception {
    Thread d = new Daemon();
    System.out.println("d.isDaemon() = " + d.isDaemon());
    // Allow the daemon threads to
    // finish their startup processes:
    Thread.sleep(1000);
    monitor.expect(new String[] {
      "d.isDaemon() = true",
      "DaemonSpawn 0 started",
      "DaemonSpawn 1 started",
      "DaemonSpawn 2 started",
      "DaemonSpawn 3 started",
      "DaemonSpawn 4 started",
      "DaemonSpawn 5 started",
      "DaemonSpawn 6 started",
      "DaemonSpawn 7 started",
      "DaemonSpawn 8 started",
      "DaemonSpawn 9 started",
      "t[0].isDaemon() = true",
      "t[1].isDaemon() = true",
      "t[2].isDaemon() = true",
      "t[3].isDaemon() = true",
      "t[4].isDaemon() = true",
      "t[5].isDaemon() = true",
      "t[6].isDaemon() = true",
      "t[7].isDaemon() = true",
      "t[8].isDaemon() = true",
      "t[9].isDaemon() = true"
    }, Test.IGNORE_ORDER + Test.WAIT);
  }
} ///:~


The Daemon thread sets its daemon flag to “true” and then spawns a bunch of other threads—which do not set themselves to daemon mode—to show that they are daemons anyway. Then it goes into an infinite loop that calls yield( ) to give up control to the other processes. Feedback

There’s nothing to keep the program from terminating once main( ) finishes its job, since there are nothing but daemon threads running. So that you can see the results of starting all the daemon threads, the main( ) thread is put to sleep for a second. Without this, you see only some of the results from the creation of the daemon threads. (Try sleep( ) calls of various lengths to see this behavior.) Feedback

Joining a thread

One thread may call join( ) on another thread to wait for the second thread to complete before proceeding. If a thread calls t.join( ) on another thread t, then the calling thread is suspended until the target thread t finishes (when t.isAlive( ) is false).

You may also call join( ) with a timeout argument (in either milliseconds or milliseconds and nanoseconds) so that if the target thread doesn’t finish in that period of time, the call to join( ) returns anyway.

The call to join( ) may be aborted by calling interrupt( ) on the calling thread, so a try-catch clause is required.

All of these operations are shown in the following example:

//: c13:Joining.java
// Understanding join().
import com.bruceeckel.simpletest.*;

class Sleeper extends Thread {
  private int duration;
  public Sleeper(String name, int sleepTime) {
    super(name);
    duration = sleepTime;
    start();
  }
  public void run() {
    try {
      sleep(duration);
    } catch (InterruptedException e) {
      System.out.println(getName() + " was interrupted. " +
        "isInterrupted(): " + isInterrupted());
      return;
    }
    System.out.println(getName() + " has awakened");
  }
}

class Joiner extends Thread {
  private Sleeper sleeper;
  public Joiner(String name, Sleeper sleeper) {
    super(name);
    this.sleeper = sleeper;
    start();
  }
  public void run() {
   try {
      sleeper.join();
    } catch (InterruptedException e) {
      throw new RuntimeException(e);
    }
    System.out.println(getName() + " join completed");
  }
}

public class Joining {
  private static Test monitor = new Test();
  public static void main(String[] args) {
    Sleeper
      sleepy = new Sleeper("Sleepy", 1500),
      grumpy = new Sleeper("Grumpy", 1500);
    Joiner
      dopey = new Joiner("Dopey", sleepy),
      doc = new Joiner("Doc", grumpy);
    grumpy.interrupt();
    monitor.expect(new String[] {
      "Grumpy was interrupted. isInterrupted(): false",
      "Doc join completed",
      "Sleepy has awakened",
      "Dopey join completed"
    }, Test.AT_LEAST + Test.WAIT);
  }
} ///:~


A Sleeper is a type of Thread that goes to sleep for a time specified in its constructor. In run( ), the call to sleep( ) may terminate when the time expires, but it may also be interrupted. Inside the catch clause, the interruption is reported, along with the value of isInterrupted( ). When another thread calls interrupt( ) on this thread, a flag is set to indicate that the thread has been interrupted. However, this flag is cleared when the exception is caught, so the result will always be false inside the catch clause. The flag is used for other situations where a thread may examine its interrupted state apart from the exception.

A Joiner is a thread that waits for a Sleeper to wake up by calling join( ) on the Sleeper object. In main( ), each Sleeper has a Joiner, and you can see in the output that if the Sleeper is either interrupted or if it ends normally, the Joiner completes in conjunction with the Sleeper.

Coding variations

In the simple examples that you’ve seen so far, the thread objects are all inherited from Thread. This makes sense because the objects are clearly only being created as threads and have no other behavior. However, your class may already be inheriting from another class, in which case you can’t also inherit from Thread (Java doesn’t support multiple inheritance). In this case, you can use the alternative approach of implementing the Runnable interface. Runnable specifies only that there be a run( ) method implemented, and Thread also implements Runnable. Feedback

This example demonstrates the basics:

//: c13:RunnableThread.java
// SimpleThread using the Runnable interface.

public class RunnableThread implements Runnable {
  private int countDown = 5;
  public String toString() {
    return "#" + Thread.currentThread().getName() +
      ": " + countDown;
  }
  public void run() {
    while(true) {
      System.out.println(this);
      if(--countDown == 0) return;
    }
  }
  public static void main(String[] args) {
    for(int i = 1; i <= 5; i++)
      new Thread(new RunnableThread(), "" + i).start();
    // Output is like SimpleThread.java
  }
} ///:~


The only thing required by a Runnable class is a run( ) method, but if you want to do anything else to the Thread object (such as getName( ) in toString( )) you must explicitly get a reference to it by calling Thread.currentThread( ). This particular Thread constructor takes a Runnable and a name for the thread.

When something has a Runnable interface, it simply means that it has a run( ) method, but there’s nothing special about that—it doesn’t produce any innate threading abilities, like those of a class inherited from Thread. So to produce a thread from a Runnable object, you must create a separate Thread object as shown in this example, handing the Runnable object to the special Thread constructor. You can then call start( ) for that thread, which performs the usual initialization and then calls run( ). Feedback

The convenient aspect about the Runnable interface is that everything belongs to the same class; that is, Runnable allows a mixin in combination with a base class and other interfaces. If you need to access something, you simply do it without going through a separate object. However, inner classes have this same easy access to all the parts of an outer class, so member access is not a compelling reason to use Runnable as a mixin rather than an inner subclass of Thread. Feedback

When you use Runnable, you’re generally saying that you want to create a process in a piece of code—implemented in the run( ) method—rather than an object representing that process. This is a matter of some debate, depending on whether you feel that it makes more sense to represent a thread as an object or as a completely different entity, a process.[68] If you choose to think of it as a process, then you are freed from the object-oriented imperative that “everything is an object.” This also means that there’s no reason to make your whole class Runnable if you only want to start a process to drive some part of your program. Because of this, it often makes more sense to hide your threading code inside your class by using an inner class, as shown here:

//: c13:ThreadVariations.java
// Creating threads with inner classes.
import com.bruceeckel.simpletest.*;

// Using a named inner class:
class InnerThread1 {
  private int countDown = 5;
  private Inner inner;
  private class Inner extends Thread {
    Inner(String name) {
      super(name);
      start();
    }
    public void run() {
      while(true) {
        System.out.println(this);
        if(--countDown == 0) return;
        try {
          sleep(10);
        } catch (InterruptedException e) {
          throw new RuntimeException(e);
        }
      }
    }
    public String toString() {
      return getName() + ": " + countDown;
    }
  }
  public InnerThread1(String name) {
    inner = new Inner(name);
  }
}

// Using an anonymous inner class:
class InnerThread2 {
  private int countDown = 5;
  private Thread t;
  public InnerThread2(String name) {
    t = new Thread(name) {
      public void run() {
        while(true) {
          System.out.println(this);
          if(--countDown == 0) return;
          try {
            sleep(10);
          } catch (InterruptedException e) {
            throw new RuntimeException(e);
          }
        }
      }
      public String toString() {
        return getName() + ": " + countDown;
      }
    };
    t.start();
  }
}

// Using a named Runnable implementation:
class InnerRunnable1 {
  private int countDown = 5;
  private Inner inner;
  private class Inner implements Runnable {
    Thread t;
    Inner(String name) {
      t = new Thread(this, name);
      t.start();
    }
    public void run() {
      while(true) {
        System.out.println(this);
        if(--countDown == 0) return;
        try {
          Thread.sleep(10);
        } catch (InterruptedException e) {
          throw new RuntimeException(e);
        }
      }
    }
    public String toString() {
      return t.getName() + ": " + countDown;
    }
  }
  public InnerRunnable1(String name) {
    inner = new Inner(name);
  }
}

// Using an anonymous Runnable implementation:
class InnerRunnable2 {
  private int countDown = 5;
  private Thread t;
  public InnerRunnable2(String name) {
    t = new Thread(new Runnable() {
      public void run() {
        while(true) {
          System.out.println(this);
          if(--countDown == 0) return;
          try {
            Thread.sleep(10);
          } catch (InterruptedException e) {
            throw new RuntimeException(e);
          }
        }
      }
      public String toString() {
        return Thread.currentThread().getName() +
          ": " + countDown;
      }
    }, name);
    t.start();
  }
}

// A separate method to run some code as a thread:
class ThreadMethod {
  private int countDown = 5;
  private Thread t;
  private String name;
  public ThreadMethod(String name) { this.name = name; }
  public void runThread() {
    if(t == null) {
      t = new Thread(name) {
        public void run() {
          while(true) {
            System.out.println(this);
            if(--countDown == 0) return;
            try {
              sleep(10);
            } catch (InterruptedException e) {
              throw new RuntimeException(e);
            }
          }
        }
        public String toString() {
          return getName() + ": " + countDown;
        }
      };
      t.start();
    }
  }
}

public class ThreadVariations {
  private static Test monitor = new Test();
  public static void main(String[] args) {
    new InnerThread1("InnerThread1");
    new InnerThread2("InnerThread2");
    new InnerRunnable1("InnerRunnable1");
    new InnerRunnable2("InnerRunnable2");
    new ThreadMethod("ThreadMethod").runThread();
    monitor.expect(new String[] {
      "InnerThread1: 5",
      "InnerThread2: 5",
      "InnerThread2: 4",
      "InnerRunnable1: 5",
      "InnerThread1: 4",
      "InnerRunnable2: 5",
      "ThreadMethod: 5",
      "InnerRunnable1: 4",
      "InnerThread2: 3",
      "InnerRunnable2: 4",
      "ThreadMethod: 4",
      "InnerThread1: 3",
      "InnerRunnable1: 3",
      "ThreadMethod: 3",
      "InnerThread1: 2",
      "InnerThread2: 2",
      "InnerRunnable2: 3",
      "InnerThread2: 1",
      "InnerRunnable2: 2",
      "InnerRunnable1: 2",
      "ThreadMethod: 2",
      "InnerThread1: 1",
      "InnerRunnable1: 1",
      "InnerRunnable2: 1",
      "ThreadMethod: 1"
    }, Test.IGNORE_ORDER + Test.WAIT);
  }
} ///:~


InnerThread1 creates a named inner class that extends Thread, and makes an instance of this inner class inside the constructor. This makes sense if the inner class has special capabilities (new methods) that you need to access in other methods. However, most of the time the reason for creating a thread is only to use the Thread capabilities, so it’s not necessary to create a named inner class. InnerThread2 shows the alternative: An anonymous inner subclass of Thread is created inside the constructor and is upcast to a Thread reference t. If other methods of the class need to access t, they can do so through the Thread interface, and they don’t need to know the exact type of the object.

The third and fourth classes in the example repeat the first two classes, but they use the Runnable interface rather than the Thread class. This is just to show that Runnable doesn’t buy you anything more in this situation, but is in fact slightly more complicated to code (and to read the code). As a result, my inclination is to use Thread unless I’m somehow compelled to use Runnable.

The ThreadMethod class shows the creation of a thread inside a method. You call the method when you’re ready to run the thread, and the method returns after the thread begins. If the thread is only performing an auxiliary operation rather than being fundamental to the class, this is probably a more useful/appropriate approach than starting a thread inside the constructor of the class.

Creating responsive user interfaces

As stated earlier, one of the motivations for using threading is to create a responsive user interface. Although we won’t get to graphical user interfaces until Chapter 14, you can see a simple example of a console-based user interface. The following example has two versions: one that gets stuck in a calculation and thus can never read console input, and a second that puts the calculation inside a thread and thus can be performing the calculation and listening for console input.

//: c13:ResponsiveUI.java
// User interface responsiveness.
import com.bruceeckel.simpletest.*;

class UnresponsiveUI {
  private volatile double d = 1;
  public UnresponsiveUI() throws Exception {
    while(d > 0)
      d = d + (Math.PI + Math.E) / d;
    System.in.read(); // Never gets here
  }
}

public class ResponsiveUI extends Thread {
  private static Test monitor = new Test();
  private static volatile double d = 1;
  public ResponsiveUI() {
    setDaemon(true);
    start();
  }
  public void run() {
    while(true) {
      d = d + (Math.PI + Math.E) / d;
    }
  }
  public static void main(String[] args) throws Exception {
    //! new UnresponsiveUI(); // Must kill this process
    new ResponsiveUI();
    Thread.sleep(300);
    System.in.read(); // 'monitor' provides input
    System.out.println(d); // Shows progress
  }
} ///:~


UnresponsiveUI performs a calculation inside an infinite while loop, so it can obviously never reach the console input line (the compiler is fooled into believing that the input line is reachable by the while conditional). If you run the program with the line that creates an UnresponsiveUI uncommented, you’ll have to kill the process to get out.

To make the program responsive, putting the calculation inside a run( ) method allows it to be preempted, and when you press the Enter key you’ll see that the calculation has indeed been running in the background while waiting for your user input (for testing purposes, the console input line is automatically provided to System.in.read( ) by the com.bruceeckel.simpletest.Test object, which is explained in Chapter 15).

Sharing limited resources

You can think of a single-threaded program as one lonely entity moving around through your problem space and doing one thing at a time. Because there’s only one entity, you never have to think about the problem of two entities trying to use the same resource at the same time, problems like two people trying to park in the same space, walk through a door at the same time, or even talk at the same time. Feedback

With multithreading, things aren’t lonely anymore, but you now have the possibility of two or more threads trying to use the same limited resource at once. Colliding over a resource must be prevented, or else you’ll have two threads trying to access the same bank account at the same time, print to the same printer, adjust the same valve, and so on. Feedback

Improperly accessing resources

Consider the following example in which the class “guarantees” that it will always deliver an even number when you call getValue( ). However, there’s a second thread named “Watcher” that is constantly calling getValue( ) and checking to see if this value is truly even. This seems like a needless activity, since it appears obvious by looking at the code that the value will indeed be even. But that’s where the surprise comes in. Here’s the first version of the program: Feedback

//: c13:AlwaysEven.java
// Demonstrating thread collision over resources by
// reading an object in an unstable intermediate state.

public class AlwaysEven {
  private int i;
  public void next() { i++; i++; }
  public int getValue() { return i; }
  public static void main(String[] args) {
    final AlwaysEven ae = new AlwaysEven();
    new Thread("Watcher") {
      public void run() {
        while(true) {
          int val = ae.getValue();
          if(val % 2 != 0) {
            System.out.println(val);
            System.exit(0);
          }
        }
      }
    }.start();
    while(true)
      ae.next();
  }
} ///:~


In main( ), an AlwaysEven object is created—it must be final because it is accessed inside the anonymous inner class defined as a Thread. If the value read by the thread is not even, it prints it out (as proof that it has caught the object in an unstable state) and then exits the program. Feedback

This example shows a fundamental problem with using threads. You never know when a thread might be run. Imagine sitting at a table with a fork, about to spear the last piece of food on your plate, and as your fork reaches for it, the food suddenly vanishes (because your thread was suspended and another thread came in and stole the food). That’s the problem that you’re dealing with when writing concurrent programs. Feedback

Sometimes you don’t care if a resource is being accessed at the same time you’re trying to use it (the food is on some other plate). But for multithreading to work, you need some way to prevent two threads from accessing the same resource, at least during critical periods. Feedback

Preventing this kind of collision is simply a matter of putting a lock on a resource when one thread is using it. The first thread that accesses a resource locks it, and then the other threads cannot access that resource until it is unlocked, at which time another thread locks and uses it, etc. If the front seat of the car is the limited resource, the child who shouts “Dibs!” asserts the lock. Feedback

A resource testing framework

Before going on, let’s try to simplify things a bit by creating a little framework for performing tests on these types of threading examples. We can accomplish this by separating out the common code that might appear across multiple examples. First, note that the “watcher” thread is actually watching for a violated invariant in a particular object. That is, the object is supposed to preserve rules about its internal state, and if you can see the object from outside in an invalid intermediate state, then the invariant has been violated from the standpoint of the client (this is not to say that the object can never exist in the invalid intermediate state, just that it should not be visible by the client in such a state). Thus, we want to be able to detect that the invariant is violated, and also know what the violation value is. To get both of these values from one method call, we combine them in a tagging interface that exists only to provide a meaningful name in the code: Feedback

//: c13:InvariantState.java
// Messenger carrying invariant data
public interface InvariantState {} ///:~


In this scheme, the information about success or failure is encoded in the class name and type to make the result more readable. The class indicating success is: Feedback

//: c13:InvariantOK.java
// Indicates that the invariant test succeeded
public class InvariantOK implements InvariantState {} ///:~


To indicate failure, the InvariantFailure object will carry an object with information about what caused the failure, typically so that it can be displayed: Feedback

//: c13:InvariantFailure.java
// Indicates that the invariant test failed

public class InvariantFailure implements InvariantState {
  public Object value;
  public InvariantFailure(Object value) {
    this.value = value;
  }
} ///:~


Now we can define an interface that must be implemented by any class that wishes to have its invariance tested: Feedback

//: c13:Invariant.java
public interface Invariant {
  InvariantState invariant();
} ///:~


Before creating the generic “watcher” thread, note that some of the examples in this chapter will not behave as expected on all platforms. Many of the examples here attempt to show violations of single-threaded behavior when multiple threads are present, and this may not always happen.[69] Alternatively, an example may attempt to show that the violation does not occur by attempting (and failing) to demonstrate the violation. In these cases, we’ll need a way to stop the program after a few seconds. The following class does this by subclassing the standard library Timer class: Feedback

//: c13:Timeout.java
// Set a time limit on the execution of a program
import java.util.*;

public class Timeout extends Timer {
  public Timeout(int delay, final String msg) {
    super(true); // Daemon thread
    schedule(new TimerTask() {
      public void run() {
        System.out.println(msg);
        System.exit(0);
      }
    }, delay);
  }
} ///:~


The delay is in milliseconds, and the message will be printed if the timeout expires. Note that by calling super(true), this is created as a daemon thread so that if your program completes in some other way, this thread will not prevent it from exiting. The Timer.schedule( ) method is given a TimerTask subclass (created here as an anonymous inner class) whose run( ) is executed after the second schedule( ) argument delay (in milliseconds) runs out. Using Timer is generally simpler and clearer than writing the code directly with an explicit sleep( ). In addition, Timer is designed to scale to large numbers of concurrently scheduled tasks (in the thousands), so it can be a very useful tool. Feedback

Now we can use the Invariant interface and the Timeout class in the InvariantWatcher thread:

//: c13:InvariantWatcher.java
// Repeatedly checks to ensure invariant is not violated

public class InvariantWatcher extends Thread {
  private Invariant invariant;
  public InvariantWatcher(Invariant invariant) {
    this.invariant = invariant;
    setDaemon(true);
    start();
  }
  // Stop everything after awhile:
  public
  InvariantWatcher(Invariant invariant, final int timeOut){
    this(invariant);
    new Timeout(timeOut,
      "Timed out without violating invariant");
  }
  public void run() {
    while(true) {
      InvariantState state = invariant.invariant();
      if(state instanceof InvariantFailure) {
        System.out.println("Invariant violated: "
          + ((InvariantFailure)state).value);
        System.exit(0);
      }
    }
  }
} ///:~


The constructor captures a reference to the Invariant object to be tested, and starts the thread. The second constructor calls the first constructor, then creates a Timeout that stops everything after a desired delay—this is used in situations where the program may not exit by violating an invariant. In run( ), the current InvariantState is captured and tested, and if it fails, the value is printed. Note that we cannot throw an exception inside this thread, because that would only terminate the thread, not the program. Feedback

Now AlwaysEven.java can be rewritten using the framework:

//: c13:EvenGenerator.java
// AlwaysEven.java using the invariance tester

public class EvenGenerator implements Invariant {
  private int i;
  public void next() { i++; i++; }
  public int getValue() { return i; }
  public InvariantState invariant() {
    int val = i; // Capture it in case it changes
    if(val % 2 == 0)
      return new InvariantOK();
    else
      return new InvariantFailure(new Integer(val));
  }
  public static void main(String[] args) {
    EvenGenerator gen = new EvenGenerator();
    new InvariantWatcher(gen);
    while(true)
      gen.next();
  }
} ///:~


When defining the invariant( ) method, you must capture all the values of interest into local variables. This way, you can return the actual value you have tested, not one that may have been changed (by another thread) in the meantime. Feedback

In this case, the problem is not that the object goes through a state that violates invariance, but that methods can be called by threads while the object is in that intermediate unstable state. Feedback

Colliding over resources

The worst thing that happens with EvenGenerator is that a client thread might see it in an unstable intermediate state. The object’s internal consistency is maintained, however, and it eventually becomes visible in a good state. But if two threads are actually modifying an object, the contention over shared resources is much worse, because the object can be put into an incorrect state. Feedback

Consider the simple concept of a semaphore, which is a flag object used for communication between threads. If the semaphore’s value is zero, then whatever it is monitoring is available, but if the value is nonzero, then the monitored entity is unavailable, and the thread must wait for it. When it’s available, the thread increments the semaphore and then goes ahead and uses the monitored entity. Because incrementing and decrementing are atomic operations (that is, they cannot be interrupted), the semaphore keeps two threads from using the same entity at the same time. Feedback

If the semaphore is going to properly guard the entity that it is monitoring, then it must never get into an unstable state. Here’s a simple version of the semaphore idea:

//: c13:Semaphore.java
// A simple threading flag

public class Semaphore implements Invariant {
  private volatile int semaphore = 0;
  public boolean available() { return semaphore == 0; }
  public void acquire() { ++semaphore; }
  public void release() { --semaphore; }
  public InvariantState invariant() {
    int val = semaphore;
    if(val == 0 || val == 1)
      return new InvariantOK();
    else
      return new InvariantFailure(new Integer(val));
  }
} ///:~


The core part of the class is straightforward, consisting of available( ), acquire( ), and release( ). Since a thread should check for availability before acquiring, the value of semaphore should never be other than one or zero, and this is tested by invariant( ). Feedback

But look what happens when Semaphore is tested for thread consistency:

//: c13:SemaphoreTester.java
// Colliding over shared resources

public class SemaphoreTester extends Thread {
  private volatile Semaphore semaphore;
  public SemaphoreTester(Semaphore semaphore) {
    this.semaphore = semaphore;
    setDaemon(true);
    start();
  }
  public void run() {
    while(true)
      if(semaphore.available()) {
        yield(); // Makes it fail faster
        semaphore.acquire();
        yield();
        semaphore.release();
        yield();
      }
  }
  public static void main(String[] args) throws Exception {
    Semaphore sem = new Semaphore();
    new SemaphoreTester(sem);
    new SemaphoreTester(sem);
    new InvariantWatcher(sem).join();
  }
} ///:~


The SemaphoreTester creates a thread that continuously tests to see if a Semaphore object is available, and if so acquires and releases it. Note that the semaphore field is volatile to make sure that the compiler doesn’t optimize away any reads of that value. Feedback

In main( ), two SemaphoreTester threads are created, and you’ll see that in short order the invariant is violated. This happens because one thread might get a true result from calling available( ), but by the time that thread calls acquire( ), the other thread may have already called acquire( ) and incremented the semaphore field. The InvariantWatcher may see the field with too high a value, or possibly see it after both threads have called release( ) and decremented it to a negative value. Note that InvariantWatcher join( )s with the main thread to keep the program running until there is a failure. Feedback

On my machine, I discovered that the inclusion of yield( ) caused failure to occur much faster, but this will vary with operating systems and JVM implementations. You should experiment with taking the yield( ) statements out; the failure might take a very long time to occur, which demonstrates how difficult it can be to detect a flaw in your program when you’re writing multithreaded code. Feedback

This class emphasizes the risk of concurrent programming: If a class this simple can produce problems, you can never trust any assumptions about concurrency. Feedback

Resolving shared resource contention

To solve the problem of thread collision, virtually all multithreading schemes serialize access to shared resources. This means that only one thread at a time is allowed to access the shared resource. This is ordinarily accomplished by putting a locked clause around a piece of code so that only one thread at a time may pass through that piece of code. Because this locked clause produces mutual exclusion, a common name for such a mechanism is mutex. Feedback

Consider the bathroom in your house; multiple people (threads) may each want to have exclusive use of the bathroom (the shared resource). To access the bathroom, a person knocks on the door to see if it’s available. If so, they enter and lock the door. Any other thread that wants to use the bathroom is “blocked” from using it, so that thread waits at the door until the bathroom is available. Feedback

The analogy breaks down a bit when the bathroom is released and it comes time to give access to another thread. There isn’t actually a line of people and we don’t know for sure who gets the bathroom next, because the thread scheduler isn’t deterministic that way. Instead, it’s as if there is a group of blocked threads milling about in front of the bathroom, and when the thread that has locked the bathroom unlocks it and emerges, the one that happens to be nearest the door at the moment goes in. As noted earlier, suggestions can be made to the thread scheduler via yield( ) and setPriority( ), but these suggestions may not have much of an effect depending on your platform and JVM implementation. Feedback

Java has built-in support to prevent collisions over resources in the form of the synchronized keyword. This works much like the Semaphore class was supposed to: When a thread wishes to execute a piece of code guarded by the synchronized keyword, it checks to see if the semaphore is available, then acquires it, executes the code, and releases it. However, synchronized is built into the language, so it’s guaranteed to always work, unlike the Semaphore class. Feedback

The shared resource is typically just a piece of memory in the form of an object, but may also be a file, I/O port, or something like a printer. To control access to a shared resource, you first put it inside an object. Then any method that accesses that resource can be made synchronized. This means that if a thread is inside one of the synchronized methods, all other threads are blocked from entering any of the synchronized methods of the class until the first thread returns from its call. Feedback

Since you typically make the data elements of a class private and access that memory only through methods, you can prevent collisions by making methods synchronized. Here is how you declare synchronized methods: Feedback

synchronized void f() { /* ... */ }
synchronized void g(){ /* ... */ }


Each object contains a single lock (also referred to as a monitor) that is automatically part of the object (you don’t have to write any special code). When you call any synchronized method, that object is locked and no other synchronized method of that object can be called until the first one finishes and releases the lock. In the preceding example, if f( ) is called for an object, g( ) cannot be called for the same object until f( ) is completed and releases the lock. Thus, there is a single lock that is shared by all the synchronized methods of a particular object, and this lock prevents common memory from being written by more than one thread at a time. Feedback

One thread may acquire an object’s lock multiple times. This happens if one method calls a second method on the same object, which in turn calls another method on the same object, etc. The JVM keeps track of the number of times the object has been locked. If the object is unlocked, it has a count of zero. As a thread acquires the lock for the first time, the count goes to one. Each time the thread acquires a lock on the same object, the count is incremented. Naturally, multiple lock acquisition is only allowed for the thread that acquired the lock in the first place. Each time the thread leaves a synchronized method, the count is decremented, until the count goes to zero, releasing the lock entirely for use by other threads. Feedback

There’s also a single lock per class (as part of the Class object for the class), so that synchronized static methods can lock each other out from simultaneous access of static data on a class-wide basis. Feedback

Synchronizing the EvenGenerator

By adding synchronized to EvenGenerator.java, we can prevent the undesirable thread access:

//: c13:SynchronizedEvenGenerator.java
// Using "synchronized" to prevent thread collisions

public
class SynchronizedEvenGenerator implements Invariant {
  private int i;
  public synchronized void next() { i++; i++; }
  public synchronized int getValue() { return i; }
  // Not synchronized so it can run at
  // any time and thus be a genuine test:
  public InvariantState invariant() {
    int val = getValue();
    if(val % 2 == 0)
      return new InvariantOK();
    else
      return new InvariantFailure(new Integer(val));
  }
  public static void main(String[] args) {
    SynchronizedEvenGenerator gen =
      new SynchronizedEvenGenerator();
    new InvariantWatcher(gen, 4000); // 4-second timeout
    while(true)
      gen.next();
  }
} ///:~


You’ll notice that both next( ) and getValue( ) are synchronized. If you synchronize only one of the methods, then the other is free to ignore the object lock and can be called with impunity. This is an important point: Every method that accesses a critical shared resource must be synchronized or it won’t work right. On the other hand, InvariantState is not synchronized because it is doing the testing, and we want it to be called at any time so that it produces a true test of the object. Feedback

Atomic operations

A common piece of lore often repeated in Java threading discussions is that “atomic operations do not need to be synchronized.” An atomic operation is one that cannot be interrupted by the thread scheduler; if the operation begins, then it will run to completion before the possibility of a context switch (switching execution to another thread). Feedback

The atomic operations commonly mentioned in this lore include simple assignment and returning a value when the variable in question is a primitive type that is not a long or a double. The latter types are excluded because they are larger than the rest of the types, and the JVM is thus not required to perform reads and assignments as single atomic operations (a JVM may choose to do so anyway, but there’s no guarantee). However, you do get atomicity if you use the volatile keyword with long or double. Feedback

If you were to blindly apply the idea of atomicity to SynchronizedEvenGenerator.java, you would notice that

  public synchronized int getValue() { return i; }


fits the description. But try removing synchronized, and the test will fail, because even though return i is indeed an atomic operation, removing synchronized allows the value to be read while the object is in an unstable intermediate state. You must genuinely understand what you’re doing before you try to apply optimizations like this. There are no easily-applicable rules that work. Feedback

As a second example, consider something even simpler: a class that produces serial numbers.[70] Each time nextSerialNumber( ) is called, it must return a unique value to the caller:

//: c13:SerialNumberGenerator.java

public class SerialNumberGenerator {
  private static volatile int serialNumber = 0;
  public static int nextSerialNumber() {
    return serialNumber++;
  }
} ///:~


SerialNumberGenerator is about as simple a class as you can imagine, and if you’re coming from C++ or some other low-level background, you would expect the increment to be an atomic operation, because increment is usually implemented as a microprocessor instruction. However, in the JVM an increment is not atomic and involves both a read and a write, so there’s room for threading problems even in such a simple operation. Feedback

The serialNumber field is volatile because it is possible for each thread to have a local stack and maintain copies of some variables there. If you define a variable as volatile, it tells the compiler not to do any optimizations that would remove reads and writes that keep the field in exact synchronization with the local data in the threads. Feedback

To test this, we need a set that doesn’t run out of memory, in case it takes a long time to detect a problem. The CircularSet shown here reuses the memory used to store ints, with the assumption that by the time you wrap around, the possibility of a collision with the overwritten values is minimal. The add( ) and contains( ) methods are synchronized to prevent thread collisions: Feedback

//: c13:SerialNumberChecker.java
// Operations that may seem safe are not,
// when threads are present.

// Reuses storage so we don't run out of memory:
class CircularSet {
  private int[] array;
  private int len;
  private int index = 0;
  public CircularSet(int size) {
    array = new int[size];
    len = size;
    // Initialize to a value not produced
    // by the SerialNumberGenerator:
    for(int i = 0; i < size; i++)
      array[i] = -1;
  }
  public synchronized void add(int i) {
    array[index] = i;
    // Wrap index and write over old elements:
    index = ++index % len;
  }
  public synchronized boolean contains(int val) {
    for(int i = 0; i < len; i++)
      if(array[i] == val) return true;
    return false;
  }
}

public class SerialNumberChecker {
  private static CircularSet serials =
    new CircularSet(1000);
  static class SerialChecker extends Thread {
    SerialChecker() { start(); }
    public void run() {
      while(true) {
        int serial =
          SerialNumberGenerator.nextSerialNumber();
        if(serials.contains(serial)) {
          System.out.println("Duplicate: " + serial);
          System.exit(0);
        }
        serials.add(serial);
      }
    }
  }
  public static void main(String[] args) {
    for(int i = 0; i < 10; i++)
      new SerialChecker();
    // Stop after 4 seconds:
    new Timeout(4000, "No duplicates detected");
  }
} ///:~


SerialNumberChecker contains a static CircularSet that contains all the serial numbers that have been extracted, and a nested Thread that gets serial numbers and ensures that they are unique. By creating multiple threads to contend over serial numbers, you’ll discover that the threads get a duplicate serial number reasonably soon (note that this program may not indicate a collision on your machine, but it has successfully detected collisions on a multiprocessor machine). To solve the problem, add the synchronized keyword to nextSerialNumber( ). Feedback

The atomic operations that are supposed to be safe are reading and assignment of primitives. However, as seen in EvenGenerator.java, it’s still easily possible to use an atomic operation that accesses your object while it’s in an unstable intermediate state, so you cannot make any assumptions. On top of this, the atomic operations are not guaranteed to work with long and double (although some JVM implementations do guarantee atomicity for long and double operations, you won’t be writing portable code if you depend on this). Feedback

It’s safest to use the following guidelines:

  1. If you need to synchronize one method in a class, synchronize all of them. It’s often difficult to tell for sure if a method will be negatively affected if you leave synchronization out. Feedback
  2. Be extremely careful when removing synchronization from methods. The typical reason to do this is for performance, but in JDK 1.3 and 1.4 the overhead of synchronized has been greatly reduced. In addition, you should only do this after using a profiler to determine that synchronized is indeed the bottleneck. Feedback

Fixing Semaphore

Now consider Semaphore.java. It would seem that we should be able to repair this by synchronizing the three class methods, like this:

//: c13:SynchronizedSemaphore.java
// Colliding over shared resources

public class SynchronizedSemaphore extends Semaphore {
  private volatile int semaphore = 0;
  public synchronized boolean available() {
    return semaphore == 0;
  }
  public synchronized void acquire() { ++semaphore; }
  public synchronized void release() { --semaphore; }
  public InvariantState invariant() {
    int val = semaphore;
    if(val == 0 || val == 1)
      return new InvariantOK();
    else
      return new InvariantFailure(new Integer(val));
  }
  public static void main(String[] args) throws Exception {
    SynchronizedSemaphore sem =new SynchronizedSemaphore();
    new SemaphoreTester(sem);
    new SemaphoreTester(sem);
    new InvariantWatcher(sem).join();
  }
} ///:~


This looks rather odd at first—SynchronizedSemaphore is inherited from Semaphore, and yet all the overridden methods are synchronized, but the base-class versions aren’t. Java doesn’t allow you to change the method signature during overriding, and yet doesn’t complain about this. That’s because the synchronized keyword is not part of the method signature, so you can add it in and it doesn’t limit overriding. Feedback

The reason for inheriting from Semaphore is to reuse the SemaphoreTester class. When you run the program you’ll see that it still causes an InvariantFailure. Feedback

Why does this fail? By the time a thread detects that the Semaphore is available because available( ) returns true, it has released the lock on the object. Another thread can dash in and increment the semaphore value before the first thread does. The first thread still assumes the Semaphore object is available and so goes ahead and blindly enters the acquire( ) method, putting the object into an unstable state. This is just one more lesson about rule zero of concurrent programming: Never make any assumptions. Feedback

The only solution to this problem is to make the test for availability and the acquisition a single atomic operation—which is exactly what the synchronized keyword provides in conjunction with the lock on an object. That is, Java’s lock and synchronized keyword is a built-in semaphore mechanism, so you don’t need to create your own. Feedback

Critical sections

Sometimes, you only want to prevent multiple thread access to part of the code inside a method instead of the entire method. The section of code you want to isolate this way is called a critical section and is also created using the synchronized keyword. Here, synchronized is used to specify the object whose lock is being used to synchronize the enclosed code: Feedback

synchronized(syncObject) {
  // This code can be accessed 
  // by only one thread at a time
}


This is also called a synchronized block; before it can be entered, the lock must be acquired on syncObject. If some other thread already has this lock, then the critical section cannot be entered until the lock is given up. Feedback

The following example compares both approaches to synchronization by showing how the time available for other threads to access an object is significantly increased by using a synchronized block instead of synchronizing an entire method. In addition, it shows how an unprotected class can be used in a multithreaded situation if it is controlled and protected by another class: Feedback

//: c13:CriticalSection.java
// Synchronizing blocks instead of entire methods. Also
// demonstrates protection of a non-thread-safe class
// with a thread-safe one.
import java.util.*;

class Pair { // Not thread-safe
  private int x, y;
  public Pair(int x, int y) {
    this.x = x;
    this.y = y;
  }
  public Pair() { this(0, 0); }
  public int getX() { return x; }
  public int getY() { return y; }
  public void incrementX() { x++; }
  public void incrementY() { y++; }
  public String toString() {
    return "x: " + x + ", y: " + y;
  }
  public class PairValuesNotEqualException
  extends RuntimeException {
    public PairValuesNotEqualException() {
      super("Pair values not equal: " + Pair.this);
    }
  }
  // Arbitrary invariant -- both variables must be equal:
  public void checkState() {
    if(x != y)
      throw new PairValuesNotEqualException();
  }
}

// Protect a Pair inside a thread-safe class:
abstract class PairManager {
  protected Pair p = new Pair();
  private List storage = new ArrayList();
  public synchronized Pair getPair() {
    // Make a copy to keep the original safe:
    return new Pair(p.getX(), p.getY());
  }
  protected void store() { storage.add(getPair()); }
  // A "template method":
  public abstract void doTask();
}

// Synchronize the entire method:
class PairManager1 extends PairManager {
  public synchronized void doTask() {
    p.incrementX();
    p.incrementY();
    store();
  }
}

// Use a critical section:
class PairManager2 extends PairManager {
  public void doTask() {
    synchronized(this) {
      p.incrementX();
      p.incrementY();
    }
    store();
  }
}

class PairManipulator extends Thread {
  private PairManager pm;
  private int checkCounter = 0;
  private class PairChecker extends Thread {
    PairChecker() { start(); }
    public void run() {
      while(true) {
        checkCounter++;
        pm.getPair().checkState();
      }
    }
  }
  public PairManipulator(PairManager pm) {
    this.pm = pm;
    start();
    new PairChecker();
  }
  public void run() {
    while(true) {
      pm.doTask();
    }
  }
  public String toString() {
    return "Pair: " + pm.getPair() +
      " checkCounter = " + checkCounter;
  }
}

public class CriticalSection {
  public static void main(String[] args) {
    // Test the two different approaches:
    final PairManipulator
      pm1 = new PairManipulator(new PairManager1()),
      pm2 = new PairManipulator(new PairManager2());
    new Timer(true).schedule(new TimerTask() {
      public void run() {
        System.out.println("pm1: " + pm1);
        System.out.println("pm2: " + pm2);
        System.exit(0);
      }
    }, 500); // run() after 500 milliseconds
  }
} ///:~


As noted, Pair is not thread-safe because its invariant (admittedly arbitrary) requires that both variables maintain the same values. In addition, as seen earlier in this chapter, the increment operations are not thread-safe, and because none of the methods are synchronized, you can’t trust a Pair object to stay uncorrupted in a threaded program. Feedback

The PairManager class holds a Pair object and controls all access to it. Note that the only public methods are getPair( ), which is synchronized, and the abstract doTask( ). Synchronization for this method will be handled when it is implemented. Feedback

The structure of PairManager, where some of the functionality is implemented in the base class with one or more abstract methods defined in derived classes, is called a Template Method in Design Patterns parlance.[71] Design patterns allow you to encapsulate change in your code; here, the part that is changing is the template method doTask( ). In PairManager1 the entire doTask( ) is synchronized, but in PairManager2 only part of doTask( ) is synchronized by using a synchronized block. Note that the synchronized keyword is not part of the method signature and thus may be added during overriding. Feedback

PairManager2 is observing, in effect, that store( ) is a protected method and thus is not available to the general client, but only to subclasses. Thus, it doesn’t necessarily need to be guarded inside a synchronized method, and is instead placed outside of the synchronized block. Feedback

A synchronized block must be given an object to synchronize upon, and usually the most sensible object to use is just the current object that the method is being called for: synchronized(this), which is the approach taken in PairManager2. That way, when the lock is acquired for the synchronized block, other synchronized methods in the object cannot be called. So the effect is that of simply reducing the scope of synchronization. Feedback

Sometimes this isn’t what you want, in which case you can create a separate object and synchronize on that. The following example demonstrates that two threads can enter an object when the methods in that object synchronize on different locks: Feedback

//: c13:SyncObject.java
// Synchronizing on another object
import com.bruceeckel.simpletest.*;

class DualSynch {
  private Object syncObject = new Object();
  public synchronized void f() {
    System.out.println("Inside f()");
    // Doesn't release lock:
    try {
      Thread.sleep(500);
    } catch(InterruptedException e) {
      throw new RuntimeException(e);
    }
    System.out.println("Leaving f()");
  }
  public void g() {
    synchronized(syncObject) {
      System.out.println("Inside g()");
      try {
        Thread.sleep(500);
      } catch(InterruptedException e) {
        throw new RuntimeException(e);
      }
      System.out.println("Leaving g()");
    }
  }
}

public class SyncObject {
  private static Test monitor = new Test();
  public static void main(String[] args) {
    final DualSynch ds = new DualSynch();
    new Thread() {
      public void run() {
        ds.f();
      }
    }.start();
    ds.g();
    monitor.expect(new String[] {
      "Inside g()",
      "Inside f()",
      "Leaving g()",
      "Leaving f()"
    }, Test.WAIT + Test.IGNORE_ORDER);
  }
} ///:~


The DualSync method f( ) synchronizes on this (by synchronizing the entire method) and g( ) has a synchronized block that synchronizes on syncObject. Thus, the two synchronizations are independent. This is demonstrated in main( ) by creating a Thread that calls f( ). The main( ) thread is used to call g( ). You can see from the output that both methods are running at the same time, so neither one is blocked by the synchronization of the other. Feedback

Returning to CriticalSection.java, PairManipulator is created to test the two different types of PairManager by running doTask( ) in one thread and an instance of the inner class PairChecker in the other. To trace how often it is able to run the test, PairChecker increments checkCounter every time it is successful. In main( ), two PairManipulator objects are created and allowed to run for awhile. When the Timer runs out, it executes its run( ) method, that displays the results of each PairManipulator and exits. When you run the program, you should see something like this: Feedback

pm1: Pair: x: 58892, y: 58892 checkCounter = 44974
pm2: Pair: x: 73153, y: 73153 checkCounter = 100535


Although you will probably see a lot of variation from one run to the next, in general you will see that PairManager1.doTask( ) does not allow the PairChecker nearly as much access as PairManager2.doTask( ), which has the synchronized block and thus provides more unlocked time. This is typically the reason that you want to use a synchronized block instead of synchronizing the whole method: to allow other threads more access (as long as it is safe to do so). Feedback

Of course, all synchronization depends on programmer diligence: Every piece of code that can access a shared resource must be wrapped in an appropriate synchronized block. Feedback

Thread states

A thread can be in any one of four states:

  1. New: The thread object has been created, but it hasn’t been started yet, so it cannot run. Feedback
  2. Runnable: This means that a thread can be run when the time-slicing mechanism has CPU cycles available for the thread. Thus, the thread might or might not be running at any moment, but there’s nothing to prevent it from being run if the scheduler can arrange it; it’s not dead or blocked. Feedback
  3. Dead: The normal way for a thread to die is by returning from its run( ) method. Before it was deprecated in Java 2, you could also call stop( ), but this could easily put your program into an unstable state. There’s also a destroy( ) method (which has never been implemented, and probably never will be, so it’s effectively deprecated). You’ll learn about an alternative way to code a stop( ) equivalent later in the chapter. Feedback
  4. Blocked: The thread could be run, but there’s something that prevents it. While a thread is in the blocked state, the scheduler will simply skip over it and not give it any CPU time. Until a thread reenters the runnable state, it won’t perform any operations. Feedback

Becoming blocked

When a thread is blocked, there’s some reason that it cannot continue running. A thread can become blocked for the following reasons: Feedback

  1. You’ve put the thread to sleep by calling sleep(milliseconds), in which case it will not be run for the specified time. Feedback
  2. You’ve suspended the execution of the thread with wait( ). It will not become runnable again until the thread gets the notify( ) or notifyAll( ) message. We’ll examine these in the next section. Feedback
  3. The thread is waiting for some I/O to complete. Feedback
  4. The thread is trying to call a synchronized method on another object, and that object’s lock is not available. Feedback

In old code, you may also see suspend( ) and resume( ) used to block and unblock threads, but these are deprecated in Java 2 (because they are deadlock-prone), and so will not be examined in this book. Feedback

Cooperation between threads

After understanding that threads can collide with each other, and how you keep them from colliding, the next step is to learn how to make threads cooperate with each other. The key to doing this is by handshaking between threads, which is safely implemented using the Object methods wait( ) and notify( ). Feedback

Wait and notify

It’s important to understand that sleep( ) does not release the lock when it is called. On the other hand, the method wait( ) does release the lock, which means that other synchronized methods in the thread object can be called during a wait( ). When a thread enters a call to wait( ) inside a method, that thread’s execution is suspended, and the lock on that object is released. Feedback

There are two forms of wait( ). The first takes an argument in milliseconds that has the same meaning as in sleep( ): “Pause for this period of time.” The difference is that in wait( ):

  1. The object lock is released during the wait( ).
  2. You can come out of the wait( ) due to a notify( ) or notifyAll( ), or by letting the clock run out. Feedback

The second form of wait( ) takes no arguments; this version is more commonly used. This wait( ) continues indefinitely until the thread receives a notify( ) or notifyAll( ). Feedback

One fairly unique aspect of wait( ), notify( ), and notifyAll( ) is that these methods are part of the base class Object and not part of Thread, as is sleep( ). Although this seems a bit strange at first—to have something that’s exclusively for threading as part of the universal base class—it’s essential because they manipulate the lock that’s also part of every object. As a result, you can put a wait( ) inside any synchronized method, regardless of whether that class extends Thread or implements Runnable. In fact, the only place you can call wait( ), notify( ), or notifyAll( ) is within a synchronized method or block (sleep( ) can be called within non-synchronized methods since it doesn’t manipulate the lock). If you call any of these within a method that’s not synchronized, the program will compile, but when you run it, you’ll get an IllegalMonitorStateException with the somewhat nonintuitive message “current thread not owner.” This message means that the thread calling wait( ), notify( ), or notifyAll( ) must “own” (acquire) the lock for the object before it can call any of these methods. Feedback

You can ask another object to perform an operation that manipulates its own lock. To do this, you must first capture that object’s lock. For example, if you want to notify( ) an object x, you must do so inside a synchronized block that acquires the lock for x: Feedback

synchronized(x) {
  x.notify();
}


Typically, wait( ) is used when you’re waiting for some condition that is under the control of forces outside of the current method to change (typically, this condition will be changed by another thread). You don’t want to idly wait while testing the condition inside your thread; this is called a “busy wait” and it’s a very bad use of CPU cycles. So wait( ) allows you to put the thread to sleep while waiting for the world to change, and only when a notify( ) or notifyAll( ) occurs does the thread wake up and check for changes. Thus, wait( ) provides a way to synchronize activities between threads. Feedback

As an example, consider a restaurant that has one chef and one waitperson. The waitperson must wait for the chef to prepare a meal. When the chef has a meal ready, the chef notifies the waitperson, who then gets the meal and goes back to waiting. This is an excellent example of thread cooperation: The chef represents the producer, and the waitperson represents the consumer. Here is the story modeled in code: Feedback

//: c13:Restaurant.java
// The producer-consumer approach to thread cooperation.
import com.bruceeckel.simpletest.*;

class Order {
  private static int i = 0;
  private int count = i++;
  public Order() {
    if(count == 10) {
      System.out.println("Out of food, closing");
      System.exit(0);
    }
  }
  public String toString() { return "Order " + count; }
}

class WaitPerson extends Thread {
  private Restaurant restaurant;
  public WaitPerson(Restaurant r) {
    restaurant = r;
    start();
  }
  public void run() {
    while(true) {
      while(restaurant.order == null)
        synchronized(this) {
          try {
            wait();
          } catch(InterruptedException e) {
            throw new RuntimeException(e);
          }
        }
      System.out.println(
        "Waitperson got " + restaurant.order);
      restaurant.order = null;
    }
  }
}

class Chef extends Thread {
  private Restaurant restaurant;
  private WaitPerson waitPerson;
  public Chef(Restaurant r, WaitPerson w) {
    restaurant = r;
    waitPerson = w;
    start();
  }
  public void run() {
    while(true) {
      if(restaurant.order == null) {
        restaurant.order = new Order();
        System.out.print("Order up! ");
        synchronized(waitPerson) {
          waitPerson.notify();
        }
      }
      try {
        sleep(100);
      } catch(InterruptedException e) {
        throw new RuntimeException(e);
      }
    }
  }
}

public class Restaurant {
  private static Test monitor = new Test();
  Order order; // Package access
  public static void main(String[] args) {
    Restaurant restaurant = new Restaurant();
    WaitPerson waitPerson = new WaitPerson(restaurant);
    Chef chef = new Chef(restaurant, waitPerson);
    monitor.expect(new String[] {
      "Order up! Waitperson got Order 0",
      "Order up! Waitperson got Order 1",
      "Order up! Waitperson got Order 2",
      "Order up! Waitperson got Order 3",
      "Order up! Waitperson got Order 4",
      "Order up! Waitperson got Order 5",
      "Order up! Waitperson got Order 6",
      "Order up! Waitperson got Order 7",
      "Order up! Waitperson got Order 8",
      "Order up! Waitperson got Order 9",
      "Out of food, closing"
    }, Test.WAIT);
  }
} ///:~


Order is a simple self-counting class, but notice that it also includes a way to terminate the program; on order 10, System.exit( ) is called. Feedback

A WaitPerson must know what Restaurant they are working for because they must fetch the order from the restaurant’s “order window,” restaurant.order. In run( ), the WaitPerson goes into wait( ) mode, stopping that thread until it is woken up with a notify( ) from the Chef. Since this is a very simple program, we know that only one thread will be waiting on the WaitPerson’s lock: the WaitPerson thread itself. For this reason it’s safe to call notify( ). In more complex situations, multiple threads may be waiting on a particular object lock, so you don’t know which thread should be awakened. The solutions is to call notifyAll( ), which wakes up all the threads waiting on that lock. Each thread must then decide whether the notification is relevant. Feedback

Notice that the wait( ) is wrapped in a while( ) statement that is testing for the same thing that is being waited for. This seems a bit strange at first—if you’re waiting for an order, once you wake up the order must be available, right? The problem is that in a multithreading application, some other thread might swoop in and grab the order while the WaitPerson is waking up. The only safe approach is to always use the following idiom for a wait( ): Feedback

while(conditionIsNotMet)
wait( );

This guarantees that the condition will be met before you get out of the wait loop, and if you have either been notified of something that doesn’t concern the condition (as can happen with notifyAll( )), or the condition changes before you get fully out of the wait loop, you are guaranteed to go back into waiting. Feedback

A Chef object must know what restaurant he or she is working for (so the Orders can be placed in restaurant.order) and the WaitPerson who is picking up the meals, so that WaitPerson can be notified when an order is ready. In this simplified example, the Chef is generating the Order objects, then notifying the WaitPerson that an order is ready. Feedback

Observe that the call to notify( ) must first capture the lock on waitPerson. The call to wait( ) in WaitPerson.run( ) automatically releases the lock, so this is possible. Because the lock must be owned in order to call notify( ), it’s guaranteed that two threads trying to call notify( ) on one object won’t step on each other’s toes. Feedback

The preceding example has only a single spot for one thread to store an object so that another thread can later use that object. However, in a typical producer-consumer implementation, you use a first-in, first-out queue in order to store the objects being produced and consumed. See the exercises at the end of the chapter to learn more about this. Feedback

Using Pipes for I/O between threads

It’s often useful for threads to communicate with each other by using I/O. Threading libraries may provide support for inter-thread I/O in the form of pipes. These exist in the Java I/O library as the classes PipedWriter (which allows a thread to write into a pipe) and PipedReader (which allows a different thread to read from the same pipe). This can be thought of as a variation of the producer-consumer problem, where the pipe is the canned solution. Feedback

Here’s a simple example in which two threads use a pipe to communicate:

//: c13:PipedIO.java
// Using pipes for inter-thread I/O
import java.io.*;
import java.util.*;

class Sender extends Thread {
  private Random rand = new Random();
  private PipedWriter out = new PipedWriter();
  public PipedWriter getPipedWriter() { return out; }
  public void run() {
    while(true) {
      for(char c = 'A'; c <= 'z'; c++) {
        try {
          out.write(c);
          sleep(rand.nextInt(500));
        } catch(Exception e) {
          throw new RuntimeException(e);
        }
      }
    }
  }
}

class Receiver extends Thread {
  private PipedReader in;
  public Receiver(Sender sender) throws IOException {
    in = new PipedReader(sender.getPipedWriter());
  }
  public void run() {
    try {
      while(true) {
        // Blocks until characters are there:
        System.out.println("Read: " + (char)in.read());
      }
    } catch(IOException e) {
      throw new RuntimeException(e);
    }
  }
}

public class PipedIO {
  public static void main(String[] args) throws Exception {
    Sender sender = new Sender();
    Receiver receiver = new Receiver(sender);
    sender.start();
    receiver.start();
    new Timeout(4000, "Terminated");
  }
} ///:~


Sender and Receiver represent threads that are performing some tasks and need to communicate with each other. Sender creates a PipedWriter, which is a standalone object, but inside Receiver the creation of PipedReader must be associated with a PipedWriter in the constructor. The Sender puts data into the Writer and sleeps for a random amount of time. However, Receiver has no sleep( ) or wait( ). But when it does a read( ), it automatically blocks when there is no more data. You get the effect of a producer-consumer, but no wait( ) loop is necessary. Feedback

Notice that the sender and receiver are started in main( ), after the objects are completely constructed. If you don’t start completely constructed objects, the pipe can produce inconsistent behavior on different platforms. Feedback

More sophisticated cooperation

Only the most basic cooperation approach (producer-consumer, usually implemented with wait( ) and notify( )/notifyAll( )) has been introduced in this section. This will solve most kinds of thread cooperation problems, but there are numerous more sophisticated approaches that are described in more advanced texts (in particular, Lea, noted at the end of this chapter). Feedback

Deadlock

Because threads can become blocked and because objects can have synchronized methods that prevent threads from accessing that object until the synchronization lock is released, it’s possible for one thread to get stuck waiting for another thread, which in turn waits for another thread, etc., until the chain leads back to a thread waiting on the first one. You get a continuous loop of threads waiting on each other, and no one can move. This is called deadlock. Feedback

If you try running a program and it deadlocks right away, you immediately know you have a problem and you can track it down. The real problem is when your program seems to be working fine but has the hidden potential to deadlock. In this case you may get no indication that deadlocking is a possibility, so it will be latent in your program until it unexpectedly happens to a customer (and you probably won’t be able to easily reproduce it). Thus, preventing deadlock by careful program design is a critical part of developing concurrent programs. Feedback

Let’s look at the classic demonstration of deadlock, invented by Dijkstra: the dining philosophers problem. The basic description specifies five philosophers (but the example shown here will allow any number). These philosophers spend part of their time thinking and part of their time eating. While they are thinking, they don’t need any shared resources, but when they are eating, they sit at a table with a limited number of utensils. In the original problem description, the utensils are forks, and two forks are required to get spaghetti from a bowl in the middle of the table, but it seems to make more sense to say that the utensils are chopsticks; clearly, each philosopher will require two chopsticks in order to eat. Feedback

A difficulty is introduced into the problem: As philosophers, they have very little money, so they can only afford five chopsticks. These are spaced around the table between them. When a philosopher wants to eat, he or she must get the chopstick to the left and the one to the right. If the philosopher on either side is using the desired chopstick, then our philosopher must wait. Feedback

Note that the reason this problem is interesting is because it demonstrates that a program can appear to run correctly but actually be deadlock prone. To show this, the command-line arguments allow you to adjust the number of philosophers and a factor to affect the amount of time each philosopher spends thinking. If you have lots of philosophers and/or they spend a lot of time thinking, you may never see the deadlock even though it remains a possibility. The default command-line arguments tend to make it deadlock fairly quickly: Feedback

//: c13:DiningPhilosophers.java
// Demonstrates how deadlock can be hidden in a program.
// {Args: 5 0 deadlock 4}
import java.util.*;

class Chopstick {
  private static int counter = 0;
  private int number = counter++;
  public String toString() {
    return "Chopstick " + number;
  }
}

class Philosopher extends Thread {
  private static Random rand = new Random();
  private static int counter = 0;
  private int number = counter++;
  private Chopstick leftChopstick;
  private Chopstick rightChopstick;
  static int ponder = 0; // Package access
  public Philosopher(Chopstick left, Chopstick right) {
    leftChopstick = left;
    rightChopstick = right;
    start();
  }
  public void think() {
    System.out.println(this + " thinking");
    if(ponder > 0)
      try {
        sleep(rand.nextInt(ponder));
      } catch(InterruptedException e) {
        throw new RuntimeException(e);
      }
  }
  public void eat() {
    synchronized(leftChopstick) {
      System.out.println(this + " has "
        + this.leftChopstick + " Waiting for "
        + this.rightChopstick);
      synchronized(rightChopstick) {
        System.out.println(this + " eating");
      }
    }
  }
  public String toString() {
    return "Philosopher " + number;
  }
  public void run() {
    while(true) {
      think();
      eat();
    }
  }
}

public class DiningPhilosophers {
  public static void main(String[] args) {
    if(args.length < 3) {
      System.err.println("usage:\n" +
        "java DiningPhilosophers numberOfPhilosophers " +
        "ponderFactor deadlock timeout\n" +
        "A nonzero ponderFactor will generate a random " +
        "sleep time during think().\n" +
        "If deadlock is not the string " +
        "'deadlock', the program will not deadlock.\n" +
        "A nonzero timeout will stop the program after " +
        "that number of seconds.");
      System.exit(1);
    }
    Philosopher[] philosopher =
      new Philosopher[Integer.parseInt(args[0])];
    Philosopher.ponder = Integer.parseInt(args[1]);
    Chopstick
      left = new Chopstick(),
      right = new Chopstick(),
      first = left;
    int i = 0;
    while(i < philosopher.length - 1) {
      philosopher[i++] =
        new Philosopher(left, right);
      left = right;
      right = new Chopstick();
    }
    if(args[2].equals("deadlock"))
      philosopher[i] = new Philosopher(left, first);
    else // Swapping values prevents deadlock:
      philosopher[i] = new Philosopher(first, left);
    // Optionally break out of program:
    if(args.length >= 4) {
      int delay = Integer.parseInt(args[3]);
      if(delay != 0)
        new Timeout(delay * 1000, "Timed out");
    }
  }
} ///:~


Both Chopstick and Philosopher use an auto-incremented static counter to give each element an identification number. Each Philosopher is given a reference to a left and right Chopstick object; these are the utensils that must be picked up before that Philosopher can eat. Feedback

The static field ponder indicates whether the philosophers will spend any time thinking. If the value is nonzero, then it will be used to randomly generate a sleep time inside think( ). This way, you can show that if your threads (philosophers) are spending more time on other tasks (thinking) then they have a much lower probability of requiring the shared resources (chopsticks) and thus you can convince yourself that the program is deadlock free, even though it isn’t. Feedback

Inside eat( ), a Philosopher acquires the left chopstick by synchronizing on it. If the chopstick is unavailable, then the philosopher blocks while waiting. When the left chopstick is acquired, the right one is acquired the same way. After eating, the right chopstick is released, then the left. Feedback

In run( ), each Philosopher just thinks and eats continuously. Feedback

The main( ) method requires at least three arguments and prints a usage message if these are not present. The third argument can be the string “deadlock,” in which case the deadlocking version of the program is used. Any other string will cause the non-deadlocking version to be used. The last (optional) argument is a timeout factor, which will abort the program after that number of seconds (whether it’s deadlocked or not). The timeout is necessary for the program to be run automatically as part of the book code testing process. Feedback

After the array of Philosopher is created and the ponder value is set, two Chopstick objects are created, and the first one is also stored in the first variable for use later. Every reference in the array except the last one is initialized by creating a new Philosopher object and handing it the left and right chopsticks. After each initialization, the left chopstick is moved to the right and the right is given a new Chopstick object to be used for the next Philosopher. Feedback

In the deadlocking version, the last Philosopher is given the left chopstick and the first chopstick that was stored earlier. That’s because the last Philosopher is sitting right next to the very first one, and they both share that first chopstick. With this arrangement, it’s possible at some point for all the philosophers to be trying to eat and waiting on the philosopher next to them to put down their chopstick, and the program will deadlock. Feedback

Try experimenting with different command-line values to see how the program behaves, and in particular to see all the ways that the program can appear to be executing without deadlock. Feedback

To repair the problem, you must understand that deadlock can occur if four conditions are simultaneously met: Feedback

  1. Mutual exclusion: At least one resource used by the threads must not be shareable. In this case, a chopstick can be used by only one philosopher at a time. Feedback
  2. At least one process must be holding a resource and waiting to acquire a resource currently held by another process. That is, for deadlock to occur, a philosopher must be holding one chopstick and waiting for the other one. Feedback
  3. A resource cannot be preemptively taken away from a process. All processes must only release resources as a normal event. Our philosophers are polite and they don’t grab chopsticks from other philosophers. Feedback
  4. A circular wait must happen, whereby a process waits on a resource held by another process, which in turn is waiting on a resource held by another process, and so on, until one of the processes is waiting on a resource held by the first process, thus gridlocking everything. In this example, the circular wait happens because each philosopher tries to get the left chopstick first and then the right. In the preceding example, the deadlock is broken by swapping the initialization order in the constructor for the last philosopher, causing that last philosopher to actually get the right chopstick first, then the left. Feedback

Because all of these conditions must be met in order to cause deadlock, you only need to stop one of them from occurring in order to prevent deadlock. In this program, the easiest way to prevent deadlock is to break condition four. This condition happens because each philosopher is trying to pick up their chopsticks in a particular sequence: first left, then right. Because of that, it’s possible to get into a situation where each of them is holding their left chopstick and waiting to get the right one, causing the circular wait condition. However, if the last philosopher is initialized to try to get the right chopstick first and then the left, then that philosopher will never prevent the philosopher on the immediate left from picking up his or her right chopstick, so the circular wait is prevented. This is only one solution to the problem, but you could also solve it by preventing one of the other conditions (see more advanced threading books for more details). Feedback

There is no Java language support to help prevent deadlock; it’s up to you to avoid it by careful design. These are not comforting words to the person who’s trying to debug a deadlocking program. Feedback

The proper way to stop

One change that was introduced in Java 2 to reduce the possibility of deadlock is the deprecation of the Thread class’s stop( ), suspend( ), and resume( ) methods. Feedback

The reason that the stop( ) method is deprecated is because it doesn’t release the locks that the thread has acquired, and if the objects are in an inconsistent state (“damaged”), other threads can view and modify them in that state. The resulting problems can be subtle and difficult to detect. Instead of using stop( ), you should use a flag to tell the thread when to terminate itself by exiting its run( ) method. Here’s a simple example: Feedback

//: c13:Stopping.java
// The safe way to stop a thread.
import java.util.*;

class CanStop extends Thread {
  // Must be volatile:
  private volatile boolean stop = false;
  private int counter = 0;
  public void run() {
    while(!stop && counter < 10000) {
      System.out.println(counter++);
    }
    if(stop)
      System.out.println("Detected stop");
  }
  public void requestStop() { stop = true; }
}

public class Stopping {
  public static void main(String[] args) {
    final CanStop stoppable = new CanStop();
    stoppable.start();
    new Timer(true).schedule(new TimerTask() {
      public void run() {
        System.out.println("Requesting stop");
        stoppable.requestStop();
      }
    }, 500); // run() after 500 milliseconds
  }
} ///:~            


The flag stop must be volatile so that the run( ) method is sure to see it (otherwise the value may be cached locally). The “job” of this thread is to print out 10,000 numbers, so it is finished whenever counter >= 10000 or someone requests a stop. Note that requestStop( ) is not synchronized because stop is both boolean (changing it to true is an atomic operation) and volatile. Feedback

In main( ), a CanStop object is started, then a Timer is set up to call requestStop( ) after one half second. The constructor for Timer is passed the argument true to make it a daemon thread so that it doesn’t prevent the program from terminating. Feedback

Interrupting a blocked thread

There are times when a thread blocks—such as when it is waiting for input—and it cannot poll a flag as it does in the previous example. In these cases, you can use the Thread.interrupt( ) method to break out of the blocked code: Feedback

//: c13:Interrupt.java
// Using interrupt() to break out of a blocked thread.
import java.util.*;

class Blocked extends Thread {
  public Blocked() {
    System.out.println("Starting Blocked");
    start();
  }
  public void run() {
    try {
      synchronized(this) {
        wait(); // Blocks
      }
    } catch(InterruptedException e) {
      System.out.println("Interrupted");
    }
    System.out.println("Exiting run()");
  }
}

public class Interrupt {
  static Blocked blocked = new Blocked();
  public static void main(String[] args) {
    new Timer(true).schedule(new TimerTask() {
      public void run() {
        System.out.println("Preparing to interrupt");
        blocked.interrupt();
        blocked = null; // to release it
      }
    }, 2000); // run() after 2000 milliseconds
  }
} ///:~


The wait( ) inside Blocked.run( ) produces the blocked thread. When the Timer runs out, the object’s interrupt( ) method is called. Then the blocked reference is set to null so the garbage collector will clean it up (not necessary here, but important in a long-running program). Feedback

Thread groups

A thread group holds a collection of threads. The value of thread groups can be summed up by a quote from Joshua Bloch,[72] the software architect at Sun who fixed and greatly improved the Java collections library in JDK 1.2: Feedback

“Thread groups are best viewed as an unsuccessful experiment, and you may simply ignore their existence.”

If you’ve spent time and energy trying to figure out the value of thread groups (as I have), you may wonder why there was not some more official announcement from Sun on the topic, sooner than this (the same question could be asked about any number of other changes that have happened to Java over the years). The Nobel Laureate economist Joseph Stiglitz has a philosophy of life that would seem to apply here.[73] It’s called The Theory of Escalating Commitment: Feedback

"The cost of continuing mistakes is borne by others, while the cost of admitting mistakes is borne by yourself."

There is one tiny remaining use for thread groups. If a thread in the group throws an uncaught exception, ThreadGroup.uncaughtException( ) is invoked, which prints a stack trace to the standard error stream. If you want to modify this behavior, you must override this method. Feedback

Summary

It is vital to learn when to use concurrency and when to avoid it. The main reasons to use it are: to manage a number of tasks whose intermingling will make more efficient use of the computer (including the ability to transparently distribute the tasks across multiple CPUs), allow better code organization, or be more convenient for the user. The classic example of resource balancing is to use the CPU during I/O waits. The classic example of user convenience is to monitor a “stop” button during long downloads. Feedback

An additional advantage to threads is that they provide “light” execution context switches (on the order of 100 instructions) rather than “heavy” process context switches (thousands of instructions). Since all threads in a given process share the same memory space, a light context switch changes only program execution and local variables. A process change –the heavy context switch—must exchange the full memory space. Feedback

The main drawbacks to multithreading are:

  1. Slowdown occurs while waiting for shared resources.
  2. Additional CPU overhead is required to manage threads.
  3. Unrewarded complexity arises from poor design decisions.
  4. Opportunities are created for pathologies such as starving, racing, deadlock, and livelock.
  5. Inconsistenciesoccur across platforms. For instance, while developing some of the examples for this book, I discovered race conditions that quickly appeared on some computers but that wouldn’t appear on others. If you developed a program on the latter, you might get badly surprised when you distribute it.

One of the biggest difficulties with threads occurs because more than one thread might be sharing a resource—such as the memory in an object—and you must make sure that multiple threads don’t try to read and change that resource at the same time. This requires judicious use of the synchronized keyword, which is an essential tool, but must be understood thoroughly because it can quietly introduce deadlock situations. Feedback

In addition, there’s a certain art to the application of threads. Java is designed to allow you to create as many objects as you need to solve your problem—at least in theory. (Creating millions of objects for an engineering finite-element analysis, for example, might not be practical in Java.) However, it seems that there is an upper bound to the number of threads you’ll want to create, because at some number, threads seem to become balky. This critical point can be hard to detect, and will often depend on the OS and JVM; it could be less than a hundred or in the thousands. As you often create only a handful of threads to solve a problem, this is typically not much of a limit; yet in a more general design it becomes a constraint. Feedback

A significant nonintuitive issue in threading is that, because of thread scheduling, you can typically make your applications run faster by inserting calls to yield( ) or even sleep( ) inside run( )’s main loop. This definitely makes it feel like an art, in particular when the longer delays seem to speed up performance. The reason this happens is that shorter delays can cause the end-of-sleep( ) scheduler interrupt to happen before the running thread is ready to go to sleep, forcing the scheduler to stop it and restart it later so it can finish what it was doing and then go to sleep. The extra context switches can end up slowing things down, and the use of yield( ) or sleep( ) may prevent the extra switches. It takes extra thought to realize how messy things can get. Feedback

For more advanced discussions of threading, see Concurrent Programming in Java, 2nd Edition, by Doug Lea, Addison-Wesley, 2000. Feedback

Exercises

Solutions to selected exercises can be found in the electronic document The Thinking in Java Annotated Solution Guide, available for a small fee from www.BruceEckel.com.

  1. Inherit a class from Thread and override the run( ) method. Inside run( ), print a message, and then call sleep( ). Repeat this three times, then return from run( ). Put a start-up message in the constructor and override finalize( ) to print a shut-down message. Make a separate thread class that calls System.gc( ) and System.runFinalization( ) inside run( ), printing a message as it does so. Make several thread objects of both types and run them to see what happens. Feedback
  2. Experiment with different sleep times in Daemons.java to see what happens. Feedback
  3. In Chapter 8, locate the GreenhouseController.java example, which consists of four files. In Event.java, the class Event is based on watching the time. Change Event so that it is a Thread, and change the rest of the design so that it works with this new Thread-based Event. Feedback
  4. Modify the previous exercise so that the java.util.Timer class is used to run the system. Feedback
  5. Modify SimpleThread.java so that all the threads are daemon threads and verify that the program ends as soon as main( ) is able to exit. Feedback
  6. Demonstrate that java.util.Timer scales to large numbers by creating a program that generates many Timer objects that perform some simple task when the timeout completes (if you want to get fancy, you can jump forward to the “Windows and Applets” chapter and use the Timer objects to draw pixels on the screen, but printing to the console is sufficient).
  7. Demonstrate that a synchronized method in a class can call a second synchronized method in the same class, which can then call a third synchronized method in the same class. Create a separate Thread object that invokes the first synchronized method.
  8. Create two Thread subclasses, one with a run( ) that starts up and then calls wait( ). The other class’s run( ) should capture the reference of the first Thread object. Its run( ) should call notifyAll( ) for the first thread after some number of seconds have passed so that first thread can print a message. Feedback
  9. Create an example of a “busy wait.” One thread sleeps for awhile and then sets a flag to true. The second thread watches that flag inside a while loop (this is the “busy wait”) and when the flag becomes true, sets it back to false and reports the change to the console. Note how much wasted time the program spends inside the “busy wait” and create a second version of the program that uses wait( ) instead of the “busy wait.”
  10. Modify Restaurant.java to use notifyAll( ) and observe any difference in behavior.
  11. Modify Restaurant.java so that there are multiple WaitPersons, and indicate which one gets each Order.
  12. Modify Restaurant.java so that multiple WaitPersons generate order requests to multiple Chefs, who produce orders and notify the WaitPerson who generated the request. You’ll need to use queues for both incoming order requests and outgoing orders.
  13. Modify the previous exercise to add Customer objects that are also threads. The Customers will place order requests with WaitPersons, who give the requests to the Chefs, who fulfill the orders and notify the appropriate WaitPerson, who gives it to the appropriate Customer.
  14. Modify PipedIO.java so that Sender reads and sends lines from a text file.
  15. Change DiningPhilosophers.java so that the philosophers just pick the next available chopstick (when a philosopher is done with their chopsticks, they drop them into a bin. When a philosopher wants to eat, they take the next two available chopsticks from the bin). Does this eliminate the possibility of deadlock? Can you re-introduce deadlock by simply reducing the number of available chopsticks?
  16. Inherit a class from java.util.Timer and implement the requestStop( ) method as in Stopping.java.
  17. Modify SimpleThread.java so that all threads receive an interrupt( ) before they are completed.
  18. Solve a single producer, single consumer problem using wait( ) and notify( ). The producer must not overflow the receiver's buffer, which can happen if the producer is faster than the consumer. If the consumer is faster than the producer, then it must not read the same data more than once. Do not assume anything about the relative speeds of the producer or consumer.

[68] Runnable was in Java 1.0, while inner classes were not introduced until Java 1.1, which may partially account for the existence of Runnable. Also, traditional multithreading architectures focused on a function to be run rather than an object. My preference is always to inherit from Thread if I can; it seems cleaner and more flexible to me.

[69] Some examples were developed on a dual-processor Win2K machine that would immediately show collisions. However, the same example run on single-processor machines might run for extended periods without demonstrating a collision—this is the kind of scary behavior that makes multithreading difficult. You can imagine developing on a single-processor machine and thinking that your code is thread safe, then discovering breakages as soon as it’s moved to a multiprocessor machine.

[70] Inspired by Joshua Bloch’s Effective Java, Addison-Wesley 2001, page 190.

[71] See Design Patterns, by Gamma et. al., Addison-Wesley 1995.

[72] Effective Java, by Joshua Bloch, Addison-Wesley 2001, page 211.

[73] And in a number of other places throughout the experience of Java. Well, why stop there?—I’ve consulted on more than a few projects where this has applied.


Previous Next Title Page Index Contents