9.5 Thread Transitions
Thread States
Understanding the life cycle of a thread is valuable when programming with threads. Threads can exist in different states. Just because a thread's start() method has been called, it does not mean that the thread has access to the CPU and can start executing straight away. Several factors determine how it will proceed.
Figure 9.3 shows the states and the transitions in the life cycle of a thread.
Ready-to-run state
A thread starts life in the Ready-to-run state (see p. 369).
Running state
If a thread is in the Running state, it means that the thread is currently executing (see p. 369).
Dead state
Once in this state, the thread cannot ever run again (see p. 380).
Non-runnable states
A running thread can transit to one of the non-runnable states, depending on the circumstances. A thread remains in a non-runnable state until a special transition occurs. A thread does not go directly to the Running state from a non-runnable state, but transits first to the Ready-to-run state.
The non-runnable states can be characterized as follows:
Sleeping: The thread sleeps for a specified amount of time (see p. 370).
Blocked for I/O: The thread waits for a blocking operation to complete (see p. 380).
Blocked for join completion: The thread awaits completion of another thread (see p. 377).
Waiting for notification: The thread awaits notification from another thread (see p. 370).
Blocked for lock acquisition: The thread waits to acquire the lock of an object (see p. 359).
Figure 9.3. Thread States
Various methods from the Thread class are presented next. Examples of their usage are presented in subsequent sections.
final boolean isAlive()
This method can be used to find out if a thread is alive or dead. A thread is alive if it has been started but not yet terminated, that is, it is not in the Dead state.
final int getPriority() final void setPriority(int newPriority)
The first method returns the priority of the current thread. The second method changes its priority. The priority set will be the minimum of the two values: the specified newPriority and the maximum priority permitted for this thread.
static void yield()
This method causes the current thread to temporarily pause its execution and, thereby, allow other threads to execute.
static void sleep (long millisec) throws InterruptedException
The current thread sleeps for the specified time before it takes its turn at running again.
final void join() throws InterruptedException final void join(long millisec) throws InterruptedException
A call to any of these two methods invoked on a thread will wait and not return until either the thread has completed or it is timed out after the specified time, respectively.
void interrupt()
The method interrupts the thread on which it is invoked. In the Waiting-for-notification, Sleeping, or Blocked-for-join-completion states, the thread will receive an InterruptedException.
Thread Priorities
Threads are assigned priorities that the thread scheduler can use to determine how the threads will be scheduled. The thread scheduler can use thread priorities to determine which thread gets to run. The thread scheduler favors giving CPU time to the thread with the highest priority in the Ready-to-run state. This is not necessarily the thread that has been the longest time in the Ready-to-run state. Heavy reliance on thread priorities for the behavior of a program can make the program unportable across platforms, as thread scheduling is host platform?dependent.
Priorities are integer values from 1 (lowest priority given by the constant Thread. MIN_PRIORITY) to 10 (highest priority given by the constant Thread.MAX_PRIORITY). The default priority is 5 (Thread.NORM_PRIORITY).
A thread inherits the priority of its parent thread. Priority of a thread can be set using the setPriority() method and read using the getPriority() method, both of which are defined in the Thread class. The following code sets the priority of the thread myThread to the minimum of two values: maximum priority and current priority incremented to the next level:
myThread.setPriority(Math.min(Thread.MAX_PRIORITY, myThread.getPriority()+1));
Thread Scheduler
Schedulers in JVM implementations usually employ one of the two following strategies:
Preemptive scheduling.
If a thread with a higher priority than the current running thread moves to the Ready-to-run state, then the current running thread can be preempted (moved to the Ready-to-run state) to let the higher priority thread execute.
Time-Sliced or Round-Robin scheduling.
A running thread is allowed to execute for a fixed length of time, after which it moves to the Ready-to-run state to await its turn to run again.
It should be pointed out that thread schedulers are implementation- and platform-dependent; therefore, how threads will be scheduled is unpredictable, at least from platform to platform.
Running and Yielding
After its start() method has been called, the thread starts life in the Ready-to-run state. Once in the Ready-to-run state, the thread is eligible for running, that is, it waits for its turn to get CPU time. The thread scheduler decides which thread gets to run and for how long.
Figure 9.4 illustrates the transitions between the Ready-to-Run and Running states. A call to the static method yield(), defined in the Thread class, will cause the current thread in the Running state to transit to the Ready-to-run state, thus relinquishing the CPU. The thread is then at the mercy of the thread scheduler as to when it will run again. If there are no threads waiting in the Ready-to-run state, this thread continues execution. If there are other threads in the Ready-to-run state, their priorities determine which thread gets to execute.
Figure 9.4. Running and Yielding
By calling the static method yield(), the running thread gives other threads in the Ready-to-run state a chance to run. A typical example where this can be useful is when a user has given some command to start a CPU-intensive computation, and has the option of canceling it by clicking on a Cancel button. If the computation thread hogs the CPU and the user clicks the Cancel button, chances are that it might take a while before the thread monitoring the user input gets a chance to run and take appropriate action to stop the computation. A thread running such a computation should do the computation in increments, yielding between increments to allow other threads to run. This is illustrated by the following run() method:
public void run() {
try {
while (!done()) {
doLittleBitMore();
Thread.yield(); // Current thread yields
}
} catch (InterruptedException e) {
doCleaningUp();
}
}
Sleeping and Waking up
Figure 9.5. Sleeping and Waking up
A call to the static method sleep() in the Thread class will cause the currently running thread to pause its execution and transit to the Sleeping state. The method does not relinquish any lock that the thread might have. The thread will sleep for at least the time specified in its argument, before transitioning to the Ready-to-run state where it takes its turn to run again. If a thread is interrupted while sleeping, it will throw an InterruptedException when it awakes and gets to execute.
There are serveral overloaded versions of the sleep() method in the Thread class.
Usage of the sleep() method is illustrated in Examples 9.1, 9.2, and 9.3.
Waiting and Notifying
Waiting and notifying provide means of communication between threads that synchronize on the same object (see Section 9.4, p. 359). The threads execute wait() and notify() (or notifyAll()) methods on the shared object for this purpose. These final methods are defined in the Object class, and therefore, inherited by all objects.
These methods can only be executed on an object whose lock the thread holds, otherwise, the call will result in an IllegalMonitorStateException.
final void wait(long timeout) throws InterruptedException final void wait(long timeout, int nanos) throws InterruptedException final void wait() throws InterruptedException
A thread invokes the wait() method on the object whose lock it holds. The thread is added to the wait set of the object.
final void notify() final void notifyAll()
A thread invokes a notification method on the object whose lock it holds to notify thread(s) that are in the wait set of the object.
Communication between threads is facilitated by waiting and notifying, as illustrated by Figures 9.6 and 9.7. A thread usually calls the wait() method on the object whose lock it holds because a condition for its continued execution was not met. The thread leaves the Running state and transits to the Waiting-for-notification state. There it waits for this condition to occur. The thread relinquishes ownership of the object lock.
Figure 9.6. Waiting and Notifying
Figure 9.7. Thread Communication
Transition to the Waiting-for-notification state and relinquishing the object lock are completed as one atomic (non-interruptable) operation. The releasing of the lock of the shared object by the thread allows other threads to run and execute synchronized code on the same object after acquiring its lock.
Note that the waiting thread does not relinquish any other object locks that it might hold, only that of the object on which the wait() method was invoked. Objects that have these other locks remain locked while the thread is waiting.
Each object has a wait set containing threads waiting for notification. Threads in the Waiting-for-notification state are grouped according to the object whose wait() method they invoked.
Figure 9.7 shows a thread t1 that first acquires a lock on the shared object, and afterwards invokes the wait() method on the shared object. This relinquishes the object lock and the thread t1 awaits to be notified. While the thread t1 is waiting, another thread t2 can acquire the lock on the shared object for its own purpose.
A thread in the Waiting-for-notification state can be awakened by the occurrence of any one of these three incidents:
Another thread invokes the notify() method on the object of the waiting thread, and the waiting thread is selected as the thread to be awakened.
The waiting thread times out.
Another thread interrupts the waiting thread.
Notify
Invoking the notify() method on an object wakes up a single thread that is waiting on the lock of this object. The selection of a thread to awaken is dependent on the thread policies implemented by the JVM. On being notified, a waiting thread first transits to the Blocked-for-lock-acquisition state to acquire the lock on the object, and not directly to the Ready-to-run state. The thread is also removed from the wait set of the object. Note that the object lock is not relinquished when the notifying thread invokes the notify() method. The notifying thread relinquishes the lock at its own discretion, and the awakened thread will not be able to run until the notifying thread relinquishes the object lock.
When the notified thread obtains the object lock, it is enabled for execution, waiting in the Ready-to-run state for its turn to execute again. Finally, when it does get to execute, the call to the wait() method returns and the thread can continue with its execution.
From Figure 9.7 we see that thread t2 does not relinquish the object lock when it invokes the notify() method. Thread t1 is forced to wait in the Blocked-for-lock-acquisition state. It is shown no privileges and must compete with any other threads waiting for lock acquisition.
A call to the notify() method has no consequences if there are no threads in the wait set of the object.
In contrast to the notify() method, the notifyAll() method wakes up all threads in the wait set of the shared object. They will all transit to the Blocked-for-lock-acquisition state and contend for the object lock as explained earlier.
Time-out
The wait() call specified the time the thread should wait before being timed out, if it was not awakened as explained earlier. The awakened thread competes in the usual manner to execute again. Note that the awakened thread has no way of knowing whether it was timed out or awakened by one of the notification methods.
Interrupt
This means that another thread invoked the interrupt() method on the waiting thread. The awakened thread is enabled as previously explained, but if and when the awakened thread finally gets a chance to run, the return from the wait() call will result in an InterruptedException. This is the reason why the code invoking the wait() method must be prepared to handle this checked exception.
Example 9.4 Waiting and Notifying
class StackImpl {
private Object[] stackArray;
private volatile int topOfStack;
StackImpl (int capacity) {
stackArray = new Object[capacity];
topOfStack = -1;
}
public synchronized Object pop() {
System.out.println(Thread.currentThread() + ": popping");
while (isEmpty())
try {
System.out.println(Thread.currentThread() + ": waiting to pop");
wait(); // (1)
} catch (InterruptedException e) { }
Object obj = stackArray[topOfStack];
stackArray[topOfStack--] = null;
System.out.println(Thread.currentThread() + ": notifying after pop");
notify(); // (2)
return obj;
}
public synchronized void push(Object element) {
System.out.println(Thread.currentThread() + ": pushing");
while (isFull())
try {
System.out.println(Thread.currentThread() + ": waiting to push");
wait(); // (3)
} catch (InterruptedException e) { }
stackArray[++topOfStack] = element;
System.out.println(Thread.currentThread() + ": notifying after push");
notify(); // (4)
}
public boolean isFull() { return topOfStack >= stackArray.length -1; }
public boolean isEmpty() { return topOfStack < 0; }
}
abstract class StackUser extends Thread { // (5) Stack user
protected StackImpl stack; // (6)
StackUser(String threadName, StackImpl stack) {
super(threadName);
this.stack = stack;
System.out.println(this);
setDaemon(true); // (7) Daemon thread
start(); // (8) Start this thread.
}
}
class StackPopper extends StackUser { // (9) Popper
StackPopper(String threadName, StackImpl stack) {
super(threadName, stack);
}
public void run() { while (true) stack.pop(); }
}
class StackPusher extends StackUser { // (10) Pusher
StackPusher(String threadName, StackImpl stack) {
super(threadName, stack);
}
public void run() { while (true) stack.push(new Integer(1)); }
}
public class WaitAndNotifyClient {
public static void main(String[] args)
throws InterruptedException { // (11)
StackImpl stack = new StackImpl(5);
new StackPusher("A", stack);
new StackPusher("B", stack);
new StackPopper("C", stack);
System.out.println("Main Thread sleeping.");
Thread.sleep(1000);
System.out.println("Exit from Main Thread.");
}
}
Possible output from the program:
Thread[A,5,main] Thread[B,5,main] Thread[C,5,main] Main Thread sleeping. ... Thread[A,5,main]: pushing Thread[A,5,main]: waiting to push Thread[B,5,main]: pushing Thread[B,5,main]: waiting to push Thread[C,5,main]: popping Thread[C,5,main]: notifying after pop Thread[A,5,main]: notifying after push Thread[A,5,main]: pushing Thread[A,5,main]: waiting to push Thread[B,5,main]: waiting to push Thread[C,5,main]: popping Thread[C,5,main]: notifying after pop Thread[A,5,main]: notifying after push ... Thread[B,5,main]: notifying after push ... Exit from Main Thread. ...
In Example 9.4, three threads are manipulating the same stack. Two of them are pushing elements on the stack, while the third one is popping elements off the stack. The class diagram for Example 9.4 is shown in Figure 9.8.
The subclasses StackPopper at (9) and StackPusher at (10) extend the abstract superclass StackUser at (5).
Class StackUser, which extends the Thread class, creates and starts each thread.
Class StackImpl implements the synchronized methods pop() and push().
Figure 9.8. Stack Users
The field topOfStack in class StackImpl is declared volatile, so that read and write operations on this variable will access the master value of this variable, and not any copies, during runtime (see Section 4.10, p. 150).
Since the threads manipulate the same stack object and the push() and pop() methods in the class StackImpl are synchronized, it means that the threads synchronize on the same object. In other words, the mutual exclusion of these operations is guaranteed on the same stack object.
Example 9.4 illustrates how a thread waiting as a result of calling the wait() method on an object, is notified by another thread calling the notify() method on the same object, in order for the first thread to start running again.
One usage of the wait() call is shown in Example 9.4 at (1) in the synchronized pop() method. When a thread executing this method on the StackImpl object finds that the stack is empty, it invokes the wait() method in order to wait for some thread to push something on this stack first.
Another use of the wait() call is shown at (3) in the synchronized push() method. When a thread executing this method on the StackImpl object finds that the stack is full, it invokes the wait() method to await some thread removing an element first, in order to make room for a push operation on the stack.
When a thread executing the synchronized method push() on the StackImpl object successfully pushes an element on the stack, it calls the notify() method at (4). The wait set of the StackImpl object contains all waiting threads that had earlier called the wait() method at either (1) or (3) on this StackImpl object. A single thread from the wait set is enabled for running. If this thread was executing a pop operation, it now has a chance of being successful because the stack is not empty at the moment. If this thread was executing a push operation, it can try again to see if there is room on the stack.
When a thread executing the synchronized method pop() on the StackImpl object successfully pops an element off the stack, it calls the notify() method at (2). Again assuming that the wait set of the StackImpl object is not empty, one thread from the set is arbitrarily chosen and enabled. If the notified thread was executing a pop operation, it can proceed to see if the stack still has an element to pop. If the notified thread was executing a push operation, it now has a chance of succeeding because the stack is not full at the moment.
Note that the waiting condition at (1) for the pop operation is executed in a loop. A waiting thread that has been notified is not guaranteed to run straight away. Before it gets to run, another thread may synchronize on the stack and empty it. If the notified thread was waiting to pop the stack, it would now incorrectly pop the stack, because the condition was not tested after notification. The loop ensures that the condition is always tested after notification, sending the thread back to the Waiting-on-notification state if the condition is not met. To avert the analogous danger of pushing on a full stack, the waiting condition at (3) for the push operation is also executed in a loop.
The behavior of each thread can be traced in the output from Example 9.4. Each push-and-pop operation can be traced by a sequence consisting of the name of the operation to be performed, followed by zero or more wait messages, and concluding with a notification after the operation is done. For example, thread A performs two pushes as shown in the output from the program:
Thread[A,5,main]: pushing Thread[A,5,main]: waiting to push ... Thread[A,5,main]: notifying after push Thread[A,5,main]: pushing Thread[A,5,main]: waiting to push ... Thread[A,5,main]: notifying after push
Thread B is shown doing one push:
Thread[B,5,main]: pushing Thread[B,5,main]: waiting to push ... Thread[B,5,main]: notifying after push
Whereas thread C pops the stack twice without any waiting:
Thread[C,5,main]: popping Thread[C,5,main]: notifying after pop ... Thread[C,5,main]: popping Thread[C,5,main]: notifying after pop
When the operations are interweaved, the output clearly shows that the pushers wait when the stack is full, and only push after the stack is popped.
The three threads created are daemon threads. Their status is set at (7). They will be terminated if they have not completed when the main user-thread dies, thereby stopping the execution of the program.
Joining
A thread can invoke the overloaded method join() on another thread in order to wait for the other thread to complete its execution before continuing, that is, the first thread waits for the second thread to join it after completion. A running thread t1 invokes the method join() on a thread t2. The join() call has no effect if thread t2 has already completed. If thread t2 is still alive, then thread t1 transits to the Blocked-for-join-completion state. Thread t1 waits in this state until one of these events occur (see Figure 9.9):
Thread t2 completes.
In this case thread t1 is enabled and when it gets to run, it will continue normally after the join() method call.
Thread t1 is timed out.
The time specified in the argument in the join() method call has elapsed, without thread t2 completing. In this case as well, thread t1 is enabled. When it gets to run, it will continue normally after the join() method call.
Thread t1 is interrupted.
Some thread interrupted thread t1 while thread t1 was waiting for join completion. Thread t1 is enabled, but when it gets to execute, it will now throw an InterruptedException.
Figure 9.9. Joining of Threads
Example 9.5 illustrates joining of threads. The AnotherClient class below uses the Counter class, which extends the Thread class from Example 9.2. It creates two threads that are enabled for execution. The main thread invokes the join() method on the Counter A thread. If the Counter A thread has not already completed, the main thread transits to the Blocked-for-join-completion state. When the Counter A thread completes, the main thread will be enabled for running. Once the main thread is running, it continues with execution after (5). A parent thread can call the isAlive() method to find out whether its child threads are alive, before terminating itself. The call to the isAlive() method on the Counter A thread at (6) correctly reports that the Counter A thread is not alive. A similar scenario transpires between the main thread and the Counter B thread. The main thread passes through the Blocked-for-join-completion state twice at the most.
Example 9.5 Joining of Threads
class Counter extends Thread { /* See Example 9.2. */ }
public class AnotherClient {
public static void main(String[] args) {
Counter counterA = new Counter("Counter A");
Counter counterB = new Counter("Counter B");
try {
System.out.println("Wait for the child threads to finish.");
counterA.join(); // (5)
if (!counterA.isAlive()) // (6)
System.out.println("Counter A not alive.");
counterB.join(); // (7)
if (!counterB.isAlive()) // (8)
System.out.println("Counter B not alive.");
} catch (InterruptedException e) {
System.out.println("Main Thread interrupted.");
}
System.out.println("Exit from Main Thread.");
}
}
Possible output from the program:
Thread[Counter A,5,main] Thread[Counter B,5,main] Wait for the child threads to finish. Counter A: 0 Counter B: 0 Counter A: 1 Counter B: 1 Counter A: 2 Counter B: 2 Counter A: 3 Counter B: 3 Counter A: 4 Counter B: 4 Exit from Counter A. Counter A not alive. Exit from Counter B. Counter B not alive. Exit from Main Thread.
Blocking for I/O
A running thread, on executing a blocking operation requiring a resource (like a call to an I/O method), will transit to the Blocked-for-I/O state. The blocking operation must complete before the thread can proceed to the Ready-to-run state. An example is a thread reading from the standard input terminal, which blocks until input is provided:
int input = System.in.read();
Thread Termination
A thread can transit to the Dead state from the Running or the Ready-to-run states. The thread dies when it completes its run() method, either by returning normally or by throwing an exception. Once in this state, the thread cannot be resurrected. There is no way the thread can be enabled for running again, not even by calling the start() method once more on the thread object.
Example 9.6 illustrates a typical scenario where a thread can be controlled by one or more threads. Work is performed by a loop body, which the thread executes continually. It should be possible for other threads to start and stop the worker thread. This functionality is implemented by the class Worker at (1), which has a private field theThread declared at (2) to keep track of the Thread object executing its run() method.
The kickStart() method at (3) in class Worker creates and starts a thread if one is not already running. It is not enough to just call the start() method on a thread that has terminated. A new Thread object must be created first. The terminate() method at (4) sets the field theThread to null. Note that this does not affect any Thread object that might have been denoted, by the reference theThread. The runtime system maintains any such Thread object; therefore, changing one of its references does not affect the object.
The run() method at (5) has a loop whose execution is controlled by a special condition. The condition tests to see whether the Thread object denoted by the reference theThread and the Thread object executing now, are one and the same. This is bound to be the case if the reference theThread has the same reference value it was assigned when the thread was created and started in the kickStart() method. The condition will then be true, and the body of the loop will execute. However, if the value in the reference theThread has changed, the condition will be false. In that case, the loop will not execute, the run() method will complete and the thread will terminate.
A client can control the thread implemented by the class Worker, using the kickStart() and the terminate() methods. The client is able to terminate the running thread at the start of the next iteration of the loop body, simply by changing the theThread reference to null.
In Example 9.6, a Worker object is first created at (8) and a thread started on this Worker object at (9). The main thread invokes the yield() method at (10) to temporarily stop its execution, and give the thread of the Worker object a chance to run. The main thread, when it is executing again, terminates the thread of the Worker object at (11), as explained earlier. This simple scenario can be generalized where several threads, sharing a single Worker object, could be starting and stopping the thread of the Worker object.
Example 9.6 Thread Termination
class Worker implements Runnable { // (1)
private Thread theThread; // (2)
public void kickStart() { // (3)
if (theThread == null) {
theThread = new Thread(this);
theThread.start();
}
}
public void terminate() { // (4)
theThread = null;
}
public void run() { // (5)
while (theThread == Thread.currentThread()) { // (6)
System.out.println("Going around in loops.");
}
}
}
public class Controller {
public static void main(String[] args) { // (7)
Worker worker = new Worker(); // (8)
worker.kickStart(); // (9)
Thread.yield(); // (10)
worker.terminate(); // (11)
}
}
Possible output from the program:
Going around in loops. Going around in loops. Going around in loops. Going around in loops. Going around in loops.
Deadlocks
A deadlock is a situation where a thread is waiting for an object lock that another thread holds, and this second thread is waiting for an object lock that the first thread holds. Since each thread is waiting for the other thread to relinquish a lock, they both remain waiting forever in the Blocked-for-lock-acquisition state. The threads are said to be deadlocked.
A deadlock is depicted in Figure 9.10. Thread t1 has a lock on object o1, but cannot acquire the lock on object o2. Thread t2 has a lock on object o2, but cannot acquire the lock on object o1. They can only proceed if one of them relinquishes a lock the other one wants, which is never going to happen.
Figure 9.10. Deadlock
The situation in Figure 9.10 is implemented in Example 9.7. Thread t1 at (3) tries to synchronize at (4) and (5), first on string o1 at (1) then on string o2 at (2), respectively. The thread t2 at (6) does the opposite. It synchronizes at (7) and (8), first on string o2 then on string o1, respectively. A deadlock can occur as explained previously.
However, the potential of deadlock in the situation in Example 9.7 is easy to fix. If the two threads acquire the locks on the objects in the same order, then mutual lock dependency is avoided and a deadlock can never occur. This means having the same locking order at (4) and (5) as at (7) and (8). In general, the cause of a deadlock is not always easy to discover, let alone easy to fix.
Example 9.7 Deadlock
public class DeadLockDanger {
String o1 = "Lock " ; // (1)
String o2 = "Step "; // (2)
Thread t1 = (new Thread("Printer1") { // (3)
public void run() {
while(true) {
synchronized(o1) { // (4)
synchronized(o2) { // (5)
System.out.println(o1 + o2);
}
}
}
}
});
Thread t2 = (new Thread("Printer2") { // (6)
public void run() {
while(true) {
synchronized(o2) { // (7)
synchronized(o1) { // (8)
System.out.println(o2 + o1);
}
}
}
}
});
public static void main(String[] args) {
DeadLockDanger dld = new DeadLockDanger();
dld.t1.start();
dld.t2.start();
}
}
Possible output from the program:
... Step Lock Step Lock Lock Step Lock Step Lock Step ...
