AbstractQueuedSynchronizer

Provides a framework for implementing blocking locks and related synchronizers (semaphores, events, etc) that rely on first-in-first-out (FIFO) wait queues. This class is designed to be a useful basis for most kinds of synchronizers that rely on a single atomic {@code int} value to represent state. Subclasses must define the protected methods that change this state, and which define what that state means in terms of this object being acquired or released. Given these, the other methods in this class carry out all queuing and blocking mechanics. Subclasses can maintain other state fields, but only the atomically updated {@code int} value manipulated using methods {@link #getState}, {@link #setState} and {@link #compareAndSetState} is tracked with respect to synchronization.

<p>Subclasses should be defined as non-internal helper classes that are used to implement the synchronization properties of their enclosing class. Class {@code AbstractQueuedSynchronizer} does not implement any synchronization interface. Instead it defines methods such as {@link #acquireInterruptibly} that can be invoked as appropriate by concrete locks and related synchronizers to implement their methods.

<p>This class supports either or both a default <em>exclusive</em> mode and a <em>shared</em> mode. When acquired in exclusive mode, attempted acquires by other threads cannot succeed. Shared mode acquires by multiple threads may (but need not) succeed. This class does not &quot;understand&quot; these differences except in the mechanical sense that when a shared mode acquire succeeds, the next waiting thread (if one exists) must also determine whether it can acquire as well. Threads waiting in the different modes share the same FIFO queue. Usually, implementation subclasses support only one of these modes, but both can come into play for example in a {@link ReadWriteLock}. Subclasses that support only exclusive or only shared modes need not define the methods supporting the unused mode.

<p>This class defines a nested {@link ConditionObject} class that can be used as a {@link Condition} implementation by subclasses supporting exclusive mode for which method {@link #isHeldExclusively} reports whether synchronization is exclusively held with respect to the current thread, method {@link #release} invoked with the current {@link #getState} value fully releases this object, and {@link #acquire}, given this saved state value, eventually restores this object to its previous acquired state. No {@code AbstractQueuedSynchronizer} method otherwise creates such a condition, so if this constraint cannot be met, do not use it. The behavior of {@link ConditionObject} depends of course on the semantics of its synchronizer implementation.

<p>This class provides inspection, instrumentation, and monitoring methods for the internal queue, as well as similar methods for condition objects. These can be exported as desired into classes using an {@code AbstractQueuedSynchronizer} for their synchronization mechanics.

<p>Serialization of this class stores only the underlying atomic integer maintaining state, so deserialized objects have empty thread queues. Typical subclasses requiring serializability will define a {@code readObject} method that restores this to a known initial state upon deserialization.

<h3>Usage</h3>

<p>To use this class as the basis of a synchronizer, redefine the following methods, as applicable, by inspecting and/or modifying the synchronization state using {@link #getState}, {@link #setState} and/or {@link #compareAndSetState}:

<ul> <li>{@link #tryAcquire} <li>{@link #tryRelease} <li>{@link #tryAcquireShared} <li>{@link #tryReleaseShared} <li>{@link #isHeldExclusively} </ul>

Each of these methods by default throws {@link UnsupportedOperationException}. Implementations of these methods must be internally thread-safe, and should in general be short and not block. Defining these methods is the <em>only</em> supported means of using this class. All other methods are declared {@code final} because they cannot be independently varied.

<p>You may also find the inherited methods from {@link AbstractOwnableSynchronizer} useful to keep track of the thread owning an exclusive synchronizer. You are encouraged to use them -- this enables monitoring and diagnostic tools to assist users in determining which threads hold locks.

<p>Even though this class is based on an internal FIFO queue, it does not automatically enforce FIFO acquisition policies. The core of exclusive synchronization takes the form:

<pre> Acquire: while (!tryAcquire(arg)) { <em>enqueue thread if it is not already queued</em>; <em>possibly block current thread</em>; }

Release: if (tryRelease(arg)) <em>unblock the first queued thread</em>; </pre>

(Shared mode is similar but may involve cascading signals.)

<p id="barging">Because checks in acquire are invoked before enqueuing, a newly acquiring thread may <em>barge</em> ahead of others that are blocked and queued. However, you can, if desired, define {@code tryAcquire} and/or {@code tryAcquireShared} to disable barging by internally invoking one or more of the inspection methods, thereby providing a <em>fair</em> FIFO acquisition order. In particular, most fair synchronizers can define {@code tryAcquire} to return {@code false} if {@link #hasQueuedPredecessors} (a method specifically designed to be used by fair synchronizers) returns {@code true}. Other variations are possible.

<p>Throughput and scalability are generally highest for the default barging (also known as <em>greedy</em>, <em>renouncement</em>, and <em>convoy-avoidance</em>) strategy. While this is not guaranteed to be fair or starvation-free, earlier queued threads are allowed to recontend before later queued threads, and each recontention has an unbiased chance to succeed against incoming threads. Also, while acquires do not &quot;spin&quot; in the usual sense, they may perform multiple invocations of {@code tryAcquire} interspersed with other computations before blocking. This gives most of the benefits of spins when exclusive synchronization is only briefly held, without most of the liabilities when it isn't. If so desired, you can augment this by preceding calls to acquire methods with "fast-path" checks, possibly prechecking {@link #hasContended} and/or {@link #hasQueuedThreads} to only do so if the synchronizer is likely not to be contended.

<p>This class provides an efficient and scalable basis for synchronization in part by specializing its range of use to synchronizers that can rely on {@code int} state, acquire, and release parameters, and an internal FIFO wait queue. When this does not suffice, you can build synchronizers from a lower level using {@link hunt.concurrency.atomic atomic} classes, your own custom {@link java.util.Queue} classes, and {@link LockSupport} blocking support.

<h3>Usage Examples</h3>

<p>Here is a non-reentrant mutual exclusion lock class that uses the value zero to represent the unlocked state, and one to represent the locked state. While a non-reentrant lock does not strictly require recording of the current owner thread, this class does so anyway to make usage easier to monitor. It also supports conditions and exposes some instrumentation methods:

<pre> {@code class Mutex implements Lock, java.io.Serializable {

// Our internal helper class private static class Sync extends AbstractQueuedSynchronizer { // Acquires the lock if state is zero bool tryAcquire(int acquires) { assert acquires == 1; // Otherwise unused if (compareAndSetState(0, 1)) { setExclusiveOwnerThread(Thread.getThis()); return true; } return false; }

// Releases the lock by setting state to zero protected bool tryRelease(int releases) { assert releases == 1; // Otherwise unused if (!isHeldExclusively()) throw new IllegalMonitorStateException(); setExclusiveOwnerThread(null); setState(0); return true; }

// Reports whether in locked state bool isLocked() { return getState() != 0; }

bool isHeldExclusively() { // a data race, but safe due to out-of-thin-air guarantees return getExclusiveOwnerThread() == Thread.getThis(); }

// Provides a Condition Condition newCondition() { return new ConditionObject(); }

// Deserializes properly private void readObject(ObjectInputStream s) throws IOException, ClassNotFoundException { s.defaultReadObject(); setState(0); // reset to unlocked state } }

// The sync object does all the hard work. We just forward to it. private final Sync sync = new Sync();

void lock() { sync.acquire(1); } bool tryLock() { return sync.tryAcquire(1); } void unlock() { sync.release(1); } Condition newCondition() { return sync.newCondition(); } bool isLocked() { return sync.isLocked(); } bool isHeldByCurrentThread() { return sync.isHeldExclusively(); } bool hasQueuedThreads() { return sync.hasQueuedThreads(); } void lockInterruptibly() { sync.acquireInterruptibly(1); } bool tryLock(Duration timeout) { return sync.tryAcquireNanos(1, unit.toNanos(timeout)); } }}</pre>

<p>Here is a latch class that is like a {@link hunt.concurrency.CountDownLatch CountDownLatch} except that it only requires a single {@code signal} to fire. Because a latch is non-exclusive, it uses the {@code shared} acquire and release methods.

<pre> {@code class BooleanLatch {

private static class Sync extends AbstractQueuedSynchronizer { bool isSignalled() { return getState() != 0; }

protected int tryAcquireShared(int ignore) { return isSignalled() ? 1 : -1; }

protected bool tryReleaseShared(int ignore) { setState(1); return true; } }

private final Sync sync = new Sync(); bool isSignalled() { return sync.isSignalled(); } void signal() { sync.releaseShared(1); } void await() { sync.acquireSharedInterruptibly(1); } }}</pre>

@author Doug Lea