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.errorprone.annotations.concurrent.GuardedBy; 022import com.google.j2objc.annotations.Weak; 023import java.util.concurrent.TimeUnit; 024import java.util.concurrent.locks.Condition; 025import java.util.concurrent.locks.ReentrantLock; 026import java.util.function.BooleanSupplier; 027import org.checkerframework.checker.nullness.qual.Nullable; 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. 203public final class Monitor { 204 // TODO(user): Use raw LockSupport or AbstractQueuedSynchronizer instead of ReentrantLock. 205 // TODO(user): "Port" jsr166 tests for ReentrantLock. 206 // 207 // TODO(user): Change API to make it impossible to use a Guard with the "wrong" monitor, 208 // by making the monitor implicit, and to eliminate other sources of IMSE. 209 // Imagine: 210 // guard.lock(); 211 // try { /* monitor locked and guard satisfied here */ } 212 // finally { guard.unlock(); } 213 // Here are Justin's design notes about this: 214 // 215 // This idea has come up from time to time, and I think one of my 216 // earlier versions of Monitor even did something like this. I ended 217 // up strongly favoring the current interface. 218 // 219 // I probably can't remember all the reasons (it's possible you 220 // could find them in the code review archives), but here are a few: 221 // 222 // 1. What about leaving/unlocking? Are you going to do 223 // guard.enter() paired with monitor.leave()? That might get 224 // confusing. It's nice for the finally block to look as close as 225 // possible to the thing right before the try. You could have 226 // guard.leave(), but that's a little odd as well because the 227 // guard doesn't have anything to do with leaving. You can't 228 // really enforce that the guard you're leaving is the same one 229 // you entered with, and it doesn't actually matter. 230 // 231 // 2. Since you can enter the monitor without a guard at all, some 232 // places you'll have monitor.enter()/monitor.leave() and other 233 // places you'll have guard.enter()/guard.leave() even though 234 // it's the same lock being acquired underneath. Always using 235 // monitor.enterXXX()/monitor.leave() will make it really clear 236 // which lock is held at any point in the code. 237 // 238 // 3. I think "enterWhen(notEmpty)" reads better than "notEmpty.enter()". 239 // 240 // TODO(user): Implement ReentrantLock features: 241 // - toString() method 242 // - getOwner() method 243 // - getQueuedThreads() method 244 // - getWaitingThreads(Guard) method 245 // - implement Serializable 246 // - redo the API to be as close to identical to ReentrantLock as possible, 247 // since, after all, this class is also a reentrant mutual exclusion lock!? 248 249 /* 250 * One of the key challenges of this class is to prevent lost signals, while trying hard to 251 * minimize unnecessary signals. One simple and correct algorithm is to signal some other waiter 252 * with a satisfied guard (if one exists) whenever any thread occupying the monitor exits the 253 * monitor, either by unlocking all of its held locks, or by starting to wait for a guard. This 254 * includes exceptional exits, so all control paths involving signalling must be protected by a 255 * finally block. 256 * 257 * Further optimizations of this algorithm become increasingly subtle. A wait that terminates 258 * without the guard being satisfied (due to timeout, but not interrupt) can then immediately exit 259 * the monitor without signalling. If it timed out without being signalled, it does not need to 260 * "pass on" the signal to another thread. If it *was* signalled, then its guard must have been 261 * satisfied at the time of signal, and has since been modified by some other thread to be 262 * non-satisfied before reacquiring the lock, and that other thread takes over the responsibility 263 * of signaling the next waiter. 264 * 265 * Unlike the underlying Condition, if we are not careful, an interrupt *can* cause a signal to be 266 * lost, because the signal may be sent to a condition whose sole waiter has just been 267 * interrupted. 268 * 269 * Imagine a monitor with multiple guards. A thread enters the monitor, satisfies all the guards, 270 * and leaves, calling signalNextWaiter. With traditional locks and conditions, all the conditions 271 * need to be signalled because it is not known which if any of them have waiters (and hasWaiters 272 * can't be used reliably because of a check-then-act race). With our Monitor guards, we only 273 * signal the first active guard that is satisfied. But the corresponding thread may have already 274 * been interrupted and is waiting to reacquire the lock while still registered in activeGuards, 275 * in which case the signal is a no-op, and the bigger-picture signal is lost unless interrupted 276 * threads take special action by participating in the signal-passing game. 277 */ 278 279 /* 280 * Timeout handling is intricate, especially given our ambitious goals: 281 * - Avoid underflow and overflow of timeout values when specified timeouts are close to 282 * Long.MIN_VALUE or Long.MAX_VALUE. 283 * - Favor responding to interrupts over timeouts. 284 * - System.nanoTime() is expensive enough that we want to call it the minimum required number of 285 * times, typically once before invoking a blocking method. This often requires keeping track of 286 * the first time in a method that nanoTime() has been invoked, for which the special value 0L 287 * is reserved to mean "uninitialized". If timeout is non-positive, then nanoTime need never be 288 * called. 289 * - Keep behavior of fair and non-fair instances consistent. 290 */ 291 292 /** 293 * A boolean condition for which a thread may wait. A {@code Guard} is associated with a single 294 * {@code Monitor}. The monitor may check the guard at arbitrary times from any thread occupying 295 * the monitor, so code should not be written to rely on how often a guard might or might not be 296 * checked. 297 * 298 * <p>If a {@code Guard} is passed into any method of a {@code Monitor} other than the one it is 299 * associated with, an {@link IllegalMonitorStateException} is thrown. 300 * 301 * @since 10.0 302 */ 303 @Beta 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 @Nullable 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 private Guard activeGuards = null; 342 343 /** 344 * Creates a monitor with a non-fair (but fast) ordering policy. Equivalent to {@code 345 * Monitor(false)}. 346 */ 347 public Monitor() { 348 this(false); 349 } 350 351 /** 352 * Creates a monitor with the given ordering policy. 353 * 354 * @param fair whether this monitor should use a fair ordering policy rather than a non-fair (but 355 * fast) one 356 */ 357 public Monitor(boolean fair) { 358 this.fair = fair; 359 this.lock = new ReentrantLock(fair); 360 } 361 362 /** 363 * Creates a new {@linkplain Guard guard} for this monitor. 364 * 365 * @param isSatisfied the new guard's boolean condition (see {@link Guard#isSatisfied 366 * isSatisfied()}) 367 * @since 21.0 368 */ 369 public Guard newGuard(final BooleanSupplier isSatisfied) { 370 checkNotNull(isSatisfied, "isSatisfied"); 371 return new Guard(this) { 372 @Override 373 public boolean isSatisfied() { 374 return isSatisfied.getAsBoolean(); 375 } 376 }; 377 } 378 379 /** Enters this monitor. Blocks indefinitely. */ 380 public void enter() { 381 lock.lock(); 382 } 383 384 /** 385 * Enters this monitor. Blocks at most the given time. 386 * 387 * @return whether the monitor was entered 388 */ 389 @SuppressWarnings("GoodTime") // should accept a java.time.Duration 390 public boolean enter(long time, TimeUnit unit) { 391 final long timeoutNanos = toSafeNanos(time, unit); 392 final ReentrantLock lock = this.lock; 393 if (!fair && lock.tryLock()) { 394 return true; 395 } 396 boolean interrupted = Thread.interrupted(); 397 try { 398 final long startTime = System.nanoTime(); 399 for (long remainingNanos = timeoutNanos; ; ) { 400 try { 401 return lock.tryLock(remainingNanos, TimeUnit.NANOSECONDS); 402 } catch (InterruptedException interrupt) { 403 interrupted = true; 404 remainingNanos = remainingNanos(startTime, timeoutNanos); 405 } 406 } 407 } finally { 408 if (interrupted) { 409 Thread.currentThread().interrupt(); 410 } 411 } 412 } 413 414 /** 415 * Enters this monitor. Blocks indefinitely, but may be interrupted. 416 * 417 * @throws InterruptedException if interrupted while waiting 418 */ 419 public void enterInterruptibly() throws InterruptedException { 420 lock.lockInterruptibly(); 421 } 422 423 /** 424 * Enters this monitor. Blocks at most the given time, and may be interrupted. 425 * 426 * @return whether the monitor was entered 427 * @throws InterruptedException if interrupted while waiting 428 */ 429 @SuppressWarnings("GoodTime") // should accept a java.time.Duration 430 public boolean enterInterruptibly(long time, TimeUnit unit) throws InterruptedException { 431 return lock.tryLock(time, unit); 432 } 433 434 /** 435 * Enters this monitor if it is possible to do so immediately. Does not block. 436 * 437 * <p><b>Note:</b> This method disregards the fairness setting of this monitor. 438 * 439 * @return whether the monitor was entered 440 */ 441 public boolean tryEnter() { 442 return lock.tryLock(); 443 } 444 445 /** 446 * Enters this monitor when the guard is satisfied. Blocks indefinitely, but may be interrupted. 447 * 448 * @throws InterruptedException if interrupted while waiting 449 */ 450 public void enterWhen(Guard guard) throws InterruptedException { 451 if (guard.monitor != this) { 452 throw new IllegalMonitorStateException(); 453 } 454 final ReentrantLock lock = this.lock; 455 boolean signalBeforeWaiting = lock.isHeldByCurrentThread(); 456 lock.lockInterruptibly(); 457 458 boolean satisfied = false; 459 try { 460 if (!guard.isSatisfied()) { 461 await(guard, signalBeforeWaiting); 462 } 463 satisfied = true; 464 } finally { 465 if (!satisfied) { 466 leave(); 467 } 468 } 469 } 470 471 /** 472 * Enters this monitor when the guard is satisfied. Blocks at most the given time, including both 473 * the time to acquire the lock and the time to wait for the guard to be satisfied, and may be 474 * interrupted. 475 * 476 * @return whether the monitor was entered, which guarantees that the guard is now satisfied 477 * @throws InterruptedException if interrupted while waiting 478 */ 479 @SuppressWarnings("GoodTime") // should accept a java.time.Duration 480 public boolean enterWhen(Guard guard, long time, TimeUnit unit) throws InterruptedException { 481 final long timeoutNanos = toSafeNanos(time, unit); 482 if (guard.monitor != this) { 483 throw new IllegalMonitorStateException(); 484 } 485 final ReentrantLock lock = this.lock; 486 boolean reentrant = lock.isHeldByCurrentThread(); 487 long startTime = 0L; 488 489 locked: 490 { 491 if (!fair) { 492 // Check interrupt status to get behavior consistent with fair case. 493 if (Thread.interrupted()) { 494 throw new InterruptedException(); 495 } 496 if (lock.tryLock()) { 497 break locked; 498 } 499 } 500 startTime = initNanoTime(timeoutNanos); 501 if (!lock.tryLock(time, unit)) { 502 return false; 503 } 504 } 505 506 boolean satisfied = false; 507 boolean threw = true; 508 try { 509 satisfied = 510 guard.isSatisfied() 511 || awaitNanos( 512 guard, 513 (startTime == 0L) ? timeoutNanos : remainingNanos(startTime, timeoutNanos), 514 reentrant); 515 threw = false; 516 return satisfied; 517 } finally { 518 if (!satisfied) { 519 try { 520 // Don't need to signal if timed out, but do if interrupted 521 if (threw && !reentrant) { 522 signalNextWaiter(); 523 } 524 } finally { 525 lock.unlock(); 526 } 527 } 528 } 529 } 530 531 /** Enters this monitor when the guard is satisfied. Blocks indefinitely. */ 532 public void enterWhenUninterruptibly(Guard guard) { 533 if (guard.monitor != this) { 534 throw new IllegalMonitorStateException(); 535 } 536 final ReentrantLock lock = this.lock; 537 boolean signalBeforeWaiting = lock.isHeldByCurrentThread(); 538 lock.lock(); 539 540 boolean satisfied = false; 541 try { 542 if (!guard.isSatisfied()) { 543 awaitUninterruptibly(guard, signalBeforeWaiting); 544 } 545 satisfied = true; 546 } finally { 547 if (!satisfied) { 548 leave(); 549 } 550 } 551 } 552 553 /** 554 * Enters this monitor when the guard is satisfied. Blocks at most the given time, including both 555 * the time to acquire the lock and the time to wait for the guard to be satisfied. 556 * 557 * @return whether the monitor was entered, which guarantees that the guard is now satisfied 558 */ 559 @SuppressWarnings("GoodTime") // should accept a java.time.Duration 560 public boolean enterWhenUninterruptibly(Guard guard, long time, TimeUnit unit) { 561 final long timeoutNanos = toSafeNanos(time, unit); 562 if (guard.monitor != this) { 563 throw new IllegalMonitorStateException(); 564 } 565 final ReentrantLock lock = this.lock; 566 long startTime = 0L; 567 boolean signalBeforeWaiting = lock.isHeldByCurrentThread(); 568 boolean interrupted = Thread.interrupted(); 569 try { 570 if (fair || !lock.tryLock()) { 571 startTime = initNanoTime(timeoutNanos); 572 for (long remainingNanos = timeoutNanos; ; ) { 573 try { 574 if (lock.tryLock(remainingNanos, TimeUnit.NANOSECONDS)) { 575 break; 576 } else { 577 return false; 578 } 579 } catch (InterruptedException interrupt) { 580 interrupted = true; 581 remainingNanos = remainingNanos(startTime, timeoutNanos); 582 } 583 } 584 } 585 586 boolean satisfied = false; 587 try { 588 while (true) { 589 try { 590 if (guard.isSatisfied()) { 591 satisfied = true; 592 } else { 593 final long remainingNanos; 594 if (startTime == 0L) { 595 startTime = initNanoTime(timeoutNanos); 596 remainingNanos = timeoutNanos; 597 } else { 598 remainingNanos = remainingNanos(startTime, timeoutNanos); 599 } 600 satisfied = awaitNanos(guard, remainingNanos, signalBeforeWaiting); 601 } 602 return satisfied; 603 } catch (InterruptedException interrupt) { 604 interrupted = true; 605 signalBeforeWaiting = false; 606 } 607 } 608 } finally { 609 if (!satisfied) { 610 lock.unlock(); // No need to signal if timed out 611 } 612 } 613 } finally { 614 if (interrupted) { 615 Thread.currentThread().interrupt(); 616 } 617 } 618 } 619 620 /** 621 * Enters this monitor if the guard is satisfied. Blocks indefinitely acquiring the lock, but does 622 * not wait for the guard to be satisfied. 623 * 624 * @return whether the monitor was entered, which guarantees that the guard is now satisfied 625 */ 626 public boolean enterIf(Guard guard) { 627 if (guard.monitor != this) { 628 throw new IllegalMonitorStateException(); 629 } 630 final ReentrantLock lock = this.lock; 631 lock.lock(); 632 633 boolean satisfied = false; 634 try { 635 return satisfied = guard.isSatisfied(); 636 } finally { 637 if (!satisfied) { 638 lock.unlock(); 639 } 640 } 641 } 642 643 /** 644 * Enters this monitor if the guard is satisfied. Blocks at most the given time acquiring the 645 * lock, but does not wait for the guard to be satisfied. 646 * 647 * @return whether the monitor was entered, which guarantees that the guard is now satisfied 648 */ 649 @SuppressWarnings("GoodTime") // should accept a java.time.Duration 650 public boolean enterIf(Guard guard, long time, TimeUnit unit) { 651 if (guard.monitor != this) { 652 throw new IllegalMonitorStateException(); 653 } 654 if (!enter(time, unit)) { 655 return false; 656 } 657 658 boolean satisfied = false; 659 try { 660 return satisfied = guard.isSatisfied(); 661 } finally { 662 if (!satisfied) { 663 lock.unlock(); 664 } 665 } 666 } 667 668 /** 669 * Enters this monitor if the guard is satisfied. Blocks indefinitely acquiring the lock, but does 670 * not wait for the guard to be satisfied, and may be interrupted. 671 * 672 * @return whether the monitor was entered, which guarantees that the guard is now satisfied 673 * @throws InterruptedException if interrupted while waiting 674 */ 675 public boolean enterIfInterruptibly(Guard guard) throws InterruptedException { 676 if (guard.monitor != this) { 677 throw new IllegalMonitorStateException(); 678 } 679 final ReentrantLock lock = this.lock; 680 lock.lockInterruptibly(); 681 682 boolean satisfied = false; 683 try { 684 return satisfied = guard.isSatisfied(); 685 } finally { 686 if (!satisfied) { 687 lock.unlock(); 688 } 689 } 690 } 691 692 /** 693 * Enters this monitor if the guard is satisfied. Blocks at most the given time acquiring the 694 * lock, but does not wait for the guard to be satisfied, and may be interrupted. 695 * 696 * @return whether the monitor was entered, which guarantees that the guard is now satisfied 697 */ 698 @SuppressWarnings("GoodTime") // should accept a java.time.Duration 699 public boolean enterIfInterruptibly(Guard guard, long time, TimeUnit unit) 700 throws InterruptedException { 701 if (guard.monitor != this) { 702 throw new IllegalMonitorStateException(); 703 } 704 final ReentrantLock lock = this.lock; 705 if (!lock.tryLock(time, unit)) { 706 return false; 707 } 708 709 boolean satisfied = false; 710 try { 711 return satisfied = guard.isSatisfied(); 712 } finally { 713 if (!satisfied) { 714 lock.unlock(); 715 } 716 } 717 } 718 719 /** 720 * Enters this monitor if it is possible to do so immediately and the guard is satisfied. Does not 721 * block acquiring the lock and does not wait for the guard to be satisfied. 722 * 723 * <p><b>Note:</b> This method disregards the fairness setting of this monitor. 724 * 725 * @return whether the monitor was entered, which guarantees that the guard is now satisfied 726 */ 727 public boolean tryEnterIf(Guard guard) { 728 if (guard.monitor != this) { 729 throw new IllegalMonitorStateException(); 730 } 731 final ReentrantLock lock = this.lock; 732 if (!lock.tryLock()) { 733 return false; 734 } 735 736 boolean satisfied = false; 737 try { 738 return satisfied = guard.isSatisfied(); 739 } finally { 740 if (!satisfied) { 741 lock.unlock(); 742 } 743 } 744 } 745 746 /** 747 * Waits for the guard to be satisfied. Waits indefinitely, but may be interrupted. May be called 748 * only by a thread currently occupying this monitor. 749 * 750 * @throws InterruptedException if interrupted while waiting 751 */ 752 public void waitFor(Guard guard) throws InterruptedException { 753 if (!((guard.monitor == this) & lock.isHeldByCurrentThread())) { 754 throw new IllegalMonitorStateException(); 755 } 756 if (!guard.isSatisfied()) { 757 await(guard, true); 758 } 759 } 760 761 /** 762 * Waits for the guard to be satisfied. Waits at most the given time, and may be interrupted. May 763 * be called only by a thread currently occupying this monitor. 764 * 765 * @return whether the guard is now satisfied 766 * @throws InterruptedException if interrupted while waiting 767 */ 768 @SuppressWarnings("GoodTime") // should accept a java.time.Duration 769 public boolean waitFor(Guard guard, long time, TimeUnit unit) throws InterruptedException { 770 final long timeoutNanos = toSafeNanos(time, unit); 771 if (!((guard.monitor == this) & lock.isHeldByCurrentThread())) { 772 throw new IllegalMonitorStateException(); 773 } 774 if (guard.isSatisfied()) { 775 return true; 776 } 777 if (Thread.interrupted()) { 778 throw new InterruptedException(); 779 } 780 return awaitNanos(guard, timeoutNanos, true); 781 } 782 783 /** 784 * Waits for the guard to be satisfied. Waits indefinitely. May be called only by a thread 785 * currently occupying this monitor. 786 */ 787 public void waitForUninterruptibly(Guard guard) { 788 if (!((guard.monitor == this) & lock.isHeldByCurrentThread())) { 789 throw new IllegalMonitorStateException(); 790 } 791 if (!guard.isSatisfied()) { 792 awaitUninterruptibly(guard, true); 793 } 794 } 795 796 /** 797 * Waits for the guard to be satisfied. Waits at most the given time. May be called only by a 798 * thread currently occupying this monitor. 799 * 800 * @return whether the guard is now satisfied 801 */ 802 @SuppressWarnings("GoodTime") // should accept a java.time.Duration 803 public boolean waitForUninterruptibly(Guard guard, long time, TimeUnit unit) { 804 final long timeoutNanos = toSafeNanos(time, unit); 805 if (!((guard.monitor == this) & lock.isHeldByCurrentThread())) { 806 throw new IllegalMonitorStateException(); 807 } 808 if (guard.isSatisfied()) { 809 return true; 810 } 811 boolean signalBeforeWaiting = true; 812 final long startTime = initNanoTime(timeoutNanos); 813 boolean interrupted = Thread.interrupted(); 814 try { 815 for (long remainingNanos = timeoutNanos; ; ) { 816 try { 817 return awaitNanos(guard, remainingNanos, signalBeforeWaiting); 818 } catch (InterruptedException interrupt) { 819 interrupted = true; 820 if (guard.isSatisfied()) { 821 return true; 822 } 823 signalBeforeWaiting = false; 824 remainingNanos = remainingNanos(startTime, timeoutNanos); 825 } 826 } 827 } finally { 828 if (interrupted) { 829 Thread.currentThread().interrupt(); 830 } 831 } 832 } 833 834 /** Leaves this monitor. May be called only by a thread currently occupying this monitor. */ 835 public void leave() { 836 final ReentrantLock lock = this.lock; 837 try { 838 // No need to signal if we will still be holding the lock when we return 839 if (lock.getHoldCount() == 1) { 840 signalNextWaiter(); 841 } 842 } finally { 843 lock.unlock(); // Will throw IllegalMonitorStateException if not held 844 } 845 } 846 847 /** Returns whether this monitor is using a fair ordering policy. */ 848 public boolean isFair() { 849 return fair; 850 } 851 852 /** 853 * Returns whether this monitor is occupied by any thread. This method is designed for use in 854 * monitoring of the system state, not for synchronization control. 855 */ 856 public boolean isOccupied() { 857 return lock.isLocked(); 858 } 859 860 /** 861 * Returns whether the current thread is occupying this monitor (has entered more times than it 862 * has left). 863 */ 864 public boolean isOccupiedByCurrentThread() { 865 return lock.isHeldByCurrentThread(); 866 } 867 868 /** 869 * Returns the number of times the current thread has entered this monitor in excess of the number 870 * of times it has left. Returns 0 if the current thread is not occupying this monitor. 871 */ 872 public int getOccupiedDepth() { 873 return lock.getHoldCount(); 874 } 875 876 /** 877 * Returns an estimate of the number of threads waiting to enter this monitor. The value is only 878 * an estimate because the number of threads may change dynamically while this method traverses 879 * internal data structures. This method is designed for use in monitoring of the system state, 880 * not for synchronization control. 881 */ 882 public int getQueueLength() { 883 return lock.getQueueLength(); 884 } 885 886 /** 887 * Returns whether any threads are waiting to enter this monitor. Note that because cancellations 888 * may occur at any time, a {@code true} return does not guarantee that any other thread will ever 889 * enter this monitor. This method is designed primarily for use in monitoring of the system 890 * state. 891 */ 892 public boolean hasQueuedThreads() { 893 return lock.hasQueuedThreads(); 894 } 895 896 /** 897 * Queries whether the given thread is waiting to enter this monitor. Note that because 898 * cancellations may occur at any time, a {@code true} return does not guarantee that this thread 899 * will ever enter this monitor. This method is designed primarily for use in monitoring of the 900 * system state. 901 */ 902 public boolean hasQueuedThread(Thread thread) { 903 return lock.hasQueuedThread(thread); 904 } 905 906 /** 907 * Queries whether any threads are waiting for the given guard to become satisfied. Note that 908 * because timeouts and interrupts may occur at any time, a {@code true} return does not guarantee 909 * that the guard becoming satisfied in the future will awaken any threads. This method is 910 * designed primarily for use in monitoring of the system state. 911 */ 912 public boolean hasWaiters(Guard guard) { 913 return getWaitQueueLength(guard) > 0; 914 } 915 916 /** 917 * Returns an estimate of the number of threads waiting for the given guard to become satisfied. 918 * Note that because timeouts and interrupts may occur at any time, the estimate serves only as an 919 * upper bound on the actual number of waiters. This method is designed for use in monitoring of 920 * the system state, not for synchronization control. 921 */ 922 public int getWaitQueueLength(Guard guard) { 923 if (guard.monitor != this) { 924 throw new IllegalMonitorStateException(); 925 } 926 lock.lock(); 927 try { 928 return guard.waiterCount; 929 } finally { 930 lock.unlock(); 931 } 932 } 933 934 /** 935 * Returns unit.toNanos(time), additionally ensuring the returned value is not at risk of 936 * overflowing or underflowing, by bounding the value between 0 and (Long.MAX_VALUE / 4) * 3. 937 * Actually waiting for more than 219 years is not supported! 938 */ 939 private static long toSafeNanos(long time, TimeUnit unit) { 940 long timeoutNanos = unit.toNanos(time); 941 return (timeoutNanos <= 0L) 942 ? 0L 943 : (timeoutNanos > (Long.MAX_VALUE / 4) * 3) ? (Long.MAX_VALUE / 4) * 3 : timeoutNanos; 944 } 945 946 /** 947 * Returns System.nanoTime() unless the timeout has already elapsed. Returns 0L if and only if the 948 * timeout has already elapsed. 949 */ 950 private static long initNanoTime(long timeoutNanos) { 951 if (timeoutNanos <= 0L) { 952 return 0L; 953 } else { 954 long startTime = System.nanoTime(); 955 return (startTime == 0L) ? 1L : startTime; 956 } 957 } 958 959 /** 960 * Returns the remaining nanos until the given timeout, or 0L if the timeout has already elapsed. 961 * Caller must have previously sanitized timeoutNanos using toSafeNanos. 962 */ 963 private static long remainingNanos(long startTime, long timeoutNanos) { 964 // assert timeoutNanos == 0L || startTime != 0L; 965 966 // TODO : NOT CORRECT, BUT TESTS PASS ANYWAYS! 967 // if (true) return timeoutNanos; 968 // ONLY 2 TESTS FAIL IF WE DO: 969 // if (true) return 0; 970 971 return (timeoutNanos <= 0L) ? 0L : timeoutNanos - (System.nanoTime() - startTime); 972 } 973 974 /** 975 * Signals some other thread waiting on a satisfied guard, if one exists. 976 * 977 * <p>We manage calls to this method carefully, to signal only when necessary, but never losing a 978 * signal, which is the classic problem of this kind of concurrency construct. We must signal if 979 * the current thread is about to relinquish the lock and may have changed the state protected by 980 * the monitor, thereby causing some guard to be satisfied. 981 * 982 * <p>In addition, any thread that has been signalled when its guard was satisfied acquires the 983 * responsibility of signalling the next thread when it again relinquishes the lock. Unlike a 984 * normal Condition, there is no guarantee that an interrupted thread has not been signalled, 985 * since the concurrency control must manage multiple Conditions. So this method must generally be 986 * called when waits are interrupted. 987 * 988 * <p>On the other hand, if a signalled thread wakes up to discover that its guard is still not 989 * satisfied, it does *not* need to call this method before returning to wait. This can only 990 * happen due to spurious wakeup (ignorable) or another thread acquiring the lock before the 991 * current thread can and returning the guard to the unsatisfied state. In the latter case the 992 * other thread (last thread modifying the state protected by the monitor) takes over the 993 * responsibility of signalling the next waiter. 994 * 995 * <p>This method must not be called from within a beginWaitingFor/endWaitingFor block, or else 996 * the current thread's guard might be mistakenly signalled, leading to a lost signal. 997 */ 998 @GuardedBy("lock") 999 private void signalNextWaiter() { 1000 for (Guard guard = activeGuards; guard != null; guard = guard.next) { 1001 if (isSatisfied(guard)) { 1002 guard.condition.signal(); 1003 break; 1004 } 1005 } 1006 } 1007 1008 /** 1009 * Exactly like signalNextWaiter, but caller guarantees that guardToSkip need not be considered, 1010 * because caller has previously checked that guardToSkip.isSatisfied() returned false. An 1011 * optimization for the case that guardToSkip.isSatisfied() may be expensive. 1012 * 1013 * <p>We decided against using this method, since in practice, isSatisfied() is likely to be very 1014 * cheap (typically one field read). Resurrect this method if you find that not to be true. 1015 */ 1016 // @GuardedBy("lock") 1017 // private void signalNextWaiterSkipping(Guard guardToSkip) { 1018 // for (Guard guard = activeGuards; guard != null; guard = guard.next) { 1019 // if (guard != guardToSkip && isSatisfied(guard)) { 1020 // guard.condition.signal(); 1021 // break; 1022 // } 1023 // } 1024 // } 1025 1026 /** 1027 * Exactly like guard.isSatisfied(), but in addition signals all waiting threads in the (hopefully 1028 * unlikely) event that isSatisfied() throws. 1029 */ 1030 @GuardedBy("lock") 1031 private boolean isSatisfied(Guard guard) { 1032 try { 1033 return guard.isSatisfied(); 1034 } catch (Throwable throwable) { 1035 signalAllWaiters(); 1036 throw throwable; 1037 } 1038 } 1039 1040 /** Signals all threads waiting on guards. */ 1041 @GuardedBy("lock") 1042 private void signalAllWaiters() { 1043 for (Guard guard = activeGuards; guard != null; guard = guard.next) { 1044 guard.condition.signalAll(); 1045 } 1046 } 1047 1048 /** Records that the current thread is about to wait on the specified guard. */ 1049 @GuardedBy("lock") 1050 private void beginWaitingFor(Guard guard) { 1051 int waiters = guard.waiterCount++; 1052 if (waiters == 0) { 1053 // push guard onto activeGuards 1054 guard.next = activeGuards; 1055 activeGuards = guard; 1056 } 1057 } 1058 1059 /** Records that the current thread is no longer waiting on the specified guard. */ 1060 @GuardedBy("lock") 1061 private void endWaitingFor(Guard guard) { 1062 int waiters = --guard.waiterCount; 1063 if (waiters == 0) { 1064 // unlink guard from activeGuards 1065 for (Guard p = activeGuards, pred = null; ; pred = p, p = p.next) { 1066 if (p == guard) { 1067 if (pred == null) { 1068 activeGuards = p.next; 1069 } else { 1070 pred.next = p.next; 1071 } 1072 p.next = null; // help GC 1073 break; 1074 } 1075 } 1076 } 1077 } 1078 1079 /* 1080 * Methods that loop waiting on a guard's condition until the guard is satisfied, while recording 1081 * this fact so that other threads know to check our guard and signal us. It's caller's 1082 * responsibility to ensure that the guard is *not* currently satisfied. 1083 */ 1084 1085 @GuardedBy("lock") 1086 private void await(Guard guard, boolean signalBeforeWaiting) throws InterruptedException { 1087 if (signalBeforeWaiting) { 1088 signalNextWaiter(); 1089 } 1090 beginWaitingFor(guard); 1091 try { 1092 do { 1093 guard.condition.await(); 1094 } while (!guard.isSatisfied()); 1095 } finally { 1096 endWaitingFor(guard); 1097 } 1098 } 1099 1100 @GuardedBy("lock") 1101 private void awaitUninterruptibly(Guard guard, boolean signalBeforeWaiting) { 1102 if (signalBeforeWaiting) { 1103 signalNextWaiter(); 1104 } 1105 beginWaitingFor(guard); 1106 try { 1107 do { 1108 guard.condition.awaitUninterruptibly(); 1109 } while (!guard.isSatisfied()); 1110 } finally { 1111 endWaitingFor(guard); 1112 } 1113 } 1114 1115 /** Caller should check before calling that guard is not satisfied. */ 1116 @GuardedBy("lock") 1117 private boolean awaitNanos(Guard guard, long nanos, boolean signalBeforeWaiting) 1118 throws InterruptedException { 1119 boolean firstTime = true; 1120 try { 1121 do { 1122 if (nanos <= 0L) { 1123 return false; 1124 } 1125 if (firstTime) { 1126 if (signalBeforeWaiting) { 1127 signalNextWaiter(); 1128 } 1129 beginWaitingFor(guard); 1130 firstTime = false; 1131 } 1132 nanos = guard.condition.awaitNanos(nanos); 1133 } while (!guard.isSatisfied()); 1134 return true; 1135 } finally { 1136 if (!firstTime) { 1137 endWaitingFor(guard); 1138 } 1139 } 1140 } 1141}