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 4504 2008-06-03 06:19:20Z 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.

Constructor Summary

ReaderWriterLock()
Creates a new ReaderWriterLock.

Method Summary

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

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