edu.rice.cs.util
Class ReaderWriterLock

java.lang.Object
  edu.rice.cs.util.ReaderWriterLock

public class ReaderWriterLock
extends Object

This class implements synchronization primitives to solve the classic readers/writers problem without deadlock or starvation.

Problem: Suppose multiple threads want to read and write a resource. Multiple threads can safely read at the same time, but only one thread can safely write at a time, and no threads can read while a thread is writing.

We must be careful to avoid starvation in our solution, so that a steady flow of reader threads cannot block waiting writer threads indefinitely. This property can be achieved by imposing an ordering on the incoming readers and writers.

To use this class, instantiate a ReaderWriterLock in the class holding the shared resource. Any methods which read from the resource must call startRead before reading and endRead after reading, and must not be synchronized themselves. Similarly, any methods which write to the resource must not be synchronized and must call startWrite before writing and endWrite after writing.

This class enforces that any readers and writers that are forced to wait are given access to the shared resource in the order in which they arrive. Groups of readers are allowed to proceed simultaneously, where each group contains all waiting readers that arrived before the next waiting writer.

This class is loosely adapted from the "Starvation-Free Readers and Writers Monitor" available from Stephen J. Hartley (Drexel University) at: http://www.mcs.drexel.edu/~shartley/ConcProgJava/monitors.html We have imposed an ordering on the pending waiting readers and writers using an ordered queue.

TODO: revise this formulation of readers/writers to allow writers to recursively readLock and writeLock!

Version:

$Id: ReaderWriterLock.java 5440 2011-08-12 01:54:19Z rcartwright $

Nested Class Summary

static class	ReaderWriterLock.DeadlockException Class representing a deadlock that would have occurred if the acquire operation had been executed.
class	ReaderWriterLock.Reader Object representing a reader thread which is waiting for read access on the queue of waiting threads.
class	ReaderWriterLock.ReaderWriterThread Represents a thread waiting to either read or write.
class	ReaderWriterLock.Writer Object representing a writer thread which is waiting for write access on the queue of waiting threads.

Field Summary

private int	_numActiveReaders The number of readers currently reading.
private int	_numActiveWriters The number of writers currently writing (ie.
private int	_numWaitingReaders The number of readers waiting to read.
private int	_numWaitingWriters The number of writers waiting to write.
private LinkedList<Thread>	_runningThreads A list of the Threads that are currently reading or writing.
private LinkedList<ReaderWriterLock.ReaderWriterThread>	_waitQueue Queue of all waiting reader and writer threads.

Constructor Summary

ReaderWriterLock()
Creates a new ReaderWriterLock.

Method Summary

private boolean	_alreadyReading() Checks if the current thread is already a reader.
private void	_ensureAlreadyRunning() Ensures that the current thread is already considered a reader or writer.
private void	_ensureNotAlreadyRunning() Ensures that the current thread is not already considered a reader or writer.
private void	_wakeFrontGroupOfWaitQueue() Wakes up either the writer or all sequential readers before a writer at the front of the waitQueue.
void	endRead() Must be called by each reader thread after it is finished reading.
void	endWrite() Must be called by each writer thread after it is finished writing.
void	startRead() Must be called by each reader thread before starting to read.
void	startWrite() Must be called by each writer thread before starting to write.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

_numActiveReaders

private volatile int _numActiveReaders

The number of readers currently reading.

_numActiveWriters

private volatile int _numActiveWriters

The number of writers currently writing (ie. 0 or 1).

_numWaitingReaders

private volatile int _numWaitingReaders

The number of readers waiting to read.

_numWaitingWriters

private volatile int _numWaitingWriters

The number of writers waiting to write.

_waitQueue

private final LinkedList<ReaderWriterLock.ReaderWriterThread> _waitQueue

Queue of all waiting reader and writer threads. The front of the queue (first element of the list) represents the thread which arrived first; new waiting threads are added at the end. "Groups" on the queue refer to several sequential Readers or a single Writer. (We can wake up the front group on the queue each time a writer finishes and each time the last reader finishes.)

_runningThreads

private final LinkedList<Thread> _runningThreads

A list of the Threads that are currently reading or writing. We maintain this list to prevent the deadlock which would occur if a Thread which is reading or writing attempted to read or write again. (If that happens, we throw an IllegalStateException.)

Constructor Detail

ReaderWriterLock

public ReaderWriterLock()

Creates a new ReaderWriterLock.

Method Detail

startRead

public void startRead()

Must be called by each reader thread before starting to read. The calling method must not be synchronized. This method blocks the reader if there are current active or waiting writers, until those writers have finished.

Throws:

IllegalStateException - if the thread is already a reader or writer

endRead

public void endRead()

Must be called by each reader thread after it is finished reading. The calling method must not be synchronized. This method wakes up a waiting writer if there are no remaining reader threads actively reading.

Throws:

IllegalStateException - if the thread is already a reader or writer

startWrite

public void startWrite()

Must be called by each writer thread before starting to write. The calling method must not be synchronized. This method blocks the writer if there are any active readers or writers, and prevents any new readers from starting to read until this writer gets a chance to write.

Throws:

IllegalStateException - if the thread is already a reader or writer

endWrite

public void endWrite()

Must be called by each writer thread after it is finished writing. The calling method must not be synchronized. This method wakes up any waiting readers and writers. If there are waiting readers, they read before the next writer, but any new readers (after this call) wait until the next waiting writer writes.

Throws:

IllegalStateException - if the thread is already a reader or writer

_alreadyReading

private boolean _alreadyReading()

Checks if the current thread is already a reader.

_ensureNotAlreadyRunning

private void _ensureNotAlreadyRunning()

Ensures that the current thread is not already considered a reader or writer. This prevents deadlock if a reader thread is trying to write (or vice versa).

Throws:

IllegalStateException - if the thread is already a reader or writer

_ensureAlreadyRunning

private void _ensureAlreadyRunning()

Ensures that the current thread is already considered a reader or writer. This prevents deadlock if a reader thread is trying to write (or vice versa).

Throws:

IllegalStateException - if the thread is already a reader or writer

_wakeFrontGroupOfWaitQueue

private void _wakeFrontGroupOfWaitQueue()

Wakes up either the writer or all sequential readers before a writer at the front of the waitQueue.