Code - Class EDU.oswego.cs.dl.util.concurrent.WaiterPreferenceSemaphore


1 /*
2   File: WaiterPreferenceSemaphore.java
3
4   Originally written by Doug Lea and released into the public domain.
5   This may be used for any purposes whatsoever without acknowledgment.
6   Thanks for the assistance and support of Sun Microsystems Labs,
7   and everyone contributing, testing, and using this code.
8
9   History:
10   Date Who What
11   11Jun1998 dl Create public version
12    5Aug1998 dl replaced int counters with longs
13 */
14
15
16 package EDU.oswego.cs.dl.util.concurrent;
17
18 /**
19  * An implementation of counting Semaphores that
20  * enforces enough fairness for applications that
21  * need to avoid indefinite overtaking without
22  * necessarily requiring FIFO ordered access.
23  * Empirically, very little is paid for this property
24  * unless there is a lot of contention among threads
25  * or very unfair JVM scheduling.
26  * The acquire method waits even if there are permits
27  * available but have not yet been claimed by threads that have
28  * been notified but not yet resumed. This makes the semaphore
29  * almost as fair as the underlying Java primitives allow.
30  * So, if synch lock entry and notify are both fair
31  * so is the semaphore -- almost: Rewaits stemming
32  * from timeouts in attempt, along with potentials for
33  * interrupted threads to be notified can compromise fairness,
34  * possibly allowing later-arriving threads to pass before
35  * later arriving ones. However, in no case can a newly
36  * entering thread obtain a permit if there are still others waiting.
37  * Also, signalling order need not coincide with
38  * resumption order. Later-arriving threads might get permits
39  * and continue before other resumable threads are actually resumed.
40  * However, all of these potential fairness breaches are
41  * very rare in practice unless the underlying JVM
42  * performs strictly LIFO notifications (which has, sadly enough,
43  * been known to occur) in which case you need to use
44  * a FIFOSemaphore to maintain a reasonable approximation
45  * of fairness.
46  * <p>[<a HREF="http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html"> Introduction to this package. </a>]
47 **/
48
49
50 public final class WaiterPreferenceSemaphore extends Semaphore {
51
52   /**
53    * Create a Semaphore with the given initial number of permits.
54   **/
55
56   public WaiterPreferenceSemaphore(long initial) { super(initial); }
57
58   /** Number of waiting threads **/
59   protected long waits_ = 0;
60
61   public void acquire() throws InterruptedException {
62     if (Thread.interrupted()) throw new InterruptedException();
63     synchronized(this) {
64       /*
65         Only take if there are more permits than threads waiting
66         for permits. This prevents infinite overtaking.
67       */
68       if (permits_ > waits_) {
69         --permits_;
70         return;
71       }
72       else {
73         ++waits_;
74         try {
75           for (;;) {
76             wait();
77             if (permits_ > 0) {
78               --waits_;
79               --permits_;
80               return;
81             }
82           }
83         }
84         catch(InterruptedException ex) {
85           --waits_;
86           notify();
87           throw ex;
88         }
89       }
90     }
91   }
92
93   public boolean attempt(long msecs) throws InterruptedException {
94     if (Thread.interrupted()) throw new InterruptedException();
95
96     synchronized(this) {
97       if (permits_ > waits_) {
98         --permits_;
99         return true;
100       }
101       else if (msecs <= 0)
102         return false;
103       else {
104         ++waits_;
105         
106         long startTime = System.currentTimeMillis();
107         long waitTime = msecs;
108         
109         try {
110           for (;;) {
111             wait(waitTime);
112             if (permits_ > 0) {
113               --waits_;
114               --permits_;
115               return true;
116             }
117             else { // got a time-out or false-alarm notify
118 waitTime = msecs - (System.currentTimeMillis() - startTime);
119               if (waitTime <= 0) {
120                 --waits_;
121                 return false;
122               }
123             }
124           }
125         }
126         catch(InterruptedException ex) {
127           --waits_;
128           notify();
129           throw ex;
130         }
131       }
132     }
133   }
134
135   public synchronized void release() {
136     ++permits_;
137     notify();
138   }
139
140   /** Release N permits **/
141   public synchronized void release(long n) {
142     permits_ += n;
143     for (long i = 0; i < n; ++i) notify();
144   }
145
146 }
147
148
Java API By Example, From Geeks To Geeks. | Conditions of Use | About Us © 2002 - 2005, KickJava.com, or its affiliates