Home » openjdk-7 » java » util » concurrent » locks » [javadoc | source]
java.util.concurrent.locks
abstract public class: AbstractQueuedSynchronizer [javadoc | source]
java.lang.Object
   java.util.concurrent.locks.AbstractOwnableSynchronizer
      java.util.concurrent.locks.AbstractQueuedSynchronizer

All Implemented Interfaces:
    Serializable

Direct Known Subclasses:
    Worker, Sync, Sync, FairSync, Sync, NonfairSync, Sync, FairSync, FairSync, NonfairSync, Sync, NonfairSync

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 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 int value manipulated using methods #getState , #setState and #compareAndSetState is tracked with respect to synchronization.

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

This class supports either or both a default exclusive mode and a shared 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 "understand" 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 ReadWriteLock . Subclasses that support only exclusive or only shared modes need not define the methods supporting the unused mode.

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

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 AbstractQueuedSynchronizer for their synchronization mechanics.

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 readObject method that restores this to a known initial state upon deserialization.

Usage

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 #getState , #setState and/or #compareAndSetState :

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

You may also find the inherited methods from 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.

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:

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

Release:
    if (tryRelease(arg))
       unblock the first queued thread;
(Shared mode is similar but may involve cascading signals.)

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

Throughput and scalability are generally highest for the default barging (also known as greedy, renouncement, and convoy-avoidance) 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 "spin" in the usual sense, they may perform multiple invocations of 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 #hasContended and/or #hasQueuedThreads to only do so if the synchronizer is likely not to be contended.

This class provides an efficient and scalable basis for synchronization in part by specializing its range of use to synchronizers that can rely on 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 atomic classes, your own custom java.util.Queue classes, and LockSupport blocking support.

Usage Examples

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 one of the instrumentation methods:

class Mutex implements Lock, java.io.Serializable {

  // Our internal helper class
  private static class Sync extends AbstractQueuedSynchronizer {
    // Report whether in locked state
    protected boolean isHeldExclusively() {
      return getState() == 1;
    }

    // Acquire the lock if state is zero
    public boolean tryAcquire(int acquires) {
      assert acquires == 1; // Otherwise unused
      if (compareAndSetState(0, 1)) {
        setExclusiveOwnerThread(Thread.currentThread());
        return true;
      }
      return false;
    }

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

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

    // Deserialize 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();

  public void lock()                { sync.acquire(1); }
  public boolean tryLock()          { return sync.tryAcquire(1); }
  public void unlock()              { sync.release(1); }
  public Condition newCondition()   { return sync.newCondition(); }
  public boolean isLocked()         { return sync.isHeldExclusively(); }
  public boolean hasQueuedThreads() { return sync.hasQueuedThreads(); }
  public void lockInterruptibly() throws InterruptedException {
    sync.acquireInterruptibly(1);
  }
  public boolean tryLock(long timeout, TimeUnit unit)
      throws InterruptedException {
    return sync.tryAcquireNanos(1, unit.toNanos(timeout));
  }
}

Here is a latch class that is like a CountDownLatch except that it only requires a single signal to fire. Because a latch is non-exclusive, it uses the shared acquire and release methods.

class BooleanLatch {

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

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

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

  private final Sync sync = new Sync();
  public boolean isSignalled() { return sync.isSignalled(); }
  public void signal()         { sync.releaseShared(1); }
  public void await() throws InterruptedException {
    sync.acquireSharedInterruptibly(1);
  }
}
Nested Class Summary:
static final class  AbstractQueuedSynchronizer.Node  Wait queue node class.

The wait queue is a variant of a "CLH" (Craig, Landin, and Hagersten) lock queue. CLH locks are normally used for spinlocks. We instead use them for blocking synchronizers, but use the same basic tactic of holding some of the control information about a thread in the predecessor of its node. A "status" field in each node keeps track of whether a thread should block. A node is signalled when its predecessor releases. Each node of the queue otherwise serves as a specific-notification-style monitor holding a single waiting thread. The status field does NOT control whether threads are granted locks etc though. A thread may try to acquire if it is first in the queue. But being first does not guarantee success; it only gives the right to contend. So the currently released contender thread may need to rewait.

To enqueue into a CLH lock, you atomically splice it in as new tail. To dequeue, you just set the head field.

     +------+  prev +-----+       +-----+
head |      | <---- |     | <---- |     |  tail
     +------+       +-----+       +-----+

Insertion into a CLH queue requires only a single atomic operation on "tail", so there is a simple atomic point of demarcation from unqueued to queued. Similarly, dequeing involves only updating the "head". However, it takes a bit more work for nodes to determine who their successors are, in part to deal with possible cancellation due to timeouts and interrupts.

The "prev" links (not used in original CLH locks), are mainly needed to handle cancellation. If a node is cancelled, its successor is (normally) relinked to a non-cancelled predecessor. For explanation of similar mechanics in the case of spin locks, see the papers by Scott and Scherer at http://www.cs.rochester.edu/u/scott/synchronization/

We also use "next" links to implement blocking mechanics. The thread id for each node is kept in its own node, so a predecessor signals the next node to wake up by traversing next link to determine which thread it is. Determination of successor must avoid races with newly queued nodes to set the "next" fields of their predecessors. This is solved when necessary by checking backwards from the atomically updated "tail" when a node's successor appears to be null. (Or, said differently, the next-links are an optimization so that we don't usually need a backward scan.)

Cancellation introduces some conservatism to the basic algorithms. Since we must poll for cancellation of other nodes, we can miss noticing whether a cancelled node is ahead or behind us. This is dealt with by always unparking successors upon cancellation, allowing them to stabilize on a new predecessor, unless we can identify an uncancelled predecessor who will carry this responsibility.

CLH queues need a dummy header node to get started. But we don't create them on construction, because it would be wasted effort if there is never contention. Instead, the node is constructed and head and tail pointers are set upon first contention.

Threads waiting on Conditions use the same nodes, but use an additional link. Conditions only need to link nodes in simple (non-concurrent) linked queues because they are only accessed when exclusively held. Upon await, a node is inserted into a condition queue. Upon signal, the node is transferred to the main queue. A special value of status field is used to mark which queue a node is on.

Thanks go to Dave Dice, Mark Moir, Victor Luchangco, Bill Scherer and Michael Scott, along with members of JSR-166 expert group, for helpful ideas, discussions, and critiques on the design of this class. 

public class  AbstractQueuedSynchronizer.ConditionObject  Condition implementation for a {@link AbstractQueuedSynchronizer} serving as the basis of a {@link Lock} implementation.

Method documentation for this class describes mechanics, not behavioral specifications from the point of view of Lock and Condition users. Exported versions of this class will in general need to be accompanied by documentation describing condition semantics that rely on those of the associated AbstractQueuedSynchronizer.

This class is Serializable, but all fields are transient, so deserialized conditions have no waiters. 

Field Summary
static final  long spinForTimeoutThreshold    The number of nanoseconds for which it is faster to spin rather than to use timed park. A rough estimate suffices to improve responsiveness with very short timeouts. 
Constructor:
 protected AbstractQueuedSynchronizer() 
Method from java.util.concurrent.locks.AbstractQueuedSynchronizer Summary:
acquire,   acquireInterruptibly,   acquireQueued,   acquireShared,   acquireSharedInterruptibly,   apparentlyFirstQueuedIsExclusive,   compareAndSetState,   fullyRelease,   getExclusiveQueuedThreads,   getFirstQueuedThread,   getQueueLength,   getQueuedThreads,   getSharedQueuedThreads,   getState,   getWaitQueueLength,   getWaitingThreads,   hasContended,   hasQueuedPredecessors,   hasQueuedThreads,   hasWaiters,   isHeldExclusively,   isOnSyncQueue,   isQueued,   owns,   release,   releaseShared,   setState,   toString,   transferAfterCancelledWait,   transferForSignal,   tryAcquire,   tryAcquireNanos,   tryAcquireShared,   tryAcquireSharedNanos,   tryRelease,   tryReleaseShared
Methods from java.util.concurrent.locks.AbstractOwnableSynchronizer:
getExclusiveOwnerThread,   setExclusiveOwnerThread
Methods from java.lang.Object:
clone,   equals,   finalize,   getClass,   hashCode,   notify,   notifyAll,   toString,   wait,   wait,   wait
Method from java.util.concurrent.locks.AbstractQueuedSynchronizer Detail:
 public final  void acquire(int arg) 
    Acquires in exclusive mode, ignoring interrupts. Implemented by invoking at least once #tryAcquire , returning on success. Otherwise the thread is queued, possibly repeatedly blocking and unblocking, invoking #tryAcquire until success. This method can be used to implement method Lock#lock .
 public final  void acquireInterruptibly(int arg) throws InterruptedException 
    Acquires in exclusive mode, aborting if interrupted. Implemented by first checking interrupt status, then invoking at least once #tryAcquire , returning on success. Otherwise the thread is queued, possibly repeatedly blocking and unblocking, invoking #tryAcquire until success or the thread is interrupted. This method can be used to implement method Lock#lockInterruptibly .
 final boolean acquireQueued(Node node,
    int arg) 
    Acquires in exclusive uninterruptible mode for thread already in queue. Used by condition wait methods as well as acquire.
 public final  void acquireShared(int arg) 
    Acquires in shared mode, ignoring interrupts. Implemented by first invoking at least once #tryAcquireShared , returning on success. Otherwise the thread is queued, possibly repeatedly blocking and unblocking, invoking #tryAcquireShared until success.
 public final  void acquireSharedInterruptibly(int arg) throws InterruptedException 
    Acquires in shared mode, aborting if interrupted. Implemented by first checking interrupt status, then invoking at least once #tryAcquireShared , returning on success. Otherwise the thread is queued, possibly repeatedly blocking and unblocking, invoking #tryAcquireShared until success or the thread is interrupted.
 final boolean apparentlyFirstQueuedIsExclusive() 
    Returns {@code true} if the apparent first queued thread, if one exists, is waiting in exclusive mode. If this method returns {@code true}, and the current thread is attempting to acquire in shared mode (that is, this method is invoked from #tryAcquireShared ) then it is guaranteed that the current thread is not the first queued thread. Used only as a heuristic in ReentrantReadWriteLock.
 protected final boolean compareAndSetState(int expect,
    int update) 
    Atomically sets synchronization state to the given updated value if the current state value equals the expected value. This operation has memory semantics of a volatile read and write.
 final int fullyRelease(Node node) 
    Invokes release with current state value; returns saved state. Cancels node and throws exception on failure.
 public final Collection<Thread> getExclusiveQueuedThreads() 
    Returns a collection containing threads that may be waiting to acquire in exclusive mode. This has the same properties as #getQueuedThreads except that it only returns those threads waiting due to an exclusive acquire.
 public final Thread getFirstQueuedThread() 
    Returns the first (longest-waiting) thread in the queue, or {@code null} if no threads are currently queued.

    In this implementation, this operation normally returns in constant time, but may iterate upon contention if other threads are concurrently modifying the queue.

 public final int getQueueLength() 
    Returns an estimate of the number of threads waiting to acquire. The value is only an estimate because the number of threads may change dynamically while this method traverses internal data structures. This method is designed for use in monitoring system state, not for synchronization control.
 public final Collection<Thread> getQueuedThreads() 
    Returns a collection containing threads that may be waiting to acquire. Because the actual set of threads may change dynamically while constructing this result, the returned collection is only a best-effort estimate. The elements of the returned collection are in no particular order. This method is designed to facilitate construction of subclasses that provide more extensive monitoring facilities.
 public final Collection<Thread> getSharedQueuedThreads() 
    Returns a collection containing threads that may be waiting to acquire in shared mode. This has the same properties as #getQueuedThreads except that it only returns those threads waiting due to a shared acquire.
 protected final int getState() 
    Returns the current value of synchronization state. This operation has memory semantics of a volatile read.
 public final int getWaitQueueLength(ConditionObject condition) 
    Returns an estimate of the number of threads waiting on the given condition associated with this synchronizer. Note that because timeouts and interrupts may occur at any time, the estimate serves only as an upper bound on the actual number of waiters. This method is designed for use in monitoring of the system state, not for synchronization control.
 public final Collection<Thread> getWaitingThreads(ConditionObject condition) 
    Returns a collection containing those threads that may be waiting on the given condition associated with this synchronizer. Because the actual set of threads may change dynamically while constructing this result, the returned collection is only a best-effort estimate. The elements of the returned collection are in no particular order.
 public final boolean hasContended() 
    Queries whether any threads have ever contended to acquire this synchronizer; that is if an acquire method has ever blocked.

    In this implementation, this operation returns in constant time.

 public final boolean hasQueuedPredecessors() 
    Queries whether any threads have been waiting to acquire longer than the current thread.

    An invocation of this method is equivalent to (but may be more efficient than):

     {@code
    getFirstQueuedThread() != Thread.currentThread() &&
    hasQueuedThreads()}

    Note that because cancellations due to interrupts and timeouts may occur at any time, a {@code true} return does not guarantee that some other thread will acquire before the current thread. Likewise, it is possible for another thread to win a race to enqueue after this method has returned {@code false}, due to the queue being empty.

    This method is designed to be used by a fair synchronizer to avoid barging. Such a synchronizer's #tryAcquire method should return {@code false}, and its #tryAcquireShared method should return a negative value, if this method returns {@code true} (unless this is a reentrant acquire). For example, the {@code tryAcquire} method for a fair, reentrant, exclusive mode synchronizer might look like this:

     {@code
    protected boolean tryAcquire(int arg) {
      if (isHeldExclusively()) {
        // A reentrant acquire; increment hold count
        return true;
      } else if (hasQueuedPredecessors()) {
        return false;
      } else {
        // try to acquire normally
      }
    }}
 public final boolean hasQueuedThreads() 
    Queries whether any threads are waiting to acquire. Note that because cancellations due to interrupts and timeouts may occur at any time, a {@code true} return does not guarantee that any other thread will ever acquire.

    In this implementation, this operation returns in constant time.

 public final boolean hasWaiters(ConditionObject condition) 
    Queries whether any threads are waiting on the given condition associated with this synchronizer. Note that because timeouts and interrupts may occur at any time, a true return does not guarantee that a future signal will awaken any threads. This method is designed primarily for use in monitoring of the system state.
 protected boolean isHeldExclusively() 
    Returns {@code true} if synchronization is held exclusively with respect to the current (calling) thread. This method is invoked upon each call to a non-waiting ConditionObject method. (Waiting methods instead invoke #release .)

    The default implementation throws UnsupportedOperationException . This method is invoked internally only within ConditionObject methods, so need not be defined if conditions are not used.

 final boolean isOnSyncQueue(Node node) 
    Returns true if a node, always one that was initially placed on a condition queue, is now waiting to reacquire on sync queue.
 public final boolean isQueued(Thread thread) 
    Returns true if the given thread is currently queued.

    This implementation traverses the queue to determine presence of the given thread.

 public final boolean owns(ConditionObject condition) 
    Queries whether the given ConditionObject uses this synchronizer as its lock.
 public final boolean release(int arg) 
    Releases in exclusive mode. Implemented by unblocking one or more threads if #tryRelease returns true. This method can be used to implement method Lock#unlock .
 public final boolean releaseShared(int arg) 
    Releases in shared mode. Implemented by unblocking one or more threads if #tryReleaseShared returns true.
 protected final  void setState(int newState) 
    Sets the value of synchronization state. This operation has memory semantics of a volatile write.
 public String toString() 
    Returns a string identifying this synchronizer, as well as its state. The state, in brackets, includes the String {@code "State ="} followed by the current value of #getState , and either {@code "nonempty"} or {@code "empty"} depending on whether the queue is empty.
 final boolean transferAfterCancelledWait(Node node) 
    Transfers node, if necessary, to sync queue after a cancelled wait. Returns true if thread was cancelled before being signalled.
 final boolean transferForSignal(Node node) 
    Transfers a node from a condition queue onto sync queue. Returns true if successful.
 protected boolean tryAcquire(int arg) 
    Attempts to acquire in exclusive mode. This method should query if the state of the object permits it to be acquired in the exclusive mode, and if so to acquire it.

    This method is always invoked by the thread performing acquire. If this method reports failure, the acquire method may queue the thread, if it is not already queued, until it is signalled by a release from some other thread. This can be used to implement method Lock#tryLock() .

    The default implementation throws UnsupportedOperationException .

 public final boolean tryAcquireNanos(int arg,
    long nanosTimeout) throws InterruptedException 
    Attempts to acquire in exclusive mode, aborting if interrupted, and failing if the given timeout elapses. Implemented by first checking interrupt status, then invoking at least once #tryAcquire , returning on success. Otherwise, the thread is queued, possibly repeatedly blocking and unblocking, invoking #tryAcquire until success or the thread is interrupted or the timeout elapses. This method can be used to implement method Lock#tryLock(long, TimeUnit) .
 protected int tryAcquireShared(int arg) 
    Attempts to acquire in shared mode. This method should query if the state of the object permits it to be acquired in the shared mode, and if so to acquire it.

    This method is always invoked by the thread performing acquire. If this method reports failure, the acquire method may queue the thread, if it is not already queued, until it is signalled by a release from some other thread.

    The default implementation throws UnsupportedOperationException .

 public final boolean tryAcquireSharedNanos(int arg,
    long nanosTimeout) throws InterruptedException 
    Attempts to acquire in shared mode, aborting if interrupted, and failing if the given timeout elapses. Implemented by first checking interrupt status, then invoking at least once #tryAcquireShared , returning on success. Otherwise, the thread is queued, possibly repeatedly blocking and unblocking, invoking #tryAcquireShared until success or the thread is interrupted or the timeout elapses.
 protected boolean tryRelease(int arg) 
    Attempts to set the state to reflect a release in exclusive mode.

    This method is always invoked by the thread performing release.

    The default implementation throws UnsupportedOperationException .

 protected boolean tryReleaseShared(int arg) 
    Attempts to set the state to reflect a release in shared mode.

    This method is always invoked by the thread performing release.

    The default implementation throws UnsupportedOperationException .