Thomas W. Christopher
Training in Concurrency, Networking, and Parallelism, especially in Python and Java.
| Thomas W. Christopher
|
Consulting in High Performance Computing. Training in Concurrency, Networking, and Parallelism, especially in Python and Java. |
Abstract
This page animates the Alternating-Readers/Writers policy for coordinating multiple readers and writers of a shared resource.
Author
Thomas W. Christopher
Tools of Computing
tc AT tools HYPHEN of HYPHEN computing DOT comRequirements
This requires Java JDK1.1 or greater. It uses the 1.1 event model that is not implemented in earlier versions of Java.
The idea of the Alternating-Readers/Writers Monitor is that readers and writers should take turns. Trying to specify this a bit more carefully, we come up with elements like this:
General Alternation. A batch of readers run, followed by a single writer, followed by another batch of readers, etc.
Immediate access. If a reader arrives and there are no writers present, it is given access to the resource immediately. If a writer arrives and neither readers nor writers have the resource, it is allocated the resource immediately.
The state of this Alternating-Readers/Writers Monitor is contained in four variables:
| nr[2]: | the number of threads currently reading, >=0 |
| thisBatch: | index in nr of batch of number of readers currently reading, 0 or 1. |
| nextBatch: | index in nr of batch of number of readers waiting to read, always 1-thisBatch. |
| nw: | the number of threads currently writing, 0 or 1 |
| nwtotal: | the number of threads either writing or waiting to write. |
When a thread tries to start reading, it checks first to see if there are any writers present. If there are none, it starts reading immediately, recording its presence in nr[thisBatch].
If there are writers present, it must wait until one writer has run, so it adds itself to the number of readers in the next batch by incrementing nr[nextBatch]. It saves the value of nextBatch in variable myBatch and waits until variable thisBatch equals myBatch, which will indicate that a writer has finished running.
public synchronized void startReading()
throws InterruptedException{
if (nwtotal==0) nr[thisBatch]++;
else {
nr[nextBatch]++;
int myBatch=nextBatch;
while (thisBatch!=myBatch) wait();
}
}
When a thread stops reading, it subtracts itself from nr[thisBatch]. It then notifies all waiting threads to try again. Readers will wait again, since thisBatch has not been set to the value they are waiting for, but one of the writers will be able to start writing.
public synchronized void stopReading(){
nr[thisBatch]--;
if (nr[thisBatch]==0) {
notifyAll();
}
}
When a writer attempts to start writing, it adds itself to the total number of writers present. Then it must wait until no threads are reading and no other thread is writing. Once that condition is true, it sets nw to 1 to indicate it is writing and proceeds.
public synchronized void startWriting()
throws InterruptedException{
nwtotal++;
while (nr[thisBatch]+nw != 0) wait();
nw=1;
}
When a thread stops writing, it sets nw back to zero to indicate no one is writing, and it subtracts itself from the total number of writers present. It then swaps the values of thisBatch and nextBatch to release the next batch of readers, and it notifies all waiting threads which will wake up the readers.
public synchronized void stopWriting(){
nw=0; nwtotal--;
int tmp=thisBatch; thisBatch=nextBatch; nextBatch=tmp;
notifyAll();
}