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.GwtIncompatible; 020import com.google.common.annotations.J2ktIncompatible; 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@J2ktIncompatible 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 public abstract static class Guard { 305 306 @Weak final Monitor monitor; 307 final Condition condition; 308 309 @GuardedBy("monitor.lock") 310 int waiterCount = 0; 311 312 /** The next active guard */ 313 @GuardedBy("monitor.lock") 314 @CheckForNull 315 Guard next; 316 317 protected Guard(Monitor monitor) { 318 this.monitor = checkNotNull(monitor, "monitor"); 319 this.condition = monitor.lock.newCondition(); 320 } 321 322 /** 323 * Evaluates this guard's boolean condition. This method is always called with the associated 324 * monitor already occupied. Implementations of this method must depend only on state protected 325 * by the associated monitor, and must not modify that state. 326 */ 327 public abstract boolean isSatisfied(); 328 } 329 330 /** Whether this monitor is fair. */ 331 private final boolean fair; 332 333 /** The lock underlying this monitor. */ 334 private final ReentrantLock lock; 335 336 /** 337 * The guards associated with this monitor that currently have waiters ({@code waiterCount > 0}). 338 * A linked list threaded through the Guard.next field. 339 */ 340 @GuardedBy("lock") 341 @CheckForNull 342 private Guard activeGuards = null; 343 344 /** 345 * Creates a monitor with a non-fair (but fast) ordering policy. Equivalent to {@code 346 * Monitor(false)}. 347 */ 348 public Monitor() { 349 this(false); 350 } 351 352 /** 353 * Creates a monitor with the given ordering policy. 354 * 355 * @param fair whether this monitor should use a fair ordering policy rather than a non-fair (but 356 * fast) one 357 */ 358 public Monitor(boolean fair) { 359 this.fair = fair; 360 this.lock = new ReentrantLock(fair); 361 } 362 363 /** Enters this monitor. Blocks indefinitely. */ 364 public void enter() { 365 lock.lock(); 366 } 367 368 /** 369 * Enters this monitor. Blocks at most the given time. 370 * 371 * @return whether the monitor was entered 372 */ 373 @SuppressWarnings("GoodTime") // should accept a java.time.Duration 374 public boolean enter(long time, TimeUnit unit) { 375 final long timeoutNanos = toSafeNanos(time, unit); 376 final ReentrantLock lock = this.lock; 377 if (!fair && lock.tryLock()) { 378 return true; 379 } 380 boolean interrupted = Thread.interrupted(); 381 try { 382 final long startTime = System.nanoTime(); 383 for (long remainingNanos = timeoutNanos; ; ) { 384 try { 385 return lock.tryLock(remainingNanos, TimeUnit.NANOSECONDS); 386 } catch (InterruptedException interrupt) { 387 interrupted = true; 388 remainingNanos = remainingNanos(startTime, timeoutNanos); 389 } 390 } 391 } finally { 392 if (interrupted) { 393 Thread.currentThread().interrupt(); 394 } 395 } 396 } 397 398 /** 399 * Enters this monitor. Blocks indefinitely, but may be interrupted. 400 * 401 * @throws InterruptedException if interrupted while waiting 402 */ 403 public void enterInterruptibly() throws InterruptedException { 404 lock.lockInterruptibly(); 405 } 406 407 /** 408 * Enters this monitor. Blocks at most the given time, and may be interrupted. 409 * 410 * @return whether the monitor was entered 411 * @throws InterruptedException if interrupted while waiting 412 */ 413 @SuppressWarnings("GoodTime") // should accept a java.time.Duration 414 public boolean enterInterruptibly(long time, TimeUnit unit) throws InterruptedException { 415 return lock.tryLock(time, unit); 416 } 417 418 /** 419 * Enters this monitor if it is possible to do so immediately. Does not block. 420 * 421 * <p><b>Note:</b> This method disregards the fairness setting of this monitor. 422 * 423 * @return whether the monitor was entered 424 */ 425 public boolean tryEnter() { 426 return lock.tryLock(); 427 } 428 429 /** 430 * Enters this monitor when the guard is satisfied. Blocks indefinitely, but may be interrupted. 431 * 432 * @throws InterruptedException if interrupted while waiting 433 */ 434 public void enterWhen(Guard guard) throws InterruptedException { 435 if (guard.monitor != this) { 436 throw new IllegalMonitorStateException(); 437 } 438 final ReentrantLock lock = this.lock; 439 boolean signalBeforeWaiting = lock.isHeldByCurrentThread(); 440 lock.lockInterruptibly(); 441 442 boolean satisfied = false; 443 try { 444 if (!guard.isSatisfied()) { 445 await(guard, signalBeforeWaiting); 446 } 447 satisfied = true; 448 } finally { 449 if (!satisfied) { 450 leave(); 451 } 452 } 453 } 454 455 /** 456 * Enters this monitor when the guard is satisfied. Blocks at most the given time, including both 457 * the time to acquire the lock and the time to wait for the guard to be satisfied, and may be 458 * interrupted. 459 * 460 * @return whether the monitor was entered, which guarantees that the guard is now satisfied 461 * @throws InterruptedException if interrupted while waiting 462 */ 463 @SuppressWarnings("GoodTime") // should accept a java.time.Duration 464 public boolean enterWhen(Guard guard, long time, TimeUnit unit) throws InterruptedException { 465 final long timeoutNanos = toSafeNanos(time, unit); 466 if (guard.monitor != this) { 467 throw new IllegalMonitorStateException(); 468 } 469 final ReentrantLock lock = this.lock; 470 boolean reentrant = lock.isHeldByCurrentThread(); 471 long startTime = 0L; 472 473 locked: 474 { 475 if (!fair) { 476 // Check interrupt status to get behavior consistent with fair case. 477 if (Thread.interrupted()) { 478 throw new InterruptedException(); 479 } 480 if (lock.tryLock()) { 481 break locked; 482 } 483 } 484 startTime = initNanoTime(timeoutNanos); 485 if (!lock.tryLock(time, unit)) { 486 return false; 487 } 488 } 489 490 boolean satisfied = false; 491 boolean threw = true; 492 try { 493 satisfied = 494 guard.isSatisfied() 495 || awaitNanos( 496 guard, 497 (startTime == 0L) ? timeoutNanos : remainingNanos(startTime, timeoutNanos), 498 reentrant); 499 threw = false; 500 return satisfied; 501 } finally { 502 if (!satisfied) { 503 try { 504 // Don't need to signal if timed out, but do if interrupted 505 if (threw && !reentrant) { 506 signalNextWaiter(); 507 } 508 } finally { 509 lock.unlock(); 510 } 511 } 512 } 513 } 514 515 /** Enters this monitor when the guard is satisfied. Blocks indefinitely. */ 516 public void enterWhenUninterruptibly(Guard guard) { 517 if (guard.monitor != this) { 518 throw new IllegalMonitorStateException(); 519 } 520 final ReentrantLock lock = this.lock; 521 boolean signalBeforeWaiting = lock.isHeldByCurrentThread(); 522 lock.lock(); 523 524 boolean satisfied = false; 525 try { 526 if (!guard.isSatisfied()) { 527 awaitUninterruptibly(guard, signalBeforeWaiting); 528 } 529 satisfied = true; 530 } finally { 531 if (!satisfied) { 532 leave(); 533 } 534 } 535 } 536 537 /** 538 * Enters this monitor when the guard is satisfied. Blocks at most the given time, including both 539 * the time to acquire the lock and the time to wait for the guard to be satisfied. 540 * 541 * @return whether the monitor was entered, which guarantees that the guard is now satisfied 542 */ 543 @SuppressWarnings("GoodTime") // should accept a java.time.Duration 544 public boolean enterWhenUninterruptibly(Guard guard, long time, TimeUnit unit) { 545 final long timeoutNanos = toSafeNanos(time, unit); 546 if (guard.monitor != this) { 547 throw new IllegalMonitorStateException(); 548 } 549 final ReentrantLock lock = this.lock; 550 long startTime = 0L; 551 boolean signalBeforeWaiting = lock.isHeldByCurrentThread(); 552 boolean interrupted = Thread.interrupted(); 553 try { 554 if (fair || !lock.tryLock()) { 555 startTime = initNanoTime(timeoutNanos); 556 for (long remainingNanos = timeoutNanos; ; ) { 557 try { 558 if (lock.tryLock(remainingNanos, TimeUnit.NANOSECONDS)) { 559 break; 560 } else { 561 return false; 562 } 563 } catch (InterruptedException interrupt) { 564 interrupted = true; 565 remainingNanos = remainingNanos(startTime, timeoutNanos); 566 } 567 } 568 } 569 570 boolean satisfied = false; 571 try { 572 while (true) { 573 try { 574 if (guard.isSatisfied()) { 575 satisfied = true; 576 } else { 577 final long remainingNanos; 578 if (startTime == 0L) { 579 startTime = initNanoTime(timeoutNanos); 580 remainingNanos = timeoutNanos; 581 } else { 582 remainingNanos = remainingNanos(startTime, timeoutNanos); 583 } 584 satisfied = awaitNanos(guard, remainingNanos, signalBeforeWaiting); 585 } 586 return satisfied; 587 } catch (InterruptedException interrupt) { 588 interrupted = true; 589 signalBeforeWaiting = false; 590 } 591 } 592 } finally { 593 if (!satisfied) { 594 lock.unlock(); // No need to signal if timed out 595 } 596 } 597 } finally { 598 if (interrupted) { 599 Thread.currentThread().interrupt(); 600 } 601 } 602 } 603 604 /** 605 * Enters this monitor if the guard is satisfied. Blocks indefinitely acquiring the lock, but does 606 * not wait for the guard to be satisfied. 607 * 608 * @return whether the monitor was entered, which guarantees that the guard is now satisfied 609 */ 610 public boolean enterIf(Guard guard) { 611 if (guard.monitor != this) { 612 throw new IllegalMonitorStateException(); 613 } 614 final ReentrantLock lock = this.lock; 615 lock.lock(); 616 617 boolean satisfied = false; 618 try { 619 return satisfied = guard.isSatisfied(); 620 } finally { 621 if (!satisfied) { 622 lock.unlock(); 623 } 624 } 625 } 626 627 /** 628 * Enters this monitor if the guard is satisfied. Blocks at most the given time acquiring the 629 * lock, but does not wait for the guard to be satisfied. 630 * 631 * @return whether the monitor was entered, which guarantees that the guard is now satisfied 632 */ 633 @SuppressWarnings("GoodTime") // should accept a java.time.Duration 634 public boolean enterIf(Guard guard, long time, TimeUnit unit) { 635 if (guard.monitor != this) { 636 throw new IllegalMonitorStateException(); 637 } 638 if (!enter(time, unit)) { 639 return false; 640 } 641 642 boolean satisfied = false; 643 try { 644 return satisfied = guard.isSatisfied(); 645 } finally { 646 if (!satisfied) { 647 lock.unlock(); 648 } 649 } 650 } 651 652 /** 653 * Enters this monitor if the guard is satisfied. Blocks indefinitely acquiring the lock, but does 654 * not wait for the guard to be satisfied, and may be interrupted. 655 * 656 * @return whether the monitor was entered, which guarantees that the guard is now satisfied 657 * @throws InterruptedException if interrupted while waiting 658 */ 659 public boolean enterIfInterruptibly(Guard guard) throws InterruptedException { 660 if (guard.monitor != this) { 661 throw new IllegalMonitorStateException(); 662 } 663 final ReentrantLock lock = this.lock; 664 lock.lockInterruptibly(); 665 666 boolean satisfied = false; 667 try { 668 return satisfied = guard.isSatisfied(); 669 } finally { 670 if (!satisfied) { 671 lock.unlock(); 672 } 673 } 674 } 675 676 /** 677 * Enters this monitor if the guard is satisfied. Blocks at most the given time acquiring the 678 * lock, but does not wait for the guard to be satisfied, and may be interrupted. 679 * 680 * @return whether the monitor was entered, which guarantees that the guard is now satisfied 681 */ 682 @SuppressWarnings("GoodTime") // should accept a java.time.Duration 683 public boolean enterIfInterruptibly(Guard guard, long time, TimeUnit unit) 684 throws InterruptedException { 685 if (guard.monitor != this) { 686 throw new IllegalMonitorStateException(); 687 } 688 final ReentrantLock lock = this.lock; 689 if (!lock.tryLock(time, unit)) { 690 return false; 691 } 692 693 boolean satisfied = false; 694 try { 695 return satisfied = guard.isSatisfied(); 696 } finally { 697 if (!satisfied) { 698 lock.unlock(); 699 } 700 } 701 } 702 703 /** 704 * Enters this monitor if it is possible to do so immediately and the guard is satisfied. Does not 705 * block acquiring the lock and does not wait for the guard to be satisfied. 706 * 707 * <p><b>Note:</b> This method disregards the fairness setting of this monitor. 708 * 709 * @return whether the monitor was entered, which guarantees that the guard is now satisfied 710 */ 711 public boolean tryEnterIf(Guard guard) { 712 if (guard.monitor != this) { 713 throw new IllegalMonitorStateException(); 714 } 715 final ReentrantLock lock = this.lock; 716 if (!lock.tryLock()) { 717 return false; 718 } 719 720 boolean satisfied = false; 721 try { 722 return satisfied = guard.isSatisfied(); 723 } finally { 724 if (!satisfied) { 725 lock.unlock(); 726 } 727 } 728 } 729 730 /** 731 * Waits for the guard to be satisfied. Waits indefinitely, but may be interrupted. May be called 732 * only by a thread currently occupying this monitor. 733 * 734 * @throws InterruptedException if interrupted while waiting 735 */ 736 public void waitFor(Guard guard) throws InterruptedException { 737 if (!((guard.monitor == this) && lock.isHeldByCurrentThread())) { 738 throw new IllegalMonitorStateException(); 739 } 740 if (!guard.isSatisfied()) { 741 await(guard, true); 742 } 743 } 744 745 /** 746 * Waits for the guard to be satisfied. Waits at most the given time, and may be interrupted. May 747 * be called only by a thread currently occupying this monitor. 748 * 749 * @return whether the guard is now satisfied 750 * @throws InterruptedException if interrupted while waiting 751 */ 752 @SuppressWarnings("GoodTime") // should accept a java.time.Duration 753 public boolean waitFor(Guard guard, long time, TimeUnit unit) throws InterruptedException { 754 final long timeoutNanos = toSafeNanos(time, unit); 755 if (!((guard.monitor == this) && lock.isHeldByCurrentThread())) { 756 throw new IllegalMonitorStateException(); 757 } 758 if (guard.isSatisfied()) { 759 return true; 760 } 761 if (Thread.interrupted()) { 762 throw new InterruptedException(); 763 } 764 return awaitNanos(guard, timeoutNanos, true); 765 } 766 767 /** 768 * Waits for the guard to be satisfied. Waits indefinitely. May be called only by a thread 769 * currently occupying this monitor. 770 */ 771 public void waitForUninterruptibly(Guard guard) { 772 if (!((guard.monitor == this) && lock.isHeldByCurrentThread())) { 773 throw new IllegalMonitorStateException(); 774 } 775 if (!guard.isSatisfied()) { 776 awaitUninterruptibly(guard, true); 777 } 778 } 779 780 /** 781 * Waits for the guard to be satisfied. Waits at most the given time. May be called only by a 782 * thread currently occupying this monitor. 783 * 784 * @return whether the guard is now satisfied 785 */ 786 @SuppressWarnings("GoodTime") // should accept a java.time.Duration 787 public boolean waitForUninterruptibly(Guard guard, long time, TimeUnit unit) { 788 final long timeoutNanos = toSafeNanos(time, unit); 789 if (!((guard.monitor == this) && lock.isHeldByCurrentThread())) { 790 throw new IllegalMonitorStateException(); 791 } 792 if (guard.isSatisfied()) { 793 return true; 794 } 795 boolean signalBeforeWaiting = true; 796 final long startTime = initNanoTime(timeoutNanos); 797 boolean interrupted = Thread.interrupted(); 798 try { 799 for (long remainingNanos = timeoutNanos; ; ) { 800 try { 801 return awaitNanos(guard, remainingNanos, signalBeforeWaiting); 802 } catch (InterruptedException interrupt) { 803 interrupted = true; 804 if (guard.isSatisfied()) { 805 return true; 806 } 807 signalBeforeWaiting = false; 808 remainingNanos = remainingNanos(startTime, timeoutNanos); 809 } 810 } 811 } finally { 812 if (interrupted) { 813 Thread.currentThread().interrupt(); 814 } 815 } 816 } 817 818 /** Leaves this monitor. May be called only by a thread currently occupying this monitor. */ 819 public void leave() { 820 final ReentrantLock lock = this.lock; 821 try { 822 // No need to signal if we will still be holding the lock when we return 823 if (lock.getHoldCount() == 1) { 824 signalNextWaiter(); 825 } 826 } finally { 827 lock.unlock(); // Will throw IllegalMonitorStateException if not held 828 } 829 } 830 831 /** Returns whether this monitor is using a fair ordering policy. */ 832 public boolean isFair() { 833 return fair; 834 } 835 836 /** 837 * Returns whether this monitor is occupied by any thread. This method is designed for use in 838 * monitoring of the system state, not for synchronization control. 839 */ 840 public boolean isOccupied() { 841 return lock.isLocked(); 842 } 843 844 /** 845 * Returns whether the current thread is occupying this monitor (has entered more times than it 846 * has left). 847 */ 848 public boolean isOccupiedByCurrentThread() { 849 return lock.isHeldByCurrentThread(); 850 } 851 852 /** 853 * Returns the number of times the current thread has entered this monitor in excess of the number 854 * of times it has left. Returns 0 if the current thread is not occupying this monitor. 855 */ 856 public int getOccupiedDepth() { 857 return lock.getHoldCount(); 858 } 859 860 /** 861 * Returns an estimate of the number of threads waiting to enter this monitor. The value is only 862 * an estimate because the number of threads may change dynamically while this method traverses 863 * internal data structures. This method is designed for use in monitoring of the system state, 864 * not for synchronization control. 865 */ 866 public int getQueueLength() { 867 return lock.getQueueLength(); 868 } 869 870 /** 871 * Returns whether any threads are waiting to enter this monitor. Note that because cancellations 872 * may occur at any time, a {@code true} return does not guarantee that any other thread will ever 873 * enter this monitor. This method is designed primarily for use in monitoring of the system 874 * state. 875 */ 876 public boolean hasQueuedThreads() { 877 return lock.hasQueuedThreads(); 878 } 879 880 /** 881 * Queries whether the given thread is waiting to enter this monitor. Note that because 882 * cancellations may occur at any time, a {@code true} return does not guarantee that this thread 883 * will ever enter this monitor. This method is designed primarily for use in monitoring of the 884 * system state. 885 */ 886 public boolean hasQueuedThread(Thread thread) { 887 return lock.hasQueuedThread(thread); 888 } 889 890 /** 891 * Queries whether any threads are waiting for the given guard to become satisfied. Note that 892 * because timeouts and interrupts may occur at any time, a {@code true} return does not guarantee 893 * that the guard becoming satisfied in the future will awaken any threads. This method is 894 * designed primarily for use in monitoring of the system state. 895 */ 896 public boolean hasWaiters(Guard guard) { 897 return getWaitQueueLength(guard) > 0; 898 } 899 900 /** 901 * Returns an estimate of the number of threads waiting for the given guard to become satisfied. 902 * Note that because timeouts and interrupts may occur at any time, the estimate serves only as an 903 * upper bound on the actual number of waiters. This method is designed for use in monitoring of 904 * the system state, not for synchronization control. 905 */ 906 public int getWaitQueueLength(Guard guard) { 907 if (guard.monitor != this) { 908 throw new IllegalMonitorStateException(); 909 } 910 lock.lock(); 911 try { 912 return guard.waiterCount; 913 } finally { 914 lock.unlock(); 915 } 916 } 917 918 /** 919 * Returns unit.toNanos(time), additionally ensuring the returned value is not at risk of 920 * overflowing or underflowing, by bounding the value between 0 and (Long.MAX_VALUE / 4) * 3. 921 * Actually waiting for more than 219 years is not supported! 922 */ 923 private static long toSafeNanos(long time, TimeUnit unit) { 924 long timeoutNanos = unit.toNanos(time); 925 return Longs.constrainToRange(timeoutNanos, 0L, (Long.MAX_VALUE / 4) * 3); 926 } 927 928 /** 929 * Returns System.nanoTime() unless the timeout has already elapsed. Returns 0L if and only if the 930 * timeout has already elapsed. 931 */ 932 private static long initNanoTime(long timeoutNanos) { 933 if (timeoutNanos <= 0L) { 934 return 0L; 935 } else { 936 long startTime = System.nanoTime(); 937 return (startTime == 0L) ? 1L : startTime; 938 } 939 } 940 941 /** 942 * Returns the remaining nanos until the given timeout, or 0L if the timeout has already elapsed. 943 * Caller must have previously sanitized timeoutNanos using toSafeNanos. 944 */ 945 private static long remainingNanos(long startTime, long timeoutNanos) { 946 // assert timeoutNanos == 0L || startTime != 0L; 947 948 // TODO : NOT CORRECT, BUT TESTS PASS ANYWAYS! 949 // if (true) return timeoutNanos; 950 // ONLY 2 TESTS FAIL IF WE DO: 951 // if (true) return 0; 952 953 return (timeoutNanos <= 0L) ? 0L : timeoutNanos - (System.nanoTime() - startTime); 954 } 955 956 /** 957 * Signals some other thread waiting on a satisfied guard, if one exists. 958 * 959 * <p>We manage calls to this method carefully, to signal only when necessary, but never losing a 960 * signal, which is the classic problem of this kind of concurrency construct. We must signal if 961 * the current thread is about to relinquish the lock and may have changed the state protected by 962 * the monitor, thereby causing some guard to be satisfied. 963 * 964 * <p>In addition, any thread that has been signalled when its guard was satisfied acquires the 965 * responsibility of signalling the next thread when it again relinquishes the lock. Unlike a 966 * normal Condition, there is no guarantee that an interrupted thread has not been signalled, 967 * since the concurrency control must manage multiple Conditions. So this method must generally be 968 * called when waits are interrupted. 969 * 970 * <p>On the other hand, if a signalled thread wakes up to discover that its guard is still not 971 * satisfied, it does *not* need to call this method before returning to wait. This can only 972 * happen due to spurious wakeup (ignorable) or another thread acquiring the lock before the 973 * current thread can and returning the guard to the unsatisfied state. In the latter case the 974 * other thread (last thread modifying the state protected by the monitor) takes over the 975 * responsibility of signalling the next waiter. 976 * 977 * <p>This method must not be called from within a beginWaitingFor/endWaitingFor block, or else 978 * the current thread's guard might be mistakenly signalled, leading to a lost signal. 979 */ 980 @GuardedBy("lock") 981 private void signalNextWaiter() { 982 for (Guard guard = activeGuards; guard != null; guard = guard.next) { 983 if (isSatisfied(guard)) { 984 guard.condition.signal(); 985 break; 986 } 987 } 988 } 989 990 /** 991 * Exactly like signalNextWaiter, but caller guarantees that guardToSkip need not be considered, 992 * because caller has previously checked that guardToSkip.isSatisfied() returned false. An 993 * optimization for the case that guardToSkip.isSatisfied() may be expensive. 994 * 995 * <p>We decided against using this method, since in practice, isSatisfied() is likely to be very 996 * cheap (typically one field read). Resurrect this method if you find that not to be true. 997 */ 998 // @GuardedBy("lock") 999 // private void signalNextWaiterSkipping(Guard guardToSkip) { 1000 // for (Guard guard = activeGuards; guard != null; guard = guard.next) { 1001 // if (guard != guardToSkip && isSatisfied(guard)) { 1002 // guard.condition.signal(); 1003 // break; 1004 // } 1005 // } 1006 // } 1007 1008 /** 1009 * Exactly like guard.isSatisfied(), but in addition signals all waiting threads in the (hopefully 1010 * unlikely) event that isSatisfied() throws. 1011 */ 1012 @GuardedBy("lock") 1013 private boolean isSatisfied(Guard guard) { 1014 try { 1015 return guard.isSatisfied(); 1016 } catch (RuntimeException | Error throwable) { 1017 signalAllWaiters(); 1018 throw throwable; 1019 } 1020 } 1021 1022 /** Signals all threads waiting on guards. */ 1023 @GuardedBy("lock") 1024 private void signalAllWaiters() { 1025 for (Guard guard = activeGuards; guard != null; guard = guard.next) { 1026 guard.condition.signalAll(); 1027 } 1028 } 1029 1030 /** Records that the current thread is about to wait on the specified guard. */ 1031 @GuardedBy("lock") 1032 private void beginWaitingFor(Guard guard) { 1033 int waiters = guard.waiterCount++; 1034 if (waiters == 0) { 1035 // push guard onto activeGuards 1036 guard.next = activeGuards; 1037 activeGuards = guard; 1038 } 1039 } 1040 1041 /** Records that the current thread is no longer waiting on the specified guard. */ 1042 @GuardedBy("lock") 1043 private void endWaitingFor(Guard guard) { 1044 int waiters = --guard.waiterCount; 1045 if (waiters == 0) { 1046 // unlink guard from activeGuards 1047 for (Guard p = activeGuards, pred = null; ; pred = p, p = p.next) { 1048 if (p == guard) { 1049 if (pred == null) { 1050 activeGuards = p.next; 1051 } else { 1052 pred.next = p.next; 1053 } 1054 p.next = null; // help GC 1055 break; 1056 } 1057 } 1058 } 1059 } 1060 1061 /* 1062 * Methods that loop waiting on a guard's condition until the guard is satisfied, while recording 1063 * this fact so that other threads know to check our guard and signal us. It's caller's 1064 * responsibility to ensure that the guard is *not* currently satisfied. 1065 */ 1066 1067 @GuardedBy("lock") 1068 private void await(Guard guard, boolean signalBeforeWaiting) throws InterruptedException { 1069 if (signalBeforeWaiting) { 1070 signalNextWaiter(); 1071 } 1072 beginWaitingFor(guard); 1073 try { 1074 do { 1075 guard.condition.await(); 1076 } while (!guard.isSatisfied()); 1077 } finally { 1078 endWaitingFor(guard); 1079 } 1080 } 1081 1082 @GuardedBy("lock") 1083 private void awaitUninterruptibly(Guard guard, boolean signalBeforeWaiting) { 1084 if (signalBeforeWaiting) { 1085 signalNextWaiter(); 1086 } 1087 beginWaitingFor(guard); 1088 try { 1089 do { 1090 guard.condition.awaitUninterruptibly(); 1091 } while (!guard.isSatisfied()); 1092 } finally { 1093 endWaitingFor(guard); 1094 } 1095 } 1096 1097 /** Caller should check before calling that guard is not satisfied. */ 1098 @GuardedBy("lock") 1099 private boolean awaitNanos(Guard guard, long nanos, boolean signalBeforeWaiting) 1100 throws InterruptedException { 1101 boolean firstTime = true; 1102 try { 1103 do { 1104 if (nanos <= 0L) { 1105 return false; 1106 } 1107 if (firstTime) { 1108 if (signalBeforeWaiting) { 1109 signalNextWaiter(); 1110 } 1111 beginWaitingFor(guard); 1112 firstTime = false; 1113 } 1114 nanos = guard.condition.awaitNanos(nanos); 1115 } while (!guard.isSatisfied()); 1116 return true; 1117 } finally { 1118 if (!firstTime) { 1119 endWaitingFor(guard); 1120 } 1121 } 1122 } 1123}