Mercurial > hg > blitz_condensed
diff src/EDU/oswego/cs/dl/util/concurrent/FIFOReadWriteLock.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/FIFOReadWriteLock.java Sat Mar 21 11:00:06 2009 +0000 @@ -0,0 +1,186 @@ +/* + File: FIFOReadWriteLock.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 + 23nov2001 dl Replace main algorithm with fairer + version based on one by Alexander Terekhov +*/ + +package EDU.oswego.cs.dl.util.concurrent; + + +/** + * This class implements a policy for reader/writer locks in which + * threads contend in a First-in/First-out manner for access (modulo + * the limitations of FIFOSemaphore, which is used for queuing). This + * policy does not particularly favor readers or writers. As a + * byproduct of the FIFO policy, the <tt>attempt</tt> methods may + * return <tt>false</tt> even when the lock might logically be + * available, but, due to contention, cannot be accessed within the + * given time bound. <p> + * + * This lock is <em>NOT</em> reentrant. Current readers and + * writers should not try to re-obtain locks while holding them. + * <p> + * + * [<a href="http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html"> Introduction to this package. </a>] <p> + * + * @see FIFOSemaphore +**/ + +public class FIFOReadWriteLock implements ReadWriteLock { + + /** + * Fair Semaphore serving as a kind of mutual exclusion lock. + * Writers acquire on entry, and hold until rwlock exit. + * Readers acquire and release only during entry (but are + * blocked from doing so if there is an active writer). + **/ + protected final FIFOSemaphore entryLock = new FIFOSemaphore(1); + + /** + * Number of threads that have entered read lock. Note that this is + * never reset to zero. Incremented only during acquisition of read + * lock while the "entryLock" is held, but read elsewhere, so is + * declared volatile. + **/ + protected volatile int readers; + + /** + * Number of threads that have exited read lock. Note that this is + * never reset to zero. Accessed only in code protected by + * synchronized(this). When exreaders != readers, the rwlock is + * being used for reading. Else if the entry lock is held, it is + * being used for writing (or in transition). Else it is free. + * Note: To distinguish these states, we assume that fewer than 2^32 + * reader threads can simultaneously execute. + **/ + protected int exreaders; + + protected void acquireRead() throws InterruptedException { + entryLock.acquire(); + ++readers; + entryLock.release(); + } + + protected synchronized void releaseRead() { + /* + If this is the last reader, notify a possibly waiting writer. + Because waits occur only when entry lock is held, at most one + writer can be waiting for this notification. Because increments + to "readers" aren't protected by "this" lock, the notification + may be spurious (when an incoming reader in in the process of + updating the field), but at the point tested in acquiring write + lock, both locks will be held, thus avoiding false alarms. And + we will never miss an opportunity to send a notification when it + is actually needed. + */ + + if (++exreaders == readers) + notify(); + } + + protected void acquireWrite() throws InterruptedException { + // Acquiring entryLock first forces subsequent entering readers + // (as well as writers) to block. + entryLock.acquire(); + + // Only read "readers" once now before loop. We know it won't + // change because we hold the entry lock needed to update it. + int r = readers; + + try { + synchronized(this) { + while (exreaders != r) + wait(); + } + } + catch (InterruptedException ie) { + entryLock.release(); + throw ie; + } + } + + protected void releaseWrite() { + entryLock.release(); + } + + protected boolean attemptRead(long msecs) throws InterruptedException { + if (!entryLock.attempt(msecs)) + return false; + + ++readers; + entryLock.release(); + return true; + } + + protected boolean attemptWrite(long msecs) throws InterruptedException { + long startTime = (msecs <= 0)? 0 : System.currentTimeMillis(); + + if (!entryLock.attempt(msecs)) + return false; + + int r = readers; + + try { + synchronized(this) { + while (exreaders != r) { + long timeLeft = (msecs <= 0)? 0: + msecs - (System.currentTimeMillis() - startTime); + + if (timeLeft <= 0) { + entryLock.release(); + return false; + } + + wait(timeLeft); + } + return true; + } + } + catch (InterruptedException ie) { + entryLock.release(); + throw ie; + } + } + + // support for ReadWriteLock interface + + protected class ReaderSync implements Sync { + public void acquire() throws InterruptedException { + acquireRead(); + } + public void release() { + releaseRead(); + } + public boolean attempt(long msecs) throws InterruptedException { + return attemptRead(msecs); + } + } + + protected class WriterSync implements Sync { + public void acquire() throws InterruptedException { + acquireWrite(); + } + public void release() { + releaseWrite(); + } + public boolean attempt(long msecs) throws InterruptedException { + return attemptWrite(msecs); + } + } + + protected final Sync readerSync = new ReaderSync(); + protected final Sync writerSync = new WriterSync(); + + public Sync writeLock() { return writerSync; } + public Sync readLock() { return readerSync; } + +}