PLT Utilities Test Coverage (plt-20120304-r5436)

Clover coverage report - PLT Utilities Test Coverage (plt-20120304-r5436)

Coverage timestamp: Sat Mar 3 2012 22:01:56 CST

FRAMES NO FRAMES

file stats:	LOC:	329		Methods:	15
	NCLOC:	120		Classes:	4

Source file

Conditionals

Statements

Methods

TOTAL

ReaderWriterLock.java

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