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.saturatedToNanos; 019 020import com.google.common.annotations.Beta; 021import com.google.common.annotations.GwtIncompatible; 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 org.checkerframework.checker.nullness.qual.Nullable; 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@Beta 203@GwtIncompatible 204@SuppressWarnings("GuardedBy") // TODO(b/35466881): Fix or suppress. 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 @Beta 306 public abstract static class Guard { 307 308 @Weak final Monitor monitor; 309 final Condition condition; 310 311 @GuardedBy("monitor.lock") 312 int waiterCount = 0; 313 314 /** The next active guard */ 315 @GuardedBy("monitor.lock") 316 @Nullable 317 Guard next; 318 319 protected Guard(Monitor monitor) { 320 this.monitor = checkNotNull(monitor, "monitor"); 321 this.condition = monitor.lock.newCondition(); 322 } 323 324 /** 325 * Evaluates this guard's boolean condition. This method is always called with the associated 326 * monitor already occupied. Implementations of this method must depend only on state protected 327 * by the associated monitor, and must not modify that state. 328 */ 329 public abstract boolean isSatisfied(); 330 } 331 332 /** Whether this monitor is fair. */ 333 private final boolean fair; 334 335 /** The lock underlying this monitor. */ 336 private final ReentrantLock lock; 337 338 /** 339 * The guards associated with this monitor that currently have waiters ({@code waiterCount > 0}). 340 * A linked list threaded through the Guard.next field. 341 */ 342 @GuardedBy("lock") 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(saturatedToNanos(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(saturatedToNanos(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, saturatedToNanos(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, saturatedToNanos(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, saturatedToNanos(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, saturatedToNanos(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, saturatedToNanos(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, saturatedToNanos(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 (timeoutNanos <= 0L) 1034 ? 0L 1035 : (timeoutNanos > (Long.MAX_VALUE / 4) * 3) ? (Long.MAX_VALUE / 4) * 3 : timeoutNanos; 1036 } 1037 1038 /** 1039 * Returns System.nanoTime() unless the timeout has already elapsed. Returns 0L if and only if the 1040 * timeout has already elapsed. 1041 */ 1042 private static long initNanoTime(long timeoutNanos) { 1043 if (timeoutNanos <= 0L) { 1044 return 0L; 1045 } else { 1046 long startTime = System.nanoTime(); 1047 return (startTime == 0L) ? 1L : startTime; 1048 } 1049 } 1050 1051 /** 1052 * Returns the remaining nanos until the given timeout, or 0L if the timeout has already elapsed. 1053 * Caller must have previously sanitized timeoutNanos using toSafeNanos. 1054 */ 1055 private static long remainingNanos(long startTime, long timeoutNanos) { 1056 // assert timeoutNanos == 0L || startTime != 0L; 1057 1058 // TODO : NOT CORRECT, BUT TESTS PASS ANYWAYS! 1059 // if (true) return timeoutNanos; 1060 // ONLY 2 TESTS FAIL IF WE DO: 1061 // if (true) return 0; 1062 1063 return (timeoutNanos <= 0L) ? 0L : timeoutNanos - (System.nanoTime() - startTime); 1064 } 1065 1066 /** 1067 * Signals some other thread waiting on a satisfied guard, if one exists. 1068 * 1069 * <p>We manage calls to this method carefully, to signal only when necessary, but never losing a 1070 * signal, which is the classic problem of this kind of concurrency construct. We must signal if 1071 * the current thread is about to relinquish the lock and may have changed the state protected by 1072 * the monitor, thereby causing some guard to be satisfied. 1073 * 1074 * <p>In addition, any thread that has been signalled when its guard was satisfied acquires the 1075 * responsibility of signalling the next thread when it again relinquishes the lock. Unlike a 1076 * normal Condition, there is no guarantee that an interrupted thread has not been signalled, 1077 * since the concurrency control must manage multiple Conditions. So this method must generally be 1078 * called when waits are interrupted. 1079 * 1080 * <p>On the other hand, if a signalled thread wakes up to discover that its guard is still not 1081 * satisfied, it does *not* need to call this method before returning to wait. This can only 1082 * happen due to spurious wakeup (ignorable) or another thread acquiring the lock before the 1083 * current thread can and returning the guard to the unsatisfied state. In the latter case the 1084 * other thread (last thread modifying the state protected by the monitor) takes over the 1085 * responsibility of signalling the next waiter. 1086 * 1087 * <p>This method must not be called from within a beginWaitingFor/endWaitingFor block, or else 1088 * the current thread's guard might be mistakenly signalled, leading to a lost signal. 1089 */ 1090 @GuardedBy("lock") 1091 private void signalNextWaiter() { 1092 for (Guard guard = activeGuards; guard != null; guard = guard.next) { 1093 if (isSatisfied(guard)) { 1094 guard.condition.signal(); 1095 break; 1096 } 1097 } 1098 } 1099 1100 /** 1101 * Exactly like signalNextWaiter, but caller guarantees that guardToSkip need not be considered, 1102 * because caller has previously checked that guardToSkip.isSatisfied() returned false. An 1103 * optimization for the case that guardToSkip.isSatisfied() may be expensive. 1104 * 1105 * <p>We decided against using this method, since in practice, isSatisfied() is likely to be very 1106 * cheap (typically one field read). Resurrect this method if you find that not to be true. 1107 */ 1108 // @GuardedBy("lock") 1109 // private void signalNextWaiterSkipping(Guard guardToSkip) { 1110 // for (Guard guard = activeGuards; guard != null; guard = guard.next) { 1111 // if (guard != guardToSkip && isSatisfied(guard)) { 1112 // guard.condition.signal(); 1113 // break; 1114 // } 1115 // } 1116 // } 1117 1118 /** 1119 * Exactly like guard.isSatisfied(), but in addition signals all waiting threads in the (hopefully 1120 * unlikely) event that isSatisfied() throws. 1121 */ 1122 @GuardedBy("lock") 1123 private boolean isSatisfied(Guard guard) { 1124 try { 1125 return guard.isSatisfied(); 1126 } catch (Throwable throwable) { 1127 signalAllWaiters(); 1128 throw throwable; 1129 } 1130 } 1131 1132 /** Signals all threads waiting on guards. */ 1133 @GuardedBy("lock") 1134 private void signalAllWaiters() { 1135 for (Guard guard = activeGuards; guard != null; guard = guard.next) { 1136 guard.condition.signalAll(); 1137 } 1138 } 1139 1140 /** Records that the current thread is about to wait on the specified guard. */ 1141 @GuardedBy("lock") 1142 private void beginWaitingFor(Guard guard) { 1143 int waiters = guard.waiterCount++; 1144 if (waiters == 0) { 1145 // push guard onto activeGuards 1146 guard.next = activeGuards; 1147 activeGuards = guard; 1148 } 1149 } 1150 1151 /** Records that the current thread is no longer waiting on the specified guard. */ 1152 @GuardedBy("lock") 1153 private void endWaitingFor(Guard guard) { 1154 int waiters = --guard.waiterCount; 1155 if (waiters == 0) { 1156 // unlink guard from activeGuards 1157 for (Guard p = activeGuards, pred = null; ; pred = p, p = p.next) { 1158 if (p == guard) { 1159 if (pred == null) { 1160 activeGuards = p.next; 1161 } else { 1162 pred.next = p.next; 1163 } 1164 p.next = null; // help GC 1165 break; 1166 } 1167 } 1168 } 1169 } 1170 1171 /* 1172 * Methods that loop waiting on a guard's condition until the guard is satisfied, while recording 1173 * this fact so that other threads know to check our guard and signal us. It's caller's 1174 * responsibility to ensure that the guard is *not* currently satisfied. 1175 */ 1176 1177 @GuardedBy("lock") 1178 private void await(Guard guard, boolean signalBeforeWaiting) throws InterruptedException { 1179 if (signalBeforeWaiting) { 1180 signalNextWaiter(); 1181 } 1182 beginWaitingFor(guard); 1183 try { 1184 do { 1185 guard.condition.await(); 1186 } while (!guard.isSatisfied()); 1187 } finally { 1188 endWaitingFor(guard); 1189 } 1190 } 1191 1192 @GuardedBy("lock") 1193 private void awaitUninterruptibly(Guard guard, boolean signalBeforeWaiting) { 1194 if (signalBeforeWaiting) { 1195 signalNextWaiter(); 1196 } 1197 beginWaitingFor(guard); 1198 try { 1199 do { 1200 guard.condition.awaitUninterruptibly(); 1201 } while (!guard.isSatisfied()); 1202 } finally { 1203 endWaitingFor(guard); 1204 } 1205 } 1206 1207 /** Caller should check before calling that guard is not satisfied. */ 1208 @GuardedBy("lock") 1209 private boolean awaitNanos(Guard guard, long nanos, boolean signalBeforeWaiting) 1210 throws InterruptedException { 1211 boolean firstTime = true; 1212 try { 1213 do { 1214 if (nanos <= 0L) { 1215 return false; 1216 } 1217 if (firstTime) { 1218 if (signalBeforeWaiting) { 1219 signalNextWaiter(); 1220 } 1221 beginWaitingFor(guard); 1222 firstTime = false; 1223 } 1224 nanos = guard.condition.awaitNanos(nanos); 1225 } while (!guard.isSatisfied()); 1226 return true; 1227 } finally { 1228 if (!firstTime) { 1229 endWaitingFor(guard); 1230 } 1231 } 1232 } 1233}