Save This Page
Home » openjdk-7 » java » util » concurrent » locks » [javadoc | source]
    1   /*
    2    * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
    3    *
    4    * This code is free software; you can redistribute it and/or modify it
    5    * under the terms of the GNU General Public License version 2 only, as
    6    * published by the Free Software Foundation.  Oracle designates this
    7    * particular file as subject to the "Classpath" exception as provided
    8    * by Oracle in the LICENSE file that accompanied this code.
    9    *
   10    * This code is distributed in the hope that it will be useful, but WITHOUT
   11    * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
   12    * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
   13    * version 2 for more details (a copy is included in the LICENSE file that
   14    * accompanied this code).
   15    *
   16    * You should have received a copy of the GNU General Public License version
   17    * 2 along with this work; if not, write to the Free Software Foundation,
   18    * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
   19    *
   20    * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
   21    * or visit www.oracle.com if you need additional information or have any
   22    * questions.
   23    */
   24   
   25   /*
   26    * This file is available under and governed by the GNU General Public
   27    * License version 2 only, as published by the Free Software Foundation.
   28    * However, the following notice accompanied the original version of this
   29    * file:
   30    *
   31    * Written by Doug Lea with assistance from members of JCP JSR-166
   32    * Expert Group and released to the public domain, as explained at
   33    * http://creativecommons.org/publicdomain/zero/1.0/
   34    */
   35   
   36   package java.util.concurrent.locks;
   37   import java.util;
   38   import java.util.concurrent;
   39   import java.util.concurrent.atomic;
   40   import sun.misc.Unsafe;
   41   
   42   /**
   43    * Provides a framework for implementing blocking locks and related
   44    * synchronizers (semaphores, events, etc) that rely on
   45    * first-in-first-out (FIFO) wait queues.  This class is designed to
   46    * be a useful basis for most kinds of synchronizers that rely on a
   47    * single atomic <tt>int</tt> value to represent state. Subclasses
   48    * must define the protected methods that change this state, and which
   49    * define what that state means in terms of this object being acquired
   50    * or released.  Given these, the other methods in this class carry
   51    * out all queuing and blocking mechanics. Subclasses can maintain
   52    * other state fields, but only the atomically updated <tt>int</tt>
   53    * value manipulated using methods {@link #getState}, {@link
   54    * #setState} and {@link #compareAndSetState} is tracked with respect
   55    * to synchronization.
   56    *
   57    * <p>Subclasses should be defined as non-public internal helper
   58    * classes that are used to implement the synchronization properties
   59    * of their enclosing class.  Class
   60    * <tt>AbstractQueuedSynchronizer</tt> does not implement any
   61    * synchronization interface.  Instead it defines methods such as
   62    * {@link #acquireInterruptibly} that can be invoked as
   63    * appropriate by concrete locks and related synchronizers to
   64    * implement their public methods.
   65    *
   66    * <p>This class supports either or both a default <em>exclusive</em>
   67    * mode and a <em>shared</em> mode. When acquired in exclusive mode,
   68    * attempted acquires by other threads cannot succeed. Shared mode
   69    * acquires by multiple threads may (but need not) succeed. This class
   70    * does not &quot;understand&quot; these differences except in the
   71    * mechanical sense that when a shared mode acquire succeeds, the next
   72    * waiting thread (if one exists) must also determine whether it can
   73    * acquire as well. Threads waiting in the different modes share the
   74    * same FIFO queue. Usually, implementation subclasses support only
   75    * one of these modes, but both can come into play for example in a
   76    * {@link ReadWriteLock}. Subclasses that support only exclusive or
   77    * only shared modes need not define the methods supporting the unused mode.
   78    *
   79    * <p>This class defines a nested {@link ConditionObject} class that
   80    * can be used as a {@link Condition} implementation by subclasses
   81    * supporting exclusive mode for which method {@link
   82    * #isHeldExclusively} reports whether synchronization is exclusively
   83    * held with respect to the current thread, method {@link #release}
   84    * invoked with the current {@link #getState} value fully releases
   85    * this object, and {@link #acquire}, given this saved state value,
   86    * eventually restores this object to its previous acquired state.  No
   87    * <tt>AbstractQueuedSynchronizer</tt> method otherwise creates such a
   88    * condition, so if this constraint cannot be met, do not use it.  The
   89    * behavior of {@link ConditionObject} depends of course on the
   90    * semantics of its synchronizer implementation.
   91    *
   92    * <p>This class provides inspection, instrumentation, and monitoring
   93    * methods for the internal queue, as well as similar methods for
   94    * condition objects. These can be exported as desired into classes
   95    * using an <tt>AbstractQueuedSynchronizer</tt> for their
   96    * synchronization mechanics.
   97    *
   98    * <p>Serialization of this class stores only the underlying atomic
   99    * integer maintaining state, so deserialized objects have empty
  100    * thread queues. Typical subclasses requiring serializability will
  101    * define a <tt>readObject</tt> method that restores this to a known
  102    * initial state upon deserialization.
  103    *
  104    * <h3>Usage</h3>
  105    *
  106    * <p>To use this class as the basis of a synchronizer, redefine the
  107    * following methods, as applicable, by inspecting and/or modifying
  108    * the synchronization state using {@link #getState}, {@link
  109    * #setState} and/or {@link #compareAndSetState}:
  110    *
  111    * <ul>
  112    * <li> {@link #tryAcquire}
  113    * <li> {@link #tryRelease}
  114    * <li> {@link #tryAcquireShared}
  115    * <li> {@link #tryReleaseShared}
  116    * <li> {@link #isHeldExclusively}
  117    *</ul>
  118    *
  119    * Each of these methods by default throws {@link
  120    * UnsupportedOperationException}.  Implementations of these methods
  121    * must be internally thread-safe, and should in general be short and
  122    * not block. Defining these methods is the <em>only</em> supported
  123    * means of using this class. All other methods are declared
  124    * <tt>final</tt> because they cannot be independently varied.
  125    *
  126    * <p>You may also find the inherited methods from {@link
  127    * AbstractOwnableSynchronizer} useful to keep track of the thread
  128    * owning an exclusive synchronizer.  You are encouraged to use them
  129    * -- this enables monitoring and diagnostic tools to assist users in
  130    * determining which threads hold locks.
  131    *
  132    * <p>Even though this class is based on an internal FIFO queue, it
  133    * does not automatically enforce FIFO acquisition policies.  The core
  134    * of exclusive synchronization takes the form:
  135    *
  136    * <pre>
  137    * Acquire:
  138    *     while (!tryAcquire(arg)) {
  139    *        <em>enqueue thread if it is not already queued</em>;
  140    *        <em>possibly block current thread</em>;
  141    *     }
  142    *
  143    * Release:
  144    *     if (tryRelease(arg))
  145    *        <em>unblock the first queued thread</em>;
  146    * </pre>
  147    *
  148    * (Shared mode is similar but may involve cascading signals.)
  149    *
  150    * <p><a name="barging">Because checks in acquire are invoked before
  151    * enqueuing, a newly acquiring thread may <em>barge</em> ahead of
  152    * others that are blocked and queued.  However, you can, if desired,
  153    * define <tt>tryAcquire</tt> and/or <tt>tryAcquireShared</tt> to
  154    * disable barging by internally invoking one or more of the inspection
  155    * methods, thereby providing a <em>fair</em> FIFO acquisition order.
  156    * In particular, most fair synchronizers can define <tt>tryAcquire</tt>
  157    * to return <tt>false</tt> if {@link #hasQueuedPredecessors} (a method
  158    * specifically designed to be used by fair synchronizers) returns
  159    * <tt>true</tt>.  Other variations are possible.
  160    *
  161    * <p>Throughput and scalability are generally highest for the
  162    * default barging (also known as <em>greedy</em>,
  163    * <em>renouncement</em>, and <em>convoy-avoidance</em>) strategy.
  164    * While this is not guaranteed to be fair or starvation-free, earlier
  165    * queued threads are allowed to recontend before later queued
  166    * threads, and each recontention has an unbiased chance to succeed
  167    * against incoming threads.  Also, while acquires do not
  168    * &quot;spin&quot; in the usual sense, they may perform multiple
  169    * invocations of <tt>tryAcquire</tt> interspersed with other
  170    * computations before blocking.  This gives most of the benefits of
  171    * spins when exclusive synchronization is only briefly held, without
  172    * most of the liabilities when it isn't. If so desired, you can
  173    * augment this by preceding calls to acquire methods with
  174    * "fast-path" checks, possibly prechecking {@link #hasContended}
  175    * and/or {@link #hasQueuedThreads} to only do so if the synchronizer
  176    * is likely not to be contended.
  177    *
  178    * <p>This class provides an efficient and scalable basis for
  179    * synchronization in part by specializing its range of use to
  180    * synchronizers that can rely on <tt>int</tt> state, acquire, and
  181    * release parameters, and an internal FIFO wait queue. When this does
  182    * not suffice, you can build synchronizers from a lower level using
  183    * {@link java.util.concurrent.atomic atomic} classes, your own custom
  184    * {@link java.util.Queue} classes, and {@link LockSupport} blocking
  185    * support.
  186    *
  187    * <h3>Usage Examples</h3>
  188    *
  189    * <p>Here is a non-reentrant mutual exclusion lock class that uses
  190    * the value zero to represent the unlocked state, and one to
  191    * represent the locked state. While a non-reentrant lock
  192    * does not strictly require recording of the current owner
  193    * thread, this class does so anyway to make usage easier to monitor.
  194    * It also supports conditions and exposes
  195    * one of the instrumentation methods:
  196    *
  197    * <pre>
  198    * class Mutex implements Lock, java.io.Serializable {
  199    *
  200    *   // Our internal helper class
  201    *   private static class Sync extends AbstractQueuedSynchronizer {
  202    *     // Report whether in locked state
  203    *     protected boolean isHeldExclusively() {
  204    *       return getState() == 1;
  205    *     }
  206    *
  207    *     // Acquire the lock if state is zero
  208    *     public boolean tryAcquire(int acquires) {
  209    *       assert acquires == 1; // Otherwise unused
  210    *       if (compareAndSetState(0, 1)) {
  211    *         setExclusiveOwnerThread(Thread.currentThread());
  212    *         return true;
  213    *       }
  214    *       return false;
  215    *     }
  216    *
  217    *     // Release the lock by setting state to zero
  218    *     protected boolean tryRelease(int releases) {
  219    *       assert releases == 1; // Otherwise unused
  220    *       if (getState() == 0) throw new IllegalMonitorStateException();
  221    *       setExclusiveOwnerThread(null);
  222    *       setState(0);
  223    *       return true;
  224    *     }
  225    *
  226    *     // Provide a Condition
  227    *     Condition newCondition() { return new ConditionObject(); }
  228    *
  229    *     // Deserialize properly
  230    *     private void readObject(ObjectInputStream s)
  231    *         throws IOException, ClassNotFoundException {
  232    *       s.defaultReadObject();
  233    *       setState(0); // reset to unlocked state
  234    *     }
  235    *   }
  236    *
  237    *   // The sync object does all the hard work. We just forward to it.
  238    *   private final Sync sync = new Sync();
  239    *
  240    *   public void lock()                { sync.acquire(1); }
  241    *   public boolean tryLock()          { return sync.tryAcquire(1); }
  242    *   public void unlock()              { sync.release(1); }
  243    *   public Condition newCondition()   { return sync.newCondition(); }
  244    *   public boolean isLocked()         { return sync.isHeldExclusively(); }
  245    *   public boolean hasQueuedThreads() { return sync.hasQueuedThreads(); }
  246    *   public void lockInterruptibly() throws InterruptedException {
  247    *     sync.acquireInterruptibly(1);
  248    *   }
  249    *   public boolean tryLock(long timeout, TimeUnit unit)
  250    *       throws InterruptedException {
  251    *     return sync.tryAcquireNanos(1, unit.toNanos(timeout));
  252    *   }
  253    * }
  254    * </pre>
  255    *
  256    * <p>Here is a latch class that is like a {@link CountDownLatch}
  257    * except that it only requires a single <tt>signal</tt> to
  258    * fire. Because a latch is non-exclusive, it uses the <tt>shared</tt>
  259    * acquire and release methods.
  260    *
  261    * <pre>
  262    * class BooleanLatch {
  263    *
  264    *   private static class Sync extends AbstractQueuedSynchronizer {
  265    *     boolean isSignalled() { return getState() != 0; }
  266    *
  267    *     protected int tryAcquireShared(int ignore) {
  268    *       return isSignalled() ? 1 : -1;
  269    *     }
  270    *
  271    *     protected boolean tryReleaseShared(int ignore) {
  272    *       setState(1);
  273    *       return true;
  274    *     }
  275    *   }
  276    *
  277    *   private final Sync sync = new Sync();
  278    *   public boolean isSignalled() { return sync.isSignalled(); }
  279    *   public void signal()         { sync.releaseShared(1); }
  280    *   public void await() throws InterruptedException {
  281    *     sync.acquireSharedInterruptibly(1);
  282    *   }
  283    * }
  284    * </pre>
  285    *
  286    * @since 1.5
  287    * @author Doug Lea
  288    */
  289   public abstract class AbstractQueuedSynchronizer
  290       extends AbstractOwnableSynchronizer
  291       implements java.io.Serializable {
  292   
  293       private static final long serialVersionUID = 7373984972572414691L;
  294   
  295       /**
  296        * Creates a new <tt>AbstractQueuedSynchronizer</tt> instance
  297        * with initial synchronization state of zero.
  298        */
  299       protected AbstractQueuedSynchronizer() { }
  300   
  301       /**
  302        * Wait queue node class.
  303        *
  304        * <p>The wait queue is a variant of a "CLH" (Craig, Landin, and
  305        * Hagersten) lock queue. CLH locks are normally used for
  306        * spinlocks.  We instead use them for blocking synchronizers, but
  307        * use the same basic tactic of holding some of the control
  308        * information about a thread in the predecessor of its node.  A
  309        * "status" field in each node keeps track of whether a thread
  310        * should block.  A node is signalled when its predecessor
  311        * releases.  Each node of the queue otherwise serves as a
  312        * specific-notification-style monitor holding a single waiting
  313        * thread. The status field does NOT control whether threads are
  314        * granted locks etc though.  A thread may try to acquire if it is
  315        * first in the queue. But being first does not guarantee success;
  316        * it only gives the right to contend.  So the currently released
  317        * contender thread may need to rewait.
  318        *
  319        * <p>To enqueue into a CLH lock, you atomically splice it in as new
  320        * tail. To dequeue, you just set the head field.
  321        * <pre>
  322        *      +------+  prev +-----+       +-----+
  323        * head |      | <---- |     | <---- |     |  tail
  324        *      +------+       +-----+       +-----+
  325        * </pre>
  326        *
  327        * <p>Insertion into a CLH queue requires only a single atomic
  328        * operation on "tail", so there is a simple atomic point of
  329        * demarcation from unqueued to queued. Similarly, dequeing
  330        * involves only updating the "head". However, it takes a bit
  331        * more work for nodes to determine who their successors are,
  332        * in part to deal with possible cancellation due to timeouts
  333        * and interrupts.
  334        *
  335        * <p>The "prev" links (not used in original CLH locks), are mainly
  336        * needed to handle cancellation. If a node is cancelled, its
  337        * successor is (normally) relinked to a non-cancelled
  338        * predecessor. For explanation of similar mechanics in the case
  339        * of spin locks, see the papers by Scott and Scherer at
  340        * http://www.cs.rochester.edu/u/scott/synchronization/
  341        *
  342        * <p>We also use "next" links to implement blocking mechanics.
  343        * The thread id for each node is kept in its own node, so a
  344        * predecessor signals the next node to wake up by traversing
  345        * next link to determine which thread it is.  Determination of
  346        * successor must avoid races with newly queued nodes to set
  347        * the "next" fields of their predecessors.  This is solved
  348        * when necessary by checking backwards from the atomically
  349        * updated "tail" when a node's successor appears to be null.
  350        * (Or, said differently, the next-links are an optimization
  351        * so that we don't usually need a backward scan.)
  352        *
  353        * <p>Cancellation introduces some conservatism to the basic
  354        * algorithms.  Since we must poll for cancellation of other
  355        * nodes, we can miss noticing whether a cancelled node is
  356        * ahead or behind us. This is dealt with by always unparking
  357        * successors upon cancellation, allowing them to stabilize on
  358        * a new predecessor, unless we can identify an uncancelled
  359        * predecessor who will carry this responsibility.
  360        *
  361        * <p>CLH queues need a dummy header node to get started. But
  362        * we don't create them on construction, because it would be wasted
  363        * effort if there is never contention. Instead, the node
  364        * is constructed and head and tail pointers are set upon first
  365        * contention.
  366        *
  367        * <p>Threads waiting on Conditions use the same nodes, but
  368        * use an additional link. Conditions only need to link nodes
  369        * in simple (non-concurrent) linked queues because they are
  370        * only accessed when exclusively held.  Upon await, a node is
  371        * inserted into a condition queue.  Upon signal, the node is
  372        * transferred to the main queue.  A special value of status
  373        * field is used to mark which queue a node is on.
  374        *
  375        * <p>Thanks go to Dave Dice, Mark Moir, Victor Luchangco, Bill
  376        * Scherer and Michael Scott, along with members of JSR-166
  377        * expert group, for helpful ideas, discussions, and critiques
  378        * on the design of this class.
  379        */
  380       static final class Node {
  381           /** Marker to indicate a node is waiting in shared mode */
  382           static final Node SHARED = new Node();
  383           /** Marker to indicate a node is waiting in exclusive mode */
  384           static final Node EXCLUSIVE = null;
  385   
  386           /** waitStatus value to indicate thread has cancelled */
  387           static final int CANCELLED =  1;
  388           /** waitStatus value to indicate successor's thread needs unparking */
  389           static final int SIGNAL    = -1;
  390           /** waitStatus value to indicate thread is waiting on condition */
  391           static final int CONDITION = -2;
  392           /**
  393            * waitStatus value to indicate the next acquireShared should
  394            * unconditionally propagate
  395            */
  396           static final int PROPAGATE = -3;
  397   
  398           /**
  399            * Status field, taking on only the values:
  400            *   SIGNAL:     The successor of this node is (or will soon be)
  401            *               blocked (via park), so the current node must
  402            *               unpark its successor when it releases or
  403            *               cancels. To avoid races, acquire methods must
  404            *               first indicate they need a signal,
  405            *               then retry the atomic acquire, and then,
  406            *               on failure, block.
  407            *   CANCELLED:  This node is cancelled due to timeout or interrupt.
  408            *               Nodes never leave this state. In particular,
  409            *               a thread with cancelled node never again blocks.
  410            *   CONDITION:  This node is currently on a condition queue.
  411            *               It will not be used as a sync queue node
  412            *               until transferred, at which time the status
  413            *               will be set to 0. (Use of this value here has
  414            *               nothing to do with the other uses of the
  415            *               field, but simplifies mechanics.)
  416            *   PROPAGATE:  A releaseShared should be propagated to other
  417            *               nodes. This is set (for head node only) in
  418            *               doReleaseShared to ensure propagation
  419            *               continues, even if other operations have
  420            *               since intervened.
  421            *   0:          None of the above
  422            *
  423            * The values are arranged numerically to simplify use.
  424            * Non-negative values mean that a node doesn't need to
  425            * signal. So, most code doesn't need to check for particular
  426            * values, just for sign.
  427            *
  428            * The field is initialized to 0 for normal sync nodes, and
  429            * CONDITION for condition nodes.  It is modified using CAS
  430            * (or when possible, unconditional volatile writes).
  431            */
  432           volatile int waitStatus;
  433   
  434           /**
  435            * Link to predecessor node that current node/thread relies on
  436            * for checking waitStatus. Assigned during enqueing, and nulled
  437            * out (for sake of GC) only upon dequeuing.  Also, upon
  438            * cancellation of a predecessor, we short-circuit while
  439            * finding a non-cancelled one, which will always exist
  440            * because the head node is never cancelled: A node becomes
  441            * head only as a result of successful acquire. A
  442            * cancelled thread never succeeds in acquiring, and a thread only
  443            * cancels itself, not any other node.
  444            */
  445           volatile Node prev;
  446   
  447           /**
  448            * Link to the successor node that the current node/thread
  449            * unparks upon release. Assigned during enqueuing, adjusted
  450            * when bypassing cancelled predecessors, and nulled out (for
  451            * sake of GC) when dequeued.  The enq operation does not
  452            * assign next field of a predecessor until after attachment,
  453            * so seeing a null next field does not necessarily mean that
  454            * node is at end of queue. However, if a next field appears
  455            * to be null, we can scan prev's from the tail to
  456            * double-check.  The next field of cancelled nodes is set to
  457            * point to the node itself instead of null, to make life
  458            * easier for isOnSyncQueue.
  459            */
  460           volatile Node next;
  461   
  462           /**
  463            * The thread that enqueued this node.  Initialized on
  464            * construction and nulled out after use.
  465            */
  466           volatile Thread thread;
  467   
  468           /**
  469            * Link to next node waiting on condition, or the special
  470            * value SHARED.  Because condition queues are accessed only
  471            * when holding in exclusive mode, we just need a simple
  472            * linked queue to hold nodes while they are waiting on
  473            * conditions. They are then transferred to the queue to
  474            * re-acquire. And because conditions can only be exclusive,
  475            * we save a field by using special value to indicate shared
  476            * mode.
  477            */
  478           Node nextWaiter;
  479   
  480           /**
  481            * Returns true if node is waiting in shared mode
  482            */
  483           final boolean isShared() {
  484               return nextWaiter == SHARED;
  485           }
  486   
  487           /**
  488            * Returns previous node, or throws NullPointerException if null.
  489            * Use when predecessor cannot be null.  The null check could
  490            * be elided, but is present to help the VM.
  491            *
  492            * @return the predecessor of this node
  493            */
  494           final Node predecessor() throws NullPointerException {
  495               Node p = prev;
  496               if (p == null)
  497                   throw new NullPointerException();
  498               else
  499                   return p;
  500           }
  501   
  502           Node() {    // Used to establish initial head or SHARED marker
  503           }
  504   
  505           Node(Thread thread, Node mode) {     // Used by addWaiter
  506               this.nextWaiter = mode;
  507               this.thread = thread;
  508           }
  509   
  510           Node(Thread thread, int waitStatus) { // Used by Condition
  511               this.waitStatus = waitStatus;
  512               this.thread = thread;
  513           }
  514       }
  515   
  516       /**
  517        * Head of the wait queue, lazily initialized.  Except for
  518        * initialization, it is modified only via method setHead.  Note:
  519        * If head exists, its waitStatus is guaranteed not to be
  520        * CANCELLED.
  521        */
  522       private transient volatile Node head;
  523   
  524       /**
  525        * Tail of the wait queue, lazily initialized.  Modified only via
  526        * method enq to add new wait node.
  527        */
  528       private transient volatile Node tail;
  529   
  530       /**
  531        * The synchronization state.
  532        */
  533       private volatile int state;
  534   
  535       /**
  536        * Returns the current value of synchronization state.
  537        * This operation has memory semantics of a <tt>volatile</tt> read.
  538        * @return current state value
  539        */
  540       protected final int getState() {
  541           return state;
  542       }
  543   
  544       /**
  545        * Sets the value of synchronization state.
  546        * This operation has memory semantics of a <tt>volatile</tt> write.
  547        * @param newState the new state value
  548        */
  549       protected final void setState(int newState) {
  550           state = newState;
  551       }
  552   
  553       /**
  554        * Atomically sets synchronization state to the given updated
  555        * value if the current state value equals the expected value.
  556        * This operation has memory semantics of a <tt>volatile</tt> read
  557        * and write.
  558        *
  559        * @param expect the expected value
  560        * @param update the new value
  561        * @return true if successful. False return indicates that the actual
  562        *         value was not equal to the expected value.
  563        */
  564       protected final boolean compareAndSetState(int expect, int update) {
  565           // See below for intrinsics setup to support this
  566           return unsafe.compareAndSwapInt(this, stateOffset, expect, update);
  567       }
  568   
  569       // Queuing utilities
  570   
  571       /**
  572        * The number of nanoseconds for which it is faster to spin
  573        * rather than to use timed park. A rough estimate suffices
  574        * to improve responsiveness with very short timeouts.
  575        */
  576       static final long spinForTimeoutThreshold = 1000L;
  577   
  578       /**
  579        * Inserts node into queue, initializing if necessary. See picture above.
  580        * @param node the node to insert
  581        * @return node's predecessor
  582        */
  583       private Node enq(final Node node) {
  584           for (;;) {
  585               Node t = tail;
  586               if (t == null) { // Must initialize
  587                   if (compareAndSetHead(new Node()))
  588                       tail = head;
  589               } else {
  590                   node.prev = t;
  591                   if (compareAndSetTail(t, node)) {
  592                       t.next = node;
  593                       return t;
  594                   }
  595               }
  596           }
  597       }
  598   
  599       /**
  600        * Creates and enqueues node for current thread and given mode.
  601        *
  602        * @param mode Node.EXCLUSIVE for exclusive, Node.SHARED for shared
  603        * @return the new node
  604        */
  605       private Node addWaiter(Node mode) {
  606           Node node = new Node(Thread.currentThread(), mode);
  607           // Try the fast path of enq; backup to full enq on failure
  608           Node pred = tail;
  609           if (pred != null) {
  610               node.prev = pred;
  611               if (compareAndSetTail(pred, node)) {
  612                   pred.next = node;
  613                   return node;
  614               }
  615           }
  616           enq(node);
  617           return node;
  618       }
  619   
  620       /**
  621        * Sets head of queue to be node, thus dequeuing. Called only by
  622        * acquire methods.  Also nulls out unused fields for sake of GC
  623        * and to suppress unnecessary signals and traversals.
  624        *
  625        * @param node the node
  626        */
  627       private void setHead(Node node) {
  628           head = node;
  629           node.thread = null;
  630           node.prev = null;
  631       }
  632   
  633       /**
  634        * Wakes up node's successor, if one exists.
  635        *
  636        * @param node the node
  637        */
  638       private void unparkSuccessor(Node node) {
  639           /*
  640            * If status is negative (i.e., possibly needing signal) try
  641            * to clear in anticipation of signalling.  It is OK if this
  642            * fails or if status is changed by waiting thread.
  643            */
  644           int ws = node.waitStatus;
  645           if (ws < 0)
  646               compareAndSetWaitStatus(node, ws, 0);
  647   
  648           /*
  649            * Thread to unpark is held in successor, which is normally
  650            * just the next node.  But if cancelled or apparently null,
  651            * traverse backwards from tail to find the actual
  652            * non-cancelled successor.
  653            */
  654           Node s = node.next;
  655           if (s == null || s.waitStatus > 0) {
  656               s = null;
  657               for (Node t = tail; t != null && t != node; t = t.prev)
  658                   if (t.waitStatus <= 0)
  659                       s = t;
  660           }
  661           if (s != null)
  662               LockSupport.unpark(s.thread);
  663       }
  664   
  665       /**
  666        * Release action for shared mode -- signal successor and ensure
  667        * propagation. (Note: For exclusive mode, release just amounts
  668        * to calling unparkSuccessor of head if it needs signal.)
  669        */
  670       private void doReleaseShared() {
  671           /*
  672            * Ensure that a release propagates, even if there are other
  673            * in-progress acquires/releases.  This proceeds in the usual
  674            * way of trying to unparkSuccessor of head if it needs
  675            * signal. But if it does not, status is set to PROPAGATE to
  676            * ensure that upon release, propagation continues.
  677            * Additionally, we must loop in case a new node is added
  678            * while we are doing this. Also, unlike other uses of
  679            * unparkSuccessor, we need to know if CAS to reset status
  680            * fails, if so rechecking.
  681            */
  682           for (;;) {
  683               Node h = head;
  684               if (h != null && h != tail) {
  685                   int ws = h.waitStatus;
  686                   if (ws == Node.SIGNAL) {
  687                       if (!compareAndSetWaitStatus(h, Node.SIGNAL, 0))
  688                           continue;            // loop to recheck cases
  689                       unparkSuccessor(h);
  690                   }
  691                   else if (ws == 0 &&
  692                            !compareAndSetWaitStatus(h, 0, Node.PROPAGATE))
  693                       continue;                // loop on failed CAS
  694               }
  695               if (h == head)                   // loop if head changed
  696                   break;
  697           }
  698       }
  699   
  700       /**
  701        * Sets head of queue, and checks if successor may be waiting
  702        * in shared mode, if so propagating if either propagate > 0 or
  703        * PROPAGATE status was set.
  704        *
  705        * @param node the node
  706        * @param propagate the return value from a tryAcquireShared
  707        */
  708       private void setHeadAndPropagate(Node node, int propagate) {
  709           Node h = head; // Record old head for check below
  710           setHead(node);
  711           /*
  712            * Try to signal next queued node if:
  713            *   Propagation was indicated by caller,
  714            *     or was recorded (as h.waitStatus) by a previous operation
  715            *     (note: this uses sign-check of waitStatus because
  716            *      PROPAGATE status may transition to SIGNAL.)
  717            * and
  718            *   The next node is waiting in shared mode,
  719            *     or we don't know, because it appears null
  720            *
  721            * The conservatism in both of these checks may cause
  722            * unnecessary wake-ups, but only when there are multiple
  723            * racing acquires/releases, so most need signals now or soon
  724            * anyway.
  725            */
  726           if (propagate > 0 || h == null || h.waitStatus < 0) {
  727               Node s = node.next;
  728               if (s == null || s.isShared())
  729                   doReleaseShared();
  730           }
  731       }
  732   
  733       // Utilities for various versions of acquire
  734   
  735       /**
  736        * Cancels an ongoing attempt to acquire.
  737        *
  738        * @param node the node
  739        */
  740       private void cancelAcquire(Node node) {
  741           // Ignore if node doesn't exist
  742           if (node == null)
  743               return;
  744   
  745           node.thread = null;
  746   
  747           // Skip cancelled predecessors
  748           Node pred = node.prev;
  749           while (pred.waitStatus > 0)
  750               node.prev = pred = pred.prev;
  751   
  752           // predNext is the apparent node to unsplice. CASes below will
  753           // fail if not, in which case, we lost race vs another cancel
  754           // or signal, so no further action is necessary.
  755           Node predNext = pred.next;
  756   
  757           // Can use unconditional write instead of CAS here.
  758           // After this atomic step, other Nodes can skip past us.
  759           // Before, we are free of interference from other threads.
  760           node.waitStatus = Node.CANCELLED;
  761   
  762           // If we are the tail, remove ourselves.
  763           if (node == tail && compareAndSetTail(node, pred)) {
  764               compareAndSetNext(pred, predNext, null);
  765           } else {
  766               // If successor needs signal, try to set pred's next-link
  767               // so it will get one. Otherwise wake it up to propagate.
  768               int ws;
  769               if (pred != head &&
  770                   ((ws = pred.waitStatus) == Node.SIGNAL ||
  771                    (ws <= 0 && compareAndSetWaitStatus(pred, ws, Node.SIGNAL))) &&
  772                   pred.thread != null) {
  773                   Node next = node.next;
  774                   if (next != null && next.waitStatus <= 0)
  775                       compareAndSetNext(pred, predNext, next);
  776               } else {
  777                   unparkSuccessor(node);
  778               }
  779   
  780               node.next = node; // help GC
  781           }
  782       }
  783   
  784       /**
  785        * Checks and updates status for a node that failed to acquire.
  786        * Returns true if thread should block. This is the main signal
  787        * control in all acquire loops.  Requires that pred == node.prev
  788        *
  789        * @param pred node's predecessor holding status
  790        * @param node the node
  791        * @return {@code true} if thread should block
  792        */
  793       private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
  794           int ws = pred.waitStatus;
  795           if (ws == Node.SIGNAL)
  796               /*
  797                * This node has already set status asking a release
  798                * to signal it, so it can safely park.
  799                */
  800               return true;
  801           if (ws > 0) {
  802               /*
  803                * Predecessor was cancelled. Skip over predecessors and
  804                * indicate retry.
  805                */
  806               do {
  807                   node.prev = pred = pred.prev;
  808               } while (pred.waitStatus > 0);
  809               pred.next = node;
  810           } else {
  811               /*
  812                * waitStatus must be 0 or PROPAGATE.  Indicate that we
  813                * need a signal, but don't park yet.  Caller will need to
  814                * retry to make sure it cannot acquire before parking.
  815                */
  816               compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
  817           }
  818           return false;
  819       }
  820   
  821       /**
  822        * Convenience method to interrupt current thread.
  823        */
  824       private static void selfInterrupt() {
  825           Thread.currentThread().interrupt();
  826       }
  827   
  828       /**
  829        * Convenience method to park and then check if interrupted
  830        *
  831        * @return {@code true} if interrupted
  832        */
  833       private final boolean parkAndCheckInterrupt() {
  834           LockSupport.park(this);
  835           return Thread.interrupted();
  836       }
  837   
  838       /*
  839        * Various flavors of acquire, varying in exclusive/shared and
  840        * control modes.  Each is mostly the same, but annoyingly
  841        * different.  Only a little bit of factoring is possible due to
  842        * interactions of exception mechanics (including ensuring that we
  843        * cancel if tryAcquire throws exception) and other control, at
  844        * least not without hurting performance too much.
  845        */
  846   
  847       /**
  848        * Acquires in exclusive uninterruptible mode for thread already in
  849        * queue. Used by condition wait methods as well as acquire.
  850        *
  851        * @param node the node
  852        * @param arg the acquire argument
  853        * @return {@code true} if interrupted while waiting
  854        */
  855       final boolean acquireQueued(final Node node, int arg) {
  856           boolean failed = true;
  857           try {
  858               boolean interrupted = false;
  859               for (;;) {
  860                   final Node p = node.predecessor();
  861                   if (p == head && tryAcquire(arg)) {
  862                       setHead(node);
  863                       p.next = null; // help GC
  864                       failed = false;
  865                       return interrupted;
  866                   }
  867                   if (shouldParkAfterFailedAcquire(p, node) &&
  868                       parkAndCheckInterrupt())
  869                       interrupted = true;
  870               }
  871           } finally {
  872               if (failed)
  873                   cancelAcquire(node);
  874           }
  875       }
  876   
  877       /**
  878        * Acquires in exclusive interruptible mode.
  879        * @param arg the acquire argument
  880        */
  881       private void doAcquireInterruptibly(int arg)
  882           throws InterruptedException {
  883           final Node node = addWaiter(Node.EXCLUSIVE);
  884           boolean failed = true;
  885           try {
  886               for (;;) {
  887                   final Node p = node.predecessor();
  888                   if (p == head && tryAcquire(arg)) {
  889                       setHead(node);
  890                       p.next = null; // help GC
  891                       failed = false;
  892                       return;
  893                   }
  894                   if (shouldParkAfterFailedAcquire(p, node) &&
  895                       parkAndCheckInterrupt())
  896                       throw new InterruptedException();
  897               }
  898           } finally {
  899               if (failed)
  900                   cancelAcquire(node);
  901           }
  902       }
  903   
  904       /**
  905        * Acquires in exclusive timed mode.
  906        *
  907        * @param arg the acquire argument
  908        * @param nanosTimeout max wait time
  909        * @return {@code true} if acquired
  910        */
  911       private boolean doAcquireNanos(int arg, long nanosTimeout)
  912           throws InterruptedException {
  913           long lastTime = System.nanoTime();
  914           final Node node = addWaiter(Node.EXCLUSIVE);
  915           boolean failed = true;
  916           try {
  917               for (;;) {
  918                   final Node p = node.predecessor();
  919                   if (p == head && tryAcquire(arg)) {
  920                       setHead(node);
  921                       p.next = null; // help GC
  922                       failed = false;
  923                       return true;
  924                   }
  925                   if (nanosTimeout <= 0)
  926                       return false;
  927                   if (shouldParkAfterFailedAcquire(p, node) &&
  928                       nanosTimeout > spinForTimeoutThreshold)
  929                       LockSupport.parkNanos(this, nanosTimeout);
  930                   long now = System.nanoTime();
  931                   nanosTimeout -= now - lastTime;
  932                   lastTime = now;
  933                   if (Thread.interrupted())
  934                       throw new InterruptedException();
  935               }
  936           } finally {
  937               if (failed)
  938                   cancelAcquire(node);
  939           }
  940       }
  941   
  942       /**
  943        * Acquires in shared uninterruptible mode.
  944        * @param arg the acquire argument
  945        */
  946       private void doAcquireShared(int arg) {
  947           final Node node = addWaiter(Node.SHARED);
  948           boolean failed = true;
  949           try {
  950               boolean interrupted = false;
  951               for (;;) {
  952                   final Node p = node.predecessor();
  953                   if (p == head) {
  954                       int r = tryAcquireShared(arg);
  955                       if (r >= 0) {
  956                           setHeadAndPropagate(node, r);
  957                           p.next = null; // help GC
  958                           if (interrupted)
  959                               selfInterrupt();
  960                           failed = false;
  961                           return;
  962                       }
  963                   }
  964                   if (shouldParkAfterFailedAcquire(p, node) &&
  965                       parkAndCheckInterrupt())
  966                       interrupted = true;
  967               }
  968           } finally {
  969               if (failed)
  970                   cancelAcquire(node);
  971           }
  972       }
  973   
  974       /**
  975        * Acquires in shared interruptible mode.
  976        * @param arg the acquire argument
  977        */
  978       private void doAcquireSharedInterruptibly(int arg)
  979           throws InterruptedException {
  980           final Node node = addWaiter(Node.SHARED);
  981           boolean failed = true;
  982           try {
  983               for (;;) {
  984                   final Node p = node.predecessor();
  985                   if (p == head) {
  986                       int r = tryAcquireShared(arg);
  987                       if (r >= 0) {
  988                           setHeadAndPropagate(node, r);
  989                           p.next = null; // help GC
  990                           failed = false;
  991                           return;
  992                       }
  993                   }
  994                   if (shouldParkAfterFailedAcquire(p, node) &&
  995                       parkAndCheckInterrupt())
  996                       throw new InterruptedException();
  997               }
  998           } finally {
  999               if (failed)
 1000                   cancelAcquire(node);
 1001           }
 1002       }
 1003   
 1004       /**
 1005        * Acquires in shared timed mode.
 1006        *
 1007        * @param arg the acquire argument
 1008        * @param nanosTimeout max wait time
 1009        * @return {@code true} if acquired
 1010        */
 1011       private boolean doAcquireSharedNanos(int arg, long nanosTimeout)
 1012           throws InterruptedException {
 1013   
 1014           long lastTime = System.nanoTime();
 1015           final Node node = addWaiter(Node.SHARED);
 1016           boolean failed = true;
 1017           try {
 1018               for (;;) {
 1019                   final Node p = node.predecessor();
 1020                   if (p == head) {
 1021                       int r = tryAcquireShared(arg);
 1022                       if (r >= 0) {
 1023                           setHeadAndPropagate(node, r);
 1024                           p.next = null; // help GC
 1025                           failed = false;
 1026                           return true;
 1027                       }
 1028                   }
 1029                   if (nanosTimeout <= 0)
 1030                       return false;
 1031                   if (shouldParkAfterFailedAcquire(p, node) &&
 1032                       nanosTimeout > spinForTimeoutThreshold)
 1033                       LockSupport.parkNanos(this, nanosTimeout);
 1034                   long now = System.nanoTime();
 1035                   nanosTimeout -= now - lastTime;
 1036                   lastTime = now;
 1037                   if (Thread.interrupted())
 1038                       throw new InterruptedException();
 1039               }
 1040           } finally {
 1041               if (failed)
 1042                   cancelAcquire(node);
 1043           }
 1044       }
 1045   
 1046       // Main exported methods
 1047   
 1048       /**
 1049        * Attempts to acquire in exclusive mode. This method should query
 1050        * if the state of the object permits it to be acquired in the
 1051        * exclusive mode, and if so to acquire it.
 1052        *
 1053        * <p>This method is always invoked by the thread performing
 1054        * acquire.  If this method reports failure, the acquire method
 1055        * may queue the thread, if it is not already queued, until it is
 1056        * signalled by a release from some other thread. This can be used
 1057        * to implement method {@link Lock#tryLock()}.
 1058        *
 1059        * <p>The default
 1060        * implementation throws {@link UnsupportedOperationException}.
 1061        *
 1062        * @param arg the acquire argument. This value is always the one
 1063        *        passed to an acquire method, or is the value saved on entry
 1064        *        to a condition wait.  The value is otherwise uninterpreted
 1065        *        and can represent anything you like.
 1066        * @return {@code true} if successful. Upon success, this object has
 1067        *         been acquired.
 1068        * @throws IllegalMonitorStateException if acquiring would place this
 1069        *         synchronizer in an illegal state. This exception must be
 1070        *         thrown in a consistent fashion for synchronization to work
 1071        *         correctly.
 1072        * @throws UnsupportedOperationException if exclusive mode is not supported
 1073        */
 1074       protected boolean tryAcquire(int arg) {
 1075           throw new UnsupportedOperationException();
 1076       }
 1077   
 1078       /**
 1079        * Attempts to set the state to reflect a release in exclusive
 1080        * mode.
 1081        *
 1082        * <p>This method is always invoked by the thread performing release.
 1083        *
 1084        * <p>The default implementation throws
 1085        * {@link UnsupportedOperationException}.
 1086        *
 1087        * @param arg the release argument. This value is always the one
 1088        *        passed to a release method, or the current state value upon
 1089        *        entry to a condition wait.  The value is otherwise
 1090        *        uninterpreted and can represent anything you like.
 1091        * @return {@code true} if this object is now in a fully released
 1092        *         state, so that any waiting threads may attempt to acquire;
 1093        *         and {@code false} otherwise.
 1094        * @throws IllegalMonitorStateException if releasing would place this
 1095        *         synchronizer in an illegal state. This exception must be
 1096        *         thrown in a consistent fashion for synchronization to work
 1097        *         correctly.
 1098        * @throws UnsupportedOperationException if exclusive mode is not supported
 1099        */
 1100       protected boolean tryRelease(int arg) {
 1101           throw new UnsupportedOperationException();
 1102       }
 1103   
 1104       /**
 1105        * Attempts to acquire in shared mode. This method should query if
 1106        * the state of the object permits it to be acquired in the shared
 1107        * mode, and if so to acquire it.
 1108        *
 1109        * <p>This method is always invoked by the thread performing
 1110        * acquire.  If this method reports failure, the acquire method
 1111        * may queue the thread, if it is not already queued, until it is
 1112        * signalled by a release from some other thread.
 1113        *
 1114        * <p>The default implementation throws {@link
 1115        * UnsupportedOperationException}.
 1116        *
 1117        * @param arg the acquire argument. This value is always the one
 1118        *        passed to an acquire method, or is the value saved on entry
 1119        *        to a condition wait.  The value is otherwise uninterpreted
 1120        *        and can represent anything you like.
 1121        * @return a negative value on failure; zero if acquisition in shared
 1122        *         mode succeeded but no subsequent shared-mode acquire can
 1123        *         succeed; and a positive value if acquisition in shared
 1124        *         mode succeeded and subsequent shared-mode acquires might
 1125        *         also succeed, in which case a subsequent waiting thread
 1126        *         must check availability. (Support for three different
 1127        *         return values enables this method to be used in contexts
 1128        *         where acquires only sometimes act exclusively.)  Upon
 1129        *         success, this object has been acquired.
 1130        * @throws IllegalMonitorStateException if acquiring would place this
 1131        *         synchronizer in an illegal state. This exception must be
 1132        *         thrown in a consistent fashion for synchronization to work
 1133        *         correctly.
 1134        * @throws UnsupportedOperationException if shared mode is not supported
 1135        */
 1136       protected int tryAcquireShared(int arg) {
 1137           throw new UnsupportedOperationException();
 1138       }
 1139   
 1140       /**
 1141        * Attempts to set the state to reflect a release in shared mode.
 1142        *
 1143        * <p>This method is always invoked by the thread performing release.
 1144        *
 1145        * <p>The default implementation throws
 1146        * {@link UnsupportedOperationException}.
 1147        *
 1148        * @param arg the release argument. This value is always the one
 1149        *        passed to a release method, or the current state value upon
 1150        *        entry to a condition wait.  The value is otherwise
 1151        *        uninterpreted and can represent anything you like.
 1152        * @return {@code true} if this release of shared mode may permit a
 1153        *         waiting acquire (shared or exclusive) to succeed; and
 1154        *         {@code false} otherwise
 1155        * @throws IllegalMonitorStateException if releasing would place this
 1156        *         synchronizer in an illegal state. This exception must be
 1157        *         thrown in a consistent fashion for synchronization to work
 1158        *         correctly.
 1159        * @throws UnsupportedOperationException if shared mode is not supported
 1160        */
 1161       protected boolean tryReleaseShared(int arg) {
 1162           throw new UnsupportedOperationException();
 1163       }
 1164   
 1165       /**
 1166        * Returns {@code true} if synchronization is held exclusively with
 1167        * respect to the current (calling) thread.  This method is invoked
 1168        * upon each call to a non-waiting {@link ConditionObject} method.
 1169        * (Waiting methods instead invoke {@link #release}.)
 1170        *
 1171        * <p>The default implementation throws {@link
 1172        * UnsupportedOperationException}. This method is invoked
 1173        * internally only within {@link ConditionObject} methods, so need
 1174        * not be defined if conditions are not used.
 1175        *
 1176        * @return {@code true} if synchronization is held exclusively;
 1177        *         {@code false} otherwise
 1178        * @throws UnsupportedOperationException if conditions are not supported
 1179        */
 1180       protected boolean isHeldExclusively() {
 1181           throw new UnsupportedOperationException();
 1182       }
 1183   
 1184       /**
 1185        * Acquires in exclusive mode, ignoring interrupts.  Implemented
 1186        * by invoking at least once {@link #tryAcquire},
 1187        * returning on success.  Otherwise the thread is queued, possibly
 1188        * repeatedly blocking and unblocking, invoking {@link
 1189        * #tryAcquire} until success.  This method can be used
 1190        * to implement method {@link Lock#lock}.
 1191        *
 1192        * @param arg the acquire argument.  This value is conveyed to
 1193        *        {@link #tryAcquire} but is otherwise uninterpreted and
 1194        *        can represent anything you like.
 1195        */
 1196       public final void acquire(int arg) {
 1197           if (!tryAcquire(arg) &&
 1198               acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
 1199               selfInterrupt();
 1200       }
 1201   
 1202       /**
 1203        * Acquires in exclusive mode, aborting if interrupted.
 1204        * Implemented by first checking interrupt status, then invoking
 1205        * at least once {@link #tryAcquire}, returning on
 1206        * success.  Otherwise the thread is queued, possibly repeatedly
 1207        * blocking and unblocking, invoking {@link #tryAcquire}
 1208        * until success or the thread is interrupted.  This method can be
 1209        * used to implement method {@link Lock#lockInterruptibly}.
 1210        *
 1211        * @param arg the acquire argument.  This value is conveyed to
 1212        *        {@link #tryAcquire} but is otherwise uninterpreted and
 1213        *        can represent anything you like.
 1214        * @throws InterruptedException if the current thread is interrupted
 1215        */
 1216       public final void acquireInterruptibly(int arg)
 1217               throws InterruptedException {
 1218           if (Thread.interrupted())
 1219               throw new InterruptedException();
 1220           if (!tryAcquire(arg))
 1221               doAcquireInterruptibly(arg);
 1222       }
 1223   
 1224       /**
 1225        * Attempts to acquire in exclusive mode, aborting if interrupted,
 1226        * and failing if the given timeout elapses.  Implemented by first
 1227        * checking interrupt status, then invoking at least once {@link
 1228        * #tryAcquire}, returning on success.  Otherwise, the thread is
 1229        * queued, possibly repeatedly blocking and unblocking, invoking
 1230        * {@link #tryAcquire} until success or the thread is interrupted
 1231        * or the timeout elapses.  This method can be used to implement
 1232        * method {@link Lock#tryLock(long, TimeUnit)}.
 1233        *
 1234        * @param arg the acquire argument.  This value is conveyed to
 1235        *        {@link #tryAcquire} but is otherwise uninterpreted and
 1236        *        can represent anything you like.
 1237        * @param nanosTimeout the maximum number of nanoseconds to wait
 1238        * @return {@code true} if acquired; {@code false} if timed out
 1239        * @throws InterruptedException if the current thread is interrupted
 1240        */
 1241       public final boolean tryAcquireNanos(int arg, long nanosTimeout)
 1242               throws InterruptedException {
 1243           if (Thread.interrupted())
 1244               throw new InterruptedException();
 1245           return tryAcquire(arg) ||
 1246               doAcquireNanos(arg, nanosTimeout);
 1247       }
 1248   
 1249       /**
 1250        * Releases in exclusive mode.  Implemented by unblocking one or
 1251        * more threads if {@link #tryRelease} returns true.
 1252        * This method can be used to implement method {@link Lock#unlock}.
 1253        *
 1254        * @param arg the release argument.  This value is conveyed to
 1255        *        {@link #tryRelease} but is otherwise uninterpreted and
 1256        *        can represent anything you like.
 1257        * @return the value returned from {@link #tryRelease}
 1258        */
 1259       public final boolean release(int arg) {
 1260           if (tryRelease(arg)) {
 1261               Node h = head;
 1262               if (h != null && h.waitStatus != 0)
 1263                   unparkSuccessor(h);
 1264               return true;
 1265           }
 1266           return false;
 1267       }
 1268   
 1269       /**
 1270        * Acquires in shared mode, ignoring interrupts.  Implemented by
 1271        * first invoking at least once {@link #tryAcquireShared},
 1272        * returning on success.  Otherwise the thread is queued, possibly
 1273        * repeatedly blocking and unblocking, invoking {@link
 1274        * #tryAcquireShared} until success.
 1275        *
 1276        * @param arg the acquire argument.  This value is conveyed to
 1277        *        {@link #tryAcquireShared} but is otherwise uninterpreted
 1278        *        and can represent anything you like.
 1279        */
 1280       public final void acquireShared(int arg) {
 1281           if (tryAcquireShared(arg) < 0)
 1282               doAcquireShared(arg);
 1283       }
 1284   
 1285       /**
 1286        * Acquires in shared mode, aborting if interrupted.  Implemented
 1287        * by first checking interrupt status, then invoking at least once
 1288        * {@link #tryAcquireShared}, returning on success.  Otherwise the
 1289        * thread is queued, possibly repeatedly blocking and unblocking,
 1290        * invoking {@link #tryAcquireShared} until success or the thread
 1291        * is interrupted.
 1292        * @param arg the acquire argument
 1293        * This value is conveyed to {@link #tryAcquireShared} but is
 1294        * otherwise uninterpreted and can represent anything
 1295        * you like.
 1296        * @throws InterruptedException if the current thread is interrupted
 1297        */
 1298       public final void acquireSharedInterruptibly(int arg)
 1299               throws InterruptedException {
 1300           if (Thread.interrupted())
 1301               throw new InterruptedException();
 1302           if (tryAcquireShared(arg) < 0)
 1303               doAcquireSharedInterruptibly(arg);
 1304       }
 1305   
 1306       /**
 1307        * Attempts to acquire in shared mode, aborting if interrupted, and
 1308        * failing if the given timeout elapses.  Implemented by first
 1309        * checking interrupt status, then invoking at least once {@link
 1310        * #tryAcquireShared}, returning on success.  Otherwise, the
 1311        * thread is queued, possibly repeatedly blocking and unblocking,
 1312        * invoking {@link #tryAcquireShared} until success or the thread
 1313        * is interrupted or the timeout elapses.
 1314        *
 1315        * @param arg the acquire argument.  This value is conveyed to
 1316        *        {@link #tryAcquireShared} but is otherwise uninterpreted
 1317        *        and can represent anything you like.
 1318        * @param nanosTimeout the maximum number of nanoseconds to wait
 1319        * @return {@code true} if acquired; {@code false} if timed out
 1320        * @throws InterruptedException if the current thread is interrupted
 1321        */
 1322       public final boolean tryAcquireSharedNanos(int arg, long nanosTimeout)
 1323               throws InterruptedException {
 1324           if (Thread.interrupted())
 1325               throw new InterruptedException();
 1326           return tryAcquireShared(arg) >= 0 ||
 1327               doAcquireSharedNanos(arg, nanosTimeout);
 1328       }
 1329   
 1330       /**
 1331        * Releases in shared mode.  Implemented by unblocking one or more
 1332        * threads if {@link #tryReleaseShared} returns true.
 1333        *
 1334        * @param arg the release argument.  This value is conveyed to
 1335        *        {@link #tryReleaseShared} but is otherwise uninterpreted
 1336        *        and can represent anything you like.
 1337        * @return the value returned from {@link #tryReleaseShared}
 1338        */
 1339       public final boolean releaseShared(int arg) {
 1340           if (tryReleaseShared(arg)) {
 1341               doReleaseShared();
 1342               return true;
 1343           }
 1344           return false;
 1345       }
 1346   
 1347       // Queue inspection methods
 1348   
 1349       /**
 1350        * Queries whether any threads are waiting to acquire. Note that
 1351        * because cancellations due to interrupts and timeouts may occur
 1352        * at any time, a {@code true} return does not guarantee that any
 1353        * other thread will ever acquire.
 1354        *
 1355        * <p>In this implementation, this operation returns in
 1356        * constant time.
 1357        *
 1358        * @return {@code true} if there may be other threads waiting to acquire
 1359        */
 1360       public final boolean hasQueuedThreads() {
 1361           return head != tail;
 1362       }
 1363   
 1364       /**
 1365        * Queries whether any threads have ever contended to acquire this
 1366        * synchronizer; that is if an acquire method has ever blocked.
 1367        *
 1368        * <p>In this implementation, this operation returns in
 1369        * constant time.
 1370        *
 1371        * @return {@code true} if there has ever been contention
 1372        */
 1373       public final boolean hasContended() {
 1374           return head != null;
 1375       }
 1376   
 1377       /**
 1378        * Returns the first (longest-waiting) thread in the queue, or
 1379        * {@code null} if no threads are currently queued.
 1380        *
 1381        * <p>In this implementation, this operation normally returns in
 1382        * constant time, but may iterate upon contention if other threads are
 1383        * concurrently modifying the queue.
 1384        *
 1385        * @return the first (longest-waiting) thread in the queue, or
 1386        *         {@code null} if no threads are currently queued
 1387        */
 1388       public final Thread getFirstQueuedThread() {
 1389           // handle only fast path, else relay
 1390           return (head == tail) ? null : fullGetFirstQueuedThread();
 1391       }
 1392   
 1393       /**
 1394        * Version of getFirstQueuedThread called when fastpath fails
 1395        */
 1396       private Thread fullGetFirstQueuedThread() {
 1397           /*
 1398            * The first node is normally head.next. Try to get its
 1399            * thread field, ensuring consistent reads: If thread
 1400            * field is nulled out or s.prev is no longer head, then
 1401            * some other thread(s) concurrently performed setHead in
 1402            * between some of our reads. We try this twice before
 1403            * resorting to traversal.
 1404            */
 1405           Node h, s;
 1406           Thread st;
 1407           if (((h = head) != null && (s = h.next) != null &&
 1408                s.prev == head && (st = s.thread) != null) ||
 1409               ((h = head) != null && (s = h.next) != null &&
 1410                s.prev == head && (st = s.thread) != null))
 1411               return st;
 1412   
 1413           /*
 1414            * Head's next field might not have been set yet, or may have
 1415            * been unset after setHead. So we must check to see if tail
 1416            * is actually first node. If not, we continue on, safely
 1417            * traversing from tail back to head to find first,
 1418            * guaranteeing termination.
 1419            */
 1420   
 1421           Node t = tail;
 1422           Thread firstThread = null;
 1423           while (t != null && t != head) {
 1424               Thread tt = t.thread;
 1425               if (tt != null)
 1426                   firstThread = tt;
 1427               t = t.prev;
 1428           }
 1429           return firstThread;
 1430       }
 1431   
 1432       /**
 1433        * Returns true if the given thread is currently queued.
 1434        *
 1435        * <p>This implementation traverses the queue to determine
 1436        * presence of the given thread.
 1437        *
 1438        * @param thread the thread
 1439        * @return {@code true} if the given thread is on the queue
 1440        * @throws NullPointerException if the thread is null
 1441        */
 1442       public final boolean isQueued(Thread thread) {
 1443           if (thread == null)
 1444               throw new NullPointerException();
 1445           for (Node p = tail; p != null; p = p.prev)
 1446               if (p.thread == thread)
 1447                   return true;
 1448           return false;
 1449       }
 1450   
 1451       /**
 1452        * Returns {@code true} if the apparent first queued thread, if one
 1453        * exists, is waiting in exclusive mode.  If this method returns
 1454        * {@code true}, and the current thread is attempting to acquire in
 1455        * shared mode (that is, this method is invoked from {@link
 1456        * #tryAcquireShared}) then it is guaranteed that the current thread
 1457        * is not the first queued thread.  Used only as a heuristic in
 1458        * ReentrantReadWriteLock.
 1459        */
 1460       final boolean apparentlyFirstQueuedIsExclusive() {
 1461           Node h, s;
 1462           return (h = head) != null &&
 1463               (s = h.next)  != null &&
 1464               !s.isShared()         &&
 1465               s.thread != null;
 1466       }
 1467   
 1468       /**
 1469        * Queries whether any threads have been waiting to acquire longer
 1470        * than the current thread.
 1471        *
 1472        * <p>An invocation of this method is equivalent to (but may be
 1473        * more efficient than):
 1474        *  <pre> {@code
 1475        * getFirstQueuedThread() != Thread.currentThread() &&
 1476        * hasQueuedThreads()}</pre>
 1477        *
 1478        * <p>Note that because cancellations due to interrupts and
 1479        * timeouts may occur at any time, a {@code true} return does not
 1480        * guarantee that some other thread will acquire before the current
 1481        * thread.  Likewise, it is possible for another thread to win a
 1482        * race to enqueue after this method has returned {@code false},
 1483        * due to the queue being empty.
 1484        *
 1485        * <p>This method is designed to be used by a fair synchronizer to
 1486        * avoid <a href="AbstractQueuedSynchronizer#barging">barging</a>.
 1487        * Such a synchronizer's {@link #tryAcquire} method should return
 1488        * {@code false}, and its {@link #tryAcquireShared} method should
 1489        * return a negative value, if this method returns {@code true}
 1490        * (unless this is a reentrant acquire).  For example, the {@code
 1491        * tryAcquire} method for a fair, reentrant, exclusive mode
 1492        * synchronizer might look like this:
 1493        *
 1494        *  <pre> {@code
 1495        * protected boolean tryAcquire(int arg) {
 1496        *   if (isHeldExclusively()) {
 1497        *     // A reentrant acquire; increment hold count
 1498        *     return true;
 1499        *   } else if (hasQueuedPredecessors()) {
 1500        *     return false;
 1501        *   } else {
 1502        *     // try to acquire normally
 1503        *   }
 1504        * }}</pre>
 1505        *
 1506        * @return {@code true} if there is a queued thread preceding the
 1507        *         current thread, and {@code false} if the current thread
 1508        *         is at the head of the queue or the queue is empty
 1509        * @since 1.7
 1510        */
 1511       public final boolean hasQueuedPredecessors() {
 1512           // The correctness of this depends on head being initialized
 1513           // before tail and on head.next being accurate if the current
 1514           // thread is first in queue.
 1515           Node t = tail; // Read fields in reverse initialization order
 1516           Node h = head;
 1517           Node s;
 1518           return h != t &&
 1519               ((s = h.next) == null || s.thread != Thread.currentThread());
 1520       }
 1521   
 1522   
 1523       // Instrumentation and monitoring methods
 1524   
 1525       /**
 1526        * Returns an estimate of the number of threads waiting to
 1527        * acquire.  The value is only an estimate because the number of
 1528        * threads may change dynamically while this method traverses
 1529        * internal data structures.  This method is designed for use in
 1530        * monitoring system state, not for synchronization
 1531        * control.
 1532        *
 1533        * @return the estimated number of threads waiting to acquire
 1534        */
 1535       public final int getQueueLength() {
 1536           int n = 0;
 1537           for (Node p = tail; p != null; p = p.prev) {
 1538               if (p.thread != null)
 1539                   ++n;
 1540           }
 1541           return n;
 1542       }
 1543   
 1544       /**
 1545        * Returns a collection containing threads that may be waiting to
 1546        * acquire.  Because the actual set of threads may change
 1547        * dynamically while constructing this result, the returned
 1548        * collection is only a best-effort estimate.  The elements of the
 1549        * returned collection are in no particular order.  This method is
 1550        * designed to facilitate construction of subclasses that provide
 1551        * more extensive monitoring facilities.
 1552        *
 1553        * @return the collection of threads
 1554        */
 1555       public final Collection<Thread> getQueuedThreads() {
 1556           ArrayList<Thread> list = new ArrayList<Thread>();
 1557           for (Node p = tail; p != null; p = p.prev) {
 1558               Thread t = p.thread;
 1559               if (t != null)
 1560                   list.add(t);
 1561           }
 1562           return list;
 1563       }
 1564   
 1565       /**
 1566        * Returns a collection containing threads that may be waiting to
 1567        * acquire in exclusive mode. This has the same properties
 1568        * as {@link #getQueuedThreads} except that it only returns
 1569        * those threads waiting due to an exclusive acquire.
 1570        *
 1571        * @return the collection of threads
 1572        */
 1573       public final Collection<Thread> getExclusiveQueuedThreads() {
 1574           ArrayList<Thread> list = new ArrayList<Thread>();
 1575           for (Node p = tail; p != null; p = p.prev) {
 1576               if (!p.isShared()) {
 1577                   Thread t = p.thread;
 1578                   if (t != null)
 1579                       list.add(t);
 1580               }
 1581           }
 1582           return list;
 1583       }
 1584   
 1585       /**
 1586        * Returns a collection containing threads that may be waiting to
 1587        * acquire in shared mode. This has the same properties
 1588        * as {@link #getQueuedThreads} except that it only returns
 1589        * those threads waiting due to a shared acquire.
 1590        *
 1591        * @return the collection of threads
 1592        */
 1593       public final Collection<Thread> getSharedQueuedThreads() {
 1594           ArrayList<Thread> list = new ArrayList<Thread>();
 1595           for (Node p = tail; p != null; p = p.prev) {
 1596               if (p.isShared()) {
 1597                   Thread t = p.thread;
 1598                   if (t != null)
 1599                       list.add(t);
 1600               }
 1601           }
 1602           return list;
 1603       }
 1604   
 1605       /**
 1606        * Returns a string identifying this synchronizer, as well as its state.
 1607        * The state, in brackets, includes the String {@code "State ="}
 1608        * followed by the current value of {@link #getState}, and either
 1609        * {@code "nonempty"} or {@code "empty"} depending on whether the
 1610        * queue is empty.
 1611        *
 1612        * @return a string identifying this synchronizer, as well as its state
 1613        */
 1614       public String toString() {
 1615           int s = getState();
 1616           String q  = hasQueuedThreads() ? "non" : "";
 1617           return super.toString() +
 1618               "[State = " + s + ", " + q + "empty queue]";
 1619       }
 1620   
 1621   
 1622       // Internal support methods for Conditions
 1623   
 1624       /**
 1625        * Returns true if a node, always one that was initially placed on
 1626        * a condition queue, is now waiting to reacquire on sync queue.
 1627        * @param node the node
 1628        * @return true if is reacquiring
 1629        */
 1630       final boolean isOnSyncQueue(Node node) {
 1631           if (node.waitStatus == Node.CONDITION || node.prev == null)
 1632               return false;
 1633           if (node.next != null) // If has successor, it must be on queue
 1634               return true;
 1635           /*
 1636            * node.prev can be non-null, but not yet on queue because
 1637            * the CAS to place it on queue can fail. So we have to
 1638            * traverse from tail to make sure it actually made it.  It
 1639            * will always be near the tail in calls to this method, and
 1640            * unless the CAS failed (which is unlikely), it will be
 1641            * there, so we hardly ever traverse much.
 1642            */
 1643           return findNodeFromTail(node);
 1644       }
 1645   
 1646       /**
 1647        * Returns true if node is on sync queue by searching backwards from tail.
 1648        * Called only when needed by isOnSyncQueue.
 1649        * @return true if present
 1650        */
 1651       private boolean findNodeFromTail(Node node) {
 1652           Node t = tail;
 1653           for (;;) {
 1654               if (t == node)
 1655                   return true;
 1656               if (t == null)
 1657                   return false;
 1658               t = t.prev;
 1659           }
 1660       }
 1661   
 1662       /**
 1663        * Transfers a node from a condition queue onto sync queue.
 1664        * Returns true if successful.
 1665        * @param node the node
 1666        * @return true if successfully transferred (else the node was
 1667        * cancelled before signal).
 1668        */
 1669       final boolean transferForSignal(Node node) {
 1670           /*
 1671            * If cannot change waitStatus, the node has been cancelled.
 1672            */
 1673           if (!compareAndSetWaitStatus(node, Node.CONDITION, 0))
 1674               return false;
 1675   
 1676           /*
 1677            * Splice onto queue and try to set waitStatus of predecessor to
 1678            * indicate that thread is (probably) waiting. If cancelled or
 1679            * attempt to set waitStatus fails, wake up to resync (in which
 1680            * case the waitStatus can be transiently and harmlessly wrong).
 1681            */
 1682           Node p = enq(node);
 1683           int ws = p.waitStatus;
 1684           if (ws > 0 || !compareAndSetWaitStatus(p, ws, Node.SIGNAL))
 1685               LockSupport.unpark(node.thread);
 1686           return true;
 1687       }
 1688   
 1689       /**
 1690        * Transfers node, if necessary, to sync queue after a cancelled
 1691        * wait. Returns true if thread was cancelled before being
 1692        * signalled.
 1693        * @param current the waiting thread
 1694        * @param node its node
 1695        * @return true if cancelled before the node was signalled
 1696        */
 1697       final boolean transferAfterCancelledWait(Node node) {
 1698           if (compareAndSetWaitStatus(node, Node.CONDITION, 0)) {
 1699               enq(node);
 1700               return true;
 1701           }
 1702           /*
 1703            * If we lost out to a signal(), then we can't proceed
 1704            * until it finishes its enq().  Cancelling during an
 1705            * incomplete transfer is both rare and transient, so just
 1706            * spin.
 1707            */
 1708           while (!isOnSyncQueue(node))
 1709               Thread.yield();
 1710           return false;
 1711       }
 1712   
 1713       /**
 1714        * Invokes release with current state value; returns saved state.
 1715        * Cancels node and throws exception on failure.
 1716        * @param node the condition node for this wait
 1717        * @return previous sync state
 1718        */
 1719       final int fullyRelease(Node node) {
 1720           boolean failed = true;
 1721           try {
 1722               int savedState = getState();
 1723               if (release(savedState)) {
 1724                   failed = false;
 1725                   return savedState;
 1726               } else {
 1727                   throw new IllegalMonitorStateException();
 1728               }
 1729           } finally {
 1730               if (failed)
 1731                   node.waitStatus = Node.CANCELLED;
 1732           }
 1733       }
 1734   
 1735       // Instrumentation methods for conditions
 1736   
 1737       /**
 1738        * Queries whether the given ConditionObject
 1739        * uses this synchronizer as its lock.
 1740        *
 1741        * @param condition the condition
 1742        * @return <tt>true</tt> if owned
 1743        * @throws NullPointerException if the condition is null
 1744        */
 1745       public final boolean owns(ConditionObject condition) {
 1746           if (condition == null)
 1747               throw new NullPointerException();
 1748           return condition.isOwnedBy(this);
 1749       }
 1750   
 1751       /**
 1752        * Queries whether any threads are waiting on the given condition
 1753        * associated with this synchronizer. Note that because timeouts
 1754        * and interrupts may occur at any time, a <tt>true</tt> return
 1755        * does not guarantee that a future <tt>signal</tt> will awaken
 1756        * any threads.  This method is designed primarily for use in
 1757        * monitoring of the system state.
 1758        *
 1759        * @param condition the condition
 1760        * @return <tt>true</tt> if there are any waiting threads
 1761        * @throws IllegalMonitorStateException if exclusive synchronization
 1762        *         is not held
 1763        * @throws IllegalArgumentException if the given condition is
 1764        *         not associated with this synchronizer
 1765        * @throws NullPointerException if the condition is null
 1766        */
 1767       public final boolean hasWaiters(ConditionObject condition) {
 1768           if (!owns(condition))
 1769               throw new IllegalArgumentException("Not owner");
 1770           return condition.hasWaiters();
 1771       }
 1772   
 1773       /**
 1774        * Returns an estimate of the number of threads waiting on the
 1775        * given condition associated with this synchronizer. Note that
 1776        * because timeouts and interrupts may occur at any time, the
 1777        * estimate serves only as an upper bound on the actual number of
 1778        * waiters.  This method is designed for use in monitoring of the
 1779        * system state, not for synchronization control.
 1780        *
 1781        * @param condition the condition
 1782        * @return the estimated number of waiting threads
 1783        * @throws IllegalMonitorStateException if exclusive synchronization
 1784        *         is not held
 1785        * @throws IllegalArgumentException if the given condition is
 1786        *         not associated with this synchronizer
 1787        * @throws NullPointerException if the condition is null
 1788        */
 1789       public final int getWaitQueueLength(ConditionObject condition) {
 1790           if (!owns(condition))
 1791               throw new IllegalArgumentException("Not owner");
 1792           return condition.getWaitQueueLength();
 1793       }
 1794   
 1795       /**
 1796        * Returns a collection containing those threads that may be
 1797        * waiting on the given condition associated with this
 1798        * synchronizer.  Because the actual set of threads may change
 1799        * dynamically while constructing this result, the returned
 1800        * collection is only a best-effort estimate. The elements of the
 1801        * returned collection are in no particular order.
 1802        *
 1803        * @param condition the condition
 1804        * @return the collection of threads
 1805        * @throws IllegalMonitorStateException if exclusive synchronization
 1806        *         is not held
 1807        * @throws IllegalArgumentException if the given condition is
 1808        *         not associated with this synchronizer
 1809        * @throws NullPointerException if the condition is null
 1810        */
 1811       public final Collection<Thread> getWaitingThreads(ConditionObject condition) {
 1812           if (!owns(condition))
 1813               throw new IllegalArgumentException("Not owner");
 1814           return condition.getWaitingThreads();
 1815       }
 1816   
 1817       /**
 1818        * Condition implementation for a {@link
 1819        * AbstractQueuedSynchronizer} serving as the basis of a {@link
 1820        * Lock} implementation.
 1821        *
 1822        * <p>Method documentation for this class describes mechanics,
 1823        * not behavioral specifications from the point of view of Lock
 1824        * and Condition users. Exported versions of this class will in
 1825        * general need to be accompanied by documentation describing
 1826        * condition semantics that rely on those of the associated
 1827        * <tt>AbstractQueuedSynchronizer</tt>.
 1828        *
 1829        * <p>This class is Serializable, but all fields are transient,
 1830        * so deserialized conditions have no waiters.
 1831        */
 1832       public class ConditionObject implements Condition, java.io.Serializable {
 1833           private static final long serialVersionUID = 1173984872572414699L;
 1834           /** First node of condition queue. */
 1835           private transient Node firstWaiter;
 1836           /** Last node of condition queue. */
 1837           private transient Node lastWaiter;
 1838   
 1839           /**
 1840            * Creates a new <tt>ConditionObject</tt> instance.
 1841            */
 1842           public ConditionObject() { }
 1843   
 1844           // Internal methods
 1845   
 1846           /**
 1847            * Adds a new waiter to wait queue.
 1848            * @return its new wait node
 1849            */
 1850           private Node addConditionWaiter() {
 1851               Node t = lastWaiter;
 1852               // If lastWaiter is cancelled, clean out.
 1853               if (t != null && t.waitStatus != Node.CONDITION) {
 1854                   unlinkCancelledWaiters();
 1855                   t = lastWaiter;
 1856               }
 1857               Node node = new Node(Thread.currentThread(), Node.CONDITION);
 1858               if (t == null)
 1859                   firstWaiter = node;
 1860               else
 1861                   t.nextWaiter = node;
 1862               lastWaiter = node;
 1863               return node;
 1864           }
 1865   
 1866           /**
 1867            * Removes and transfers nodes until hit non-cancelled one or
 1868            * null. Split out from signal in part to encourage compilers
 1869            * to inline the case of no waiters.
 1870            * @param first (non-null) the first node on condition queue
 1871            */
 1872           private void doSignal(Node first) {
 1873               do {
 1874                   if ( (firstWaiter = first.nextWaiter) == null)
 1875                       lastWaiter = null;
 1876                   first.nextWaiter = null;
 1877               } while (!transferForSignal(first) &&
 1878                        (first = firstWaiter) != null);
 1879           }
 1880   
 1881           /**
 1882            * Removes and transfers all nodes.
 1883            * @param first (non-null) the first node on condition queue
 1884            */
 1885           private void doSignalAll(Node first) {
 1886               lastWaiter = firstWaiter = null;
 1887               do {
 1888                   Node next = first.nextWaiter;
 1889                   first.nextWaiter = null;
 1890                   transferForSignal(first);
 1891                   first = next;
 1892               } while (first != null);
 1893           }
 1894   
 1895           /**
 1896            * Unlinks cancelled waiter nodes from condition queue.
 1897            * Called only while holding lock. This is called when
 1898            * cancellation occurred during condition wait, and upon
 1899            * insertion of a new waiter when lastWaiter is seen to have
 1900            * been cancelled. This method is needed to avoid garbage
 1901            * retention in the absence of signals. So even though it may
 1902            * require a full traversal, it comes into play only when
 1903            * timeouts or cancellations occur in the absence of
 1904            * signals. It traverses all nodes rather than stopping at a
 1905            * particular target to unlink all pointers to garbage nodes
 1906            * without requiring many re-traversals during cancellation
 1907            * storms.
 1908            */
 1909           private void unlinkCancelledWaiters() {
 1910               Node t = firstWaiter;
 1911               Node trail = null;
 1912               while (t != null) {
 1913                   Node next = t.nextWaiter;
 1914                   if (t.waitStatus != Node.CONDITION) {
 1915                       t.nextWaiter = null;
 1916                       if (trail == null)
 1917                           firstWaiter = next;
 1918                       else
 1919                           trail.nextWaiter = next;
 1920                       if (next == null)
 1921                           lastWaiter = trail;
 1922                   }
 1923                   else
 1924                       trail = t;
 1925                   t = next;
 1926               }
 1927           }
 1928   
 1929           // public methods
 1930   
 1931           /**
 1932            * Moves the longest-waiting thread, if one exists, from the
 1933            * wait queue for this condition to the wait queue for the
 1934            * owning lock.
 1935            *
 1936            * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
 1937            *         returns {@code false}
 1938            */
 1939           public final void signal() {
 1940               if (!isHeldExclusively())
 1941                   throw new IllegalMonitorStateException();
 1942               Node first = firstWaiter;
 1943               if (first != null)
 1944                   doSignal(first);
 1945           }
 1946   
 1947           /**
 1948            * Moves all threads from the wait queue for this condition to
 1949            * the wait queue for the owning lock.
 1950            *
 1951            * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
 1952            *         returns {@code false}
 1953            */
 1954           public final void signalAll() {
 1955               if (!isHeldExclusively())
 1956                   throw new IllegalMonitorStateException();
 1957               Node first = firstWaiter;
 1958               if (first != null)
 1959                   doSignalAll(first);
 1960           }
 1961   
 1962           /**
 1963            * Implements uninterruptible condition wait.
 1964            * <ol>
 1965            * <li> Save lock state returned by {@link #getState}.
 1966            * <li> Invoke {@link #release} with
 1967            *      saved state as argument, throwing
 1968            *      IllegalMonitorStateException if it fails.
 1969            * <li> Block until signalled.
 1970            * <li> Reacquire by invoking specialized version of
 1971            *      {@link #acquire} with saved state as argument.
 1972            * </ol>
 1973            */
 1974           public final void awaitUninterruptibly() {
 1975               Node node = addConditionWaiter();
 1976               int savedState = fullyRelease(node);
 1977               boolean interrupted = false;
 1978               while (!isOnSyncQueue(node)) {
 1979                   LockSupport.park(this);
 1980                   if (Thread.interrupted())
 1981                       interrupted = true;
 1982               }
 1983               if (acquireQueued(node, savedState) || interrupted)
 1984                   selfInterrupt();
 1985           }
 1986   
 1987           /*
 1988            * For interruptible waits, we need to track whether to throw
 1989            * InterruptedException, if interrupted while blocked on
 1990            * condition, versus reinterrupt current thread, if
 1991            * interrupted while blocked waiting to re-acquire.
 1992            */
 1993   
 1994           /** Mode meaning to reinterrupt on exit from wait */
 1995           private static final int REINTERRUPT =  1;
 1996           /** Mode meaning to throw InterruptedException on exit from wait */
 1997           private static final int THROW_IE    = -1;
 1998   
 1999           /**
 2000            * Checks for interrupt, returning THROW_IE if interrupted
 2001            * before signalled, REINTERRUPT if after signalled, or
 2002            * 0 if not interrupted.
 2003            */
 2004           private int checkInterruptWhileWaiting(Node node) {
 2005               return Thread.interrupted() ?
 2006                   (transferAfterCancelledWait(node) ? THROW_IE : REINTERRUPT) :
 2007                   0;
 2008           }
 2009   
 2010           /**
 2011            * Throws InterruptedException, reinterrupts current thread, or
 2012            * does nothing, depending on mode.
 2013            */
 2014           private void reportInterruptAfterWait(int interruptMode)
 2015               throws InterruptedException {
 2016               if (interruptMode == THROW_IE)
 2017                   throw new InterruptedException();
 2018               else if (interruptMode == REINTERRUPT)
 2019                   selfInterrupt();
 2020           }
 2021   
 2022           /**
 2023            * Implements interruptible condition wait.
 2024            * <ol>
 2025            * <li> If current thread is interrupted, throw InterruptedException.
 2026            * <li> Save lock state returned by {@link #getState}.
 2027            * <li> Invoke {@link #release} with
 2028            *      saved state as argument, throwing
 2029            *      IllegalMonitorStateException if it fails.
 2030            * <li> Block until signalled or interrupted.
 2031            * <li> Reacquire by invoking specialized version of
 2032            *      {@link #acquire} with saved state as argument.
 2033            * <li> If interrupted while blocked in step 4, throw InterruptedException.
 2034            * </ol>
 2035            */
 2036           public final void await() throws InterruptedException {
 2037               if (Thread.interrupted())
 2038                   throw new InterruptedException();
 2039               Node node = addConditionWaiter();
 2040               int savedState = fullyRelease(node);
 2041               int interruptMode = 0;
 2042               while (!isOnSyncQueue(node)) {
 2043                   LockSupport.park(this);
 2044                   if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
 2045                       break;
 2046               }
 2047               if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
 2048                   interruptMode = REINTERRUPT;
 2049               if (node.nextWaiter != null) // clean up if cancelled
 2050                   unlinkCancelledWaiters();
 2051               if (interruptMode != 0)
 2052                   reportInterruptAfterWait(interruptMode);
 2053           }
 2054   
 2055           /**
 2056            * Implements timed condition wait.
 2057            * <ol>
 2058            * <li> If current thread is interrupted, throw InterruptedException.
 2059            * <li> Save lock state returned by {@link #getState}.
 2060            * <li> Invoke {@link #release} with
 2061            *      saved state as argument, throwing
 2062            *      IllegalMonitorStateException if it fails.
 2063            * <li> Block until signalled, interrupted, or timed out.
 2064            * <li> Reacquire by invoking specialized version of
 2065            *      {@link #acquire} with saved state as argument.
 2066            * <li> If interrupted while blocked in step 4, throw InterruptedException.
 2067            * </ol>
 2068            */
 2069           public final long awaitNanos(long nanosTimeout)
 2070                   throws InterruptedException {
 2071               if (Thread.interrupted())
 2072                   throw new InterruptedException();
 2073               Node node = addConditionWaiter();
 2074               int savedState = fullyRelease(node);
 2075               long lastTime = System.nanoTime();
 2076               int interruptMode = 0;
 2077               while (!isOnSyncQueue(node)) {
 2078                   if (nanosTimeout <= 0L) {
 2079                       transferAfterCancelledWait(node);
 2080                       break;
 2081                   }
 2082                   LockSupport.parkNanos(this, nanosTimeout);
 2083                   if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
 2084                       break;
 2085   
 2086                   long now = System.nanoTime();
 2087                   nanosTimeout -= now - lastTime;
 2088                   lastTime = now;
 2089               }
 2090               if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
 2091                   interruptMode = REINTERRUPT;
 2092               if (node.nextWaiter != null)
 2093                   unlinkCancelledWaiters();
 2094               if (interruptMode != 0)
 2095                   reportInterruptAfterWait(interruptMode);
 2096               return nanosTimeout - (System.nanoTime() - lastTime);
 2097           }
 2098   
 2099           /**
 2100            * Implements absolute timed condition wait.
 2101            * <ol>
 2102            * <li> If current thread is interrupted, throw InterruptedException.
 2103            * <li> Save lock state returned by {@link #getState}.
 2104            * <li> Invoke {@link #release} with
 2105            *      saved state as argument, throwing
 2106            *      IllegalMonitorStateException if it fails.
 2107            * <li> Block until signalled, interrupted, or timed out.
 2108            * <li> Reacquire by invoking specialized version of
 2109            *      {@link #acquire} with saved state as argument.
 2110            * <li> If interrupted while blocked in step 4, throw InterruptedException.
 2111            * <li> If timed out while blocked in step 4, return false, else true.
 2112            * </ol>
 2113            */
 2114           public final boolean awaitUntil(Date deadline)
 2115                   throws InterruptedException {
 2116               if (deadline == null)
 2117                   throw new NullPointerException();
 2118               long abstime = deadline.getTime();
 2119               if (Thread.interrupted())
 2120                   throw new InterruptedException();
 2121               Node node = addConditionWaiter();
 2122               int savedState = fullyRelease(node);
 2123               boolean timedout = false;
 2124               int interruptMode = 0;
 2125               while (!isOnSyncQueue(node)) {
 2126                   if (System.currentTimeMillis() > abstime) {
 2127                       timedout = transferAfterCancelledWait(node);
 2128                       break;
 2129                   }
 2130                   LockSupport.parkUntil(this, abstime);
 2131                   if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
 2132                       break;
 2133               }
 2134               if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
 2135                   interruptMode = REINTERRUPT;
 2136               if (node.nextWaiter != null)
 2137                   unlinkCancelledWaiters();
 2138               if (interruptMode != 0)
 2139                   reportInterruptAfterWait(interruptMode);
 2140               return !timedout;
 2141           }
 2142   
 2143           /**
 2144            * Implements timed condition wait.
 2145            * <ol>
 2146            * <li> If current thread is interrupted, throw InterruptedException.
 2147            * <li> Save lock state returned by {@link #getState}.
 2148            * <li> Invoke {@link #release} with
 2149            *      saved state as argument, throwing
 2150            *      IllegalMonitorStateException if it fails.
 2151            * <li> Block until signalled, interrupted, or timed out.
 2152            * <li> Reacquire by invoking specialized version of
 2153            *      {@link #acquire} with saved state as argument.
 2154            * <li> If interrupted while blocked in step 4, throw InterruptedException.
 2155            * <li> If timed out while blocked in step 4, return false, else true.
 2156            * </ol>
 2157            */
 2158           public final boolean await(long time, TimeUnit unit)
 2159                   throws InterruptedException {
 2160               if (unit == null)
 2161                   throw new NullPointerException();
 2162               long nanosTimeout = unit.toNanos(time);
 2163               if (Thread.interrupted())
 2164                   throw new InterruptedException();
 2165               Node node = addConditionWaiter();
 2166               int savedState = fullyRelease(node);
 2167               long lastTime = System.nanoTime();
 2168               boolean timedout = false;
 2169               int interruptMode = 0;
 2170               while (!isOnSyncQueue(node)) {
 2171                   if (nanosTimeout <= 0L) {
 2172                       timedout = transferAfterCancelledWait(node);
 2173                       break;
 2174                   }
 2175                   if (nanosTimeout >= spinForTimeoutThreshold)
 2176                       LockSupport.parkNanos(this, nanosTimeout);
 2177                   if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
 2178                       break;
 2179                   long now = System.nanoTime();
 2180                   nanosTimeout -= now - lastTime;
 2181                   lastTime = now;
 2182               }
 2183               if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
 2184                   interruptMode = REINTERRUPT;
 2185               if (node.nextWaiter != null)
 2186                   unlinkCancelledWaiters();
 2187               if (interruptMode != 0)
 2188                   reportInterruptAfterWait(interruptMode);
 2189               return !timedout;
 2190           }
 2191   
 2192           //  support for instrumentation
 2193   
 2194           /**
 2195            * Returns true if this condition was created by the given
 2196            * synchronization object.
 2197            *
 2198            * @return {@code true} if owned
 2199            */
 2200           final boolean isOwnedBy(AbstractQueuedSynchronizer sync) {
 2201               return sync == AbstractQueuedSynchronizer.this;
 2202           }
 2203   
 2204           /**
 2205            * Queries whether any threads are waiting on this condition.
 2206            * Implements {@link AbstractQueuedSynchronizer#hasWaiters}.
 2207            *
 2208            * @return {@code true} if there are any waiting threads
 2209            * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
 2210            *         returns {@code false}
 2211            */
 2212           protected final boolean hasWaiters() {
 2213               if (!isHeldExclusively())
 2214                   throw new IllegalMonitorStateException();
 2215               for (Node w = firstWaiter; w != null; w = w.nextWaiter) {
 2216                   if (w.waitStatus == Node.CONDITION)
 2217                       return true;
 2218               }
 2219               return false;
 2220           }
 2221   
 2222           /**
 2223            * Returns an estimate of the number of threads waiting on
 2224            * this condition.
 2225            * Implements {@link AbstractQueuedSynchronizer#getWaitQueueLength}.
 2226            *
 2227            * @return the estimated number of waiting threads
 2228            * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
 2229            *         returns {@code false}
 2230            */
 2231           protected final int getWaitQueueLength() {
 2232               if (!isHeldExclusively())
 2233                   throw new IllegalMonitorStateException();
 2234               int n = 0;
 2235               for (Node w = firstWaiter; w != null; w = w.nextWaiter) {
 2236                   if (w.waitStatus == Node.CONDITION)
 2237                       ++n;
 2238               }
 2239               return n;
 2240           }
 2241   
 2242           /**
 2243            * Returns a collection containing those threads that may be
 2244            * waiting on this Condition.
 2245            * Implements {@link AbstractQueuedSynchronizer#getWaitingThreads}.
 2246            *
 2247            * @return the collection of threads
 2248            * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
 2249            *         returns {@code false}
 2250            */
 2251           protected final Collection<Thread> getWaitingThreads() {
 2252               if (!isHeldExclusively())
 2253                   throw new IllegalMonitorStateException();
 2254               ArrayList<Thread> list = new ArrayList<Thread>();
 2255               for (Node w = firstWaiter; w != null; w = w.nextWaiter) {
 2256                   if (w.waitStatus == Node.CONDITION) {
 2257                       Thread t = w.thread;
 2258                       if (t != null)
 2259                           list.add(t);
 2260                   }
 2261               }
 2262               return list;
 2263           }
 2264       }
 2265   
 2266       /**
 2267        * Setup to support compareAndSet. We need to natively implement
 2268        * this here: For the sake of permitting future enhancements, we
 2269        * cannot explicitly subclass AtomicInteger, which would be
 2270        * efficient and useful otherwise. So, as the lesser of evils, we
 2271        * natively implement using hotspot intrinsics API. And while we
 2272        * are at it, we do the same for other CASable fields (which could
 2273        * otherwise be done with atomic field updaters).
 2274        */
 2275       private static final Unsafe unsafe = Unsafe.getUnsafe();
 2276       private static final long stateOffset;
 2277       private static final long headOffset;
 2278       private static final long tailOffset;
 2279       private static final long waitStatusOffset;
 2280       private static final long nextOffset;
 2281   
 2282       static {
 2283           try {
 2284               stateOffset = unsafe.objectFieldOffset
 2285                   (AbstractQueuedSynchronizer.class.getDeclaredField("state"));
 2286               headOffset = unsafe.objectFieldOffset
 2287                   (AbstractQueuedSynchronizer.class.getDeclaredField("head"));
 2288               tailOffset = unsafe.objectFieldOffset
 2289                   (AbstractQueuedSynchronizer.class.getDeclaredField("tail"));
 2290               waitStatusOffset = unsafe.objectFieldOffset
 2291                   (Node.class.getDeclaredField("waitStatus"));
 2292               nextOffset = unsafe.objectFieldOffset
 2293                   (Node.class.getDeclaredField("next"));
 2294   
 2295           } catch (Exception ex) { throw new Error(ex); }
 2296       }
 2297   
 2298       /**
 2299        * CAS head field. Used only by enq.
 2300        */
 2301       private final boolean compareAndSetHead(Node update) {
 2302           return unsafe.compareAndSwapObject(this, headOffset, null, update);
 2303       }
 2304   
 2305       /**
 2306        * CAS tail field. Used only by enq.
 2307        */
 2308       private final boolean compareAndSetTail(Node expect, Node update) {
 2309           return unsafe.compareAndSwapObject(this, tailOffset, expect, update);
 2310       }
 2311   
 2312       /**
 2313        * CAS waitStatus field of a node.
 2314        */
 2315       private static final boolean compareAndSetWaitStatus(Node node,
 2316                                                            int expect,
 2317                                                            int update) {
 2318           return unsafe.compareAndSwapInt(node, waitStatusOffset,
 2319                                           expect, update);
 2320       }
 2321   
 2322       /**
 2323        * CAS next field of a node.
 2324        */
 2325       private static final boolean compareAndSetNext(Node node,
 2326                                                      Node expect,
 2327                                                      Node update) {
 2328           return unsafe.compareAndSwapObject(node, nextOffset, expect, update);
 2329       }
 2330   }

Save This Page
Home » openjdk-7 » java » util » concurrent » locks » [javadoc | source]