Mercurial > hg > blitz_stable

comparison src/EDU/oswego/cs/dl/util/concurrent/WaiterPreferenceSemaphore.java @ 0:3dc0c5604566

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Initial checkin of blitz 2.0 fcs - no installer yet.
author Dan Creswell <dan.creswell@gmail.com>
date Sat, 21 Mar 2009 11:00:06 +0000
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:3dc0c5604566
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