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