Mercurial > hg > blitz_stable

comparison src/EDU/oswego/cs/dl/util/concurrent/FIFOReadWriteLock.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: FIFOReadWriteLock.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 23nov2001 dl Replace main algorithm with fairer
13 version based on one by Alexander Terekhov
14 */
15
16 package EDU.oswego.cs.dl.util.concurrent;
17
18
19 /**
20 * This class implements a policy for reader/writer locks in which
21 * threads contend in a First-in/First-out manner for access (modulo
22 * the limitations of FIFOSemaphore, which is used for queuing). This
23 * policy does not particularly favor readers or writers. As a
24 * byproduct of the FIFO policy, the <tt>attempt</tt> methods may
25 * return <tt>false</tt> even when the lock might logically be
26 * available, but, due to contention, cannot be accessed within the
27 * given time bound. <p>
28 *
29 * This lock is <em>NOT</em> reentrant. Current readers and
30 * writers should not try to re-obtain locks while holding them.
31 * <p>
32 *
33 * [<a href="http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html"> Introduction to this package. </a>] <p>
34 *
35 * @see FIFOSemaphore
36 **/
37
38 public class FIFOReadWriteLock implements ReadWriteLock {
39
40 /**
41 * Fair Semaphore serving as a kind of mutual exclusion lock.
42 * Writers acquire on entry, and hold until rwlock exit.
43 * Readers acquire and release only during entry (but are
44 * blocked from doing so if there is an active writer).
45 **/
46 protected final FIFOSemaphore entryLock = new FIFOSemaphore(1);
47
48 /**
49 * Number of threads that have entered read lock. Note that this is
50 * never reset to zero. Incremented only during acquisition of read
51 * lock while the "entryLock" is held, but read elsewhere, so is
52 * declared volatile.
53 **/
54 protected volatile int readers;
55
56 /**
57 * Number of threads that have exited read lock. Note that this is
58 * never reset to zero. Accessed only in code protected by
59 * synchronized(this). When exreaders != readers, the rwlock is
60 * being used for reading. Else if the entry lock is held, it is
61 * being used for writing (or in transition). Else it is free.
62 * Note: To distinguish these states, we assume that fewer than 2^32
63 * reader threads can simultaneously execute.
64 **/
65 protected int exreaders;
66
67 protected void acquireRead() throws InterruptedException {
68 entryLock.acquire();
69 ++readers;
70 entryLock.release();
71 }
72
73 protected synchronized void releaseRead() {
74 /*
75 If this is the last reader, notify a possibly waiting writer.
76 Because waits occur only when entry lock is held, at most one
77 writer can be waiting for this notification. Because increments
78 to "readers" aren't protected by "this" lock, the notification
79 may be spurious (when an incoming reader in in the process of
80 updating the field), but at the point tested in acquiring write
81 lock, both locks will be held, thus avoiding false alarms. And
82 we will never miss an opportunity to send a notification when it
83 is actually needed.
84 */
85
86 if (++exreaders == readers)
87 notify();
88 }
89
90 protected void acquireWrite() throws InterruptedException {
91 // Acquiring entryLock first forces subsequent entering readers
92 // (as well as writers) to block.
93 entryLock.acquire();
94
95 // Only read "readers" once now before loop. We know it won't
96 // change because we hold the entry lock needed to update it.
97 int r = readers;
98
99 try {
100 synchronized(this) {
101 while (exreaders != r)
102 wait();
103 }
104 }
105 catch (InterruptedException ie) {
106 entryLock.release();
107 throw ie;
108 }
109 }
110
111 protected void releaseWrite() {
112 entryLock.release();
113 }
114
115 protected boolean attemptRead(long msecs) throws InterruptedException {
116 if (!entryLock.attempt(msecs))
117 return false;
118
119 ++readers;
120 entryLock.release();
121 return true;
122 }
123
124 protected boolean attemptWrite(long msecs) 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:
136 msecs - (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 }
148 catch (InterruptedException ie) {
149 entryLock.release();
150 throw ie;
151 }
152 }
153
154 // support for ReadWriteLock interface
155
156 protected class ReaderSync implements Sync {
157 public void acquire() throws InterruptedException {
158 acquireRead();
159 }
160 public void release() {
161 releaseRead();
162 }
163 public boolean attempt(long msecs) throws InterruptedException {
164 return attemptRead(msecs);
165 }
166 }
167
168 protected class WriterSync implements Sync {
169 public void acquire() throws InterruptedException {
170 acquireWrite();
171 }
172 public void release() {
173 releaseWrite();
174 }
175 public boolean attempt(long msecs) throws InterruptedException {
176 return attemptWrite(msecs);
177 }
178 }
179
180 protected final Sync readerSync = new ReaderSync();
181 protected final Sync writerSync = new WriterSync();
182
183 public Sync writeLock() { return writerSync; }
184 public Sync readLock() { return readerSync; }
185
186 }