Java Threads Monologue
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.
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.
posted by Anand @ 4:42 AM
1 comments
