wait and notify ​

In a Java program, synchronized solves the problem of thread competition. For example, in a task manager where multiple threads add tasks to a queue simultaneously, you can use synchronized for locking:

class TaskQueue {
    Queue<String> queue = new LinkedList<>();

    public synchronized void addTask(String s) {
        this.queue.add(s);
    }
}

However, synchronized does not solve the issue of thread coordination.

Take the above TaskQueue as an example, and let's add a getTask() method to retrieve the first task from the queue:

class TaskQueue {
    Queue<String> queue = new LinkedList<>();

    public synchronized void addTask(String s) {
        this.queue.add(s);
    }

    public synchronized String getTask() {
        while (queue.isEmpty()) {
        }
        return queue.remove();
    }
}

The code above seems fine: getTask() first checks if the queue is empty, and if it is, it loops until another thread adds a task to the queue. Once the while() loop exits, it returns an element from the queue.

However, in practice, the while() loop will never exit. This is because when a thread executes the while() loop, it has already acquired the this lock at the entrance of getTask(). Other threads cannot call addTask() because it also requires acquiring the this lock.

As a result, executing the above code will cause the thread to enter an infinite loop in getTask(), occupying 100% of the CPU resources.

If we think deeper, the desired execution behavior is:

1. Thread 1 can continuously add tasks to the queue by calling addTask().
2. Thread 2 can retrieve tasks from the queue by calling getTask(). If the queue is empty, getTask() should wait until there is at least one task in the queue before returning.

Thus, the principle of thread coordination is: when a condition is not met, the thread enters a waiting state; when the condition is met, the thread is awakened to continue executing tasks.

For the above TaskQueue, we first modify the getTask() method to put the thread into a waiting state when the condition is not met:

public synchronized String getTask() {
    while (queue.isEmpty()) {
        this.wait();
    }
    return queue.remove();
}

When a thread reaches the while loop inside getTask(), it has already acquired the this lock. At this point, the thread checks the condition, and if it is true (the queue is empty), the thread executes this.wait() and enters a waiting state.

The key here is that the wait() method must be called on the current lock object. Since the lock acquired here is this, we call this.wait().

After calling wait(), the thread enters a waiting state, and the wait() method will not return until, at some future time, another thread awakens it. Once awakened, the wait() method returns, and the thread continues executing the next statement.

Some attentive readers might point out that even if the thread is waiting inside getTask(), other threads cannot execute addTask() if they cannot acquire the this lock. What should be done?

The solution lies in the complex execution mechanism of the wait() method. It is not a regular Java method but a native method defined in the Object class, implemented in C within the JVM. Also, the wait() method can only be called within a synchronized block because it releases the lock acquired by the thread when called, and when returning, it attempts to re-acquire the lock.

Thus, wait() can only be called on a lock object. Since we acquired the this lock in getTask(), we can only call wait() on the this object:

public synchronized String getTask() {
    while (queue.isEmpty()) {
        // Release the this lock:
        this.wait();
        // Reacquire the this lock
    }
    return queue.remove();
}

When a thread is waiting on this.wait(), it releases the this lock, allowing other threads to acquire the this lock in the addTask() method.

Now, we face a second issue: how do we wake up the waiting thread so that it can return from the wait() method? The answer is to call the notify() method on the same lock object. We modify addTask() as follows:

public synchronized void addTask(String s) {
    this.queue.add(s);
    this.notify(); // Wake up the thread waiting on the this lock
}

Notice that after adding a task to the queue, the thread immediately calls notify() on the this lock object. This method will wake up a thread that is currently waiting on the this lock (the thread in getTask() waiting on this.wait()), allowing the waiting thread to return from the wait() method.

Let's look at a complete example:

import java.util.*;

public class Main {
    public static void main(String[] args) throws InterruptedException {
        var q = new TaskQueue();
        var ts = new ArrayList<Thread>();
        for (int i = 0; i < 5; i++) {
            var t = new Thread() {
                public void run() {
                    // Execute task:
                    while (true) {
                        try {
                            String s = q.getTask();
                            System.out.println("execute task: " + s);
                        } catch (InterruptedException e) {
                            return;
                        }
                    }
                }
            };
            t.start();
            ts.add(t);
        }
        var add = new Thread(() -> {
            for (int i = 0; i < 10; i++) {
                // Add task:
                String s = "t-" + Math.random();
                System.out.println("add task: " + s);
                q.addTask(s);
                try { Thread.sleep(100); } catch (InterruptedException e) {}
            }
        });
        add.start();
        add.join();
        Thread.sleep(100);
        for (var t : ts) {
            t.interrupt();
        }
    }
}

class TaskQueue {
    Queue<String> queue = new LinkedList<>();

    public synchronized void addTask(String s) {
        this.queue.add(s);
        this.notifyAll();
    }

    public synchronized String getTask() throws InterruptedException {
        while (queue.isEmpty()) {
            this.wait();
        }
        return queue.remove();
    }
}

In this example, we focus on the addTask() method, where this.notifyAll() is called instead of this.notify(). Using notifyAll() wakes up all the threads currently waiting on the this lock, whereas notify() would wake up just one of them (which one depends on the operating system and is somewhat random). Since there could be multiple threads waiting in the getTask() method, using notifyAll() ensures that all of them are awakened. Generally, notifyAll() is safer. In some cases, if the logic is not carefully designed, using notify() may wake up only one thread, leaving the others waiting indefinitely.

However, note that when a thread is awakened from wait(), it needs to reacquire the this lock before it can continue executing. If three threads are awakened, they must first wait for the thread executing addTask() to finish and release the this lock. Afterward, only one of these threads can acquire the lock, while the other two will continue to wait.

Also, notice that we call wait() inside a while loop rather than an if statement:

public synchronized String getTask() throws InterruptedException {
    if (queue.isEmpty()) {
        this.wait();
    }
    return queue.remove();
}

This approach is incorrect because, when a thread is awakened, it must reacquire the this lock. If multiple threads are awakened, only one can acquire the lock, and that thread can then remove an element from the queue. If the other threads get the lock later, the queue might already be empty. Therefore, always use a while loop for wait(), and after being awakened and acquiring the lock, the condition must be checked again:

while (queue.isEmpty()) {
    this.wait();
}

Writing correct multithreaded code is very challenging. Many conditions need to be carefully considered, and any oversight can cause abnormal thread behavior.

Summary ​

wait and notify are used for thread coordination:

• wait() can be called inside a synchronized block to put a thread into a waiting state.
• The wait() method must be called on an acquired lock object.
• notify() or notifyAll() can be called inside a synchronized block to wake up waiting threads.
• These methods must be called on the acquired lock object.
• Awakened threads must reacquire the lock before proceeding.