FileDocCategorySizeDatePackage
AbstractQueuedSynchronizer.javaAPI DocAndroid 1.5 API81254Wed May 06 22:41:02 BST 2009java.util.concurrent.locks

AbstractQueuedSynchronizer

public abstract class AbstractQueuedSynchronizer extends Object implements Serializable
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 {@link #getState}, {@link #setState} and {@link #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 {@link #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 {@link ReadWriteLock}. Subclasses that support only exclusive or only shared modes need not define the methods supporting the unused mode.

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 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.

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

  • {@link #tryAcquire}
  • {@link #tryRelease}
  • {@link #tryAcquireShared}
  • {@link #tryReleaseShared}
  • {@link #isHeldExclusively}
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 only supported means of using this class. All other methods are declared final because they cannot be independently varied.

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. In particular, a strict FIFO lock can define tryAcquire to immediately return false if {@link #getFirstQueuedThread} does not return the current thread. A normally preferable non-strict fair version can immediately return false only if {@link #hasQueuedThreads} returns true and getFirstQueuedThread is not the current thread; or equivalently, that getFirstQueuedThread is both non-null and not the current thread. Further 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 {@link #hasContended} and/or {@link #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 {@link java.util.concurrent.atomic atomic} classes, your own custom {@link java.util.Queue} classes, and {@link 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. 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
return compareAndSetState(0, 1);
}

// Release the lock by setting state to zero
protected boolean tryRelease(int releases) {
assert releases == 1; // Otherwise unused
if (getState() == 0) throw new IllegalMonitorStateException();
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 {@link 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);
}
}
since
1.5
author
Doug Lea

Fields Summary
private static final long
serialVersionUID
private volatile transient Node
head
Head of the wait queue, lazily initialized. Except for initialization, it is modified only via method setHead. Note: If head exists, its waitStatus is guaranteed not to be CANCELLED.
private volatile transient Node
tail
Tail of the wait queue, lazily initialized. Modified only via method enq to add new wait node.
private volatile int
state
The synchronization state.
private static final Unsafe
unsafe
Setup to support compareAndSet. We need to natively implement this here: For the sake of permitting future enhancements, we cannot explicitly subclass AtomicInteger, which would be efficient and useful otherwise. So, as the lesser of evils, we natively implement using hotspot intrinsics API. And while we are at it, we do the same for other CASable fields (which could otherwise be done with atomic field updaters).
private static final long
stateOffset
private static final long
headOffset
private static final long
tailOffset
private static final long
waitStatusOffset
Constructors Summary
protected AbstractQueuedSynchronizer()
Creates a new AbstractQueuedSynchronizer instance with initial synchronization state of zero.
Methods Summary
public final voidacquire(int arg)
Acquires in exclusive mode, ignoring interrupts. Implemented by invoking at least once {@link #tryAcquire}, returning on success. Otherwise the thread is queued, possibly repeatedly blocking and unblocking, invoking {@link #tryAcquire} until success. This method can be used to implement method {@link Lock#lock}

param
arg the acquire argument. This value is conveyed to {@link #tryAcquire} but is otherwise uninterpreted and can represent anything you like.

        if (!tryAcquire(arg) &&
            acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
            selfInterrupt();
public final voidacquireInterruptibly(int arg)
Acquires in exclusive mode, aborting if interrupted. Implemented by first checking interrupt status, then invoking at least once {@link #tryAcquire}, returning on success. Otherwise the thread is queued, possibly repeatedly blocking and unblocking, invoking {@link #tryAcquire} until success or the thread is interrupted. This method can be used to implement method {@link Lock#lockInterruptibly}

param
arg the acquire argument. This value is conveyed to {@link #tryAcquire} but is otherwise uninterpreted and can represent anything you like.
throws
InterruptedException if the current thread is interrupted

        if (Thread.interrupted())
            throw new InterruptedException();
        if (!tryAcquire(arg))
            doAcquireInterruptibly(arg);
final booleanacquireQueued(java.util.concurrent.locks.AbstractQueuedSynchronizer$Node node, int arg)
Acquire in exclusive uninterruptible mode for thread already in queue. Used by condition wait methods as well as acquire.

param
node the node
param
arg the acquire argument
return
true if interrupted while waiting

        try {
            boolean interrupted = false;
            for (;;) {
                final Node p = node.predecessor();
                if (p == head && tryAcquire(arg)) {
                    setHead(node);
                    p.next = null; // help GC
                    return interrupted;
                }
                if (shouldParkAfterFailedAcquire(p, node) && 
                    parkAndCheckInterrupt()) 
                    interrupted = true;
            }
        } catch (RuntimeException ex) {
            cancelAcquire(node);
            throw ex;
        }
public final voidacquireShared(int arg)
Acquires in shared mode, ignoring interrupts. Implemented by first invoking at least once {@link #tryAcquireShared}, returning on success. Otherwise the thread is queued, possibly repeatedly blocking and unblocking, invoking {@link #tryAcquireShared} until success.

param
arg the acquire argument. This value is conveyed to {@link #tryAcquireShared} but is otherwise uninterpreted and can represent anything you like.

        if (tryAcquireShared(arg) < 0)
            doAcquireShared(arg);
public final voidacquireSharedInterruptibly(int arg)
Acquires in shared mode, aborting if interrupted. Implemented by first checking interrupt status, then invoking at least once {@link #tryAcquireShared}, returning on success. Otherwise the thread is queued, possibly repeatedly blocking and unblocking, invoking {@link #tryAcquireShared} until success or the thread is interrupted.

param
arg the acquire argument. This value is conveyed to {@link #tryAcquireShared} but is otherwise uninterpreted and can represent anything you like.
throws
InterruptedException if the current thread is interrupted

        if (Thread.interrupted())
            throw new InterruptedException();
        if (tryAcquireShared(arg) < 0)
            doAcquireSharedInterruptibly(arg);
private java.util.concurrent.locks.AbstractQueuedSynchronizer$NodeaddWaiter(java.util.concurrent.locks.AbstractQueuedSynchronizer$Node mode)
Create and enq node for given thread and mode

param
current the thread
param
mode Node.EXCLUSIVE for exclusive, Node.SHARED for shared
return
the new node

        Node node = new Node(Thread.currentThread(), mode);
        // Try the fast path of enq; backup to full enq on failure
        Node pred = tail;
        if (pred != null) {
            node.prev = pred;     
            if (compareAndSetTail(pred, node)) {
                pred.next = node; 
                return node;
            }
        }
        enq(node);
        return node;
private voidcancelAcquire(java.util.concurrent.locks.AbstractQueuedSynchronizer$Node node)
Cancel an ongoing attempt to acquire.

param
node the node

        if (node != null) { // Ignore if node doesn't exist
            node.thread = null;
            // Can use unconditional write instead of CAS here
            node.waitStatus = Node.CANCELLED;
            unparkSuccessor(node);
        }
private final booleancompareAndSetHead(java.util.concurrent.locks.AbstractQueuedSynchronizer$Node update)
CAS head field. Used only by enq


     
        try {
            stateOffset = unsafe.objectFieldOffset
                (AbstractQueuedSynchronizer.class.getDeclaredField("state"));
            headOffset = unsafe.objectFieldOffset
                (AbstractQueuedSynchronizer.class.getDeclaredField("head"));
            tailOffset = unsafe.objectFieldOffset
                (AbstractQueuedSynchronizer.class.getDeclaredField("tail"));
            waitStatusOffset = unsafe.objectFieldOffset
                (Node.class.getDeclaredField("waitStatus"));
            
        } catch(Exception ex) { throw new Error(ex); }
    
        return unsafe.compareAndSwapObject(this, headOffset, null, update);
protected final booleancompareAndSetState(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.

param
expect the expected value
param
update the new value
return
true if successful. False return indicates that the actual value was not equal to the expected value.

        // See below for intrinsics setup to support this
        return unsafe.compareAndSwapInt(this, stateOffset, expect, update);
private final booleancompareAndSetTail(java.util.concurrent.locks.AbstractQueuedSynchronizer$Node expect, java.util.concurrent.locks.AbstractQueuedSynchronizer$Node update)
CAS tail field. Used only by enq

        return unsafe.compareAndSwapObject(this, tailOffset, expect, update);
private static final booleancompareAndSetWaitStatus(java.util.concurrent.locks.AbstractQueuedSynchronizer$Node node, int expect, int update)
CAS waitStatus field of a node.

        return unsafe.compareAndSwapInt(node, waitStatusOffset, 
                                        expect, update);
private voiddoAcquireInterruptibly(int arg)
Acquire in exclusive interruptible mode

param
arg the acquire argument

        final Node node = addWaiter(Node.EXCLUSIVE);
        try {
            for (;;) {
                final Node p = node.predecessor();
                if (p == head && tryAcquire(arg)) {
                    setHead(node);
                    p.next = null; // help GC
                    return;
                }
                if (shouldParkAfterFailedAcquire(p, node) && 
                    parkAndCheckInterrupt()) 
                    break;
            }
        } catch (RuntimeException ex) {
            cancelAcquire(node);
            throw ex;
        }
        // Arrive here only if interrupted
        cancelAcquire(node);
        throw new InterruptedException();
private booleandoAcquireNanos(int arg, long nanosTimeout)
Acquire in exclusive timed mode

param
arg the acquire argument
param
nanosTimeout max wait time
return
true if acquired

        long lastTime = System.nanoTime();
        final Node node = addWaiter(Node.EXCLUSIVE);
        try {
            for (;;) {
                final Node p = node.predecessor();
                if (p == head && tryAcquire(arg)) {
                    setHead(node);
                    p.next = null; // help GC
                    return true;
                }
                if (nanosTimeout <= 0) {
                    cancelAcquire(node);
                    return false;
                }
                if (shouldParkAfterFailedAcquire(p, node)) {
                    LockSupport.parkNanos(nanosTimeout);
                    if (Thread.interrupted()) 
                        break;
                    long now = System.nanoTime();
                    nanosTimeout -= now - lastTime;
                    lastTime = now;
                }
            }
        } catch (RuntimeException ex) {
            cancelAcquire(node);
            throw ex;
        }
        // Arrive here only if interrupted
        cancelAcquire(node);
        throw new InterruptedException();
private voiddoAcquireShared(int arg)
Acquire in shared uninterruptible mode

param
arg the acquire argument

        final Node node = addWaiter(Node.SHARED);
        try {
            boolean interrupted = false;
            for (;;) {
                final Node p = node.predecessor();
                if (p == head) {
                    int r = tryAcquireShared(arg);
                    if (r >= 0) {
                        setHeadAndPropagate(node, r);
                        p.next = null; // help GC
                        if (interrupted)
                            selfInterrupt();
                        return;
                    }
                }
                if (shouldParkAfterFailedAcquire(p, node) && 
                    parkAndCheckInterrupt()) 
                    interrupted = true;
            }
        } catch (RuntimeException ex) {
            cancelAcquire(node);
            throw ex;
        }
private voiddoAcquireSharedInterruptibly(int arg)
Acquire in shared interruptible mode

param
arg the acquire argument

        final Node node = addWaiter(Node.SHARED);
        try {
            for (;;) {
                final Node p = node.predecessor();
                if (p == head) {
                    int r = tryAcquireShared(arg);
                    if (r >= 0) {
                        setHeadAndPropagate(node, r);
                        p.next = null; // help GC
                        return;
                    }
                }
                if (shouldParkAfterFailedAcquire(p, node) && 
                    parkAndCheckInterrupt()) 
                    break;
            }
        } catch (RuntimeException ex) {
            cancelAcquire(node);
            throw ex;
        }
        // Arrive here only if interrupted
        cancelAcquire(node);
        throw new InterruptedException();
private booleandoAcquireSharedNanos(int arg, long nanosTimeout)
Acquire in shared timed mode

param
arg the acquire argument
param
nanosTimeout max wait time
return
true if acquired


        long lastTime = System.nanoTime();
        final Node node = addWaiter(Node.SHARED);
        try {
            for (;;) {
                final Node p = node.predecessor();
                if (p == head) {
                    int r = tryAcquireShared(arg);
                    if (r >= 0) {
                        setHeadAndPropagate(node, r);
                        p.next = null; // help GC
                        return true;
                    }
                }
                if (nanosTimeout <= 0) {
                    cancelAcquire(node);
                    return false;
                }
                if (shouldParkAfterFailedAcquire(p, node)) {
                    LockSupport.parkNanos(nanosTimeout);
                    if (Thread.interrupted()) 
                        break;
                    long now = System.nanoTime();
                    nanosTimeout -= now - lastTime;
                    lastTime = now;
                }
            }
        } catch (RuntimeException ex) {
            cancelAcquire(node);
            throw ex;
        }
        // Arrive here only if interrupted
        cancelAcquire(node);
        throw new InterruptedException();
private java.util.concurrent.locks.AbstractQueuedSynchronizer$Nodeenq(java.util.concurrent.locks.AbstractQueuedSynchronizer$Node node)
Insert node into queue, initializing if necessary. See picture above.

param
node the node to insert
return
node's predecessor

        for (;;) {
            Node t = tail;
            if (t == null) { // Must initialize
                Node h = new Node(); // Dummy header
                h.next = node;
                node.prev = h;
                if (compareAndSetHead(h)) {
                    tail = node;
                    return h;
                }
            }
            else {
                node.prev = t;     
                if (compareAndSetTail(t, node)) {
                    t.next = node; 
                    return t; 
                }
            }
        }
private booleanfindNodeFromTail(java.util.concurrent.locks.AbstractQueuedSynchronizer$Node node)
Returns true if node is on sync queue by searching backwards from tail. Called only when needed by isOnSyncQueue.

return
true if present

        Node t = tail; 
        for (;;) {
            if (t == node)
                return true;
            if (t == null)
                return false;
            t = t.prev;
        }
private java.lang.ThreadfullGetFirstQueuedThread()
Version of getFirstQueuedThread called when fastpath fails

        /*
         * This loops only if the queue changes while we read sets of
         * fields.
         */
        for (;;) {
            Node h = head;
            if (h == null)                    // No queue
                return null;

            /*
             * The first node is normally h.next. Try to get its
             * thread field, ensuring consistent reads: If thread
             * field is nulled out or s.prev is no longer head, then
             * some other thread(s) concurrently performed setHead in
             * between some of our reads, so we must reread.
             */
            Node s = h.next;
            if (s != null) {
                Thread st = s.thread;
                Node sp = s.prev;
                if (st != null && sp == head)
                    return st;
            }

            /*
             * Head's next field might not have been set yet, or may
             * have been unset after setHead. So we must check to see
             * if tail is actually first node, in almost the same way
             * as above.
             */
            Node t = tail; 
            if (t == h)                       // Empty queue
                return null;

            if (t != null) {
                Thread tt = t.thread;
                Node tp = t.prev;
                if (tt != null && tp == head)
                    return tt;
            }
        }
final intfullyRelease(java.util.concurrent.locks.AbstractQueuedSynchronizer$Node node)
Invoke release with current state value; return saved state. Cancel node and throw exception on failure.

param
node the condition node for this wait
return
previous sync state

        try {
            int savedState = getState();
            if (release(savedState))
                return savedState;
        } catch(RuntimeException ex) {
            node.waitStatus = Node.CANCELLED;
            throw ex;
        }
        // reach here if release fails
        node.waitStatus = Node.CANCELLED;
        throw new IllegalMonitorStateException();
public final java.util.CollectiongetExclusiveQueuedThreads()
Returns a collection containing threads that may be waiting to acquire in exclusive mode. This has the same properties as {@link #getQueuedThreads} except that it only returns those threads waiting due to an exclusive acquire.

return
the collection of threads

        ArrayList<Thread> list = new ArrayList<Thread>();
        for (Node p = tail; p != null; p = p.prev) {
            if (!p.isShared()) {
                Thread t = p.thread;
                if (t != null)
                    list.add(t);
            }
        }
        return list;
public final java.lang.ThreadgetFirstQueuedThread()
Returns the first (longest-waiting) thread in the queue, or 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.

return
the first (longest-waiting) thread in the queue, or null if no threads are currently queued.

        // handle only fast path, else relay
        return (head == tail)? null : fullGetFirstQueuedThread();
public final intgetQueueLength()
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.

return
the estimated number of threads waiting for this lock

        int n = 0;
        for (Node p = tail; p != null; p = p.prev) {
            if (p.thread != null)
                ++n;
        }
        return n;
public final java.util.CollectiongetQueuedThreads()
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.

return
the collection of threads

        ArrayList<Thread> list = new ArrayList<Thread>();
        for (Node p = tail; p != null; p = p.prev) {
            Thread t = p.thread;
            if (t != null)
                list.add(t);
        }
        return list;
public final java.util.CollectiongetSharedQueuedThreads()
Returns a collection containing threads that may be waiting to acquire in shared mode. This has the same properties as {@link #getQueuedThreads} except that it only returns those threads waiting due to a shared acquire.

return
the collection of threads

        ArrayList<Thread> list = new ArrayList<Thread>();
        for (Node p = tail; p != null; p = p.prev) {
            if (p.isShared()) {
                Thread t = p.thread;
                if (t != null)
                    list.add(t);
            }
        }
        return list;
protected final intgetState()
Returns the current value of synchronization state. This operation has memory semantics of a volatile read.

return
current state value

        return state;
public final intgetWaitQueueLength(java.util.concurrent.locks.AbstractQueuedSynchronizer$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.

param
condition the condition
return
the estimated number of waiting threads.
throws
IllegalMonitorStateException if exclusive synchronization is not held
throws
IllegalArgumentException if the given condition is not associated with this synchronizer
throws
NullPointerException if condition null

        if (!owns(condition))
            throw new IllegalArgumentException("Not owner");
        return condition.getWaitQueueLength();
public final java.util.CollectiongetWaitingThreads(java.util.concurrent.locks.AbstractQueuedSynchronizer$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.

param
condition the condition
return
the collection of threads
throws
IllegalMonitorStateException if exclusive synchronization is not held
throws
IllegalArgumentException if the given condition is not associated with this synchronizer
throws
NullPointerException if condition null

        if (!owns(condition))
            throw new IllegalArgumentException("Not owner");
        return condition.getWaitingThreads();
public final booleanhasContended()
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.

return
true if there has ever been contention

        return head != null;
public final booleanhasQueuedThreads()
Queries whether any threads are waiting to acquire. Note that because cancellations due to interrupts and timeouts may occur at any time, a true return does not guarantee that any other thread will ever acquire.

In this implementation, this operation returns in constant time.

return
true if there may be other threads waiting to acquire the lock.

 
        return head != tail;
public final booleanhasWaiters(java.util.concurrent.locks.AbstractQueuedSynchronizer$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.

param
condition the condition
return
true if there are any waiting threads.
throws
IllegalMonitorStateException if exclusive synchronization is not held
throws
IllegalArgumentException if the given condition is not associated with this synchronizer
throws
NullPointerException if condition null

        if (!owns(condition))
            throw new IllegalArgumentException("Not owner");
        return condition.hasWaiters();
protected booleanisHeldExclusively()
Returns true if synchronization is held exclusively with respect to the current (calling) thread. This method is invoked upon each call to a non-waiting {@link ConditionObject} method. (Waiting methods instead invoke {@link #release}.)

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

return
true if synchronization is held exclusively; else false
throws
UnsupportedOperationException if conditions are not supported

        throw new UnsupportedOperationException();
final booleanisOnSyncQueue(java.util.concurrent.locks.AbstractQueuedSynchronizer$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.

param
node the node
return
true if is reacquiring

        if (node.waitStatus == Node.CONDITION || node.prev == null)
            return false;
        if (node.next != null) // If has successor, it must be on queue
            return true;
        /*
         * node.prev can be non-null, but not yet on queue because
         * the CAS to place it on queue can fail. So we have to
         * traverse from tail to make sure it actually made it.  It
         * will always be near the tail in calls to this method, and
         * unless the CAS failed (which is unlikely), it will be
         * there, so we hardly ever traverse much.
         */
        return findNodeFromTail(node);
public final booleanisQueued(java.lang.Thread thread)
Returns true if the given thread is currently queued.

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

param
thread the thread
return
true if the given thread in on the queue
throws
NullPointerException if thread null

        if (thread == null)
            throw new NullPointerException();
        for (Node p = tail; p != null; p = p.prev)
            if (p.thread == thread)
                return true;
        return false;
public final booleanowns(java.util.concurrent.locks.AbstractQueuedSynchronizer$ConditionObject condition)
Queries whether the given ConditionObject uses this synchronizer as its lock.

param
condition the condition
return
true if owned
throws
NullPointerException if condition null

        if (condition == null)
            throw new NullPointerException();
        return condition.isOwnedBy(this);
private static booleanparkAndCheckInterrupt()
Convenience method to park and then check if interrupted

return
true if interrupted

        LockSupport.park();
        return Thread.interrupted();
public final booleanrelease(int arg)
Releases in exclusive mode. Implemented by unblocking one or more threads if {@link #tryRelease} returns true. This method can be used to implement method {@link Lock#unlock}

param
arg the release argument. This value is conveyed to {@link #tryRelease} but is otherwise uninterpreted and can represent anything you like.
return
the value returned from {@link #tryRelease}

        if (tryRelease(arg)) {
            Node h = head;
            if (h != null && h.waitStatus != 0) 
                unparkSuccessor(h);
            return true;
        }
        return false;
public final booleanreleaseShared(int arg)
Releases in shared mode. Implemented by unblocking one or more threads if {@link #tryReleaseShared} returns true.

param
arg the release argument. This value is conveyed to {@link #tryReleaseShared} but is otherwise uninterpreted and can represent anything you like.
return
the value returned from {@link #tryReleaseShared}

        if (tryReleaseShared(arg)) {
            Node h = head;
            if (h != null && h.waitStatus != 0) 
                unparkSuccessor(h);
            return true;
        }
        return false;
private static voidselfInterrupt()
Convenience method to interrupt current thread.

        Thread.currentThread().interrupt();
private voidsetHead(java.util.concurrent.locks.AbstractQueuedSynchronizer$Node node)
Set head of queue to be node, thus dequeuing. Called only by acquire methods. Also nulls out unused fields for sake of GC and to suppress unnecessary signals and traversals.

param
node the node

        head = node;
        node.thread = null;
        node.prev = null;
private voidsetHeadAndPropagate(java.util.concurrent.locks.AbstractQueuedSynchronizer$Node node, int propagate)
Set head of queue, and check if successor may be waiting in shared mode, if so propagating if propagate > 0.

param
pred the node holding waitStatus for node
param
node the node
param
propagate the return value from a tryAcquireShared

        setHead(node);
        if (propagate > 0 && node.waitStatus != 0) {
            /*
             * Don't bother fully figuring out successor.  If it
             * looks null, call unparkSuccessor anyway to be safe.
             */
            Node s = node.next; 
            if (s == null || s.isShared())
                unparkSuccessor(node);
        }
protected final voidsetState(int newState)
Sets the value of synchronization state. This operation has memory semantics of a volatile write.

param
newState the new state value

        state = newState;
private static booleanshouldParkAfterFailedAcquire(java.util.concurrent.locks.AbstractQueuedSynchronizer$Node pred, java.util.concurrent.locks.AbstractQueuedSynchronizer$Node node)
Checks and updates status for a node that failed to acquire. Returns true if thread should block. This is the main signal control in all acquire loops. Requires that pred == node.prev

param
pred node's predecessor holding status
param
node the node
return
true if thread should block

        int s = pred.waitStatus;
        if (s < 0)
            /*
             * This node has already set status asking a release
             * to signal it, so it can safely park
             */
            return true;
        if (s > 0) 
            /*
             * Predecessor was cancelled. Move up to its predecessor
             * and indicate retry.
             */
            node.prev = pred.prev;
        else
            /*
             * Indicate that we need a signal, but don't park yet. Caller
             * will need to retry to make sure it cannot acquire before
             * parking.
             */
            compareAndSetWaitStatus(pred, 0, Node.SIGNAL);
        return false;
public java.lang.StringtoString()
Returns a string identifying this synchronizer, as well as its state. The state, in brackets, includes the String "State =" followed by the current value of {@link #getState}, and either "nonempty" or "empty" depending on whether the queue is empty.

return
a string identifying this synchronizer, as well as its state.

        int s = getState();
        String q  = hasQueuedThreads()? "non" : "";
        return super.toString() + 
            "[State = " + s + ", " + q + "empty queue]";
final booleantransferAfterCancelledWait(java.util.concurrent.locks.AbstractQueuedSynchronizer$Node node)
Transfers node, if necessary, to sync queue after a cancelled wait. Returns true if thread was cancelled before being signalled.

param
current the waiting thread
param
node its node
return
true if cancelled before the node was signalled.

        if (compareAndSetWaitStatus(node, Node.CONDITION, 0)) {
            enq(node);
            return true;
        }
        /*
         * If we lost out to a signal(), then we can't proceed
         * until it finishes its enq().  Cancelling during an
         * incomplete transfer is both rare and transient, so just
         * spin.
         */
        while (!isOnSyncQueue(node)) 
            Thread.yield();
        return false;
final booleantransferForSignal(java.util.concurrent.locks.AbstractQueuedSynchronizer$Node node)
Transfers a node from a condition queue onto sync queue. Returns true if successful.

param
node the node
return
true if successfully transferred (else the node was cancelled before signal).

        /*
         * If cannot change waitStatus, the node has been cancelled.
         */
        if (!compareAndSetWaitStatus(node, Node.CONDITION, 0))
            return false;

        /*
         * Splice onto queue and try to set waitStatus of predecessor to
         * indicate that thread is (probably) waiting. If cancelled or
         * attempt to set waitStatus fails, wake up to resync (in which
         * case the waitStatus can be transiently and harmlessly wrong).
         */
        Node p = enq(node);
        int c = p.waitStatus;
        if (c > 0 || !compareAndSetWaitStatus(p, c, Node.SIGNAL)) 
            LockSupport.unpark(node.thread);
        return true;
protected booleantryAcquire(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 {@link Lock#tryLock()}.

The default implementation throws {@link UnsupportedOperationException}

param
arg the acquire argument. This value is always the one passed to an acquire method, or is the value saved on entry to a condition wait. The value is otherwise uninterpreted and can represent anything you like.
return
true if successful. Upon success, this object has been acquired.
throws
IllegalMonitorStateException if acquiring would place this synchronizer in an illegal state. This exception must be thrown in a consistent fashion for synchronization to work correctly.
throws
UnsupportedOperationException if exclusive mode is not supported

        throw new UnsupportedOperationException();
public final booleantryAcquireNanos(int arg, long nanosTimeout)
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 {@link #tryAcquire}, returning on success. Otherwise, the thread is queued, possibly repeatedly blocking and unblocking, invoking {@link #tryAcquire} until success or the thread is interrupted or the timeout elapses. This method can be used to implement method {@link Lock#tryLock(long, TimeUnit)}.

param
arg the acquire argument. This value is conveyed to {@link #tryAcquire} but is otherwise uninterpreted and can represent anything you like.
param
nanosTimeout the maximum number of nanoseconds to wait
return
true if acquired; false if timed out
throws
InterruptedException if the current thread is interrupted

       if (Thread.interrupted())
           throw new InterruptedException();
       return tryAcquire(arg) ||
           doAcquireNanos(arg, nanosTimeout);
protected inttryAcquireShared(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 {@link UnsupportedOperationException}

param
arg the acquire argument. This value is always the one passed to an acquire method, or is the value saved on entry to a condition wait. The value is otherwise uninterpreted and can represent anything you like.
return
a negative value on failure, zero on exclusive success, and a positive value if non-exclusively successful, in which case a subsequent waiting thread must check availability. (Support for three different return values enables this method to be used in contexts where acquires only sometimes act exclusively.) Upon success, this object has been acquired.
throws
IllegalMonitorStateException if acquiring would place this synchronizer in an illegal state. This exception must be thrown in a consistent fashion for synchronization to work correctly.
throws
UnsupportedOperationException if shared mode is not supported

        throw new UnsupportedOperationException();
public final booleantryAcquireSharedNanos(int arg, long nanosTimeout)
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 {@link #tryAcquireShared}, returning on success. Otherwise, the thread is queued, possibly repeatedly blocking and unblocking, invoking {@link #tryAcquireShared} until success or the thread is interrupted or the timeout elapses.

param
arg the acquire argument. This value is conveyed to {@link #tryAcquireShared} but is otherwise uninterpreted and can represent anything you like.
param
nanosTimeout the maximum number of nanoseconds to wait
return
true if acquired; false if timed out
throws
InterruptedException if the current thread is interrupted

       if (Thread.interrupted())
           throw new InterruptedException();
       return tryAcquireShared(arg) >= 0 ||
           doAcquireSharedNanos(arg, nanosTimeout);
protected booleantryRelease(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 {@link UnsupportedOperationException}

param
arg the release argument. This value is always the one passed to a release method, or the current state value upon entry to a condition wait. The value is otherwise uninterpreted and can represent anything you like.
return
true if this object is now in a fully released state, so that any waiting threads may attempt to acquire; and false otherwise.
throws
IllegalMonitorStateException if releasing would place this synchronizer in an illegal state. This exception must be thrown in a consistent fashion for synchronization to work correctly.
throws
UnsupportedOperationException if exclusive mode is not supported

        throw new UnsupportedOperationException();
protected booleantryReleaseShared(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 {@link UnsupportedOperationException}

param
arg the release argument. This value is always the one passed to a release method, or the current state value upon entry to a condition wait. The value is otherwise uninterpreted and can represent anything you like.
return
true if this object is now in a fully released state, so that any waiting threads may attempt to acquire; and false otherwise.
throws
IllegalMonitorStateException if releasing would place this synchronizer in an illegal state. This exception must be thrown in a consistent fashion for synchronization to work correctly.
throws
UnsupportedOperationException if shared mode is not supported

        throw new UnsupportedOperationException();
private voidunparkSuccessor(java.util.concurrent.locks.AbstractQueuedSynchronizer$Node node)
Wake up node's successor, if one exists.

param
node the node

        /*
         * Try to clear status in anticipation of signalling.  It is
         * OK if this fails or if status is changed by waiting thread.
         */
        compareAndSetWaitStatus(node, Node.SIGNAL, 0);
        
        /*
         * Thread to unpark is held in successor, which is normally
         * just the next node.  But if cancelled or apparently null,
         * traverse backwards from tail to find the actual
         * non-cancelled successor.
         */
        Thread thread;
        Node s = node.next;
        if (s != null && s.waitStatus <= 0)
            thread = s.thread;
        else {
            thread = null;
            for (s = tail; s != null && s != node; s = s.prev) 
                if (s.waitStatus <= 0)
                    thread = s.thread;
        }
        LockSupport.unpark(thread);