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