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