The basic await operation is:

create and add new node to condition queue; release  lock;

block until node is on lock queue; re-acquire lock;

And the signal operation is:

transfer the first node from condition queue to lock queue;

Because these operations are performed only when the lock is held, they can use sequential linked queue operations (using a nextWaiter field in nodes) to maintain the condition queue。 The transfer operation simply unlinks the first node from the condition queue, and then uses CLH insertion to attach it to the lock queue。

}

And the release operation is:

if (tryRelease(arg) && head node's signal bit is set) { compareAndSet head's signal bit to false;

unpark head's successor, if one exists

}

The number of iterations of the main acquire loop depends, of course, on the nature of tryAcquire。  Otherwise,  in the absence of cancellation, each component of acquire and release is a constant-time O(1) operation, amortized across threads, disregarding any OS thread scheduling occuring within  park。

Cancellation support mainly entails checking for interrupt or timeout upon each return from park inside the acquire loop。 A cancelled thread due to timeout or interrupt sets  its node status and unparks its successor so it may reset links。 With cancellation, determining predecessors and successors and resetting status may include O(n) traversals (where n is the length of the queue)。 Because a thread never again blocks for a cancelled operation, links and status fields tend to restabilize quickly。

3。4Condition Queues

The synchronizer framework provides a ConditionObject class for use by synchronizers that maintain exclusive synchronization and conform to the Lock interface。 Any number of condition objects may be attached to a lock object, providing classic monitor-style await, signal, and signalAll operations, including those with timeouts, along with some inspection and monitoring methods。

The main complication in implementing these operations is dealing with cancellation of condition waits due to timeouts or Thread。interrupt。 A cancellation and signal occuring at approximately the same time encounter a race whose outcome conforms to the specifications for built-in monitors。 As revised in JSR133, these require that if an interrupt occurs before a signal, then the await method must, after re-acquiring the lock, throw InterruptedException。 But if it is interrupted after a signal, then the method must return without throwing an exception, but with its thread interrupt status set。

To maintain proper ordering, a bit in the queue node  status records whether the node has been (or is in the process of being) transferred。  Both the signalling code and the cancelling code  try to compareAndSet this status。 If a signal operation loses this race, it instead transfers the next node on the queue, if one exists。 If a cancellation loses, it must abort the transfer, and then await lock re-acquisition。 This latter case introduces  a  potentially unbounded spin。 A cancelled wait cannot commence lock re- acquisition until the node has been successfully inserted on the lock queue, so must spin waiting for the CLH queue insertion compareAndSet being performed by the signalling thread to succeed。 The need to spin here is rare, and employs a Thread。yield to provide a scheduling hint that some other thread, ideally the one doing the signal, should instead run。 While it would be possible to implement here a helping strategy for the cancellation to insert the node, the case is much too rare to justify the added overhead that this would entail。 In all other cases, the basic mechanics here and elsewhere use no spins or yields, which maintains reasonable performance on uniprocessors。

4。USAGE

Class AbstractQueuedSynchronizer ties together the above functionality and serves as a "template method pattern" [6] base class for synchronizers。 Subclasses define only the methods that implement the state inspections and updates that control acquire and release。 However, subclasses of Ab- stractQueuedSynchronizer are not themselves usable as synchronizer ADTs, because the class necessarily exports the methods needed to internally control acquire and release policies, which should not be made visible to users of these classes。 All java。util。concurrent synchronizer classes declare a private inner AbstractQueuedSynchronizer subclass and delegate all synchronization methods to it。 This also allows public methods to be given names appropriate to the synchronizer。