• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * Copyright (C) 2010 The Guava Authors
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 package com.google.common.util.concurrent;
18 
19 import static com.google.common.base.Preconditions.checkNotNull;
20 
21 import com.google.common.annotations.Beta;
22 import com.google.common.base.Throwables;
23 
24 import java.util.concurrent.TimeUnit;
25 import java.util.concurrent.locks.Condition;
26 import java.util.concurrent.locks.ReentrantLock;
27 
28 import javax.annotation.concurrent.GuardedBy;
29 
30 /**
31  * A synchronization abstraction supporting waiting on arbitrary boolean conditions.
32  *
33  * <p>This class is intended as a replacement for {@link ReentrantLock}. Code using {@code Monitor}
34  * is less error-prone and more readable than code using {@code ReentrantLock}, without significant
35  * performance loss. {@code Monitor} even has the potential for performance gain by optimizing the
36  * evaluation and signaling of conditions.  Signaling is entirely
37  * <a href="http://en.wikipedia.org/wiki/Monitor_(synchronization)#Implicit_signaling">
38  * implicit</a>.
39  * By eliminating explicit signaling, this class can guarantee that only one thread is awakened
40  * when a condition becomes true (no "signaling storms" due to use of {@link
41  * java.util.concurrent.locks.Condition#signalAll Condition.signalAll}) and that no signals are lost
42  * (no "hangs" due to incorrect use of {@link java.util.concurrent.locks.Condition#signal
43  * Condition.signal}).
44  *
45  * <p>A thread is said to <i>occupy</i> a monitor if it has <i>entered</i> the monitor but not yet
46  * <i>left</i>. Only one thread may occupy a given monitor at any moment. A monitor is also
47  * reentrant, so a thread may enter a monitor any number of times, and then must leave the same
48  * number of times. The <i>enter</i> and <i>leave</i> operations have the same synchronization
49  * semantics as the built-in Java language synchronization primitives.
50  *
51  * <p>A call to any of the <i>enter</i> methods with <b>void</b> return type should always be
52  * followed immediately by a <i>try/finally</i> block to ensure that the current thread leaves the
53  * monitor cleanly: <pre>   {@code
54  *
55  *   monitor.enter();
56  *   try {
57  *     // do things while occupying the monitor
58  *   } finally {
59  *     monitor.leave();
60  *   }}</pre>
61  *
62  * <p>A call to any of the <i>enter</i> methods with <b>boolean</b> return type should always
63  * appear as the condition of an <i>if</i> statement containing a <i>try/finally</i> block to
64  * ensure that the current thread leaves the monitor cleanly: <pre>   {@code
65  *
66  *   if (monitor.tryEnter()) {
67  *     try {
68  *       // do things while occupying the monitor
69  *     } finally {
70  *       monitor.leave();
71  *     }
72  *   } else {
73  *     // do other things since the monitor was not available
74  *   }}</pre>
75  *
76  * <h2>Comparison with {@code synchronized} and {@code ReentrantLock}</h2>
77  *
78  * <p>The following examples show a simple threadsafe holder expressed using {@code synchronized},
79  * {@link ReentrantLock}, and {@code Monitor}.
80  *
81  * <h3>{@code synchronized}</h3>
82  *
83  * <p>This version is the fewest lines of code, largely because the synchronization mechanism used
84  * is built into the language and runtime. But the programmer has to remember to avoid a couple of
85  * common bugs: The {@code wait()} must be inside a {@code while} instead of an {@code if}, and
86  * {@code notifyAll()} must be used instead of {@code notify()} because there are two different
87  * logical conditions being awaited. <pre>   {@code
88  *
89  *   public class SafeBox<V> {
90  *     private V value;
91  *
92  *     public synchronized V get() throws InterruptedException {
93  *       while (value == null) {
94  *         wait();
95  *       }
96  *       V result = value;
97  *       value = null;
98  *       notifyAll();
99  *       return result;
100  *     }
101  *
102  *     public synchronized void set(V newValue) throws InterruptedException {
103  *       while (value != null) {
104  *         wait();
105  *       }
106  *       value = newValue;
107  *       notifyAll();
108  *     }
109  *   }}</pre>
110  *
111  * <h3>{@code ReentrantLock}</h3>
112  *
113  * <p>This version is much more verbose than the {@code synchronized} version, and still suffers
114  * from the need for the programmer to remember to use {@code while} instead of {@code if}.
115  * However, one advantage is that we can introduce two separate {@code Condition} objects, which
116  * allows us to use {@code signal()} instead of {@code signalAll()}, which may be a performance
117  * benefit. <pre>   {@code
118  *
119  *   public class SafeBox<V> {
120  *     private final ReentrantLock lock = new ReentrantLock();
121  *     private final Condition valuePresent = lock.newCondition();
122  *     private final Condition valueAbsent = lock.newCondition();
123  *     private V value;
124  *
125  *     public V get() throws InterruptedException {
126  *       lock.lock();
127  *       try {
128  *         while (value == null) {
129  *           valuePresent.await();
130  *         }
131  *         V result = value;
132  *         value = null;
133  *         valueAbsent.signal();
134  *         return result;
135  *       } finally {
136  *         lock.unlock();
137  *       }
138  *     }
139  *
140  *     public void set(V newValue) throws InterruptedException {
141  *       lock.lock();
142  *       try {
143  *         while (value != null) {
144  *           valueAbsent.await();
145  *         }
146  *         value = newValue;
147  *         valuePresent.signal();
148  *       } finally {
149  *         lock.unlock();
150  *       }
151  *     }
152  *   }}</pre>
153  *
154  * <h3>{@code Monitor}</h3>
155  *
156  * <p>This version adds some verbosity around the {@code Guard} objects, but removes that same
157  * verbosity, and more, from the {@code get} and {@code set} methods. {@code Monitor} implements the
158  * same efficient signaling as we had to hand-code in the {@code ReentrantLock} version above.
159  * Finally, the programmer no longer has to hand-code the wait loop, and therefore doesn't have to
160  * remember to use {@code while} instead of {@code if}. <pre>   {@code
161  *
162  *   public class SafeBox<V> {
163  *     private final Monitor monitor = new Monitor();
164  *     private final Monitor.Guard valuePresent = new Monitor.Guard(monitor) {
165  *       public boolean isSatisfied() {
166  *         return value != null;
167  *       }
168  *     };
169  *     private final Monitor.Guard valueAbsent = new Monitor.Guard(monitor) {
170  *       public boolean isSatisfied() {
171  *         return value == null;
172  *       }
173  *     };
174  *     private V value;
175  *
176  *     public V get() throws InterruptedException {
177  *       monitor.enterWhen(valuePresent);
178  *       try {
179  *         V result = value;
180  *         value = null;
181  *         return result;
182  *       } finally {
183  *         monitor.leave();
184  *       }
185  *     }
186  *
187  *     public void set(V newValue) throws InterruptedException {
188  *       monitor.enterWhen(valueAbsent);
189  *       try {
190  *         value = newValue;
191  *       } finally {
192  *         monitor.leave();
193  *       }
194  *     }
195  *   }}</pre>
196  *
197  * @author Justin T. Sampson
198  * @author Martin Buchholz
199  * @since 10.0
200  */
201 @Beta
202 public final class Monitor {
203   // TODO(user): Use raw LockSupport or AbstractQueuedSynchronizer instead of ReentrantLock.
204   // TODO(user): "Port" jsr166 tests for ReentrantLock.
205   //
206   // TODO(user): Change API to make it impossible to use a Guard with the "wrong" monitor,
207   //    by making the monitor implicit, and to eliminate other sources of IMSE.
208   //    Imagine:
209   //    guard.lock();
210   //    try { /* monitor locked and guard satisfied here */ }
211   //    finally { guard.unlock(); }
212   // Here are Justin's design notes about this:
213   //
214   // This idea has come up from time to time, and I think one of my
215   // earlier versions of Monitor even did something like this. I ended
216   // up strongly favoring the current interface.
217   //
218   // I probably can't remember all the reasons (it's possible you
219   // could find them in the code review archives), but here are a few:
220   //
221   // 1. What about leaving/unlocking? Are you going to do
222   //    guard.enter() paired with monitor.leave()? That might get
223   //    confusing. It's nice for the finally block to look as close as
224   //    possible to the thing right before the try. You could have
225   //    guard.leave(), but that's a little odd as well because the
226   //    guard doesn't have anything to do with leaving. You can't
227   //    really enforce that the guard you're leaving is the same one
228   //    you entered with, and it doesn't actually matter.
229   //
230   // 2. Since you can enter the monitor without a guard at all, some
231   //    places you'll have monitor.enter()/monitor.leave() and other
232   //    places you'll have guard.enter()/guard.leave() even though
233   //    it's the same lock being acquired underneath. Always using
234   //    monitor.enterXXX()/monitor.leave() will make it really clear
235   //    which lock is held at any point in the code.
236   //
237   // 3. I think "enterWhen(notEmpty)" reads better than "notEmpty.enter()".
238   //
239   // TODO(user): Implement ReentrantLock features:
240   //    - toString() method
241   //    - getOwner() method
242   //    - getQueuedThreads() method
243   //    - getWaitingThreads(Guard) method
244   //    - implement Serializable
245   //    - redo the API to be as close to identical to ReentrantLock as possible,
246   //      since, after all, this class is also a reentrant mutual exclusion lock!?
247 
248   /*
249    * One of the key challenges of this class is to prevent lost signals, while trying hard to
250    * minimize unnecessary signals.  One simple and correct algorithm is to signal some other
251    * waiter with a satisfied guard (if one exists) whenever any thread occupying the monitor
252    * exits the monitor, either by unlocking all of its held locks, or by starting to wait for a
253    * guard.  This includes exceptional exits, so all control paths involving signalling must be
254    * protected by a finally block.
255    *
256    * Further optimizations of this algorithm become increasingly subtle.  A wait that terminates
257    * without the guard being satisfied (due to timeout, but not interrupt) can then immediately
258    * exit the monitor without signalling.  If it timed out without being signalled, it does not
259    * need to "pass on" the signal to another thread.  If it *was* signalled, then its guard must
260    * have been satisfied at the time of signal, and has since been modified by some other thread
261    * to be non-satisfied before reacquiring the lock, and that other thread takes over the
262    * responsibility of signaling the next waiter.
263    *
264    * Unlike the underlying Condition, if we are not careful, an interrupt *can* cause a signal to
265    * be lost, because the signal may be sent to a condition whose sole waiter has just been
266    * interrupted.
267    *
268    * Imagine a monitor with multiple guards.  A thread enters the monitor, satisfies all the
269    * guards, and leaves, calling signalNextWaiter.  With traditional locks and conditions, all
270    * the conditions need to be signalled because it is not known which if any of them have
271    * waiters (and hasWaiters can't be used reliably because of a check-then-act race).  With our
272    * Monitor guards, we only signal the first active guard that is satisfied.  But the
273    * corresponding thread may have already been interrupted and is waiting to reacquire the lock
274    * while still registered in activeGuards, in which case the signal is a no-op, and the
275    * bigger-picture signal is lost unless interrupted threads take special action by
276    * participating in the signal-passing game.
277    */
278 
279   /**
280    * A boolean condition for which a thread may wait. A {@code Guard} is associated with a single
281    * {@code Monitor}. The monitor may check the guard at arbitrary times from any thread occupying
282    * the monitor, so code should not be written to rely on how often a guard might or might not be
283    * checked.
284    *
285    * <p>If a {@code Guard} is passed into any method of a {@code Monitor} other than the one it is
286    * associated with, an {@link IllegalMonitorStateException} is thrown.
287    *
288    * @since 10.0
289    */
290   @Beta
291   public abstract static class Guard {
292 
293     final Monitor monitor;
294     final Condition condition;
295 
296     @GuardedBy("monitor.lock")
297     int waiterCount = 0;
298 
299     /** The next active guard */
300     @GuardedBy("monitor.lock")
301     Guard next;
302 
Guard(Monitor monitor)303     protected Guard(Monitor monitor) {
304       this.monitor = checkNotNull(monitor, "monitor");
305       this.condition = monitor.lock.newCondition();
306     }
307 
308     /**
309      * Evaluates this guard's boolean condition. This method is always called with the associated
310      * monitor already occupied. Implementations of this method must depend only on state protected
311      * by the associated monitor, and must not modify that state.
312      */
isSatisfied()313     public abstract boolean isSatisfied();
314 
315   }
316 
317   /**
318    * Whether this monitor is fair.
319    */
320   private final boolean fair;
321 
322   /**
323    * The lock underlying this monitor.
324    */
325   private final ReentrantLock lock;
326 
327   /**
328    * The guards associated with this monitor that currently have waiters ({@code waiterCount > 0}).
329    * A linked list threaded through the Guard.next field.
330    */
331   @GuardedBy("lock")
332   private Guard activeGuards = null;
333 
334   /**
335    * Creates a monitor with a non-fair (but fast) ordering policy. Equivalent to {@code
336    * Monitor(false)}.
337    */
Monitor()338   public Monitor() {
339     this(false);
340   }
341 
342   /**
343    * Creates a monitor with the given ordering policy.
344    *
345    * @param fair whether this monitor should use a fair ordering policy rather than a non-fair (but
346    *        fast) one
347    */
Monitor(boolean fair)348   public Monitor(boolean fair) {
349     this.fair = fair;
350     this.lock = new ReentrantLock(fair);
351   }
352 
353   /**
354    * Enters this monitor. Blocks indefinitely.
355    */
enter()356   public void enter() {
357     lock.lock();
358   }
359 
360   /**
361    * Enters this monitor. Blocks indefinitely, but may be interrupted.
362    */
enterInterruptibly()363   public void enterInterruptibly() throws InterruptedException {
364     lock.lockInterruptibly();
365   }
366 
367   /**
368    * Enters this monitor. Blocks at most the given time.
369    *
370    * @return whether the monitor was entered
371    */
enter(long time, TimeUnit unit)372   public boolean enter(long time, TimeUnit unit) {
373     long timeoutNanos = unit.toNanos(time);
374     final ReentrantLock lock = this.lock;
375     if (!fair && lock.tryLock()) {
376       return true;
377     }
378     long deadline = System.nanoTime() + timeoutNanos;
379     boolean interrupted = Thread.interrupted();
380     try {
381       while (true) {
382         try {
383           return lock.tryLock(timeoutNanos, TimeUnit.NANOSECONDS);
384         } catch (InterruptedException interrupt) {
385           interrupted = true;
386           timeoutNanos = deadline - System.nanoTime();
387         }
388       }
389     } finally {
390       if (interrupted) {
391         Thread.currentThread().interrupt();
392       }
393     }
394   }
395 
396   /**
397    * Enters this monitor. Blocks at most the given time, and may be interrupted.
398    *
399    * @return whether the monitor was entered
400    */
enterInterruptibly(long time, TimeUnit unit)401   public boolean enterInterruptibly(long time, TimeUnit unit) throws InterruptedException {
402     return lock.tryLock(time, unit);
403   }
404 
405   /**
406    * Enters this monitor if it is possible to do so immediately. Does not block.
407    *
408    * <p><b>Note:</b> This method disregards the fairness setting of this monitor.
409    *
410    * @return whether the monitor was entered
411    */
tryEnter()412   public boolean tryEnter() {
413     return lock.tryLock();
414   }
415 
416   /**
417    * Enters this monitor when the guard is satisfied. Blocks indefinitely, but may be interrupted.
418    */
enterWhen(Guard guard)419   public void enterWhen(Guard guard) throws InterruptedException {
420     if (guard.monitor != this) {
421       throw new IllegalMonitorStateException();
422     }
423     final ReentrantLock lock = this.lock;
424     boolean signalBeforeWaiting = lock.isHeldByCurrentThread();
425     lock.lockInterruptibly();
426 
427     boolean satisfied = false;
428     try {
429       if (!guard.isSatisfied()) {
430         await(guard, signalBeforeWaiting);
431       }
432       satisfied = true;
433     } finally {
434       if (!satisfied) {
435         leave();
436       }
437     }
438   }
439 
440   /**
441    * Enters this monitor when the guard is satisfied. Blocks indefinitely.
442    */
enterWhenUninterruptibly(Guard guard)443   public void enterWhenUninterruptibly(Guard guard) {
444     if (guard.monitor != this) {
445       throw new IllegalMonitorStateException();
446     }
447     final ReentrantLock lock = this.lock;
448     boolean signalBeforeWaiting = lock.isHeldByCurrentThread();
449     lock.lock();
450 
451     boolean satisfied = false;
452     try {
453       if (!guard.isSatisfied()) {
454         awaitUninterruptibly(guard, signalBeforeWaiting);
455       }
456       satisfied = true;
457     } finally {
458       if (!satisfied) {
459         leave();
460       }
461     }
462   }
463 
464   /**
465    * Enters this monitor when the guard is satisfied. Blocks at most the given time, including both
466    * the time to acquire the lock and the time to wait for the guard to be satisfied, and may be
467    * interrupted.
468    *
469    * @return whether the monitor was entered with the guard satisfied
470    */
enterWhen(Guard guard, long time, TimeUnit unit)471   public boolean enterWhen(Guard guard, long time, TimeUnit unit) throws InterruptedException {
472     long timeoutNanos = unit.toNanos(time);
473     if (guard.monitor != this) {
474       throw new IllegalMonitorStateException();
475     }
476     final ReentrantLock lock = this.lock;
477     boolean reentrant = lock.isHeldByCurrentThread();
478     if (fair || !lock.tryLock()) {
479       long deadline = System.nanoTime() + timeoutNanos;
480       if (!lock.tryLock(time, unit)) {
481         return false;
482       }
483       timeoutNanos = deadline - System.nanoTime();
484     }
485 
486     boolean satisfied = false;
487     boolean threw = true;
488     try {
489       satisfied = guard.isSatisfied() || awaitNanos(guard, timeoutNanos, reentrant);
490       threw = false;
491       return satisfied;
492     } finally {
493       if (!satisfied) {
494         try {
495           // Don't need to signal if timed out, but do if interrupted
496           if (threw && !reentrant) {
497             signalNextWaiter();
498           }
499         } finally {
500           lock.unlock();
501         }
502       }
503     }
504   }
505 
506   /**
507    * Enters this monitor when the guard is satisfied. Blocks at most the given time, including
508    * both the time to acquire the lock and the time to wait for the guard to be satisfied.
509    *
510    * @return whether the monitor was entered with the guard satisfied
511    */
enterWhenUninterruptibly(Guard guard, long time, TimeUnit unit)512   public boolean enterWhenUninterruptibly(Guard guard, long time, TimeUnit unit) {
513     long timeoutNanos = unit.toNanos(time);
514     if (guard.monitor != this) {
515       throw new IllegalMonitorStateException();
516     }
517     final ReentrantLock lock = this.lock;
518     long deadline = System.nanoTime() + timeoutNanos;
519     boolean signalBeforeWaiting = lock.isHeldByCurrentThread();
520     boolean interrupted = Thread.interrupted();
521     try {
522       if (fair || !lock.tryLock()) {
523         boolean locked = false;
524         do {
525           try {
526             locked = lock.tryLock(timeoutNanos, TimeUnit.NANOSECONDS);
527             if (!locked) {
528               return false;
529             }
530           } catch (InterruptedException interrupt) {
531             interrupted = true;
532           }
533           timeoutNanos = deadline - System.nanoTime();
534         } while (!locked);
535       }
536 
537       boolean satisfied = false;
538       try {
539         while (true) {
540           try {
541             return satisfied = guard.isSatisfied()
542                 || awaitNanos(guard, timeoutNanos, signalBeforeWaiting);
543           } catch (InterruptedException interrupt) {
544             interrupted = true;
545             signalBeforeWaiting = false;
546             timeoutNanos = deadline - System.nanoTime();
547           }
548         }
549       } finally {
550         if (!satisfied) {
551           lock.unlock();  // No need to signal if timed out
552         }
553       }
554     } finally {
555       if (interrupted) {
556         Thread.currentThread().interrupt();
557       }
558     }
559   }
560 
561   /**
562    * Enters this monitor if the guard is satisfied. Blocks indefinitely acquiring the lock, but
563    * does not wait for the guard to be satisfied.
564    *
565    * @return whether the monitor was entered with the guard satisfied
566    */
enterIf(Guard guard)567   public boolean enterIf(Guard guard) {
568     if (guard.monitor != this) {
569       throw new IllegalMonitorStateException();
570     }
571     final ReentrantLock lock = this.lock;
572     lock.lock();
573 
574     boolean satisfied = false;
575     try {
576       return satisfied = guard.isSatisfied();
577     } finally {
578       if (!satisfied) {
579         lock.unlock();
580       }
581     }
582   }
583 
584   /**
585    * Enters this monitor if the guard is satisfied. Blocks indefinitely acquiring the lock, but does
586    * not wait for the guard to be satisfied, and may be interrupted.
587    *
588    * @return whether the monitor was entered with the guard satisfied
589    */
enterIfInterruptibly(Guard guard)590   public boolean enterIfInterruptibly(Guard guard) throws InterruptedException {
591     if (guard.monitor != this) {
592       throw new IllegalMonitorStateException();
593     }
594     final ReentrantLock lock = this.lock;
595     lock.lockInterruptibly();
596 
597     boolean satisfied = false;
598     try {
599       return satisfied = guard.isSatisfied();
600     } finally {
601       if (!satisfied) {
602         lock.unlock();
603       }
604     }
605   }
606 
607   /**
608    * Enters this monitor if the guard is satisfied. Blocks at most the given time acquiring the
609    * lock, but does not wait for the guard to be satisfied.
610    *
611    * @return whether the monitor was entered with the guard satisfied
612    */
enterIf(Guard guard, long time, TimeUnit unit)613   public boolean enterIf(Guard guard, long time, TimeUnit unit) {
614     if (guard.monitor != this) {
615       throw new IllegalMonitorStateException();
616     }
617     if (!enter(time, unit)) {
618       return false;
619     }
620 
621     boolean satisfied = false;
622     try {
623       return satisfied = guard.isSatisfied();
624     } finally {
625       if (!satisfied) {
626         lock.unlock();
627       }
628     }
629   }
630 
631   /**
632    * Enters this monitor if the guard is satisfied. Blocks at most the given time acquiring the
633    * lock, but does not wait for the guard to be satisfied, and may be interrupted.
634    *
635    * @return whether the monitor was entered with the guard satisfied
636    */
enterIfInterruptibly(Guard guard, long time, TimeUnit unit)637   public boolean enterIfInterruptibly(Guard guard, long time, TimeUnit unit)
638       throws InterruptedException {
639     if (guard.monitor != this) {
640       throw new IllegalMonitorStateException();
641     }
642     final ReentrantLock lock = this.lock;
643     if (!lock.tryLock(time, unit)) {
644       return false;
645     }
646 
647     boolean satisfied = false;
648     try {
649       return satisfied = guard.isSatisfied();
650     } finally {
651       if (!satisfied) {
652         lock.unlock();
653       }
654     }
655   }
656 
657   /**
658    * Enters this monitor if it is possible to do so immediately and the guard is satisfied. Does not
659    * block acquiring the lock and does not wait for the guard to be satisfied.
660    *
661    * <p><b>Note:</b> This method disregards the fairness setting of this monitor.
662    *
663    * @return whether the monitor was entered with the guard satisfied
664    */
tryEnterIf(Guard guard)665   public boolean tryEnterIf(Guard guard) {
666     if (guard.monitor != this) {
667       throw new IllegalMonitorStateException();
668     }
669     final ReentrantLock lock = this.lock;
670     if (!lock.tryLock()) {
671       return false;
672     }
673 
674     boolean satisfied = false;
675     try {
676       return satisfied = guard.isSatisfied();
677     } finally {
678       if (!satisfied) {
679         lock.unlock();
680       }
681     }
682   }
683 
684   /**
685    * Waits for the guard to be satisfied. Waits indefinitely, but may be interrupted. May be
686    * called only by a thread currently occupying this monitor.
687    */
waitFor(Guard guard)688   public void waitFor(Guard guard) throws InterruptedException {
689     if (!((guard.monitor == this) & lock.isHeldByCurrentThread())) {
690       throw new IllegalMonitorStateException();
691     }
692     if (!guard.isSatisfied()) {
693       await(guard, true);
694     }
695   }
696 
697   /**
698    * Waits for the guard to be satisfied. Waits indefinitely. May be called only by a thread
699    * currently occupying this monitor.
700    */
waitForUninterruptibly(Guard guard)701   public void waitForUninterruptibly(Guard guard) {
702     if (!((guard.monitor == this) & lock.isHeldByCurrentThread())) {
703       throw new IllegalMonitorStateException();
704     }
705     if (!guard.isSatisfied()) {
706       awaitUninterruptibly(guard, true);
707     }
708   }
709 
710   /**
711    * Waits for the guard to be satisfied. Waits at most the given time, and may be interrupted.
712    * May be called only by a thread currently occupying this monitor.
713    *
714    * @return whether the guard is now satisfied
715    */
waitFor(Guard guard, long time, TimeUnit unit)716   public boolean waitFor(Guard guard, long time, TimeUnit unit) throws InterruptedException {
717     long timeoutNanos = unit.toNanos(time);
718     if (!((guard.monitor == this) & lock.isHeldByCurrentThread())) {
719       throw new IllegalMonitorStateException();
720     }
721     return guard.isSatisfied() || awaitNanos(guard, timeoutNanos, true);
722   }
723 
724   /**
725    * Waits for the guard to be satisfied. Waits at most the given time. May be called only by a
726    * thread currently occupying this monitor.
727    *
728    * @return whether the guard is now satisfied
729    */
waitForUninterruptibly(Guard guard, long time, TimeUnit unit)730   public boolean waitForUninterruptibly(Guard guard, long time, TimeUnit unit) {
731     long timeoutNanos = unit.toNanos(time);
732     if (!((guard.monitor == this) & lock.isHeldByCurrentThread())) {
733       throw new IllegalMonitorStateException();
734     }
735     if (guard.isSatisfied()) {
736       return true;
737     }
738     boolean signalBeforeWaiting = true;
739     long deadline = System.nanoTime() + timeoutNanos;
740     boolean interrupted = Thread.interrupted();
741     try {
742       while (true) {
743         try {
744           return awaitNanos(guard, timeoutNanos, signalBeforeWaiting);
745         } catch (InterruptedException interrupt) {
746           interrupted = true;
747           if (guard.isSatisfied()) {
748             return true;
749           }
750           signalBeforeWaiting = false;
751           timeoutNanos = deadline - System.nanoTime();
752         }
753       }
754     } finally {
755       if (interrupted) {
756         Thread.currentThread().interrupt();
757       }
758     }
759   }
760 
761   /**
762    * Leaves this monitor. May be called only by a thread currently occupying this monitor.
763    */
leave()764   public void leave() {
765     final ReentrantLock lock = this.lock;
766     try {
767       // No need to signal if we will still be holding the lock when we return
768       if (lock.getHoldCount() == 1) {
769         signalNextWaiter();
770       }
771     } finally {
772       lock.unlock();  // Will throw IllegalMonitorStateException if not held
773     }
774   }
775 
776   /**
777    * Returns whether this monitor is using a fair ordering policy.
778    */
isFair()779   public boolean isFair() {
780     return fair;
781   }
782 
783   /**
784    * Returns whether this monitor is occupied by any thread. This method is designed for use in
785    * monitoring of the system state, not for synchronization control.
786    */
isOccupied()787   public boolean isOccupied() {
788     return lock.isLocked();
789   }
790 
791   /**
792    * Returns whether the current thread is occupying this monitor (has entered more times than it
793    * has left).
794    */
isOccupiedByCurrentThread()795   public boolean isOccupiedByCurrentThread() {
796     return lock.isHeldByCurrentThread();
797   }
798 
799   /**
800    * Returns the number of times the current thread has entered this monitor in excess of the number
801    * of times it has left. Returns 0 if the current thread is not occupying this monitor.
802    */
getOccupiedDepth()803   public int getOccupiedDepth() {
804     return lock.getHoldCount();
805   }
806 
807   /**
808    * Returns an estimate of the number of threads waiting to enter this monitor. The value is only
809    * an estimate because the number of threads may change dynamically while this method traverses
810    * internal data structures. This method is designed for use in monitoring of the system state,
811    * not for synchronization control.
812    */
getQueueLength()813   public int getQueueLength() {
814     return lock.getQueueLength();
815   }
816 
817   /**
818    * Returns whether any threads are waiting to enter this monitor. Note that because cancellations
819    * may occur at any time, a {@code true} return does not guarantee that any other thread will ever
820    * enter this monitor. This method is designed primarily for use in monitoring of the system
821    * state.
822    */
hasQueuedThreads()823   public boolean hasQueuedThreads() {
824     return lock.hasQueuedThreads();
825   }
826 
827   /**
828    * Queries whether the given thread is waiting to enter this monitor. Note that because
829    * cancellations may occur at any time, a {@code true} return does not guarantee that this thread
830    * will ever enter this monitor. This method is designed primarily for use in monitoring of the
831    * system state.
832    */
hasQueuedThread(Thread thread)833   public boolean hasQueuedThread(Thread thread) {
834     return lock.hasQueuedThread(thread);
835   }
836 
837   /**
838    * Queries whether any threads are waiting for the given guard to become satisfied. Note that
839    * because timeouts and interrupts may occur at any time, a {@code true} return does not guarantee
840    * that the guard becoming satisfied in the future will awaken any threads. This method is
841    * designed primarily for use in monitoring of the system state.
842    */
hasWaiters(Guard guard)843   public boolean hasWaiters(Guard guard) {
844     return getWaitQueueLength(guard) > 0;
845   }
846 
847   /**
848    * Returns an estimate of the number of threads waiting for the given guard to become satisfied.
849    * Note that because timeouts and interrupts may occur at any time, the estimate serves only as an
850    * upper bound on the actual number of waiters. This method is designed for use in monitoring of
851    * the system state, not for synchronization control.
852    */
getWaitQueueLength(Guard guard)853   public int getWaitQueueLength(Guard guard) {
854     if (guard.monitor != this) {
855       throw new IllegalMonitorStateException();
856     }
857     lock.lock();
858     try {
859       return guard.waiterCount;
860     } finally {
861       lock.unlock();
862     }
863   }
864 
865   /**
866    * Signals some other thread waiting on a satisfied guard, if one exists.
867    *
868    * We manage calls to this method carefully, to signal only when necessary, but never losing a
869    * signal, which is the classic problem of this kind of concurrency construct.  We must signal if
870    * the current thread is about to relinquish the lock and may have changed the state protected by
871    * the monitor, thereby causing some guard to be satisfied.
872    *
873    * In addition, any thread that has been signalled when its guard was satisfied acquires the
874    * responsibility of signalling the next thread when it again relinquishes the lock.  Unlike a
875    * normal Condition, there is no guarantee that an interrupted thread has not been signalled,
876    * since the concurrency control must manage multiple Conditions.  So this method must generally
877    * be called when waits are interrupted.
878    *
879    * On the other hand, if a signalled thread wakes up to discover that its guard is still not
880    * satisfied, it does *not* need to call this method before returning to wait.  This can only
881    * happen due to spurious wakeup (ignorable) or another thread acquiring the lock before the
882    * current thread can and returning the guard to the unsatisfied state.  In the latter case the
883    * other thread (last thread modifying the state protected by the monitor) takes over the
884    * responsibility of signalling the next waiter.
885    *
886    * This method must not be called from within a beginWaitingFor/endWaitingFor block, or else the
887    * current thread's guard might be mistakenly signalled, leading to a lost signal.
888    */
889   @GuardedBy("lock")
signalNextWaiter()890   private void signalNextWaiter() {
891     for (Guard guard = activeGuards; guard != null; guard = guard.next) {
892       if (isSatisfied(guard)) {
893         guard.condition.signal();
894         break;
895       }
896     }
897   }
898 
899   /**
900    * Exactly like signalNextWaiter, but caller guarantees that guardToSkip need not be considered,
901    * because caller has previously checked that guardToSkip.isSatisfied() returned false.
902    * An optimization for the case that guardToSkip.isSatisfied() may be expensive.
903    *
904    * We decided against using this method, since in practice, isSatisfied() is likely to be very
905    * cheap (typically one field read).  Resurrect this method if you find that not to be true.
906    */
907 //   @GuardedBy("lock")
908 //   private void signalNextWaiterSkipping(Guard guardToSkip) {
909 //     for (Guard guard = activeGuards; guard != null; guard = guard.next) {
910 //       if (guard != guardToSkip && isSatisfied(guard)) {
911 //         guard.condition.signal();
912 //         break;
913 //       }
914 //     }
915 //   }
916 
917   /**
918    * Exactly like guard.isSatisfied(), but in addition signals all waiting threads in the
919    * (hopefully unlikely) event that isSatisfied() throws.
920    */
921   @GuardedBy("lock")
isSatisfied(Guard guard)922   private boolean isSatisfied(Guard guard) {
923     try {
924       return guard.isSatisfied();
925     } catch (Throwable throwable) {
926       signalAllWaiters();
927       throw Throwables.propagate(throwable);
928     }
929   }
930 
931   /**
932    * Signals all threads waiting on guards.
933    */
934   @GuardedBy("lock")
signalAllWaiters()935   private void signalAllWaiters() {
936     for (Guard guard = activeGuards; guard != null; guard = guard.next) {
937       guard.condition.signalAll();
938     }
939   }
940 
941   /**
942    * Records that the current thread is about to wait on the specified guard.
943    */
944   @GuardedBy("lock")
beginWaitingFor(Guard guard)945   private void beginWaitingFor(Guard guard) {
946     int waiters = guard.waiterCount++;
947     if (waiters == 0) {
948       // push guard onto activeGuards
949       guard.next = activeGuards;
950       activeGuards = guard;
951     }
952   }
953 
954   /**
955    * Records that the current thread is no longer waiting on the specified guard.
956    */
957   @GuardedBy("lock")
endWaitingFor(Guard guard)958   private void endWaitingFor(Guard guard) {
959     int waiters = --guard.waiterCount;
960     if (waiters == 0) {
961       // unlink guard from activeGuards
962       for (Guard p = activeGuards, pred = null;; pred = p, p = p.next) {
963         if (p == guard) {
964           if (pred == null) {
965             activeGuards = p.next;
966           } else {
967             pred.next = p.next;
968           }
969           p.next = null;  // help GC
970           break;
971         }
972       }
973     }
974   }
975 
976   /*
977    * Methods that loop waiting on a guard's condition until the guard is satisfied, while
978    * recording this fact so that other threads know to check our guard and signal us.
979    * It's caller's responsibility to ensure that the guard is *not* currently satisfied.
980    */
981 
982   @GuardedBy("lock")
await(Guard guard, boolean signalBeforeWaiting)983     private void await(Guard guard, boolean signalBeforeWaiting)
984       throws InterruptedException {
985     if (signalBeforeWaiting) {
986       signalNextWaiter();
987     }
988     beginWaitingFor(guard);
989     try {
990       do {
991         guard.condition.await();
992       } while (!guard.isSatisfied());
993     } finally {
994       endWaitingFor(guard);
995     }
996   }
997 
998   @GuardedBy("lock")
awaitUninterruptibly(Guard guard, boolean signalBeforeWaiting)999   private void awaitUninterruptibly(Guard guard, boolean signalBeforeWaiting) {
1000     if (signalBeforeWaiting) {
1001       signalNextWaiter();
1002     }
1003     beginWaitingFor(guard);
1004     try {
1005       do {
1006         guard.condition.awaitUninterruptibly();
1007       } while (!guard.isSatisfied());
1008     } finally {
1009       endWaitingFor(guard);
1010     }
1011   }
1012 
1013   @GuardedBy("lock")
awaitNanos(Guard guard, long nanos, boolean signalBeforeWaiting)1014   private boolean awaitNanos(Guard guard, long nanos, boolean signalBeforeWaiting)
1015       throws InterruptedException {
1016     if (signalBeforeWaiting) {
1017       signalNextWaiter();
1018     }
1019     beginWaitingFor(guard);
1020     try {
1021       do {
1022         if (nanos < 0L) {
1023           return false;
1024         }
1025         nanos = guard.condition.awaitNanos(nanos);
1026       } while (!guard.isSatisfied());
1027       return true;
1028     } finally {
1029       endWaitingFor(guard);
1030     }
1031   }
1032 
1033 }
1034