Java Threads, Second Edition

Wait and Notify

Just as each object has a lock that can be obtained and released, each object also provides a mechanism that allows it to be a waiting area. And just like the lock mechanism, the main reason for this mechanism is to aid communication between threads.^[3] The idea behind the mechanism is actually simple: one thread needs a certain condition to exist and assumes that another thread will create that condition. When this other thread creates the condition, it notifies the first thread that has been waiting for the condition. This is accomplished with the following methods:

void wait()

Waits for a condition to occur. This is a method of the Object class and must be called from within a synchronized method or block.

void notify()

Notifies a thread that is waiting for a condition that the condition has occurred. This is a method of the Object class and must be called from within a synchronized method or block.

wait(), notify(), and the Object Class

Interestingly enough, just like the synchronized method, the wait and notify mechanism is available from every object in the Java system. However, this mechanism is accomplished by method invocations, whereas the synchronized mechanism is done by adding a keyword.

The wait()/notify() mechanism works because these are methods of the Object class. Since every object in the Java system inherits directly or indirectly from the Object class, it is also an Object and hence has support for this mechanism.

What is the purpose of the wait and notify mechanism, and how does it work? The wait and notify mechanism is also a synchronization mechanism; however, it is more of a communication mechanism: it allows one thread to communicate to another thread that a particular condition has occurred. The wait and notify mechanism does not specify what the specific condition is.

Can wait and notify be used to replace the synchronized method? Actually, the answer is no. Wait and notify does not solve the race condition problem that the synchronized mechanism solves. As a matter of fact, wait and notify must be used in conjunction with the synchronized lock to prevent a race condition in the wait and notify mechanism itself.

Let’s use this technique to solve the timing problem in the BusyFlag class. In our earlier version, the getBusyFlag() method would call tryGetBusyFlag() to obtain the busyflag. If it could not get the flag, it would try again 100 milliseconds later. But what we are really doing is waiting for a condition (a free busyflag) to occur. So we can apply this mechanism: if we don’t have the condition (a free busyflag), we wait() for the condition. And when the flag is freed, we notify() a waiting thread that the condition now exists. This gives us the final, optimal implementation of the BusyFlag class:

public class BusyFlag {
    protected Thread busyflag = null;
    protected int busycount = 0;

    public synchronized void getBusyFlag() {
        while (tryGetBusyFlag() == false) {
            try {
                wait();
            } catch (Exception e) {}
        }
    }

    public synchronized boolean tryGetBusyFlag() {
        if (busyflag == null) {
            busyflag = Thread.currentThread();
            busycount = 1;
            return true;
        }
        if (busyflag == Thread.currentThread()) {
            busycount++;
            return true;
        }
        return false;
    }

    public synchronized void freeBusyFlag() {
        if (getBusyFlagOwner() == Thread.currentThread()) {
            busycount--;
            if (busycount == 0) {
                busyflag = null;
                notify();
            }
        }
    }

    public synchronized Thread getBusyFlagOwner() {
        return busyflag;
    }
}

In this new version of the getBusyFlag() method, the 100-millisecond sleep is removed and replaced with a call to the wait() method. This is the wait for the required condition to occur. The freeBusyFlag() method now contains a call to the notify() method. This is the notification that the required condition has occurred. This new implementation is much better than the old one. We now wait() until the busyflag is free—no more and no less—and we no longer waste CPU cycles by waking up every 100 milliseconds to test if the busyflag is free.

Wait and Notify and Synchronization

As noted, the wait and notify mechanism has a race condition that needs to be solved with the synchronization lock. Unfortunately, it is not possible to solve the race condition without integrating the lock into the wait and notify mechanism. This is why it is mandatory for the wait() and notify() methods to hold the locks for the objects for which they are waiting or notifying.

The wait() method releases the lock prior to waiting, and reacquires the lock prior to returning from the wait() method. This is done so that no race condition exists. If you recall, there is no concept of releasing and reacquiring a lock in the Java API. The wait() method is actually tightly integrated with the synchronization lock, using a feature not available directly from the synchronization mechanism. In other words, it is not possible for us to implement the wait() method purely in Java: it is a native method.

This integration of the wait and notify and the synchronized method is actually standard. In other systems, such as Solaris or POSIX threads, condition variables also require that a mutex lock be held for the mechanism to work.

There is another change: the getBusyFlag() method is now synchronized. The getBusyFlag() method was not synchronized in our earlier examples because the lock scope would have been too large. It would not have been possible for the freeBusyFlag() method to be called while the getBusyFlag() method held the lock. However, because of the way in which the wait() method works, there is no longer a danger of deadlock. The wait() method will release the lock, which will allow other threads to execute the freeBusyFlag() method. Before the wait() method returns, it will reacquire the lock, so that to the developer, it appears as if the lock has been held the entire time.

What happens when notify() is called and there is no thread waiting? This is a valid situation. Even with our BusyFlag class, it is perfectly valid to free the busyflag when there is no other thread waiting to get the busyflag. Since the wait and notify mechanism does not know the condition about which it is sending notification, it assumes that a notification for which there is no thread waiting is a notification that goes unheard. In other words, if notify() is called without another thread waiting, then notify() simply returns.

What are the details of the race condition that exists in wait and notify? In general, a thread that uses the wait() method confirms that a condition does not exist (typically by checking a variable) and then calls the wait() method. When another thread sets the condition (typically by setting that same variable), it then calls the notify() method. A race condition occurs when:

1. The first thread tests the condition and confirms that it must wait.

2. The second thread sets the condition.

3. The second thread calls the notify() method; this goes unheard, since the first thread is not yet waiting.

4. The first thread calls the wait() method.

How does this potential race condition get resolved? This race condition is resolved by the synchronization lock discussed earlier. In order to call wait() or notify(), we must have obtained the lock for the object on which we’re calling the wait() or notify() method. This is mandatory: the methods will not work properly and will generate an exception condition if the lock is not held. Furthermore, the wait() method also releases the lock prior to waiting and reacquires the lock prior to returning from the wait() method. The developer must use this lock to ensure that checking the condition and setting the condition is atomic, which typically means that the condition is held in an instance variable within the locked object.

Is there a race condition during the period that the wait() method releases and reacquires the lock? The wait() method is tightly integrated with the lock mechanism. The object lock is not actually freed until the waiting thread is already in a state in which it can receive notifications. This would have been difficult, if not impossible, to accomplish if we had needed to implement the wait() and notify() methods ourselves. For our purposes, this is an implementation detail. It works, and works correctly. The system prevents any race conditions from occurring in this mechanism.

Wait and Notify and the Synchronized Block

In all the wait and notify examples so far, we have used synchronized methods. However, there is no reason we can’t use the synchronized block syntax instead. The only requirement is that the object on which we are synchronizing must be the same object on which we call the wait() and notify() methods. An example could be as follows:

public class ExampleBlockLock {
    private StringBuffer sb = new StringBuffer();
    public void getLock() {
        doSomething(sb);
        synchronized (sb) {
            try {
                sb.wait();
            } catch (Exception e) {}
        }
    }
    public void freeLock() {
        doSomethingElse(sb);
        synchronized (sb) {
            sb.notify();
        }
    }
}

Why does the getBusyFlag() method loop to test if the tryGetBusyFlag() method returns false? Isn’t the flag going to be free when the wait() method returns? No, the flag won’t necessarily be free when the wait() method returns. The race condition that is solved internally to the wait and notify mechanism only prevents the loss of notifications. It does not solve the following case:

1. The first thread acquires the busyflag.

2. The second thread calls tryGetBusyFlag(), which returns false.

3. The second thread executes the wait() method, which frees the synchronization lock.

4. The first thread enters the freeBusyFlag() method, obtaining the synchronization lock.

5. The first thread calls the notify() method.

6. The third thread attempts to call getBusyFlag() and blocks waiting for the synchronization lock.

7. The first thread exits the freeBusyFlag() method, releasing the synchronization lock.

8. The third thread acquires the synchronization lock and enters the getBusyFlag() method. Because the busyflag is free, it obtains the busyflag and exits the getBusyFlag() method, releasing the synchronization lock.

9. The second thread, having received notification, returns from the wait() method, reacquiring the synchronization lock along the way.

10. The second thread calls the tryGetBusyFlag() method again, confirms that the flag is busy, and calls the wait() method.

If we had implemented the getBusyFlag() method without the loop:

public synchronized void getBusyFlag() {
    if (tryGetBusyFlag() == false) {
        try {
            wait();
            tryGetBusyFlag();
        } catch (Exception e) {}
    }
}

then in step 10 the second thread would have returned from the getBusyFlag() method even though the tryGetBusyFlag() method had not acquired the busyflag. All we know when the wait() method returns is that at some point in the past, the condition had been satisfied and another thread called the notify() method; we cannot assume that the condition is still satisfied without testing the condition again. Hence, we always need to put the call to the wait() method in a loop.

---

^[3] Under Solaris or POSIX threads, these are often referred to as condition variables ; on Windows 95/NT, they are referred to as event variables.