Java多线程系列--“JUC锁”05之 非公平锁

1 /*
2 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
3 *
4 *
5 *
6 *
7 *
8 *
9 *
10 *
11 *
12 *
13 *
14 *
15 *
16 *
17 *
18 *
19 *
20 *
21 *
22 *
23  */
24 
25 /*
26 *
27 *
28 *
29 *
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 packagejava.util.concurrent.locks;
37 import java.util.*;
38 import java.util.concurrent.*;
39 import java.util.concurrent.atomic.*;
40 
41 /**
42 * A reentrant mutual exclusion {@linkLock} with the same basic
43 * behavior and semantics as the implicit monitor lock accessed using
44 * {@codesynchronized} methods and statements, but with extended
45 * capabilities.
46 *
47 * <p>A {@codeReentrantLock} is <em>owned</em> by the thread last
48 * successfully locking, but not yet unlocking it. A thread invoking
49 * {@codelock} will return, successfully acquiring the lock, when
50 * the lock is not owned by another thread. The method will return
51 * immediately if the current thread already owns the lock. This can
52 * be checked using methods {@link#isHeldByCurrentThread}, and {@link
53 * #getHoldCount}.
54 *
55 * <p>The constructor for this class accepts an optional
56 * <em>fairness</em> parameter.  When set {@codetrue}, under
57 * contention, locks favor granting access to the longest-waiting
58 * thread.  Otherwise this lock does not guarantee any particular
59 * access order.  Programs using fair locks accessed by many threads
60 * may display lower overall throughput (i.e., are slower; often much
61 * slower) than those using the default setting, but have smaller
62 * variances in times to obtain locks and guarantee lack of
63 * starvation. Note however, that fairness of locks does not guarantee
64 * fairness of thread scheduling. Thus, one of many threads using a
65 * fair lock may obtain it multiple times in succession while other
66 * active threads are not progressing and not currently holding the
67 * lock.
68 * Also note that the untimed {@link#tryLock() tryLock} method does not
69 * honor the fairness setting. It will succeed if the lock
70 * is available even if other threads are waiting.
71 *
72 * <p>It is recommended practice to <em>always</em> immediately
73 * follow a call to {@codelock} with a {@codetry} block, most
74 * typically in a before/after construction such as:
75 *
76 * <pre>
77 * class X {
78 *   private final ReentrantLock lock = new ReentrantLock();
79 *   // ...
80 *
81 *   public void m() {
82 *     lock.lock();  // block until condition holds
83 *     try {
84 *       // ... method body
85 *     } finally {
86 *       lock.unlock()
87 *     }
88 *   }
89 * }
90 * </pre>
91 *
92 * <p>In addition to implementing the {@linkLock} interface, this
93 * class defines methods {@codeisLocked} and
94 * {@codegetLockQueueLength}, as well as some associated
95 * {@codeprotected} access methods that may be useful for
96 * instrumentation and monitoring.
97 *
98 * <p>Serialization of this class behaves in the same way as built-in
99 * locks: a deserialized lock is in the unlocked state, regardless of
100 * its state when serialized.
101 *
102 * <p>This lock supports a maximum of 2147483647 recursive locks by
103 * the same thread. Attempts to exceed this limit result in
104 * {@linkError} throws from locking methods.
105 *
106 * @since1.5
107 * @authorDoug Lea
108  */
109 public class ReentrantLock implementsLock, java.io.Serializable {
110     private static final long serialVersionUID = 7373984872572414699L;
111     /**Synchronizer providing all implementation mechanics */
112     private finalSync sync;
113 
114     /**
115 * Base of synchronization control for this lock. Subclassed
116 * into fair and nonfair versions below. Uses AQS state to
117 * represent the number of holds on the lock.
118      */
119     abstract static class Sync extendsAbstractQueuedSynchronizer {
120         private static final long serialVersionUID = -5179523762034025860L;
121 
122         /**
123 * Performs {@linkLock#lock}. The main reason for subclassing
124 * is to allow fast path for nonfair version.
125          */
126         abstract voidlock();
127 
128         /**
129 * Performs non-fair tryLock.  tryAcquire is
130 * implemented in subclasses, but both need nonfair
131 * try for trylock method.
132          */
133         final boolean nonfairTryAcquire(intacquires) {
134             final Thread current =Thread.currentThread();
135             int c =getState();
136             if (c == 0) {
137                 if (compareAndSetState(0, acquires)) {
138 setExclusiveOwnerThread(current);
139                     return true;
140 }
141 }
142             else if (current ==getExclusiveOwnerThread()) {
143                 int nextc = c +acquires;
144                 if (nextc < 0) //overflow
145                     throw new Error("Maximum lock count exceeded");
146 setState(nextc);
147                 return true;
148 }
149             return false;
150 }
151 
152         protected final boolean tryRelease(intreleases) {
153             int c = getState() -releases;
154             if (Thread.currentThread() !=getExclusiveOwnerThread())
155                 throw newIllegalMonitorStateException();
156             boolean free = false;
157             if (c == 0) {
158                 free = true;
159                 setExclusiveOwnerThread(null);
160 }
161 setState(c);
162             returnfree;
163 }
164 
165         protected final booleanisHeldExclusively() {
166             //While we must in general read state before owner,
167             //we don't need to do so to check if current thread is owner
168             return getExclusiveOwnerThread() ==Thread.currentThread();
169 }
170 
171         finalConditionObject newCondition() {
172             return newConditionObject();
173 }
174 
175         //Methods relayed from outer class
176 
177         finalThread getOwner() {
178             return getState() == 0 ? null: getExclusiveOwnerThread();
179 }
180 
181         final intgetHoldCount() {
182             return isHeldExclusively() ? getState() : 0;
183 }
184 
185         final booleanisLocked() {
186             return getState() != 0;
187 }
188 
189         /**
190 * Reconstitutes this lock instance from a stream.
191 * @params the stream
192          */
193         private voidreadObject(java.io.ObjectInputStream s)
194             throwsjava.io.IOException, ClassNotFoundException {
195 s.defaultReadObject();
196             setState(0); //reset to unlocked state
197 }
198 }
199 
200     /**
201 * Sync object for non-fair locks
202      */
203     static final class NonfairSync extendsSync {
204         private static final long serialVersionUID = 7316153563782823691L;
205 
206         /**
207 * Performs lock.  Try immediate barge, backing up to normal
208 * acquire on failure.
209          */
210         final voidlock() {
211             if (compareAndSetState(0, 1))
212 setExclusiveOwnerThread(Thread.currentThread());
213             else
214                 acquire(1);
215 }
216 
217         protected final boolean tryAcquire(intacquires) {
218             returnnonfairTryAcquire(acquires);
219 }
220 }
221 
222     /**
223 * Sync object for fair locks
224      */
225     static final class FairSync extendsSync {
226         private static final long serialVersionUID = -3000897897090466540L;
227 
228         final voidlock() {
229             acquire(1);
230 }
231 
232         /**
233 * Fair version of tryAcquire.  Don't grant access unless
234 * recursive call or no waiters or is first.
235          */
236         protected final boolean tryAcquire(intacquires) {
237             final Thread current =Thread.currentThread();
238             int c =getState();
239             if (c == 0) {
240                 if (!hasQueuedPredecessors() &&
241                     compareAndSetState(0, acquires)) {
242 setExclusiveOwnerThread(current);
243                     return true;
244 }
245 }
246             else if (current ==getExclusiveOwnerThread()) {
247                 int nextc = c +acquires;
248                 if (nextc < 0)
249                     throw new Error("Maximum lock count exceeded");
250 setState(nextc);
251                 return true;
252 }
253             return false;
254 }
255 }
256 
257     /**
258 * Creates an instance of {@codeReentrantLock}.
259 * This is equivalent to using {@codeReentrantLock(false)}.
260      */
261     publicReentrantLock() {
262         sync = newNonfairSync();
263 }
264 
265     /**
266 * Creates an instance of {@codeReentrantLock} with the
267 * given fairness policy.
268 *
269 * @paramfair {@codetrue} if this lock should use a fair ordering policy
270      */
271     public ReentrantLock(booleanfair) {
272         sync = fair ? new FairSync() : newNonfairSync();
273 }
274 
275     /**
276 * Acquires the lock.
277 *
278 * <p>Acquires the lock if it is not held by another thread and returns
279 * immediately, setting the lock hold count to one.
280 *
281 * <p>If the current thread already holds the lock then the hold
282 * count is incremented by one and the method returns immediately.
283 *
284 * <p>If the lock is held by another thread then the
285 * current thread becomes disabled for thread scheduling
286 * purposes and lies dormant until the lock has been acquired,
287 * at which time the lock hold count is set to one.
288      */
289     public voidlock() {
290 sync.lock();
291 }
292 
293     /**
294 * Acquires the lock unless the current thread is
295 * {@linkplainThread#interrupt interrupted}.
296 *
297 * <p>Acquires the lock if it is not held by another thread and returns
298 * immediately, setting the lock hold count to one.
299 *
300 * <p>If the current thread already holds this lock then the hold count
301 * is incremented by one and the method returns immediately.
302 *
303 * <p>If the lock is held by another thread then the
304 * current thread becomes disabled for thread scheduling
305 * purposes and lies dormant until one of two things happens:
306 *
307 * <ul>
308 *
309 * <li>The lock is acquired by the current thread; or
310 *
311 * <li>Some other thread {@linkplainThread#interrupt interrupts} the
312 * current thread.
313 *
314 * </ul>
315 *
316 * <p>If the lock is acquired by the current thread then the lock hold
317 * count is set to one.
318 *
319 * <p>If the current thread:
320 *
321 * <ul>
322 *
323 * <li>has its interrupted status set on entry to this method; or
324 *
325 * <li>is {@linkplainThread#interrupt interrupted} while acquiring
326 * the lock,
327 *
328 * </ul>
329 *
330 * then {@linkInterruptedException} is thrown and the current thread's
331 * interrupted status is cleared.
332 *
333 * <p>In this implementation, as this method is an explicit
334 * interruption point, preference is given to responding to the
335 * interrupt over normal or reentrant acquisition of the lock.
336 *
337 * @throwsInterruptedException if the current thread is interrupted
338      */
339     public void lockInterruptibly() throwsInterruptedException {
340         sync.acquireInterruptibly(1);
341 }
342 
343     /**
344 * Acquires the lock only if it is not held by another thread at the time
345 * of invocation.
346 *
347 * <p>Acquires the lock if it is not held by another thread and
348 * returns immediately with the value {@codetrue}, setting the
349 * lock hold count to one. Even when this lock has been set to use a
350 * fair ordering policy, a call to {@codetryLock()} <em>will</em>
351 * immediately acquire the lock if it is available, whether or not
352 * other threads are currently waiting for the lock.
353 * This &quot;barging&quot; behavior can be useful in certain
354 * circumstances, even though it breaks fairness. If you want to honor
355 * the fairness setting for this lock, then use
356 * {@link#tryLock(long, TimeUnit) tryLock(0, TimeUnit.SECONDS) }
357 * which is almost equivalent (it also detects interruption).
358 *
359 * <p> If the current thread already holds this lock then the hold
360 * count is incremented by one and the method returns {@codetrue}.
361 *
362 * <p>If the lock is held by another thread then this method will return
363 * immediately with the value {@codefalse}.
364 *
365 * @return{@codetrue} if the lock was free and was acquired by the
366 *         current thread, or the lock was already held by the current
367 *         thread; and {@codefalse} otherwise
368      */
369     public booleantryLock() {
370         return sync.nonfairTryAcquire(1);
371 }
372 
373     /**
374 * Acquires the lock if it is not held by another thread within the given
375 * waiting time and the current thread has not been
376 * {@linkplainThread#interrupt interrupted}.
377 *
378 * <p>Acquires the lock if it is not held by another thread and returns
379 * immediately with the value {@codetrue}, setting the lock hold count
380 * to one. If this lock has been set to use a fair ordering policy then
381 * an available lock <em>will not</em> be acquired if any other threads
382 * are waiting for the lock. This is in contrast to the {@link#tryLock()}
383 * method. If you want a timed {@codetryLock} that does permit barging on
384 * a fair lock then combine the timed and un-timed forms together:
385 *
386 * <pre>if (lock.tryLock() || lock.tryLock(timeout, unit) ) { ... }
387 * </pre>
388 *
389 * <p>If the current thread
390 * already holds this lock then the hold count is incremented by one and
391 * the method returns {@codetrue}.
392 *
393 * <p>If the lock is held by another thread then the
394 * current thread becomes disabled for thread scheduling
395 * purposes and lies dormant until one of three things happens:
396 *
397 * <ul>
398 *
399 * <li>The lock is acquired by the current thread; or
400 *
401 * <li>Some other thread {@linkplainThread#interrupt interrupts}
402 * the current thread; or
403 *
404 * <li>The specified waiting time elapses
405 *
406 * </ul>
407 *
408 * <p>If the lock is acquired then the value {@codetrue} is returned and
409 * the lock hold count is set to one.
410 *
411 * <p>If the current thread:
412 *
413 * <ul>
414 *
415 * <li>has its interrupted status set on entry to this method; or
416 *
417 * <li>is {@linkplainThread#interrupt interrupted} while
418 * acquiring the lock,
419 *
420 * </ul>
421 * then {@linkInterruptedException} is thrown and the current thread's
422 * interrupted status is cleared.
423 *
424 * <p>If the specified waiting time elapses then the value {@codefalse}
425 * is returned.  If the time is less than or equal to zero, the method
426 * will not wait at all.
427 *
428 * <p>In this implementation, as this method is an explicit
429 * interruption point, preference is given to responding to the
430 * interrupt over normal or reentrant acquisition of the lock, and
431 * over reporting the elapse of the waiting time.
432 *
433 * @paramtimeout the time to wait for the lock
434 * @paramunit the time unit of the timeout argument
435 * @return{@codetrue} if the lock was free and was acquired by the
436 *         current thread, or the lock was already held by the current
437 *         thread; and {@codefalse} if the waiting time elapsed before
438 *         the lock could be acquired
439 * @throwsInterruptedException if the current thread is interrupted
440 * @throwsNullPointerException if the time unit is null
441 *
442      */
443     public boolean tryLock(longtimeout, TimeUnit unit)
444             throwsInterruptedException {
445         return sync.tryAcquireNanos(1, unit.toNanos(timeout));
446 }
447 
448     /**
449 * Attempts to release this lock.
450 *
451 * <p>If the current thread is the holder of this lock then the hold
452 * count is decremented.  If the hold count is now zero then the lock
453 * is released.  If the current thread is not the holder of this
454 * lock then {@linkIllegalMonitorStateException} is thrown.
455 *
456 * @throwsIllegalMonitorStateException if the current thread does not
457 *         hold this lock
458      */
459     public voidunlock() {
460         sync.release(1);
461 }
462 
463     /**
464 * Returns a {@linkCondition} instance for use with this
465 * {@linkLock} instance.
466 *
467 * <p>The returned {@linkCondition} instance supports the same
468 * usages as do the {@linkObject} monitor methods ({@link
469 * Object#wait() wait}, {@linkObject#notify notify}, and {@link
470 * Object#notifyAll notifyAll}) when used with the built-in
471 * monitor lock.
472 *
473 * <ul>
474 *
475 * <li>If this lock is not held when any of the {@linkCondition}
476 * {@linkplainCondition#await() waiting} or {@linkplain
477 * Condition#signal signalling} methods are called, then an {@link
478 * IllegalMonitorStateException} is thrown.
479 *
480 * <li>When the condition {@linkplainCondition#await() waiting}
481 * methods are called the lock is released and, before they
482 * return, the lock is reacquired and the lock hold count restored
483 * to what it was when the method was called.
484 *
485 * <li>If a thread is {@linkplainThread#interrupt interrupted}
486 * while waiting then the wait will terminate, an {@link
487 * InterruptedException} will be thrown, and the thread's
488 * interrupted status will be cleared.
489 *
490 * <li> Waiting threads are signalled in FIFO order.
491 *
492 * <li>The ordering of lock reacquisition for threads returning
493 * from waiting methods is the same as for threads initially
494 * acquiring the lock, which is in the default case not specified,
495 * but for <em>fair</em> locks favors those threads that have been
496 * waiting the longest.
497 *
498 * </ul>
499 *
500 * @returnthe Condition object
501      */
502     publicCondition newCondition() {
503         returnsync.newCondition();
504 }
505 
506     /**
507 * Queries the number of holds on this lock by the current thread.
508 *
509 * <p>A thread has a hold on a lock for each lock action that is not
510 * matched by an unlock action.
511 *
512 * <p>The hold count information is typically only used for testing and
513 * debugging purposes. For example, if a certain section of code should
514 * not be entered with the lock already held then we can assert that
515 * fact:
516 *
517 * <pre>
518 * class X {
519 *   ReentrantLock lock = new ReentrantLock();
520 *   // ...
521 *   public void m() {
522 *     assert lock.getHoldCount() == 0;
523 *     lock.lock();
524 *     try {
525 *       // ... method body
526 *     } finally {
527 *       lock.unlock();
528 *     }
529 *   }
530 * }
531 * </pre>
532 *
533 * @returnthe number of holds on this lock by the current thread,
534 *         or zero if this lock is not held by the current thread
535      */
536     public intgetHoldCount() {
537         returnsync.getHoldCount();
538 }
539 
540     /**
541 * Queries if this lock is held by the current thread.
542 *
543 * <p>Analogous to the {@linkThread#holdsLock} method for built-in
544 * monitor locks, this method is typically used for debugging and
545 * testing. For example, a method that should only be called while
546 * a lock is held can assert that this is the case:
547 *
548 * <pre>
549 * class X {
550 *   ReentrantLock lock = new ReentrantLock();
551 *   // ...
552 *
553 *   public void m() {
554 *       assert lock.isHeldByCurrentThread();
555 *       // ... method body
556 *   }
557 * }
558 * </pre>
559 *
560 * <p>It can also be used to ensure that a reentrant lock is used
561 * in a non-reentrant manner, for example:
562 *
563 * <pre>
564 * class X {
565 *   ReentrantLock lock = new ReentrantLock();
566 *   // ...
567 *
568 *   public void m() {
569 *       assert !lock.isHeldByCurrentThread();
570 *       lock.lock();
571 *       try {
572 *           // ... method body
573 *       } finally {
574 *           lock.unlock();
575 *       }
576 *   }
577 * }
578 * </pre>
579 *
580 * @return{@codetrue} if current thread holds this lock and
581 *         {@codefalse} otherwise
582      */
583     public booleanisHeldByCurrentThread() {
584         returnsync.isHeldExclusively();
585 }
586 
587     /**
588 * Queries if this lock is held by any thread. This method is
589 * designed for use in monitoring of the system state,
590 * not for synchronization control.
591 *
592 * @return{@codetrue} if any thread holds this lock and
593 *         {@codefalse} otherwise
594      */
595     public booleanisLocked() {
596         returnsync.isLocked();
597 }
598 
599     /**
600 * Returns {@codetrue} if this lock has fairness set true.
601 *
602 * @return{@codetrue} if this lock has fairness set true
603      */
604     public final booleanisFair() {
605         return sync instanceofFairSync;
606 }
607 
608     /**
609 * Returns the thread that currently owns this lock, or
610 * {@codenull} if not owned. When this method is called by a
611 * thread that is not the owner, the return value reflects a
612 * best-effort approximation of current lock status. For example,
613 * the owner may be momentarily {@codenull} even if there are
614 * threads trying to acquire the lock but have not yet done so.
615 * This method is designed to facilitate construction of
616 * subclasses that provide more extensive lock monitoring
617 * facilities.
618 *
619 * @returnthe owner, or {@codenull} if not owned
620      */
621     protectedThread getOwner() {
622         returnsync.getOwner();
623 }
624 
625     /**
626 * Queries whether any threads are waiting to acquire this lock. Note that
627 * because cancellations may occur at any time, a {@codetrue}
628 * return does not guarantee that any other thread will ever
629 * acquire this lock.  This method is designed primarily for use in
630 * monitoring of the system state.
631 *
632 * @return{@codetrue} if there may be other threads waiting to
633 *         acquire the lock
634      */
635     public final booleanhasQueuedThreads() {
636         returnsync.hasQueuedThreads();
637 }
638 
639 
640     /**
641 * Queries whether the given thread is waiting to acquire this
642 * lock. Note that because cancellations may occur at any time, a
643 * {@codetrue} return does not guarantee that this thread
644 * will ever acquire this lock.  This method is designed primarily for use
645 * in monitoring of the system state.
646 *
647 * @paramthread the thread
648 * @return{@codetrue} if the given thread is queued waiting for this lock
649 * @throwsNullPointerException if the thread is null
650      */
651     public final booleanhasQueuedThread(Thread thread) {
652         returnsync.isQueued(thread);
653 }
654 
655 
656     /**
657 * Returns an estimate of the number of threads waiting to
658 * acquire this lock.  The value is only an estimate because the number of
659 * threads may change dynamically while this method traverses
660 * internal data structures.  This method is designed for use in
661 * monitoring of the system state, not for synchronization
662 * control.
663 *
664 * @returnthe estimated number of threads waiting for this lock
665      */
666     public final intgetQueueLength() {
667         returnsync.getQueueLength();
668 }
669 
670     /**
671 * Returns a collection containing threads that may be waiting to
672 * acquire this lock.  Because the actual set of threads may change
673 * dynamically while constructing this result, the returned
674 * collection is only a best-effort estimate.  The elements of the
675 * returned collection are in no particular order.  This method is
676 * designed to facilitate construction of subclasses that provide
677 * more extensive monitoring facilities.
678 *
679 * @returnthe collection of threads
680      */
681     protected Collection<Thread>getQueuedThreads() {
682         returnsync.getQueuedThreads();
683 }
684 
685     /**
686 * Queries whether any threads are waiting on the given condition
687 * associated with this lock. Note that because timeouts and
688 * interrupts may occur at any time, a {@codetrue} return does
689 * not guarantee that a future {@codesignal} will awaken any
690 * threads.  This method is designed primarily for use in
691 * monitoring of the system state.
692 *
693 * @paramcondition the condition
694 * @return{@codetrue} if there are any waiting threads
695 * @throwsIllegalMonitorStateException if this lock is not held
696 * @throwsIllegalArgumentException if the given condition is
697 *         not associated with this lock
698 * @throwsNullPointerException if the condition is null
699      */
700     public booleanhasWaiters(Condition condition) {
701         if (condition == null)
702             throw newNullPointerException();
703         if (!(condition instanceofAbstractQueuedSynchronizer.ConditionObject))
704             throw new IllegalArgumentException("not owner");
705         returnsync.hasWaiters((AbstractQueuedSynchronizer.ConditionObject)condition);
706 }
707 
708     /**
709 * Returns an estimate of the number of threads waiting on the
710 * given condition associated with this lock. Note that because
711 * timeouts and interrupts may occur at any time, the estimate
712 * serves only as an upper bound on the actual number of waiters.
713 * This method is designed for use in monitoring of the system
714 * state, not for synchronization control.
715 *
716 * @paramcondition the condition
717 * @returnthe estimated number of waiting threads
718 * @throwsIllegalMonitorStateException if this lock is not held
719 * @throwsIllegalArgumentException if the given condition is
720 *         not associated with this lock
721 * @throwsNullPointerException if the condition is null
722      */
723     public intgetWaitQueueLength(Condition condition) {
724         if (condition == null)
725             throw newNullPointerException();
726         if (!(condition instanceofAbstractQueuedSynchronizer.ConditionObject))
727             throw new IllegalArgumentException("not owner");
728         returnsync.getWaitQueueLength((AbstractQueuedSynchronizer.ConditionObject)condition);
729 }
730 
731     /**
732 * Returns a collection containing those threads that may be
733 * waiting on the given condition associated with this lock.
734 * Because the actual set of threads may change dynamically while
735 * constructing this result, the returned collection is only a
736 * best-effort estimate. The elements of the returned collection
737 * are in no particular order.  This method is designed to
738 * facilitate construction of subclasses that provide more
739 * extensive condition monitoring facilities.
740 *
741 * @paramcondition the condition
742 * @returnthe collection of threads
743 * @throwsIllegalMonitorStateException if this lock is not held
744 * @throwsIllegalArgumentException if the given condition is
745 *         not associated with this lock
746 * @throwsNullPointerException if the condition is null
747      */
748     protected Collection<Thread>getWaitingThreads(Condition condition) {
749         if (condition == null)
750             throw newNullPointerException();
751         if (!(condition instanceofAbstractQueuedSynchronizer.ConditionObject))
752             throw new IllegalArgumentException("not owner");
753         returnsync.getWaitingThreads((AbstractQueuedSynchronizer.ConditionObject)condition);
754 }
755 
756     /**
757 * Returns a string identifying this lock, as well as its lock state.
758 * The state, in brackets, includes either the String {@code"Unlocked"}
759 * or the String {@code"Locked by"} followed by the
760 * {@linkplainThread#getName name} of the owning thread.
761 *
762 * @returna string identifying this lock, as well as its lock state
763      */
764     publicString toString() {
765         Thread o =sync.getOwner();
766         return super.toString() + ((o == null) ?
767                                    "[Unlocked]":
768                                    "[Locked by thread " + o.getName() + "]");
769 }
770 }

1 /*
2 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
3 *
4 *
5 *
6 *
7 *
8 *
9 *
10 *
11 *
12 *
13 *
14 *
15 *
16 *
17 *
18 *
19 *
20 *
21 *
22 *
23  */
24 
25 /*
26 *
27 *
28 *
29 *
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 packagejava.util.concurrent.locks;
37 import java.util.*;
38 import java.util.concurrent.*;
39 import java.util.concurrent.atomic.*;
40 importsun.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 * {@linkReadWriteLock}. 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 {@linkConditionObject} class that
80 * can be used as a {@linkCondition} 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 {@linkConditionObject} 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 * {@linkjava.util.concurrent.atomic atomic} classes, your own custom
184 * {@linkjava.util.Queue} classes, and {@linkLockSupport} 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 {@linkCountDownLatch}
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 * @since1.5
287 * @authorDoug Lea
288  */
289 public abstract classAbstractQueuedSynchronizer
290     extendsAbstractOwnableSynchronizer
291     implementsjava.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     protectedAbstractQueuedSynchronizer() { }
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 classNode {
381         /**Marker to indicate a node is waiting in shared mode */
382         static final Node SHARED = newNode();
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 intwaitStatus;
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         volatileNode 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         volatileNode next;
461 
462         /**
463 * The thread that enqueued this node.  Initialized on
464 * construction and nulled out after use.
465          */
466         volatileThread 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 booleanisShared() {
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 * @returnthe predecessor of this node
493          */
494         final Node predecessor() throwsNullPointerException {
495             Node p =prev;
496             if (p == null)
497                 throw newNullPointerException();
498             else
499                 returnp;
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 volatileNode 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 volatileNode tail;
529 
530     /**
531 * The synchronization state.
532      */
533     private volatile intstate;
534 
535     /**
536 * Returns the current value of synchronization state.
537 * This operation has memory semantics of a <tt>volatile</tt> read.
538 * @returncurrent state value
539      */
540     protected final intgetState() {
541         returnstate;
542 }
543 
544     /**
545 * Sets the value of synchronization state.
546 * This operation has memory semantics of a <tt>volatile</tt> write.
547 * @paramnewState the new state value
548      */
549     protected final void setState(intnewState) {
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 * @paramexpect the expected value
560 * @paramupdate the new value
561 * @returntrue 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, intupdate) {
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 * @paramnode the node to insert
581 * @returnnode's predecessor
582      */
583     private Node enq(finalNode node) {
584         for(;;) {
585             Node t =tail;
586             if (t == null) { //Must initialize
587                 if (compareAndSetHead(newNode()))
588                     tail =head;
589             } else{
590                 node.prev =t;
591                 if(compareAndSetTail(t, node)) {
592                     t.next =node;
593                     returnt;
594 }
595 }
596 }
597 }
598 
599     /**
600 * Creates and enqueues node for current thread and given mode.
601 *
602 * @parammode Node.EXCLUSIVE for exclusive, Node.SHARED for shared
603 * @returnthe new node
604      */
605     privateNode addWaiter(Node mode) {
606         Node node = newNode(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                 returnnode;
614 }
615 }
616 enq(node);
617         returnnode;
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 * @paramnode the node
626      */
627     private voidsetHead(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 * @paramnode the node
637      */
638     private voidunparkSuccessor(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 voiddoReleaseShared() {
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 * @paramnode the node
706 * @parampropagate the return value from a tryAcquireShared
707      */
708     private void setHeadAndPropagate(Node node, intpropagate) {
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 * @paramnode the node
739      */
740     private voidcancelAcquire(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             intws;
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 * @parampred node's predecessor holding status
790 * @paramnode the node
791 * @return{@codetrue} if thread should block
792      */
793     private static booleanshouldParkAfterFailedAcquire(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 voidselfInterrupt() {
825 Thread.currentThread().interrupt();
826 }
827 
828     /**
829 * Convenience method to park and then check if interrupted
830 *
831 * @return{@codetrue} if interrupted
832      */
833     private final booleanparkAndCheckInterrupt() {
834         LockSupport.park(this);
835         returnThread.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 * @paramnode the node
852 * @paramarg the acquire argument
853 * @return{@codetrue} if interrupted while waiting
854      */
855     final boolean acquireQueued(final Node node, intarg) {
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                     returninterrupted;
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 * @paramarg the acquire argument
880      */
881     private void doAcquireInterruptibly(intarg)
882         throwsInterruptedException {
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 newInterruptedException();
897 }
898         } finally{
899             if(failed)
900 cancelAcquire(node);
901 }
902 }
903 
904     /**
905 * Acquires in exclusive timed mode.
906 *
907 * @paramarg the acquire argument
908 * @paramnanosTimeout max wait time
909 * @return{@codetrue} if acquired
910      */
911     private boolean doAcquireNanos(int arg, longnanosTimeout)
912         throwsInterruptedException {
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 newInterruptedException();
935 }
936         } finally{
937             if(failed)
938 cancelAcquire(node);
939 }
940 }
941 
942     /**
943 * Acquires in shared uninterruptible mode.
944 * @paramarg the acquire argument
945      */
946     private void doAcquireShared(intarg) {
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 * @paramarg the acquire argument
977      */
978     private void doAcquireSharedInterruptibly(intarg)
979         throwsInterruptedException {
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 newInterruptedException();
997 }
998         } finally{
999             if(failed)
1000 cancelAcquire(node);
1001 }
1002 }
1003 
1004     /**
1005 * Acquires in shared timed mode.
1006 *
1007 * @paramarg the acquire argument
1008 * @paramnanosTimeout max wait time
1009 * @return{@codetrue} if acquired
1010      */
1011     private boolean doAcquireSharedNanos(int arg, longnanosTimeout)
1012         throwsInterruptedException {
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 newInterruptedException();
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 {@linkLock#tryLock()}.
1058 *
1059 * <p>The default
1060 * implementation throws {@linkUnsupportedOperationException}.
1061 *
1062 * @paramarg 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{@codetrue} if successful. Upon success, this object has
1067 *         been acquired.
1068 * @throwsIllegalMonitorStateException 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 * @throwsUnsupportedOperationException if exclusive mode is not supported
1073      */
1074     protected boolean tryAcquire(intarg) {
1075         throw newUnsupportedOperationException();
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 * {@linkUnsupportedOperationException}.
1086 *
1087 * @paramarg 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{@codetrue} if this object is now in a fully released
1092 *         state, so that any waiting threads may attempt to acquire;
1093 *         and {@codefalse} otherwise.
1094 * @throwsIllegalMonitorStateException 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 * @throwsUnsupportedOperationException if exclusive mode is not supported
1099      */
1100     protected boolean tryRelease(intarg) {
1101         throw newUnsupportedOperationException();
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 * @paramarg 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 * @returna 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 * @throwsIllegalMonitorStateException 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 * @throwsUnsupportedOperationException if shared mode is not supported
1135      */
1136     protected int tryAcquireShared(intarg) {
1137         throw newUnsupportedOperationException();
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 * {@linkUnsupportedOperationException}.
1147 *
1148 * @paramarg 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{@codetrue} if this release of shared mode may permit a
1153 *         waiting acquire (shared or exclusive) to succeed; and
1154 *         {@codefalse} otherwise
1155 * @throwsIllegalMonitorStateException 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 * @throwsUnsupportedOperationException if shared mode is not supported
1160      */
1161     protected boolean tryReleaseShared(intarg) {
1162         throw newUnsupportedOperationException();
1163 }
1164 
1165     /**
1166 * Returns {@codetrue} 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 {@linkConditionObject} 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 {@linkConditionObject} methods, so need
1174 * not be defined if conditions are not used.
1175 *
1176 * @return{@codetrue} if synchronization is held exclusively;
1177 *         {@codefalse} otherwise
1178 * @throwsUnsupportedOperationException if conditions are not supported
1179      */
1180     protected booleanisHeldExclusively() {
1181         throw newUnsupportedOperationException();
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 {@linkLock#lock}.
1191 *
1192 * @paramarg 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(intarg) {
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 {@linkLock#lockInterruptibly}.
1210 *
1211 * @paramarg the acquire argument.  This value is conveyed to
1212 *        {@link#tryAcquire} but is otherwise uninterpreted and
1213 *        can represent anything you like.
1214 * @throwsInterruptedException if the current thread is interrupted
1215      */
1216     public final void acquireInterruptibly(intarg)
1217             throwsInterruptedException {
1218         if(Thread.interrupted())
1219             throw newInterruptedException();
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 {@linkLock#tryLock(long, TimeUnit)}.
1233 *
1234 * @paramarg the acquire argument.  This value is conveyed to
1235 *        {@link#tryAcquire} but is otherwise uninterpreted and
1236 *        can represent anything you like.
1237 * @paramnanosTimeout the maximum number of nanoseconds to wait
1238 * @return{@codetrue} if acquired; {@codefalse} if timed out
1239 * @throwsInterruptedException if the current thread is interrupted
1240      */
1241     public final boolean tryAcquireNanos(int arg, longnanosTimeout)
1242             throwsInterruptedException {
1243         if(Thread.interrupted())
1244             throw newInterruptedException();
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 {@linkLock#unlock}.
1253 *
1254 * @paramarg the release argument.  This value is conveyed to
1255 *        {@link#tryRelease} but is otherwise uninterpreted and
1256 *        can represent anything you like.
1257 * @returnthe value returned from {@link#tryRelease}
1258      */
1259     public final boolean release(intarg) {
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 * @paramarg 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(intarg) {
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 * @paramarg the acquire argument
1293 * This value is conveyed to {@link#tryAcquireShared} but is
1294 * otherwise uninterpreted and can represent anything
1295 * you like.
1296 * @throwsInterruptedException if the current thread is interrupted
1297      */
1298     public final void acquireSharedInterruptibly(intarg)
1299             throwsInterruptedException {
1300         if(Thread.interrupted())
1301             throw newInterruptedException();
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 * @paramarg the acquire argument.  This value is conveyed to
1316 *        {@link#tryAcquireShared} but is otherwise uninterpreted
1317 *        and can represent anything you like.
1318 * @paramnanosTimeout the maximum number of nanoseconds to wait
1319 * @return{@codetrue} if acquired; {@codefalse} if timed out
1320 * @throwsInterruptedException if the current thread is interrupted
1321      */
1322     public final boolean tryAcquireSharedNanos(int arg, longnanosTimeout)
1323             throwsInterruptedException {
1324         if(Thread.interrupted())
1325             throw newInterruptedException();
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 * @paramarg the release argument.  This value is conveyed to
1335 *        {@link#tryReleaseShared} but is otherwise uninterpreted
1336 *        and can represent anything you like.
1337 * @returnthe value returned from {@link#tryReleaseShared}
1338      */
1339     public final boolean releaseShared(intarg) {
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 {@codetrue} 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{@codetrue} if there may be other threads waiting to acquire
1359      */
1360     public final booleanhasQueuedThreads() {
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{@codetrue} if there has ever been contention
1372      */
1373     public final booleanhasContended() {
1374         return head != null;
1375 }
1376 
1377     /**
1378 * Returns the first (longest-waiting) thread in the queue, or
1379 * {@codenull} 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 * @returnthe first (longest-waiting) thread in the queue, or
1386 *         {@codenull} if no threads are currently queued
1387      */
1388     public finalThread 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     privateThread 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             returnst;
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         returnfirstThread;
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 * @paramthread the thread
1439 * @return{@codetrue} if the given thread is on the queue
1440 * @throwsNullPointerException if the thread is null
1441      */
1442     public final booleanisQueued(Thread thread) {
1443         if (thread == null)
1444             throw newNullPointerException();
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 {@codetrue} if the apparent first queued thread, if one
1453 * exists, is waiting in exclusive mode.  If this method returns
1454 * {@codetrue}, 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 booleanapparentlyFirstQueuedIsExclusive() {
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 {@codetrue} 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 {@codefalse},
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="http://t.zoukankan.com/AbstractQueuedSynchronizer#barging">barging</a>.
1487 * Such a synchronizer's {@link#tryAcquire} method should return
1488 * {@codefalse}, and its {@link#tryAcquireShared} method should
1489 * return a negative value, if this method returns {@codetrue}
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{@codetrue} if there is a queued thread preceding the
1507 *         current thread, and {@codefalse} if the current thread
1508 *         is at the head of the queue or the queue is empty
1509 * @since1.7
1510      */
1511     public final booleanhasQueuedPredecessors() {
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 * @returnthe estimated number of threads waiting to acquire
1534      */
1535     public final intgetQueueLength() {
1536         int n = 0;
1537         for (Node p = tail; p != null; p =p.prev) {
1538             if (p.thread != null)
1539                 ++n;
1540 }
1541         returnn;
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 * @returnthe 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         returnlist;
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 * @returnthe 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         returnlist;
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 * @returnthe 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         returnlist;
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 * @returna string identifying this synchronizer, as well as its state
1613      */
1614     publicString 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 * @paramnode the node
1628 * @returntrue if is reacquiring
1629      */
1630     final booleanisOnSyncQueue(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         returnfindNodeFromTail(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 * @returntrue if present
1650      */
1651     private booleanfindNodeFromTail(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 * @paramnode the node
1666 * @returntrue if successfully transferred (else the node was
1667 * cancelled before signal).
1668      */
1669     final booleantransferForSignal(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 * @paramcurrent the waiting thread
1694 * @paramnode its node
1695 * @returntrue if cancelled before the node was signalled
1696      */
1697     final booleantransferAfterCancelledWait(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 * @paramnode the condition node for this wait
1717 * @returnprevious sync state
1718      */
1719     final intfullyRelease(Node node) {
1720         boolean failed = true;
1721         try{
1722             int savedState =getState();
1723             if(release(savedState)) {
1724                 failed = false;
1725                 returnsavedState;
1726             } else{
1727                 throw newIllegalMonitorStateException();
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 * @paramcondition the condition
1742 * @return<tt>true</tt> if owned
1743 * @throwsNullPointerException if the condition is null
1744      */
1745     public final booleanowns(ConditionObject condition) {
1746         if (condition == null)
1747             throw newNullPointerException();
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 * @paramcondition the condition
1760 * @return<tt>true</tt> if there are any waiting threads
1761 * @throwsIllegalMonitorStateException if exclusive synchronization
1762 *         is not held
1763 * @throwsIllegalArgumentException if the given condition is
1764 *         not associated with this synchronizer
1765 * @throwsNullPointerException if the condition is null
1766      */
1767     public final booleanhasWaiters(ConditionObject condition) {
1768         if (!owns(condition))
1769             throw new IllegalArgumentException("Not owner");
1770         returncondition.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 * @paramcondition the condition
1782 * @returnthe estimated number of waiting threads
1783 * @throwsIllegalMonitorStateException if exclusive synchronization
1784 *         is not held
1785 * @throwsIllegalArgumentException if the given condition is
1786 *         not associated with this synchronizer
1787 * @throwsNullPointerException if the condition is null
1788      */
1789     public final intgetWaitQueueLength(ConditionObject condition) {
1790         if (!owns(condition))
1791             throw new IllegalArgumentException("Not owner");
1792         returncondition.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 * @paramcondition the condition
1804 * @returnthe collection of threads
1805 * @throwsIllegalMonitorStateException if exclusive synchronization
1806 *         is not held
1807 * @throwsIllegalArgumentException if the given condition is
1808 *         not associated with this synchronizer
1809 * @throwsNullPointerException 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         returncondition.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 implementsCondition, java.io.Serializable {
1833         private static final long serialVersionUID = 1173984872572414699L;
1834         /**First node of condition queue. */
1835         private transientNode firstWaiter;
1836         /**Last node of condition queue. */
1837         private transientNode lastWaiter;
1838 
1839         /**
1840 * Creates a new <tt>ConditionObject</tt> instance.
1841          */
1842         publicConditionObject() { }
1843 
1844         //Internal methods
1845 
1846         /**
1847 * Adds a new waiter to wait queue.
1848 * @returnits new wait node
1849          */
1850         privateNode 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 = newNode(Thread.currentThread(), Node.CONDITION);
1858             if (t == null)
1859                 firstWaiter =node;
1860             else
1861                 t.nextWaiter =node;
1862             lastWaiter =node;
1863             returnnode;
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 * @paramfirst (non-null) the first node on condition queue
1871          */
1872         private voiddoSignal(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 * @paramfirst (non-null) the first node on condition queue
1884          */
1885         private voiddoSignalAll(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 voidunlinkCancelledWaiters() {
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 * @throwsIllegalMonitorStateException if {@link#isHeldExclusively}
1937 *         returns {@codefalse}
1938          */
1939         public final voidsignal() {
1940             if (!isHeldExclusively())
1941                 throw newIllegalMonitorStateException();
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 * @throwsIllegalMonitorStateException if {@link#isHeldExclusively}
1952 *         returns {@codefalse}
1953          */
1954         public final voidsignalAll() {
1955             if (!isHeldExclusively())
1956                 throw newIllegalMonitorStateException();
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 voidawaitUninterruptibly() {
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 intcheckInterruptWhileWaiting(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(intinterruptMode)
2015             throwsInterruptedException {
2016             if (interruptMode ==THROW_IE)
2017                 throw newInterruptedException();
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() throwsInterruptedException {
2037             if(Thread.interrupted())
2038                 throw newInterruptedException();
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(longnanosTimeout)
2070                 throwsInterruptedException {
2071             if(Thread.interrupted())
2072                 throw newInterruptedException();
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 booleanawaitUntil(Date deadline)
2115                 throwsInterruptedException {
2116             if (deadline == null)
2117                 throw newNullPointerException();
2118             long abstime =deadline.getTime();
2119             if(Thread.interrupted())
2120                 throw newInterruptedException();
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(longtime, TimeUnit unit)
2159                 throwsInterruptedException {
2160             if (unit == null)
2161                 throw newNullPointerException();
2162             long nanosTimeout =unit.toNanos(time);
2163             if(Thread.interrupted())
2164                 throw newInterruptedException();
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{@codetrue} if owned
2199          */
2200         final booleanisOwnedBy(AbstractQueuedSynchronizer sync) {
2201             return sync == AbstractQueuedSynchronizer.this;
2202 }
2203 
2204         /**
2205 * Queries whether any threads are waiting on this condition.
2206 * Implements {@linkAbstractQueuedSynchronizer#hasWaiters}.
2207 *
2208 * @return{@codetrue} if there are any waiting threads
2209 * @throwsIllegalMonitorStateException if {@link#isHeldExclusively}
2210 *         returns {@codefalse}
2211          */
2212         protected final booleanhasWaiters() {
2213             if (!isHeldExclusively())
2214                 throw newIllegalMonitorStateException();
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 {@linkAbstractQueuedSynchronizer#getWaitQueueLength}.
2226 *
2227 * @returnthe estimated number of waiting threads
2228 * @throwsIllegalMonitorStateException if {@link#isHeldExclusively}
2229 *         returns {@codefalse}
2230          */
2231         protected final intgetWaitQueueLength() {
2232             if (!isHeldExclusively())
2233                 throw newIllegalMonitorStateException();
2234             int n = 0;
2235             for (Node w = firstWaiter; w != null; w =w.nextWaiter) {
2236                 if (w.waitStatus ==Node.CONDITION)
2237                     ++n;
2238 }
2239             returnn;
2240 }
2241 
2242         /**
2243 * Returns a collection containing those threads that may be
2244 * waiting on this Condition.
2245 * Implements {@linkAbstractQueuedSynchronizer#getWaitingThreads}.
2246 *
2247 * @returnthe collection of threads
2248 * @throwsIllegalMonitorStateException if {@link#isHeldExclusively}
2249 *         returns {@codefalse}
2250          */
2251         protected final Collection<Thread>getWaitingThreads() {
2252             if (!isHeldExclusively())
2253                 throw newIllegalMonitorStateException();
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             returnlist;
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 longstateOffset;
2277     private static final longheadOffset;
2278     private static final longtailOffset;
2279     private static final longwaitStatusOffset;
2280     private static final longnextOffset;
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 newError(ex); }
2296 }
2297 
2298     /**
2299 * CAS head field. Used only by enq.
2300      */
2301     private final booleancompareAndSetHead(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 booleancompareAndSetTail(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 booleancompareAndSetWaitStatus(Node node,
2316                                                          intexpect,
2317                                                          intupdate) {
2318         returnunsafe.compareAndSwapInt(node, waitStatusOffset,
2319 expect, update);
2320 }
2321 
2322     /**
2323 * CAS next field of a node.
2324      */
2325     private static final booleancompareAndSetNext(Node node,
2326 Node expect,
2327 Node update) {
2328         returnunsafe.compareAndSwapObject(node, nextOffset, expect, update);
2329 }
2330 }