001: /*BEGIN_COPYRIGHT_BLOCK
002: *
003: * Copyright (c) 2001-2007, JavaPLT group at Rice University (javaplt@rice.edu)
004: * All rights reserved.
005: *
006: * Redistribution and use in source and binary forms, with or without
007: * modification, are permitted provided that the following conditions are met:
008: * * Redistributions of source code must retain the above copyright
009: * notice, this list of conditions and the following disclaimer.
010: * * Redistributions in binary form must reproduce the above copyright
011: * notice, this list of conditions and the following disclaimer in the
012: * documentation and/or other materials provided with the distribution.
013: * * Neither the names of DrJava, the JavaPLT group, Rice University, nor the
014: * names of its contributors may be used to endorse or promote products
015: * derived from this software without specific prior written permission.
016: *
017: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
018: * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
019: * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
020: * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
021: * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
022: * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
023: * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
024: * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
025: * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
026: * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
027: * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
028: *
029: * This software is Open Source Initiative approved Open Source Software.
030: * Open Source Initative Approved is a trademark of the Open Source Initiative.
031: *
032: * This file is part of DrJava. Download the current version of this project
033: * from http://www.drjava.org/ or http://sourceforge.net/projects/drjava/
034: *
035: * END_COPYRIGHT_BLOCK*/
036:
037: package edu.rice.cs.util;
038:
039: import java.util.LinkedList;
040:
041: /**
042: * This class implements synchronization primitives to solve the classic
043: * readers/writers problem without allowing deadlock or starvation.
044: *
045: * <p>
046: * Problem: Suppose multiple threads want to read and write to a resource.
047: * Multiple readers can be active at a time, but only a single writer can
048: * be active at a time, and no readers can be active while the writer is
049: * active.
050: * </p>
051: *
052: * <p>
053: * We must be careful to avoid starvation in our solution, so that a steady
054: * flow of reader threads cannot block waiting writer threads indefinitely.
055: * This can be achieved by imposing an ordering on the incoming readers
056: * and writers.
057: * </p>
058: *
059: * <p>
060: * To use this class, instantiate a ReaderWriterLock in the class holding
061: * the shared resource. Any methods which read from the resource must call
062: * startRead before reading and endRead after reading, and must not be
063: * synchronized themselves. Similarly, any methods which write to the resource
064: * must not be synchronized and must call startWrite before writing and endWrite
065: * after writing.
066: * </p>
067: *
068: * <p>
069: * This class enforces that any readers and writers that are forced to wait
070: * are allowed access to the shared resource in the order in which they arrive.
071: * Groups of readers are allowed to proceed simultaneously, where each group
072: * contains all waiting readers that arrived before the next waiting writer.
073: * </p>
074: *
075: * <p>
076: * This class is loosely adapted from the "Starvation-Free Readers and Writers
077: * Monitor" available from Stephen J. Hartley (Drexel University) at:
078: * http://www.mcs.drexel.edu/~shartley/ConcProgJava/monitors.html
079: * We have imposed an ordering on the pending waiting readers and writers
080: * using an ordered queue.
081: * </p>
082: *
083: * @version $Id: ReaderWriterLock.java 4268 2007-11-29 00:52:17Z mgricken $
084: */
085: public class ReaderWriterLock {
086: /** The number of readers currently reading. */
087: private volatile int _numActiveReaders = 0;
088: /** The number of writers currently writing (ie. 0 or 1). */
089: private volatile int _numActiveWriters = 0;
090: /** The number of readers waiting to read. */
091: private volatile int _numWaitingReaders = 0;
092: /** The number of writers waiting to write. */
093: private volatile int _numWaitingWriters = 0;
094:
095: /**
096: * Queue of all waiting reader and writer threads. The front of the queue
097: * (first element of the list) represents the thread which arrived first;
098: * new waiting threads are added at the end.
099: * "Groups" on the queue refer to several sequential Readers or a
100: * single Writer. (We can wake up the front group on the queue each
101: * time a writer finishes and each time the last reader finishes.)
102: */
103: private final LinkedList<ReaderWriterThread> _waitQueue;
104:
105: /**
106: * A list of the Threads that are currently reading or writing.
107: * We maintain this list to prevent the deadlock which would occur if
108: * a Thread which is reading or writing attempted to read or write again.
109: * (If that happens, we throw an IllegalStateException.)
110: */
111: private final LinkedList<Thread> _runningThreads;
112:
113: /** Creates a new ReaderWriterLock. */
114: public ReaderWriterLock() {
115: _waitQueue = new LinkedList<ReaderWriterThread>();
116: _runningThreads = new LinkedList<Thread>();
117: }
118:
119: /** Must be called by each reader thread before starting to read. The calling method must <i>not</i> be
120: * synchronized. This method blocks the reader if there are current active or waiting writers, until those
121: * writers have finished.
122: * @throws IllegalStateException if the thread is already a reader or writer
123: */
124: public synchronized void startRead() {
125: // If we're already reading, we can perform another read without waiting
126: if (!_alreadyReading()) {
127:
128: // Make sure this thread isn't already writing.
129: _ensureNotAlreadyRunning();
130:
131: // Check if any writers are active or waiting
132: if (_numWaitingWriters > 0 || _numActiveWriters > 0) {
133: // If so, we wait until it's our turn (on the waitQueue)
134: _numWaitingReaders++;
135: Reader r = new Reader();
136: r.startWaiting();
137:
138: // Ok, we're no longer on the waitQueue
139: _numWaitingReaders--;
140: }
141: }
142:
143: // Ok, start the read
144: _numActiveReaders++;
145: _runningThreads.add(Thread.currentThread());
146: }
147:
148: /** Must be called by each reader thread after it is finished reading. The calling method must <i>not</i> be
149: * synchronized. This method wakes up a waiting writer if there are no remaining reader threads actively reading.
150: *
151: * @throws IllegalStateException if the thread is already a reader or writer
152: */
153: public synchronized void endRead() {
154: if (_numActiveReaders == 0) {
155: throw new IllegalStateException(
156: "Trying to end a read with no active readers!");
157: }
158:
159: _numActiveReaders--;
160: _ensureAlreadyRunning();
161: _runningThreads.remove(Thread.currentThread());
162:
163: // There shouldn't be any active writers at this point
164: if (_numActiveWriters > 0) {
165: String msg = "A writer was active during a read!";
166: throw new UnexpectedException(new Exception(msg));
167: }
168:
169: // Only safe to write if there are no more active readers
170: if (_numActiveReaders == 0) {
171: // Wake up any waiting writers
172: // (We expect there to be a writer at the front, if anything.)
173: _wakeFrontGroupOfWaitQueue();
174: }
175: }
176:
177: /** Must be called by each writer thread before starting to write. The calling method must <i>not</i> be
178: * synchronized. This method blocks the writer if there are any active readers or writers, and prevents any new
179: * readers from starting to read until this writer gets a chance to write.
180: *
181: * @throws IllegalStateException if the thread is already a reader or writer
182: */
183: public synchronized void startWrite() {
184: // Make sure this thread isn't already reading or writing.
185: _ensureNotAlreadyRunning();
186:
187: // Can only write if no other readers *or* writers
188: // Note: normally, there will be no waiting readers/writers if there
189: // are no active reader/writers. However, a new thread could call
190: // startWrite at just the wrong time, allowing it to sneak in after
191: // the last reader/writer finished, while others are waiting. Thus,
192: // we also check to see if anyone is waiting.
193: if ((_numActiveReaders > 0 || _numActiveWriters > 0)
194: || (_numWaitingReaders > 0 || _numWaitingWriters > 0)) {
195: // Must wait
196: _numWaitingWriters++;
197:
198: // If _okToWrite is true, it means there are no active writers (and thus
199: // there are active readers). We set it to false so that we wait until
200: // the last reader finishes, setting it back to true in endRead().
201: //_okToWrite = false;
202:
203: Writer w = new Writer();
204: w.startWaiting();
205:
206: _numWaitingWriters--;
207: }
208:
209: // We're writing now, so it's not ok for others to write
210: _numActiveWriters++;
211: _runningThreads.add(Thread.currentThread());
212: }
213:
214: /** Must be called by each writer thread after it is finished writing. The calling method must <i>not</i> be
215: * synchronized. This method wakes up any waiting readers and writers. If there are waiting readers, they read
216: * before the next writer, but any new readers (after this call) wait until the next waiting writer writes.
217: *
218: * @throws IllegalStateException if the thread is already a reader or writer
219: */
220: public synchronized void endWrite() {
221: if (_numActiveWriters != 1) {
222: throw new IllegalStateException(
223: "Trying to end a write with " + _numActiveWriters
224: + " active writers!");
225: }
226:
227: _numActiveWriters--;
228: _ensureAlreadyRunning();
229: _runningThreads.remove(Thread.currentThread());
230:
231: // There shouldn't be any active threads at this point
232: if ((_numActiveWriters > 0) || (_numActiveReaders > 0)) {
233: String msg = "Multiple readers/writers were active during a write!";
234: throw new UnexpectedException(new Exception(msg));
235: }
236:
237: // Wake up any waiting readers and writers
238: _wakeFrontGroupOfWaitQueue();
239: }
240:
241: /** Checks if the current thread is already a reader. */
242: private boolean _alreadyReading() {
243: // If the current thread is active, and there are active readers, then
244: // the current thread must be a reader and not a writer.
245: return _numActiveReaders > 0
246: && _runningThreads.contains(Thread.currentThread());
247:
248: }
249:
250: /** Ensures that the current thread is not already considered a reader or writer. This prevents the deadlock which
251: * would occur if a reader thread tries to write (or vice versa).
252: * @throws IllegalStateException if the thread is already a reader or writer
253: */
254: private void _ensureNotAlreadyRunning() {
255: if (_runningThreads.contains(Thread.currentThread())) {
256: throw new DeadlockException(
257: "Same thread cannot read or write multiple "
258: + "times! (Would cause deadlock.)");
259: }
260: }
261:
262: /** Ensures that the current thread is not already considered a reader or writer. This prevents the deadlock which
263: * would occur if a reader thread tries to write (or vice versa).
264: * @throws IllegalStateException if the thread is already a reader or writer
265: */
266: private void _ensureAlreadyRunning() {
267: if (!_runningThreads.contains(Thread.currentThread())) {
268: throw new IllegalStateException(
269: "Current thread did not initiate a read or write!");
270: }
271: }
272:
273: /** Wakes up either the writer or all sequential readers before a writer at the front of the waitQueue. */
274: private synchronized void _wakeFrontGroupOfWaitQueue() {
275: if (!_waitQueue.isEmpty()) {
276: // Wake, whether it's a reader or writer
277: ReaderWriterThread front = _waitQueue.getFirst();
278: front.stopWaiting(); // removes front from queue
279:
280: // If it's a reader, wake up more until we find a writer
281: if (front.isReader()) {
282: while (!_waitQueue.isEmpty()) {
283: front = _waitQueue.getFirst();
284: if (front.isReader()) {
285: front.stopWaiting(); // removes front from queue
286: } else {
287: // Found a writer, so we're done
288: break;
289: }
290: }
291: }
292: }
293: }
294:
295: /** Represents a thread waiting to either read or write. Instances of this class are placed in a queue to enforce
296: * the correct order when allowing new threads to read or write. The waiting thread must call wait() on this object,
297: * allowing it to be notified when it reaches the front of the queue. This object will remain on the queue until the
298: * thread completes its read or write, allowing us to check for and prevent deadlock if the same thread tries to both
299: * read and write at the same time.
300: */
301: public abstract class ReaderWriterThread {
302: private volatile boolean _isWaiting = true;
303:
304: /** Returns whether this ReaderWriter is a writer. */
305: public abstract boolean isWriter();
306:
307: /** Returns whether this ReaderWriter is a reader. */
308: public abstract boolean isReader();
309:
310: /** Causes this ReaderWriterThread to wait until stopWaiting is called. While it's waiting, it is on the waitQueue.
311: */
312: public void startWaiting() {
313: synchronized (ReaderWriterLock.this ) {
314: _isWaiting = true;
315: _waitQueue.addLast(this );
316: while (_isWaiting) {
317: try {
318: ReaderWriterLock.this .wait();
319: } catch (InterruptedException e) {
320: // loop checks if we still need to wait...
321: }
322: }
323: }
324: }
325:
326: /** Wakes up this ReaderWriterThread, removing it from the waitQueue. */
327: public void stopWaiting() {
328: synchronized (ReaderWriterLock.this ) {
329: _isWaiting = false;
330: _waitQueue.remove(this ); // note: we must be in the front group!
331: ReaderWriterLock.this .notifyAll();
332: }
333: }
334: }
335:
336: /** Object representing a reader thread which is waiting for read access on the queue of waiting threads. */
337: public class Reader extends ReaderWriterThread {
338: public boolean isReader() {
339: return true;
340: }
341:
342: public boolean isWriter() {
343: return false;
344: }
345: }
346:
347: /** Object representing a writer thread which is waiting for write access on the queue of waiting threads. */
348: public class Writer extends ReaderWriterThread {
349: public boolean isReader() {
350: return false;
351: }
352:
353: public boolean isWriter() {
354: return true;
355: }
356: }
357:
358: /** Class representing a reader-writer deadlock that would have occurred if the acquire operation
359: * had been executed. */
360: public class DeadlockException extends IllegalStateException {
361: public DeadlockException() {
362: }
363:
364: public DeadlockException(String s) {
365: super (s);
366: }
367:
368: public DeadlockException(String s, Throwable t) {
369: super (s, t);
370: }
371:
372: public DeadlockException(Throwable t) {
373: super(t);
374: }
375: }
376: }
|