Mercurial > hg > blitz_condensed
diff src/EDU/oswego/cs/dl/util/concurrent/WaiterPreferenceSemaphore.java @ 0:3dc0c5604566
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 |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/EDU/oswego/cs/dl/util/concurrent/WaiterPreferenceSemaphore.java Sat Mar 21 11:00:06 2009 +0000 @@ -0,0 +1,147 @@ +/* + File: WaiterPreferenceSemaphore.java + + Originally written by Doug Lea and released into the public domain. + This may be used for any purposes whatsoever without acknowledgment. + Thanks for the assistance and support of Sun Microsystems Labs, + and everyone contributing, testing, and using this code. + + History: + Date Who What + 11Jun1998 dl Create public version + 5Aug1998 dl replaced int counters with longs +*/ + + +package EDU.oswego.cs.dl.util.concurrent; + +/** + * An implementation of counting Semaphores that + * enforces enough fairness for applications that + * need to avoid indefinite overtaking without + * necessarily requiring FIFO ordered access. + * Empirically, very little is paid for this property + * unless there is a lot of contention among threads + * or very unfair JVM scheduling. + * The acquire method waits even if there are permits + * available but have not yet been claimed by threads that have + * been notified but not yet resumed. This makes the semaphore + * almost as fair as the underlying Java primitives allow. + * So, if synch lock entry and notify are both fair + * so is the semaphore -- almost: Rewaits stemming + * from timeouts in attempt, along with potentials for + * interrupted threads to be notified can compromise fairness, + * possibly allowing later-arriving threads to pass before + * later arriving ones. However, in no case can a newly + * entering thread obtain a permit if there are still others waiting. + * Also, signalling order need not coincide with + * resumption order. Later-arriving threads might get permits + * and continue before other resumable threads are actually resumed. + * However, all of these potential fairness breaches are + * very rare in practice unless the underlying JVM + * performs strictly LIFO notifications (which has, sadly enough, + * been known to occur) in which case you need to use + * a FIFOSemaphore to maintain a reasonable approximation + * of fairness. + * <p>[<a href="http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html"> Introduction to this package. </a>] +**/ + + +public final class WaiterPreferenceSemaphore extends Semaphore { + + /** + * Create a Semaphore with the given initial number of permits. + **/ + + public WaiterPreferenceSemaphore(long initial) { super(initial); } + + /** Number of waiting threads **/ + protected long waits_ = 0; + + public void acquire() throws InterruptedException { + if (Thread.interrupted()) throw new InterruptedException(); + synchronized(this) { + /* + Only take if there are more permits than threads waiting + for permits. This prevents infinite overtaking. + */ + if (permits_ > waits_) { + --permits_; + return; + } + else { + ++waits_; + try { + for (;;) { + wait(); + if (permits_ > 0) { + --waits_; + --permits_; + return; + } + } + } + catch(InterruptedException ex) { + --waits_; + notify(); + throw ex; + } + } + } + } + + public boolean attempt(long msecs) throws InterruptedException { + if (Thread.interrupted()) throw new InterruptedException(); + + synchronized(this) { + if (permits_ > waits_) { + --permits_; + return true; + } + else if (msecs <= 0) + return false; + else { + ++waits_; + + long startTime = System.currentTimeMillis(); + long waitTime = msecs; + + try { + for (;;) { + wait(waitTime); + if (permits_ > 0) { + --waits_; + --permits_; + return true; + } + else { // got a time-out or false-alarm notify + waitTime = msecs - (System.currentTimeMillis() - startTime); + if (waitTime <= 0) { + --waits_; + return false; + } + } + } + } + catch(InterruptedException ex) { + --waits_; + notify(); + throw ex; + } + } + } + } + + public synchronized void release() { + ++permits_; + notify(); + } + + /** Release N permits **/ + public synchronized void release(long n) { + permits_ += n; + for (long i = 0; i < n; ++i) notify(); + } + +} +