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