|
|
Optimize with a SATA RAID Storage Solution
Range of capacities as low as $1250 per TB. Ideal if you currently rely on servers/disks/JBODs
Page 3 of 7
wait() and notify()The following code demonstrates a blocking queue used for one thread to notify another when some event occurs. (We'll see a more realistic version of these in a future article, but for now I want to keep things simple.) The basic notion is that a thread that tries to dequeue from an empty queue will block until some other thread puts something in the queue.
class Notifying_queue
{
private static final queue_size = 10;
private Object[] queue = new Object[ queue_size ];
private int head = 0;
private int tail = 0;
public void synchronized enqueue( Object item )
{
queue[++head %= queue_size ]= item;
this.notify(); // The "this" is there only to
} // improve readability.
public Object synchronized dequeue( )
{
try
{ if( head == tail ) // <=== This is a bug
this.wait();
}
catch( InterruptedException e )
{
// If we get here, we were not actually notified.
// returning null doesn't indicate that the
// queue is empty, only that the waiting was
// abandoned.
return null;
}
return queue[++tail %= queue_size ];
}
}
Starting with an empty queue, let's follow the sequence of operations in play if one thread does a dequeue and then another (at some later time) enqueues an item.
dequeue(), entering the monitor (and locking out other threads) until the monitor is released. The thread tests for an empty queue
(head==tailwait(). (I'll explain why this is a bug in a moment.)wait() releases the lock. (The current thread temporarily leaves the monitor.) It then blocks on a second synchronization object called a condition variable. (The basic notion of a condition variable is that a thread blocks until some condition becomes true. In the case of Java's
built-in condition variable, the thread will wait until the notified condition is set to true by some other thread calling
notify.) It's important to realize that the waiting thread has released the monitor at this juncture.notify(), thereby releasing the waiting (dequeueing) thread.wait() can return, so it blocks again, this time on the lock associated with the monitor.enqueue() method releasing the monitor.wait() returns, an object is dequeued, and dequeue() returns, releasing the monitor.
Race conditions following a wait()
Now, what sorts of problems can arise? The main ones are unexpected race conditions. First, what if you replaced the notify() call with a call to notifyAll()? Imagine that several threads were simultaneously trying to dequeue something from the same, empty, queue. All of these threads
are blocked on a single condition variable, waiting for an enqueue operation to be executed. When enqueue() sets the condition to true by calling notifyAll(), the threads are all released from the wait (moved from a suspended to a runnable state). The released threads all try to acquire the monitor at once, but only one would "win" and get the enqueued object.
The problem is that the others would then get the monitor too, in some undefined sequence, after the winning thread had dequeued
the object and returned from dequeue(). Since these other threads don't retest for an empty queue, they will dequeue garbage. (Looking at the code, the dequeue() method will advance the tail pointer to the next slot, the contents of which are undefined since the queue is empty.)