Java Threads: The Hand-Off Traditionally, one of the most difficult (or even impossible) parts of multi-threaded programming was the hand-off, the coordinated transfer of control from one thread to another. Let's build an example using a queue:
On
Thread-A, application code asks a
Queue to
add() a
Task for
Thread-B to perform.
The
Queue, which is performing the
add() on
Thread-A, places the
Task into its list of tasks, and notifies
Thread-B.
Thread-B wakes up, and asks the
Queue to
take() the next
Task.
Well, that's pretty simple. Except it doesn't include any thread safety. So, let's introduce the concept of
synchronizing on some object. Synchronizing, in computer terms, means to obtain a specific
monitor (or semaphore) that only one thread can hold at a time. Think of it as the key to the bathroom door at the gas station on the side of the highway. The owner wants to make sure that either no one is in the bathroom, or one customer is in the bathroom, so a lock (monitor) is placed on the bathroom door and only the customer that gets the key (of which there is only one) can get in. So let's rewrite the above:
Thread-A synchronizes on (obtains the monitor for) the
Queue.
On
Thread-A, application code asks a
Queue to
add() a
Task for
Thread-B to perform.
The
Queue, which is performing the
add() on
Thread-A, places the
Task into its list of tasks.
As part of adding the task, the
Queue notifies
Thread-B that a task is queued.
Thread-A releases the monitor for the
Queue.
Thread-B wakes up.
Thread-B synchronizes on (obtains the monitor for) the
Queue.
Thread-B asks the
Queue to
take() the next
Task.
Thread-B releases the monitor for the
Queue.
Thread-B executes the
Task.
Thread-B checks to see if the
Queue is empty, and since it is, it goes back to sleep, waiting on the
Queue for the next
Task.
(If you're the smart kid with the thick glasses that knows that the above is incorrect, please put your hand down and wait patiently.)
Without going into a lot of details, because I know I'd get them all wrong, the above is similar to how we were forced to do multi-threaded programming on Windows (WIN32) in C++ in the mid-90s. It has a problem, though. There are "gaps" in the hand-off.
So what's a hand-off? Rugby and (American) Football players know quite well that one of the most dangerous times in terms of "protecting the ball" comes when one player gives it to another. Similarly, in a relay race (track & field), each runner must hand the baton to the next, and it is the most dangerous part of the race for a runner, in that time can easily be lost in a bad transfer, and a team that drops the baton will surely lose the race (see the Berlin Olympics, 1936, if I remember one example correctly.)
Similarly, for one thread to pick up responsibility from another, there must be a hand-off. That means that both threads must have some overlap in their ownership. To prove the problem in the above execution, just imagine many tasks being added, and tasks being taken off for execution in parallel, and then suddenly no more tasks are added. Every once in a while,
Thread-A will
add() a
Task to the
Queue and notify
Thread-B, and
Thread-B will not get the notification, because it wasn't yet waiting for the notification. This will cause that
Task to "stick" in the
Queue until someone adds another
Task. So let's re-write it again:
When
Thread-B starts running, it synchronizes on (obtains the monitor for) the
Queue.
Thread-B checks to see if the
Queue is empty, and since it is, it goes to sleep, waiting on the
Queue for the next
Task. (Note that
Thread-B never released the monitor on the
Queue.)
Thread-A synchronizes on (obtains the monitor for) the
Queue. This is permitted because, while
Thread-B holds the monitor for the
Queue, it is explicitly waiting on the
Queue, which means it has given permission for another thread to obtain the monitor for as long as
Thread-B is waiting.
On
Thread-A, application code asks a
Queue to
add() a
Task for
Thread-B to perform.
The
Queue, which is performing the
add() on
Thread-A, places the
Task into its list of tasks.
As part of adding the task, the
Queue notifies
Thread-B that a task is queued.
Since
Thread-B is waiting on the
Queue, through which it has just been notified, it (
Thread-B) is awoken.
Thread-B is supposed to own the monitor for the
Queue; since it is still taken by
Thread-A,
Thread-B is blocked from finishing the "wait" until the monitor becomes available.
Meanwhile,
Thread-A releases the monitor for the
Queue.
Thread-B now is able to re-obtain the monitor for the
Queue, and thus can finish its "wait" and start running again.
Thread-B asks the
Queue to
take() the next
Task.
Thread-B executes the
Task.
Thread-B checks to see if the
Queue is empty, and since it is, it goes back to sleep, waiting on the
Queue for the next
Task.
Now, the cycle is complete, because
Thread-B now is in a steady state such that it only will go into a wait if there is nothing in the
Queue, and if it is certain of that (even as it goes to sleep) because the monitor is not released until
Thread-B is actually set up in that "wait" state. Here is an example of the
Queue's
take() operation that
Thread-B performs:
public synchronized Runnable take() throws InterruptedException { // wait for tasks to be added if there are none already there while (getList().isEmpty()) { wait(); } // return the first task to be executed return (Runnable) getList().remove(0); }From the point of view of
Thread-A, when it obtains the monitor for the
Queue, it knows that
Thread-B is in a state in which it will hear the notification that something has been added. Here is an example of the
Queue's
add() operation that
Thread-A performs:
public synchronized void add(Runnable task) { // enqueue the task getList().add(task); // tell the waiting thread to process the task notify(); }The main thing to notice is that the wait() and notify() methods can only be used on objects for which a monitor is already obtained. And simply, that is the secret behind the safe hand-off.