001/* 002 * Copyright (C) 2010 The Guava Authors 003 * 004 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 005 * in compliance with the License. You may obtain a copy of the License at 006 * 007 * http://www.apache.org/licenses/LICENSE-2.0 008 * 009 * Unless required by applicable law or agreed to in writing, software distributed under the License 010 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express 011 * or implied. See the License for the specific language governing permissions and limitations under 012 * the License. 013 */ 014 015package com.google.common.util.concurrent; 016 017import static com.google.common.base.Preconditions.checkNotNull; 018 019import com.google.common.annotations.Beta; 020import com.google.common.annotations.GwtIncompatible; 021import com.google.common.primitives.Longs; 022import com.google.errorprone.annotations.concurrent.GuardedBy; 023import com.google.j2objc.annotations.Weak; 024import java.util.concurrent.TimeUnit; 025import java.util.concurrent.locks.Condition; 026import java.util.concurrent.locks.ReentrantLock; 027import javax.annotation.CheckForNull; 028 029/** 030 * A synchronization abstraction supporting waiting on arbitrary boolean conditions. 031 * 032 * <p>This class is intended as a replacement for {@link ReentrantLock}. Code using {@code Monitor} 033 * is less error-prone and more readable than code using {@code ReentrantLock}, without significant 034 * performance loss. {@code Monitor} even has the potential for performance gain by optimizing the 035 * evaluation and signaling of conditions. Signaling is entirely <a 036 * href="http://en.wikipedia.org/wiki/Monitor_(synchronization)#Implicit_signaling">implicit</a>. By 037 * eliminating explicit signaling, this class can guarantee that only one thread is awakened when a 038 * condition becomes true (no "signaling storms" due to use of {@link 039 * java.util.concurrent.locks.Condition#signalAll Condition.signalAll}) and that no signals are lost 040 * (no "hangs" due to incorrect use of {@link java.util.concurrent.locks.Condition#signal 041 * Condition.signal}). 042 * 043 * <p>A thread is said to <i>occupy</i> a monitor if it has <i>entered</i> the monitor but not yet 044 * <i>left</i>. Only one thread may occupy a given monitor at any moment. A monitor is also 045 * reentrant, so a thread may enter a monitor any number of times, and then must leave the same 046 * number of times. The <i>enter</i> and <i>leave</i> operations have the same synchronization 047 * semantics as the built-in Java language synchronization primitives. 048 * 049 * <p>A call to any of the <i>enter</i> methods with <b>void</b> return type should always be 050 * followed immediately by a <i>try/finally</i> block to ensure that the current thread leaves the 051 * monitor cleanly: 052 * 053 * <pre>{@code 054 * monitor.enter(); 055 * try { 056 * // do things while occupying the monitor 057 * } finally { 058 * monitor.leave(); 059 * } 060 * }</pre> 061 * 062 * <p>A call to any of the <i>enter</i> methods with <b>boolean</b> return type should always appear 063 * as the condition of an <i>if</i> statement containing a <i>try/finally</i> block to ensure that 064 * the current thread leaves the monitor cleanly: 065 * 066 * <pre>{@code 067 * if (monitor.tryEnter()) { 068 * try { 069 * // do things while occupying the monitor 070 * } finally { 071 * monitor.leave(); 072 * } 073 * } else { 074 * // do other things since the monitor was not available 075 * } 076 * }</pre> 077 * 078 * <h2>Comparison with {@code synchronized} and {@code ReentrantLock}</h2> 079 * 080 * <p>The following examples show a simple threadsafe holder expressed using {@code synchronized}, 081 * {@link ReentrantLock}, and {@code Monitor}. 082 * 083 * <h3>{@code synchronized}</h3> 084 * 085 * <p>This version is the fewest lines of code, largely because the synchronization mechanism used 086 * is built into the language and runtime. But the programmer has to remember to avoid a couple of 087 * common bugs: The {@code wait()} must be inside a {@code while} instead of an {@code if}, and 088 * {@code notifyAll()} must be used instead of {@code notify()} because there are two different 089 * logical conditions being awaited. 090 * 091 * <pre>{@code 092 * public class SafeBox<V> { 093 * private V value; 094 * 095 * public synchronized V get() throws InterruptedException { 096 * while (value == null) { 097 * wait(); 098 * } 099 * V result = value; 100 * value = null; 101 * notifyAll(); 102 * return result; 103 * } 104 * 105 * public synchronized void set(V newValue) throws InterruptedException { 106 * while (value != null) { 107 * wait(); 108 * } 109 * value = newValue; 110 * notifyAll(); 111 * } 112 * } 113 * }</pre> 114 * 115 * <h3>{@code ReentrantLock}</h3> 116 * 117 * <p>This version is much more verbose than the {@code synchronized} version, and still suffers 118 * from the need for the programmer to remember to use {@code while} instead of {@code if}. However, 119 * one advantage is that we can introduce two separate {@code Condition} objects, which allows us to 120 * use {@code signal()} instead of {@code signalAll()}, which may be a performance benefit. 121 * 122 * <pre>{@code 123 * public class SafeBox<V> { 124 * private V value; 125 * private final ReentrantLock lock = new ReentrantLock(); 126 * private final Condition valuePresent = lock.newCondition(); 127 * private final Condition valueAbsent = lock.newCondition(); 128 * 129 * public V get() throws InterruptedException { 130 * lock.lock(); 131 * try { 132 * while (value == null) { 133 * valuePresent.await(); 134 * } 135 * V result = value; 136 * value = null; 137 * valueAbsent.signal(); 138 * return result; 139 * } finally { 140 * lock.unlock(); 141 * } 142 * } 143 * 144 * public void set(V newValue) throws InterruptedException { 145 * lock.lock(); 146 * try { 147 * while (value != null) { 148 * valueAbsent.await(); 149 * } 150 * value = newValue; 151 * valuePresent.signal(); 152 * } finally { 153 * lock.unlock(); 154 * } 155 * } 156 * } 157 * }</pre> 158 * 159 * <h3>{@code Monitor}</h3> 160 * 161 * <p>This version adds some verbosity around the {@code Guard} objects, but removes that same 162 * verbosity, and more, from the {@code get} and {@code set} methods. {@code Monitor} implements the 163 * same efficient signaling as we had to hand-code in the {@code ReentrantLock} version above. 164 * Finally, the programmer no longer has to hand-code the wait loop, and therefore doesn't have to 165 * remember to use {@code while} instead of {@code if}. 166 * 167 * <pre>{@code 168 * public class SafeBox<V> { 169 * private V value; 170 * private final Monitor monitor = new Monitor(); 171 * private final Monitor.Guard valuePresent = monitor.newGuard(() -> value != null); 172 * private final Monitor.Guard valueAbsent = monitor.newGuard(() -> value == null); 173 * 174 * public V get() throws InterruptedException { 175 * monitor.enterWhen(valuePresent); 176 * try { 177 * V result = value; 178 * value = null; 179 * return result; 180 * } finally { 181 * monitor.leave(); 182 * } 183 * } 184 * 185 * public void set(V newValue) throws InterruptedException { 186 * monitor.enterWhen(valueAbsent); 187 * try { 188 * value = newValue; 189 * } finally { 190 * monitor.leave(); 191 * } 192 * } 193 * } 194 * }</pre> 195 * 196 * @author Justin T. Sampson 197 * @author Martin Buchholz 198 * @since 10.0 199 */ 200@Beta 201@GwtIncompatible 202@SuppressWarnings("GuardedBy") // TODO(b/35466881): Fix or suppress. 203@ElementTypesAreNonnullByDefault 204public final class Monitor { 205 // TODO(user): Use raw LockSupport or AbstractQueuedSynchronizer instead of ReentrantLock. 206 // TODO(user): "Port" jsr166 tests for ReentrantLock. 207 // 208 // TODO(user): Change API to make it impossible to use a Guard with the "wrong" monitor, 209 // by making the monitor implicit, and to eliminate other sources of IMSE. 210 // Imagine: 211 // guard.lock(); 212 // try { /* monitor locked and guard satisfied here */ } 213 // finally { guard.unlock(); } 214 // Here are Justin's design notes about this: 215 // 216 // This idea has come up from time to time, and I think one of my 217 // earlier versions of Monitor even did something like this. I ended 218 // up strongly favoring the current interface. 219 // 220 // I probably can't remember all the reasons (it's possible you 221 // could find them in the code review archives), but here are a few: 222 // 223 // 1. What about leaving/unlocking? Are you going to do 224 // guard.enter() paired with monitor.leave()? That might get 225 // confusing. It's nice for the finally block to look as close as 226 // possible to the thing right before the try. You could have 227 // guard.leave(), but that's a little odd as well because the 228 // guard doesn't have anything to do with leaving. You can't 229 // really enforce that the guard you're leaving is the same one 230 // you entered with, and it doesn't actually matter. 231 // 232 // 2. Since you can enter the monitor without a guard at all, some 233 // places you'll have monitor.enter()/monitor.leave() and other 234 // places you'll have guard.enter()/guard.leave() even though 235 // it's the same lock being acquired underneath. Always using 236 // monitor.enterXXX()/monitor.leave() will make it really clear 237 // which lock is held at any point in the code. 238 // 239 // 3. I think "enterWhen(notEmpty)" reads better than "notEmpty.enter()". 240 // 241 // TODO(user): Implement ReentrantLock features: 242 // - toString() method 243 // - getOwner() method 244 // - getQueuedThreads() method 245 // - getWaitingThreads(Guard) method 246 // - implement Serializable 247 // - redo the API to be as close to identical to ReentrantLock as possible, 248 // since, after all, this class is also a reentrant mutual exclusion lock!? 249 250 /* 251 * One of the key challenges of this class is to prevent lost signals, while trying hard to 252 * minimize unnecessary signals. One simple and correct algorithm is to signal some other waiter 253 * with a satisfied guard (if one exists) whenever any thread occupying the monitor exits the 254 * monitor, either by unlocking all of its held locks, or by starting to wait for a guard. This 255 * includes exceptional exits, so all control paths involving signalling must be protected by a 256 * finally block. 257 * 258 * Further optimizations of this algorithm become increasingly subtle. A wait that terminates 259 * without the guard being satisfied (due to timeout, but not interrupt) can then immediately exit 260 * the monitor without signalling. If it timed out without being signalled, it does not need to 261 * "pass on" the signal to another thread. If it *was* signalled, then its guard must have been 262 * satisfied at the time of signal, and has since been modified by some other thread to be 263 * non-satisfied before reacquiring the lock, and that other thread takes over the responsibility 264 * of signaling the next waiter. 265 * 266 * Unlike the underlying Condition, if we are not careful, an interrupt *can* cause a signal to be 267 * lost, because the signal may be sent to a condition whose sole waiter has just been 268 * interrupted. 269 * 270 * Imagine a monitor with multiple guards. A thread enters the monitor, satisfies all the guards, 271 * and leaves, calling signalNextWaiter. With traditional locks and conditions, all the conditions 272 * need to be signalled because it is not known which if any of them have waiters (and hasWaiters 273 * can't be used reliably because of a check-then-act race). With our Monitor guards, we only 274 * signal the first active guard that is satisfied. But the corresponding thread may have already 275 * been interrupted and is waiting to reacquire the lock while still registered in activeGuards, 276 * in which case the signal is a no-op, and the bigger-picture signal is lost unless interrupted 277 * threads take special action by participating in the signal-passing game. 278 */ 279 280 /* 281 * Timeout handling is intricate, especially given our ambitious goals: 282 * - Avoid underflow and overflow of timeout values when specified timeouts are close to 283 * Long.MIN_VALUE or Long.MAX_VALUE. 284 * - Favor responding to interrupts over timeouts. 285 * - System.nanoTime() is expensive enough that we want to call it the minimum required number of 286 * times, typically once before invoking a blocking method. This often requires keeping track of 287 * the first time in a method that nanoTime() has been invoked, for which the special value 0L 288 * is reserved to mean "uninitialized". If timeout is non-positive, then nanoTime need never be 289 * called. 290 * - Keep behavior of fair and non-fair instances consistent. 291 */ 292 293 /** 294 * A boolean condition for which a thread may wait. A {@code Guard} is associated with a single 295 * {@code Monitor}. The monitor may check the guard at arbitrary times from any thread occupying 296 * the monitor, so code should not be written to rely on how often a guard might or might not be 297 * checked. 298 * 299 * <p>If a {@code Guard} is passed into any method of a {@code Monitor} other than the one it is 300 * associated with, an {@link IllegalMonitorStateException} is thrown. 301 * 302 * @since 10.0 303 */ 304 @Beta 305 public abstract static class Guard { 306 307 @Weak final Monitor monitor; 308 final Condition condition; 309 310 @GuardedBy("monitor.lock") 311 int waiterCount = 0; 312 313 /** The next active guard */ 314 @GuardedBy("monitor.lock") 315 @CheckForNull 316 Guard next; 317 318 protected Guard(Monitor monitor) { 319 this.monitor = checkNotNull(monitor, "monitor"); 320 this.condition = monitor.lock.newCondition(); 321 } 322 323 /** 324 * Evaluates this guard's boolean condition. This method is always called with the associated 325 * monitor already occupied. Implementations of this method must depend only on state protected 326 * by the associated monitor, and must not modify that state. 327 */ 328 public abstract boolean isSatisfied(); 329 } 330 331 /** Whether this monitor is fair. */ 332 private final boolean fair; 333 334 /** The lock underlying this monitor. */ 335 private final ReentrantLock lock; 336 337 /** 338 * The guards associated with this monitor that currently have waiters ({@code waiterCount > 0}). 339 * A linked list threaded through the Guard.next field. 340 */ 341 @GuardedBy("lock") 342 @CheckForNull 343 private Guard activeGuards = null; 344 345 /** 346 * Creates a monitor with a non-fair (but fast) ordering policy. Equivalent to {@code 347 * Monitor(false)}. 348 */ 349 public Monitor() { 350 this(false); 351 } 352 353 /** 354 * Creates a monitor with the given ordering policy. 355 * 356 * @param fair whether this monitor should use a fair ordering policy rather than a non-fair (but 357 * fast) one 358 */ 359 public Monitor(boolean fair) { 360 this.fair = fair; 361 this.lock = new ReentrantLock(fair); 362 } 363 364 /** Enters this monitor. Blocks indefinitely. */ 365 public void enter() { 366 lock.lock(); 367 } 368 369 /** 370 * Enters this monitor. Blocks at most the given time. 371 * 372 * @return whether the monitor was entered 373 */ 374 @SuppressWarnings("GoodTime") // should accept a java.time.Duration 375 public boolean enter(long time, TimeUnit unit) { 376 final long timeoutNanos = toSafeNanos(time, unit); 377 final ReentrantLock lock = this.lock; 378 if (!fair && lock.tryLock()) { 379 return true; 380 } 381 boolean interrupted = Thread.interrupted(); 382 try { 383 final long startTime = System.nanoTime(); 384 for (long remainingNanos = timeoutNanos; ; ) { 385 try { 386 return lock.tryLock(remainingNanos, TimeUnit.NANOSECONDS); 387 } catch (InterruptedException interrupt) { 388 interrupted = true; 389 remainingNanos = remainingNanos(startTime, timeoutNanos); 390 } 391 } 392 } finally { 393 if (interrupted) { 394 Thread.currentThread().interrupt(); 395 } 396 } 397 } 398 399 /** 400 * Enters this monitor. Blocks indefinitely, but may be interrupted. 401 * 402 * @throws InterruptedException if interrupted while waiting 403 */ 404 public void enterInterruptibly() throws InterruptedException { 405 lock.lockInterruptibly(); 406 } 407 408 /** 409 * Enters this monitor. Blocks at most the given time, and may be interrupted. 410 * 411 * @return whether the monitor was entered 412 * @throws InterruptedException if interrupted while waiting 413 */ 414 @SuppressWarnings("GoodTime") // should accept a java.time.Duration 415 public boolean enterInterruptibly(long time, TimeUnit unit) throws InterruptedException { 416 return lock.tryLock(time, unit); 417 } 418 419 /** 420 * Enters this monitor if it is possible to do so immediately. Does not block. 421 * 422 * <p><b>Note:</b> This method disregards the fairness setting of this monitor. 423 * 424 * @return whether the monitor was entered 425 */ 426 public boolean tryEnter() { 427 return lock.tryLock(); 428 } 429 430 /** 431 * Enters this monitor when the guard is satisfied. Blocks indefinitely, but may be interrupted. 432 * 433 * @throws InterruptedException if interrupted while waiting 434 */ 435 public void enterWhen(Guard guard) throws InterruptedException { 436 if (guard.monitor != this) { 437 throw new IllegalMonitorStateException(); 438 } 439 final ReentrantLock lock = this.lock; 440 boolean signalBeforeWaiting = lock.isHeldByCurrentThread(); 441 lock.lockInterruptibly(); 442 443 boolean satisfied = false; 444 try { 445 if (!guard.isSatisfied()) { 446 await(guard, signalBeforeWaiting); 447 } 448 satisfied = true; 449 } finally { 450 if (!satisfied) { 451 leave(); 452 } 453 } 454 } 455 456 /** 457 * Enters this monitor when the guard is satisfied. Blocks at most the given time, including both 458 * the time to acquire the lock and the time to wait for the guard to be satisfied, and may be 459 * interrupted. 460 * 461 * @return whether the monitor was entered, which guarantees that the guard is now satisfied 462 * @throws InterruptedException if interrupted while waiting 463 */ 464 @SuppressWarnings("GoodTime") // should accept a java.time.Duration 465 public boolean enterWhen(Guard guard, long time, TimeUnit unit) throws InterruptedException { 466 final long timeoutNanos = toSafeNanos(time, unit); 467 if (guard.monitor != this) { 468 throw new IllegalMonitorStateException(); 469 } 470 final ReentrantLock lock = this.lock; 471 boolean reentrant = lock.isHeldByCurrentThread(); 472 long startTime = 0L; 473 474 locked: 475 { 476 if (!fair) { 477 // Check interrupt status to get behavior consistent with fair case. 478 if (Thread.interrupted()) { 479 throw new InterruptedException(); 480 } 481 if (lock.tryLock()) { 482 break locked; 483 } 484 } 485 startTime = initNanoTime(timeoutNanos); 486 if (!lock.tryLock(time, unit)) { 487 return false; 488 } 489 } 490 491 boolean satisfied = false; 492 boolean threw = true; 493 try { 494 satisfied = 495 guard.isSatisfied() 496 || awaitNanos( 497 guard, 498 (startTime == 0L) ? timeoutNanos : remainingNanos(startTime, timeoutNanos), 499 reentrant); 500 threw = false; 501 return satisfied; 502 } finally { 503 if (!satisfied) { 504 try { 505 // Don't need to signal if timed out, but do if interrupted 506 if (threw && !reentrant) { 507 signalNextWaiter(); 508 } 509 } finally { 510 lock.unlock(); 511 } 512 } 513 } 514 } 515 516 /** Enters this monitor when the guard is satisfied. Blocks indefinitely. */ 517 public void enterWhenUninterruptibly(Guard guard) { 518 if (guard.monitor != this) { 519 throw new IllegalMonitorStateException(); 520 } 521 final ReentrantLock lock = this.lock; 522 boolean signalBeforeWaiting = lock.isHeldByCurrentThread(); 523 lock.lock(); 524 525 boolean satisfied = false; 526 try { 527 if (!guard.isSatisfied()) { 528 awaitUninterruptibly(guard, signalBeforeWaiting); 529 } 530 satisfied = true; 531 } finally { 532 if (!satisfied) { 533 leave(); 534 } 535 } 536 } 537 538 /** 539 * Enters this monitor when the guard is satisfied. Blocks at most the given time, including both 540 * the time to acquire the lock and the time to wait for the guard to be satisfied. 541 * 542 * @return whether the monitor was entered, which guarantees that the guard is now satisfied 543 */ 544 @SuppressWarnings("GoodTime") // should accept a java.time.Duration 545 public boolean enterWhenUninterruptibly(Guard guard, long time, TimeUnit unit) { 546 final long timeoutNanos = toSafeNanos(time, unit); 547 if (guard.monitor != this) { 548 throw new IllegalMonitorStateException(); 549 } 550 final ReentrantLock lock = this.lock; 551 long startTime = 0L; 552 boolean signalBeforeWaiting = lock.isHeldByCurrentThread(); 553 boolean interrupted = Thread.interrupted(); 554 try { 555 if (fair || !lock.tryLock()) { 556 startTime = initNanoTime(timeoutNanos); 557 for (long remainingNanos = timeoutNanos; ; ) { 558 try { 559 if (lock.tryLock(remainingNanos, TimeUnit.NANOSECONDS)) { 560 break; 561 } else { 562 return false; 563 } 564 } catch (InterruptedException interrupt) { 565 interrupted = true; 566 remainingNanos = remainingNanos(startTime, timeoutNanos); 567 } 568 } 569 } 570 571 boolean satisfied = false; 572 try { 573 while (true) { 574 try { 575 if (guard.isSatisfied()) { 576 satisfied = true; 577 } else { 578 final long remainingNanos; 579 if (startTime == 0L) { 580 startTime = initNanoTime(timeoutNanos); 581 remainingNanos = timeoutNanos; 582 } else { 583 remainingNanos = remainingNanos(startTime, timeoutNanos); 584 } 585 satisfied = awaitNanos(guard, remainingNanos, signalBeforeWaiting); 586 } 587 return satisfied; 588 } catch (InterruptedException interrupt) { 589 interrupted = true; 590 signalBeforeWaiting = false; 591 } 592 } 593 } finally { 594 if (!satisfied) { 595 lock.unlock(); // No need to signal if timed out 596 } 597 } 598 } finally { 599 if (interrupted) { 600 Thread.currentThread().interrupt(); 601 } 602 } 603 } 604 605 /** 606 * Enters this monitor if the guard is satisfied. Blocks indefinitely acquiring the lock, but does 607 * not wait for the guard to be satisfied. 608 * 609 * @return whether the monitor was entered, which guarantees that the guard is now satisfied 610 */ 611 public boolean enterIf(Guard guard) { 612 if (guard.monitor != this) { 613 throw new IllegalMonitorStateException(); 614 } 615 final ReentrantLock lock = this.lock; 616 lock.lock(); 617 618 boolean satisfied = false; 619 try { 620 return satisfied = guard.isSatisfied(); 621 } finally { 622 if (!satisfied) { 623 lock.unlock(); 624 } 625 } 626 } 627 628 /** 629 * Enters this monitor if the guard is satisfied. Blocks at most the given time acquiring the 630 * lock, but does not wait for the guard to be satisfied. 631 * 632 * @return whether the monitor was entered, which guarantees that the guard is now satisfied 633 */ 634 @SuppressWarnings("GoodTime") // should accept a java.time.Duration 635 public boolean enterIf(Guard guard, long time, TimeUnit unit) { 636 if (guard.monitor != this) { 637 throw new IllegalMonitorStateException(); 638 } 639 if (!enter(time, unit)) { 640 return false; 641 } 642 643 boolean satisfied = false; 644 try { 645 return satisfied = guard.isSatisfied(); 646 } finally { 647 if (!satisfied) { 648 lock.unlock(); 649 } 650 } 651 } 652 653 /** 654 * Enters this monitor if the guard is satisfied. Blocks indefinitely acquiring the lock, but does 655 * not wait for the guard to be satisfied, and may be interrupted. 656 * 657 * @return whether the monitor was entered, which guarantees that the guard is now satisfied 658 * @throws InterruptedException if interrupted while waiting 659 */ 660 public boolean enterIfInterruptibly(Guard guard) throws InterruptedException { 661 if (guard.monitor != this) { 662 throw new IllegalMonitorStateException(); 663 } 664 final ReentrantLock lock = this.lock; 665 lock.lockInterruptibly(); 666 667 boolean satisfied = false; 668 try { 669 return satisfied = guard.isSatisfied(); 670 } finally { 671 if (!satisfied) { 672 lock.unlock(); 673 } 674 } 675 } 676 677 /** 678 * Enters this monitor if the guard is satisfied. Blocks at most the given time acquiring the 679 * lock, but does not wait for the guard to be satisfied, and may be interrupted. 680 * 681 * @return whether the monitor was entered, which guarantees that the guard is now satisfied 682 */ 683 @SuppressWarnings("GoodTime") // should accept a java.time.Duration 684 public boolean enterIfInterruptibly(Guard guard, long time, TimeUnit unit) 685 throws InterruptedException { 686 if (guard.monitor != this) { 687 throw new IllegalMonitorStateException(); 688 } 689 final ReentrantLock lock = this.lock; 690 if (!lock.tryLock(time, unit)) { 691 return false; 692 } 693 694 boolean satisfied = false; 695 try { 696 return satisfied = guard.isSatisfied(); 697 } finally { 698 if (!satisfied) { 699 lock.unlock(); 700 } 701 } 702 } 703 704 /** 705 * Enters this monitor if it is possible to do so immediately and the guard is satisfied. Does not 706 * block acquiring the lock and does not wait for the guard to be satisfied. 707 * 708 * <p><b>Note:</b> This method disregards the fairness setting of this monitor. 709 * 710 * @return whether the monitor was entered, which guarantees that the guard is now satisfied 711 */ 712 public boolean tryEnterIf(Guard guard) { 713 if (guard.monitor != this) { 714 throw new IllegalMonitorStateException(); 715 } 716 final ReentrantLock lock = this.lock; 717 if (!lock.tryLock()) { 718 return false; 719 } 720 721 boolean satisfied = false; 722 try { 723 return satisfied = guard.isSatisfied(); 724 } finally { 725 if (!satisfied) { 726 lock.unlock(); 727 } 728 } 729 } 730 731 /** 732 * Waits for the guard to be satisfied. Waits indefinitely, but may be interrupted. May be called 733 * only by a thread currently occupying this monitor. 734 * 735 * @throws InterruptedException if interrupted while waiting 736 */ 737 public void waitFor(Guard guard) throws InterruptedException { 738 if (!((guard.monitor == this) & lock.isHeldByCurrentThread())) { 739 throw new IllegalMonitorStateException(); 740 } 741 if (!guard.isSatisfied()) { 742 await(guard, true); 743 } 744 } 745 746 /** 747 * Waits for the guard to be satisfied. Waits at most the given time, and may be interrupted. May 748 * be called only by a thread currently occupying this monitor. 749 * 750 * @return whether the guard is now satisfied 751 * @throws InterruptedException if interrupted while waiting 752 */ 753 @SuppressWarnings("GoodTime") // should accept a java.time.Duration 754 public boolean waitFor(Guard guard, long time, TimeUnit unit) throws InterruptedException { 755 final long timeoutNanos = toSafeNanos(time, unit); 756 if (!((guard.monitor == this) & lock.isHeldByCurrentThread())) { 757 throw new IllegalMonitorStateException(); 758 } 759 if (guard.isSatisfied()) { 760 return true; 761 } 762 if (Thread.interrupted()) { 763 throw new InterruptedException(); 764 } 765 return awaitNanos(guard, timeoutNanos, true); 766 } 767 768 /** 769 * Waits for the guard to be satisfied. Waits indefinitely. May be called only by a thread 770 * currently occupying this monitor. 771 */ 772 public void waitForUninterruptibly(Guard guard) { 773 if (!((guard.monitor == this) & lock.isHeldByCurrentThread())) { 774 throw new IllegalMonitorStateException(); 775 } 776 if (!guard.isSatisfied()) { 777 awaitUninterruptibly(guard, true); 778 } 779 } 780 781 /** 782 * Waits for the guard to be satisfied. Waits at most the given time. May be called only by a 783 * thread currently occupying this monitor. 784 * 785 * @return whether the guard is now satisfied 786 */ 787 @SuppressWarnings("GoodTime") // should accept a java.time.Duration 788 public boolean waitForUninterruptibly(Guard guard, long time, TimeUnit unit) { 789 final long timeoutNanos = toSafeNanos(time, unit); 790 if (!((guard.monitor == this) & lock.isHeldByCurrentThread())) { 791 throw new IllegalMonitorStateException(); 792 } 793 if (guard.isSatisfied()) { 794 return true; 795 } 796 boolean signalBeforeWaiting = true; 797 final long startTime = initNanoTime(timeoutNanos); 798 boolean interrupted = Thread.interrupted(); 799 try { 800 for (long remainingNanos = timeoutNanos; ; ) { 801 try { 802 return awaitNanos(guard, remainingNanos, signalBeforeWaiting); 803 } catch (InterruptedException interrupt) { 804 interrupted = true; 805 if (guard.isSatisfied()) { 806 return true; 807 } 808 signalBeforeWaiting = false; 809 remainingNanos = remainingNanos(startTime, timeoutNanos); 810 } 811 } 812 } finally { 813 if (interrupted) { 814 Thread.currentThread().interrupt(); 815 } 816 } 817 } 818 819 /** Leaves this monitor. May be called only by a thread currently occupying this monitor. */ 820 public void leave() { 821 final ReentrantLock lock = this.lock; 822 try { 823 // No need to signal if we will still be holding the lock when we return 824 if (lock.getHoldCount() == 1) { 825 signalNextWaiter(); 826 } 827 } finally { 828 lock.unlock(); // Will throw IllegalMonitorStateException if not held 829 } 830 } 831 832 /** Returns whether this monitor is using a fair ordering policy. */ 833 public boolean isFair() { 834 return fair; 835 } 836 837 /** 838 * Returns whether this monitor is occupied by any thread. This method is designed for use in 839 * monitoring of the system state, not for synchronization control. 840 */ 841 public boolean isOccupied() { 842 return lock.isLocked(); 843 } 844 845 /** 846 * Returns whether the current thread is occupying this monitor (has entered more times than it 847 * has left). 848 */ 849 public boolean isOccupiedByCurrentThread() { 850 return lock.isHeldByCurrentThread(); 851 } 852 853 /** 854 * Returns the number of times the current thread has entered this monitor in excess of the number 855 * of times it has left. Returns 0 if the current thread is not occupying this monitor. 856 */ 857 public int getOccupiedDepth() { 858 return lock.getHoldCount(); 859 } 860 861 /** 862 * Returns an estimate of the number of threads waiting to enter this monitor. The value is only 863 * an estimate because the number of threads may change dynamically while this method traverses 864 * internal data structures. This method is designed for use in monitoring of the system state, 865 * not for synchronization control. 866 */ 867 public int getQueueLength() { 868 return lock.getQueueLength(); 869 } 870 871 /** 872 * Returns whether any threads are waiting to enter this monitor. Note that because cancellations 873 * may occur at any time, a {@code true} return does not guarantee that any other thread will ever 874 * enter this monitor. This method is designed primarily for use in monitoring of the system 875 * state. 876 */ 877 public boolean hasQueuedThreads() { 878 return lock.hasQueuedThreads(); 879 } 880 881 /** 882 * Queries whether the given thread is waiting to enter this monitor. Note that because 883 * cancellations may occur at any time, a {@code true} return does not guarantee that this thread 884 * will ever enter this monitor. This method is designed primarily for use in monitoring of the 885 * system state. 886 */ 887 public boolean hasQueuedThread(Thread thread) { 888 return lock.hasQueuedThread(thread); 889 } 890 891 /** 892 * Queries whether any threads are waiting for the given guard to become satisfied. Note that 893 * because timeouts and interrupts may occur at any time, a {@code true} return does not guarantee 894 * that the guard becoming satisfied in the future will awaken any threads. This method is 895 * designed primarily for use in monitoring of the system state. 896 */ 897 public boolean hasWaiters(Guard guard) { 898 return getWaitQueueLength(guard) > 0; 899 } 900 901 /** 902 * Returns an estimate of the number of threads waiting for the given guard to become satisfied. 903 * Note that because timeouts and interrupts may occur at any time, the estimate serves only as an 904 * upper bound on the actual number of waiters. This method is designed for use in monitoring of 905 * the system state, not for synchronization control. 906 */ 907 public int getWaitQueueLength(Guard guard) { 908 if (guard.monitor != this) { 909 throw new IllegalMonitorStateException(); 910 } 911 lock.lock(); 912 try { 913 return guard.waiterCount; 914 } finally { 915 lock.unlock(); 916 } 917 } 918 919 /** 920 * Returns unit.toNanos(time), additionally ensuring the returned value is not at risk of 921 * overflowing or underflowing, by bounding the value between 0 and (Long.MAX_VALUE / 4) * 3. 922 * Actually waiting for more than 219 years is not supported! 923 */ 924 private static long toSafeNanos(long time, TimeUnit unit) { 925 long timeoutNanos = unit.toNanos(time); 926 return Longs.constrainToRange(timeoutNanos, 0L, (Long.MAX_VALUE / 4) * 3); 927 } 928 929 /** 930 * Returns System.nanoTime() unless the timeout has already elapsed. Returns 0L if and only if the 931 * timeout has already elapsed. 932 */ 933 private static long initNanoTime(long timeoutNanos) { 934 if (timeoutNanos <= 0L) { 935 return 0L; 936 } else { 937 long startTime = System.nanoTime(); 938 return (startTime == 0L) ? 1L : startTime; 939 } 940 } 941 942 /** 943 * Returns the remaining nanos until the given timeout, or 0L if the timeout has already elapsed. 944 * Caller must have previously sanitized timeoutNanos using toSafeNanos. 945 */ 946 private static long remainingNanos(long startTime, long timeoutNanos) { 947 // assert timeoutNanos == 0L || startTime != 0L; 948 949 // TODO : NOT CORRECT, BUT TESTS PASS ANYWAYS! 950 // if (true) return timeoutNanos; 951 // ONLY 2 TESTS FAIL IF WE DO: 952 // if (true) return 0; 953 954 return (timeoutNanos <= 0L) ? 0L : timeoutNanos - (System.nanoTime() - startTime); 955 } 956 957 /** 958 * Signals some other thread waiting on a satisfied guard, if one exists. 959 * 960 * <p>We manage calls to this method carefully, to signal only when necessary, but never losing a 961 * signal, which is the classic problem of this kind of concurrency construct. We must signal if 962 * the current thread is about to relinquish the lock and may have changed the state protected by 963 * the monitor, thereby causing some guard to be satisfied. 964 * 965 * <p>In addition, any thread that has been signalled when its guard was satisfied acquires the 966 * responsibility of signalling the next thread when it again relinquishes the lock. Unlike a 967 * normal Condition, there is no guarantee that an interrupted thread has not been signalled, 968 * since the concurrency control must manage multiple Conditions. So this method must generally be 969 * called when waits are interrupted. 970 * 971 * <p>On the other hand, if a signalled thread wakes up to discover that its guard is still not 972 * satisfied, it does *not* need to call this method before returning to wait. This can only 973 * happen due to spurious wakeup (ignorable) or another thread acquiring the lock before the 974 * current thread can and returning the guard to the unsatisfied state. In the latter case the 975 * other thread (last thread modifying the state protected by the monitor) takes over the 976 * responsibility of signalling the next waiter. 977 * 978 * <p>This method must not be called from within a beginWaitingFor/endWaitingFor block, or else 979 * the current thread's guard might be mistakenly signalled, leading to a lost signal. 980 */ 981 @GuardedBy("lock") 982 private void signalNextWaiter() { 983 for (Guard guard = activeGuards; guard != null; guard = guard.next) { 984 if (isSatisfied(guard)) { 985 guard.condition.signal(); 986 break; 987 } 988 } 989 } 990 991 /** 992 * Exactly like signalNextWaiter, but caller guarantees that guardToSkip need not be considered, 993 * because caller has previously checked that guardToSkip.isSatisfied() returned false. An 994 * optimization for the case that guardToSkip.isSatisfied() may be expensive. 995 * 996 * <p>We decided against using this method, since in practice, isSatisfied() is likely to be very 997 * cheap (typically one field read). Resurrect this method if you find that not to be true. 998 */ 999 // @GuardedBy("lock") 1000 // private void signalNextWaiterSkipping(Guard guardToSkip) { 1001 // for (Guard guard = activeGuards; guard != null; guard = guard.next) { 1002 // if (guard != guardToSkip && isSatisfied(guard)) { 1003 // guard.condition.signal(); 1004 // break; 1005 // } 1006 // } 1007 // } 1008 1009 /** 1010 * Exactly like guard.isSatisfied(), but in addition signals all waiting threads in the (hopefully 1011 * unlikely) event that isSatisfied() throws. 1012 */ 1013 @GuardedBy("lock") 1014 private boolean isSatisfied(Guard guard) { 1015 try { 1016 return guard.isSatisfied(); 1017 } catch (Throwable throwable) { 1018 signalAllWaiters(); 1019 throw throwable; 1020 } 1021 } 1022 1023 /** Signals all threads waiting on guards. */ 1024 @GuardedBy("lock") 1025 private void signalAllWaiters() { 1026 for (Guard guard = activeGuards; guard != null; guard = guard.next) { 1027 guard.condition.signalAll(); 1028 } 1029 } 1030 1031 /** Records that the current thread is about to wait on the specified guard. */ 1032 @GuardedBy("lock") 1033 private void beginWaitingFor(Guard guard) { 1034 int waiters = guard.waiterCount++; 1035 if (waiters == 0) { 1036 // push guard onto activeGuards 1037 guard.next = activeGuards; 1038 activeGuards = guard; 1039 } 1040 } 1041 1042 /** Records that the current thread is no longer waiting on the specified guard. */ 1043 @GuardedBy("lock") 1044 private void endWaitingFor(Guard guard) { 1045 int waiters = --guard.waiterCount; 1046 if (waiters == 0) { 1047 // unlink guard from activeGuards 1048 for (Guard p = activeGuards, pred = null; ; pred = p, p = p.next) { 1049 if (p == guard) { 1050 if (pred == null) { 1051 activeGuards = p.next; 1052 } else { 1053 pred.next = p.next; 1054 } 1055 p.next = null; // help GC 1056 break; 1057 } 1058 } 1059 } 1060 } 1061 1062 /* 1063 * Methods that loop waiting on a guard's condition until the guard is satisfied, while recording 1064 * this fact so that other threads know to check our guard and signal us. It's caller's 1065 * responsibility to ensure that the guard is *not* currently satisfied. 1066 */ 1067 1068 @GuardedBy("lock") 1069 private void await(Guard guard, boolean signalBeforeWaiting) throws InterruptedException { 1070 if (signalBeforeWaiting) { 1071 signalNextWaiter(); 1072 } 1073 beginWaitingFor(guard); 1074 try { 1075 do { 1076 guard.condition.await(); 1077 } while (!guard.isSatisfied()); 1078 } finally { 1079 endWaitingFor(guard); 1080 } 1081 } 1082 1083 @GuardedBy("lock") 1084 private void awaitUninterruptibly(Guard guard, boolean signalBeforeWaiting) { 1085 if (signalBeforeWaiting) { 1086 signalNextWaiter(); 1087 } 1088 beginWaitingFor(guard); 1089 try { 1090 do { 1091 guard.condition.awaitUninterruptibly(); 1092 } while (!guard.isSatisfied()); 1093 } finally { 1094 endWaitingFor(guard); 1095 } 1096 } 1097 1098 /** Caller should check before calling that guard is not satisfied. */ 1099 @GuardedBy("lock") 1100 private boolean awaitNanos(Guard guard, long nanos, boolean signalBeforeWaiting) 1101 throws InterruptedException { 1102 boolean firstTime = true; 1103 try { 1104 do { 1105 if (nanos <= 0L) { 1106 return false; 1107 } 1108 if (firstTime) { 1109 if (signalBeforeWaiting) { 1110 signalNextWaiter(); 1111 } 1112 beginWaitingFor(guard); 1113 firstTime = false; 1114 } 1115 nanos = guard.condition.awaitNanos(nanos); 1116 } while (!guard.isSatisfied()); 1117 return true; 1118 } finally { 1119 if (!firstTime) { 1120 endWaitingFor(guard); 1121 } 1122 } 1123 } 1124}