001: /*
002: File: FIFOReadWriteLock.java
003:
004: Originally written by Doug Lea and released into the public domain.
005: This may be used for any purposes whatsoever without acknowledgment.
006: Thanks for the assistance and support of Sun Microsystems Labs,
007: and everyone contributing, testing, and using this code.
008:
009: History:
010: Date Who What
011: 11Jun1998 dl Create public version
012: 23nov2001 dl Replace main algorithm with fairer
013: version based on one by Alexander Terekhov
014: */
015:
016: package EDU.oswego.cs.dl.util.concurrent;
017:
018: /**
019: * This class implements a policy for reader/writer locks in which
020: * threads contend in a First-in/First-out manner for access (modulo
021: * the limitations of FIFOSemaphore, which is used for queuing). This
022: * policy does not particularly favor readers or writers. As a
023: * byproduct of the FIFO policy, the <tt>attempt</tt> methods may
024: * return <tt>false</tt> even when the lock might logically be
025: * available, but, due to contention, cannot be accessed within the
026: * given time bound. <p>
027: *
028: * This lock is <em>NOT</em> reentrant. Current readers and
029: * writers should not try to re-obtain locks while holding them.
030: * <p>
031: *
032: * [<a href="http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html"> Introduction to this package. </a>] <p>
033: *
034: * @see FIFOSemaphore
035: **/
036:
037: public class FIFOReadWriteLock implements ReadWriteLock {
038:
039: /**
040: * Fair Semaphore serving as a kind of mutual exclusion lock.
041: * Writers acquire on entry, and hold until rwlock exit.
042: * Readers acquire and release only during entry (but are
043: * blocked from doing so if there is an active writer).
044: **/
045: protected final FIFOSemaphore entryLock = new FIFOSemaphore(1);
046:
047: /**
048: * Number of threads that have entered read lock. Note that this is
049: * never reset to zero. Incremented only during acquisition of read
050: * lock while the "entryLock" is held, but read elsewhere, so is
051: * declared volatile.
052: **/
053: protected volatile int readers;
054:
055: /**
056: * Number of threads that have exited read lock. Note that this is
057: * never reset to zero. Accessed only in code protected by
058: * synchronized(this). When exreaders != readers, the rwlock is
059: * being used for reading. Else if the entry lock is held, it is
060: * being used for writing (or in transition). Else it is free.
061: * Note: To distinguish these states, we assume that fewer than 2^32
062: * reader threads can simultaneously execute.
063: **/
064: protected int exreaders;
065:
066: protected void acquireRead() throws InterruptedException {
067: entryLock.acquire();
068: ++readers;
069: entryLock.release();
070: }
071:
072: protected synchronized void releaseRead() {
073: /*
074: If this is the last reader, notify a possibly waiting writer.
075: Because waits occur only when entry lock is held, at most one
076: writer can be waiting for this notification. Because increments
077: to "readers" aren't protected by "this" lock, the notification
078: may be spurious (when an incoming reader in in the process of
079: updating the field), but at the point tested in acquiring write
080: lock, both locks will be held, thus avoiding false alarms. And
081: we will never miss an opportunity to send a notification when it
082: is actually needed.
083: */
084:
085: if (++exreaders == readers)
086: notify();
087: }
088:
089: protected void acquireWrite() throws InterruptedException {
090: // Acquiring entryLock first forces subsequent entering readers
091: // (as well as writers) to block.
092: entryLock.acquire();
093:
094: // Only read "readers" once now before loop. We know it won't
095: // change because we hold the entry lock needed to update it.
096: int r = readers;
097:
098: try {
099: synchronized (this ) {
100: while (exreaders != r)
101: wait();
102: }
103: } catch (InterruptedException ie) {
104: entryLock.release();
105: throw ie;
106: }
107: }
108:
109: protected void releaseWrite() {
110: entryLock.release();
111: }
112:
113: protected boolean attemptRead(long msecs)
114: throws InterruptedException {
115: if (!entryLock.attempt(msecs))
116: return false;
117:
118: ++readers;
119: entryLock.release();
120: return true;
121: }
122:
123: protected boolean attemptWrite(long msecs)
124: throws InterruptedException {
125: long startTime = (msecs <= 0) ? 0 : System.currentTimeMillis();
126:
127: if (!entryLock.attempt(msecs))
128: return false;
129:
130: int r = readers;
131:
132: try {
133: synchronized (this ) {
134: while (exreaders != r) {
135: long timeLeft = (msecs <= 0) ? 0 : msecs
136: - (System.currentTimeMillis() - startTime);
137:
138: if (timeLeft <= 0) {
139: entryLock.release();
140: return false;
141: }
142:
143: wait(timeLeft);
144: }
145: return true;
146: }
147: } catch (InterruptedException ie) {
148: entryLock.release();
149: throw ie;
150: }
151: }
152:
153: // support for ReadWriteLock interface
154:
155: protected class ReaderSync implements Sync {
156: public void acquire() throws InterruptedException {
157: acquireRead();
158: }
159:
160: public void release() {
161: releaseRead();
162: }
163:
164: public boolean attempt(long msecs) throws InterruptedException {
165: return attemptRead(msecs);
166: }
167: }
168:
169: protected class WriterSync implements Sync {
170: public void acquire() throws InterruptedException {
171: acquireWrite();
172: }
173:
174: public void release() {
175: releaseWrite();
176: }
177:
178: public boolean attempt(long msecs) throws InterruptedException {
179: return attemptWrite(msecs);
180: }
181: }
182:
183: protected final Sync readerSync = new ReaderSync();
184: protected final Sync writerSync = new WriterSync();
185:
186: public Sync writeLock() {
187: return writerSync;
188: }
189:
190: public Sync readLock() {
191: return readerSync;
192: }
193:
194: }
|