ReaderWriterLock


1   /*BEGIN_COPYRIGHT_BLOCK
2    *
3    * This file is part of DrJava.  Download the current version of this project from http://www.drjava.org/
4    * or http://sourceforge.net/projects/drjava/
5    *
6    * DrJava Open Source License
7    * 
8    * Copyright (C) 2001-2006 JavaPLT group at Rice University (javaplt@rice.edu).  All rights reserved.
9    *
10   * Developed by:   Java Programming Languages Team, Rice University, http://www.cs.rice.edu/~javaplt/
11   * 
12   * Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated 
13   * documentation files (the "Software"), to deal with the Software without restriction, including without limitation
14   * the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and 
15   * to permit persons to whom the Software is furnished to do so, subject to the following conditions:
16   * 
17   *     - Redistributions of source code must retain the above copyright notice, this list of conditions and the 
18   *       following disclaimers.
19   *     - Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the 
20   *       following disclaimers in the documentation and/or other materials provided with the distribution.
21   *     - Neither the names of DrJava, the JavaPLT, Rice University, nor the names of its contributors may be used to 
22   *       endorse or promote products derived from this Software without specific prior written permission.
23   *     - Products derived from this software may not be called "DrJava" nor use the term "DrJava" as part of their 
24   *       names without prior written permission from the JavaPLT group.  For permission, write to javaplt@rice.edu.
25   * 
26   * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO 
27   * THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 
28   * CONTRIBUTORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF 
29   * CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS 
30   * WITH THE SOFTWARE.
31   * 
32   *END_COPYRIGHT_BLOCK*/
33  
34  package edu.rice.cs.util;
35  
36  import java.util.LinkedList  ;
37  
38  /**
39   * This class implements synchronization primitives to solve the classic
40   * readers/writers problem without allowing deadlock or starvation.
41   * 
42   * <p>
43   * Problem: Suppose multiple threads want to read and write to a resource.
44   * Multiple readers can be active at a time, but only a single writer can
45   * be active at a time, and no readers can be active while the writer is
46   * active.
47   * </p>
48   * 
49   * <p>
50   * We must be careful to avoid starvation in our solution, so that a steady
51   * flow of reader threads cannot block waiting writer threads indefinitely.
52   * This can be achieved by imposing an ordering on the incoming readers
53   * and writers.
54   * </p>
55   * 
56   * <p>
57   * To use this class, instantiate a ReaderWriterLock in the class holding
58   * the shared resource.  Any methods which read from the resource must call
59   * startRead before reading and endRead after reading, and must not be
60   * synchronized themselves.  Similarly, any methods which write to the resource
61   * must not be synchronized and must call startWrite before writing and endWrite
62   * after writing.
63   * </p>
64   * 
65   * <p>
66   * This class enforces that any readers and writers that are forced to wait
67   * are allowed access to the shared resource in the order in which they arrive.
68   * Groups of readers are allowed to proceed simultaneously, where each group
69   * contains all waiting readers that arrived before the next waiting writer.
70   * </p>
71   * 
72   * <p>
73   * This class is loosely adapted from the "Starvation-Free Readers and Writers
74   * Monitor" available from Stephen J. Hartley (Drexel University) at:
75   * http://www.mcs.drexel.edu/~shartley/ConcProgJava/monitors.html
76   * We have imposed an ordering on the pending waiting readers and writers
77   * using an ordered queue.
78   * </p>
79   * 
80   * @version $Id: ReaderWriterLock.java 4031 2006-11-15 22:09:06Z rcartwright $
81   */
82  public class ReaderWriterLock {
83    /** The number of readers currently reading. */
84    private volatile int _numActiveReaders = 0;
85    /** The number of writers currently writing (ie. 0 or 1). */
86    private volatile int _numActiveWriters = 0;
87    /** The number of readers waiting to read. */
88    private volatile int _numWaitingReaders = 0;
89    /** The number of writers waiting to write. */
90    private volatile int _numWaitingWriters = 0;
91    
92    /**
93     * Queue of all waiting reader and writer threads.  The front of the queue
94     * (first element of the list) represents the thread which arrived first;
95     * new waiting threads are added at the end.
96     * "Groups" on the queue refer to several sequential Readers or a
97     * single Writer.  (We can wake up the front group on the queue each
98     * time a writer finishes and each time the last reader finishes.)
99     */
100   private final LinkedList  <ReaderWriterThread> _waitQueue;
101   
102   /**
103    * A list of the Threads that are currently reading or writing.
104    * We maintain this list to prevent the deadlock which would occur if
105    * a Thread which is reading or writing attempted to read or write again.
106    * (If that happens, we throw an IllegalStateException.)
107    */
108   private final LinkedList  <Thread  > _runningThreads;
109   
110   /** Creates a new ReaderWriterLock. */
111   public ReaderWriterLock() {
112     _waitQueue = new LinkedList  <ReaderWriterThread>();
113     _runningThreads = new LinkedList  <Thread  >();
114   }
115   
116   /** Must be called by each reader thread before starting to read.  The calling method must <i>not</i> be 
117    *  synchronized.  This method blocks the reader if there are current active or waiting writers, until those 
118    *  writers have finished.
119    *  @throws IllegalStateException if the thread is already a reader or writer
120    */
121   public synchronized void startRead() {
122     // If we're already reading, we can perform another read without waiting
123     if (!_alreadyReading()) {
124       
125       // Make sure this thread isn't already writing.
126       _ensureNotAlreadyRunning();
127       
128       // Check if any writers are active or waiting
129       if (_numWaitingWriters > 0 || _numActiveWriters > 0) {
130         // If so, we wait until it's our turn (on the waitQueue)
131         _numWaitingReaders++;
132         Reader r = new Reader();
133         r.startWaiting();
134         
135         // Ok, we're no longer on the waitQueue
136         _numWaitingReaders--;
137       }
138     }
139     
140     // Ok, start the read
141     _numActiveReaders++;
142     _runningThreads.add(Thread.currentThread());
143   }
144   
145   /** Must be called by each reader thread after it is finished reading.  The calling method must <i>not</i> be 
146    *  synchronized. This method wakes up a waiting writer if there are no remaining reader threads actively reading.
147    * 
148    *  @throws IllegalStateException if the thread is already a reader or writer
149    */
150   public synchronized void endRead() {
151     if (_numActiveReaders == 0) {
152       throw new IllegalStateException  ("Trying to end a read with no active readers!");
153     }
154     
155     _numActiveReaders--;
156     _ensureAlreadyRunning();
157     _runningThreads.remove(Thread.currentThread());
158     
159     // There shouldn't be any active writers at this point
160     if (_numActiveWriters > 0) {
161       String   msg = "A writer was active during a read!";
162       throw new UnexpectedException(new Exception  (msg));
163     }
164     
165     // Only safe to write if there are no more active readers
166     if (_numActiveReaders == 0) {
167       // Wake up any waiting writers
168       //  (We expect there to be a writer at the front, if anything.)
169       _wakeFrontGroupOfWaitQueue();
170     }
171   }
172   
173   
174   /** Must be called by each writer thread before starting to write.  The calling method must <i>not</i> be 
175    *  synchronized. This method blocks the writer if there are any active readers or writers, and prevents any new 
176    *  readers from starting to read until this writer gets a chance to write.
177    * 
178    *  @throws IllegalStateException if the thread is already a reader or writer
179    */
180   public synchronized void startWrite() {
181     // Make sure this thread isn't already reading or writing.
182     _ensureNotAlreadyRunning();
183     
184     // Can only write if no other readers *or* writers
185     // Note: normally, there will be no waiting readers/writers if there
186     //  are no active reader/writers.  However, a new thread could call
187     //  startWrite at just the wrong time, allowing it to sneak in after
188     //  the last reader/writer finished, while others are waiting.  Thus,
189     //  we also check to see if anyone is waiting.
190     if ((_numActiveReaders > 0 || _numActiveWriters > 0) ||
191         (_numWaitingReaders > 0 || _numWaitingWriters > 0)) {
192       // Must wait
193       _numWaitingWriters++;
194       
195       // If _okToWrite is true, it means there are no active writers (and thus
196       //  there are active readers).  We set it to false so that we wait until
197       //  the last reader finishes, setting it back to true in endRead().
198       //_okToWrite = false;
199       
200       Writer w = new Writer();
201       w.startWaiting();
202 
203       _numWaitingWriters--;
204     }
205     
206     // We're writing now, so it's not ok for others to write
207     _numActiveWriters++;
208     _runningThreads.add(Thread.currentThread());
209   }
210   
211   /** Must be called by each writer thread after it is finished writing.  The calling method must <i>not</i> be 
212    *  synchronized. This method wakes up any waiting readers and writers.  If there are waiting readers, they read 
213    *  before the next writer, but any new readers (after this call) wait until the next waiting writer writes.
214    * 
215    *  @throws IllegalStateException if the thread is already a reader or writer
216    */
217   public synchronized void endWrite() {
218     if (_numActiveWriters != 1) {
219       throw new IllegalStateException  ("Trying to end a write with " +
220                                       _numActiveWriters + " active writers!");
221     }
222     
223     _numActiveWriters--;
224     _ensureAlreadyRunning();
225     _runningThreads.remove(Thread.currentThread());
226     
227     // There shouldn't be any active threads at this point
228     if ((_numActiveWriters > 0) || (_numActiveReaders > 0)) {
229       String   msg = "Multiple readers/writers were active during a write!";
230       throw new UnexpectedException(new Exception  (msg));
231     }
232     
233     // Wake up any waiting readers and writers
234     _wakeFrontGroupOfWaitQueue();
235   }
236   
237   /** Checks if the current thread is already a reader. */
238   private boolean _alreadyReading() {
239     // If the current thread is active, and there are active readers, then
240     //  the current thread must be a reader and not a writer.
241     return _numActiveReaders > 0 &&
242            _runningThreads.contains(Thread.currentThread());
243       
244   }
245 
246   /** Ensures that the current thread is not already considered a reader or writer.  This prevents the deadlock which 
247    *  would occur if a reader thread tries to write (or vice versa).
248    *  @throws IllegalStateException if the thread is already a reader or writer
249    */
250   private void _ensureNotAlreadyRunning() {
251     if (_runningThreads.contains(Thread.currentThread())) {
252       throw new IllegalStateException  ("Same thread cannot read or write multiple " +
253                                       "times!  (Would cause deadlock.)");
254     }
255   }
256   
257   /**  Ensures that the current thread is not already considered a reader or writer.  This prevents the deadlock which 
258    *   would occur if a reader thread tries to write (or vice versa).
259    *   @throws IllegalStateException if the thread is already a reader or writer
260    */
261   private void _ensureAlreadyRunning() {
262     if (!_runningThreads.contains(Thread.currentThread())) {
263       throw new IllegalStateException  ("Current thread did not initiate a read or write!");
264     }
265   }
266   
267   /** Wakes up either the writer or all sequential readers before a writer at the front of the waitQueue. */
268   private synchronized void _wakeFrontGroupOfWaitQueue() {
269     if (!_waitQueue.isEmpty()) {
270       // Wake, whether it's a reader or writer
271       ReaderWriterThread front = _waitQueue.getFirst();
272       front.stopWaiting();  // removes front from queue
273       
274       // If it's a reader, wake up more until we find a writer
275       if (front.isReader()) {
276         while (!_waitQueue.isEmpty()) {
277           front = _waitQueue.getFirst();
278           if (front.isReader()) {
279             front.stopWaiting();  // removes front from queue
280           }
281           else {
282             // Found a writer, so we're done
283             break;
284           }
285         }
286       }
287     }
288   }
289   
290   
291   /** Represents a thread waiting to either read or write.  Instances of this class are placed in a queue to enforce
292    *  the correct order when allowing new threads to read or write.  The waiting thread must call wait() on this object,
293    *  allowing it to be notified when it reaches the front of the queue.  This object will remain on the queue until the
294    *  thread completes its read or write, allowing us to check for and prevent deadlock if the same thread tries to both 
295    *  read and write at the same time.
296    */
297   public abstract class ReaderWriterThread {
298     private volatile boolean _isWaiting = true;
299     /** Returns whether this ReaderWriter is a writer. */
300     public abstract boolean isWriter();
301     /** Returns whether this ReaderWriter is a reader. */
302     public abstract boolean isReader();
303     
304     /** Causes this ReaderWriterThread to wait until stopWaiting is called. While it's waiting, it is on the waitQueue.
305      */
306     public void startWaiting() {
307       synchronized(ReaderWriterLock.this) {
308         _isWaiting = true;
309         _waitQueue.addLast(this);
310         while (_isWaiting) {
311           try { ReaderWriterLock.this.wait(); }
312           catch (InterruptedException   e) {
313             // loop checks if we still need to wait...
314           }
315         }
316       }
317     }
318     
319     /** Wakes up this ReaderWriterThread, removing it from the waitQueue. */
320     public void stopWaiting() {
321       synchronized(ReaderWriterLock.this) {
322         _isWaiting = false;
323         _waitQueue.remove(this);  // note: we must be in the front group!
324         ReaderWriterLock.this.notifyAll();
325       }
326     }
327   }
328   
329   /** Object representing a reader thread which is waiting for read access on the queue of waiting threads. */
330   public class Reader extends ReaderWriterThread {
331     public boolean isReader() { return true; }
332     public boolean isWriter() { return false; }
333   }
334   
335   /** Object representing a writer thread which is waiting for write access on the queue of waiting threads. */
336   public class Writer extends ReaderWriterThread {
337     public boolean isReader() { return false; }
338     public boolean isWriter() { return true; }
339   }
340 }
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags