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