Thomas W. Christopher

Consulting in High Performance Computing.
Training in Concurrency, Networking, and Parallelism, especially in Python and Java.

Animation of Multiple Readers/Writers Algorithms

Abstract

These demonstration pages contain Java Applets that animate solutions to the Multiple Readers/Writers problem, a classic O/S problem in coordinating access to a shared resource.

Author

Thomas W. Christopher
Tools of Computing
tc AT tools HYPHEN of HYPHEN computing DOT com

Requirements

This requires Java JDK1.1 or greater. It uses the 1.1 event model that is not implemented in earlier versions of Java. You can get a Java 1.1 system for your Netscape or Microsoft browser if you haven't yet.

The Multiple Readers/Writers Problem

Threads that share data structures can run into problems if one of the threads is writing into the structure while another thread is reading it, or if two threads try to write into it at the same time. This is because typically several values must be stored to move the data structure from one consistent state to another. When only some of the stores have been made when it is read, the reader will get confused. If more than one thread is writing into it, some of the fields may end up changed by one of the threads and other fields changed by the other, and thereafter anyone reading it will be confused.

The easiest solution is to lock the data structure whenever accessing it. Any other thread trying to access the structure will have to wait until it is unlocked before being able to lock the structure itself. The simulation below shows this solution.

The problem with locking the data structure is this: although it is essential to prevent any thread from writing into the data structure while another thread is writing or reading, there is no reason to prevent several threads from simultaneously reading. If many threads are permitted to read at the same time, we would expect better performance.

TestSingleReaderWriter About the Simulation

Single Reader/Writer

This applet animates a monitor that allows only a single process to access the resource at a time, whether the process is a reader or a writer.

Color codes

The simulation includes an array of buttons that indicate the states of the threads accessing the shared structure. Their colors indicate their states:

Red writing

Blue reading

Magenta waiting to write

Cyan waiting to read

White resting between reads and/or writes

Gray has finished its iterations

How the change the parameters

You may choose to have a thread choose randomly each time whether to read or write (the default) or always be a reader or a writer. The "% reads" and "# readers" radio buttons choose which. You use the corresponding text fields to specify the percentage probability of reading or the number of threads that are readers, respectively.

To change any number, edit the field and then type ENTER. The new value will not be stored until ENTER is pressed. [I should probably change this to store the changes immediately. Having to press ENTER is annoying. -TC]

You can change any of the values in the left column. The actual read and write and rest times are generated from negative exponential distributions. You get to specify their mean values. If you change the mean read, write, or rest times, you should probably no go much below 200ms; smaller values don't give Java enough time to refresh the display.

The bottom four text fields on the right are output fields. Although you can change them yourself, it won't have any influence on the simulation.

Policies

These pages compare four policies for synchronizing threads trying to read or write a shared data structure.

*	The Single Reader/Writer Monitor, simulated on this page, locks the data structure so that only one thread can access the data structure at a time, whether the thread is a Reader or a Writer.
*	The Writers Preferred Monitor will give the shared structure to a waiting writer, if there is one, and only if there is no writer waiting will it be given to readers. All waiting readers will be allowed to access the structure at the same time.
*	The Readers-Preferred Monitor will give the shared structure to all waiting readers, if there are any, and only if there is no reader waiting will it be given to a writer.
*	The Alternating-Readers/Writers Monitor will give the shared structure to a waiting writer when readers have finished with it and to readers when a writer has finished with it.
*	The Queued-Readers/Writers Monitor gives the shared resource to the threads in order of arrival.

The Writers-Preferred, Readers-Preferred, and Alternating-Readers/Writers Monitors all have complexities in design that are discussed on their individual pages.

Entering and Leaving the Critical Sections

Readers and writers must explicitly lock and unlock the shared resource. The locking is done via method calls to a monitor object that implements the desired policy:

Reader

monitor.startReading();
try {
	...read...

} finally {monitor.stopReading();}

Writer

monitor.startWriting();
try {
	...write...

} finally {monitor.stopWriting();}

The reason for the try...finally statements is that the thread could throw an exception within the code to read or write. It is important to unlock shared resources upon abnormal exit.

The Single-Reader/Writer Monitor

This demonstration shows a simple lock on the data structure. Only a single reader or writer can access the shared resource at one time.

With a fair scheduling algorithm, each thread in turn should get a chance to run, cycling through the threads over and over. Most Java implementations this has been run on are not fair: a small subset of the threads run while all the others wait.

The Single Reader/Writer Monitor is equivalent to a lock or binary semaphore. Methods startReading and startWriting are identical as are stopReading and stopWriting.

The code is


class SingleReaderWriter extends MultipleReadersWritersMonitor{
int n=0;    /* number readers reading and writers writing, 0 or 1*/
public void reset(){
    n=0;
}
public synchronized void startReading() 
        throws InterruptedException{
    while (n!=0) wait();
    n=1;
}
public synchronized void stopReading(){
    n=0;
    notify();
}
public synchronized void startWriting() 
        throws InterruptedException{
    while (n!=0) wait();
    n=1;
}
public synchronized void stopWriting(){
    n=0;
    notify();
}
public String getMonitorInfo(){
    return "Single Reader Writer Monitor";
}
}

AWT

We give the Applet a BorderLayout. Into the North section we put a new Panel containing a Label. The content of the label is the string returned by the monitor's getMonitorInfo() method.

The Center of the Applet contains the array of buttons representing the threads. Each thread is of a class ReaderWriter that extends Button and implements Runnable (an example where multiple inheritance is useful).

The ReaderWriter buttons are placed in a panel which has been given a GridLayout. This panel is placed in another panel which is placed in the Center of the Applet. Why the extra layer? BorderLayout enlarges contents to fill all the space available, and we didn't want huge buttons.

The South section of the Applet is filled with a panel laid out with a GridBagLayout. It is composed of four columns.

The Restart button is centered in the top row, extending across all four columns. It is inset (given an Insets object) with 10 pixels on the south side so it won't be flush against the other rows.

The labels (and checkboxs) in the first and third columns are right justified. The text fields are left justified.

The check boxes for "% reads" and "# readers" are placed in the same CheckboxGroup, making them into Radio buttons. Their text fields are also programmed to select the corresponding checkbox when changed (using method setState).

The code executed when Restart is clicked has to remove the ReaderWriter buttons from the display and kill their threads. It must sleep for a time (we use a second) to allow the threads to actually terminate. Then it can reset the system to start a new simulation. When new buttons have been created and added to the display panel, the panel's validate method must be called to lay it out properly again.

Killing all the ReaderWriter threads is easy if they are in a ThreadGroup. Unfortunately, one browser's Java implementation seems to consider the attempt to use a ThreadGroup to be a security violation, so for portability I had to keep a Vector of threads and run through it killing them.

Red	writing
Blue	reading
Magenta	waiting to write
Cyan	waiting to read
White	resting between reads and/or writes
Gray	has finished its iterations