DrJava Test Coverage (drjava-20120304-r5456)

Clover coverage report - DrJava Test Coverage (drjava-20120304-r5456)

Coverage timestamp: Sun Mar 4 2012 03:13:23 CST

FRAMES NO FRAMES

file stats:	LOC:	321		Methods:	19
	NCLOC:	137		Classes:	5

Source file

Conditionals

Statements

Methods

TOTAL

ReaderWriterLock.java

80%

84.1%

73.7%

81.4%

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