The R-W problem

The R-W problem: is another classic problem for which design of synchronization and concurrency mechanisms can be tested. The producer/consumer is another such problem; the dining philosophers is another.

Definition

* There is a data area that is shared among a number of processes.

* Any number of readers may simultaneously write to the data area.

* Only one writer at a time may write to the data area.

* If a writer is writing to the data area, no reader may read it.

* If there is at least one reader reading the data area, no writer may write to it.

* Readers only read and writers only write

* A process that reads and writes to a data area must be considered a writer (consider producer or consumer)





Semaphore Solution: Readers have Priority


int readcount = 0;

semaphore wsem = 1; //

semaphore x = 1; //

void main(){

int p = fork();

if (readcount==1)

wait(wsem);

signal(x);

doReading();

wait(x);

readcount--;

if (readcount==0)

signal(wsem);

signal(x);

}

}


void writer(){

while(1){

wait(wsem)

doWriting();

signal(wsem)

}

}

if(p) reader; // assume multiple instances

else writer; // assume multiple instances

}

void reader(){

while(1){

wait(x);

readcount++;


Once readers have gained control, a flow of reader processes could starve the writer processes.
Rather have the case that when a write needs access, then hold up subsequent reading requests until after the writing is done.





Semaphore Solution: Writers have Priority


int readcount, writecount = 0;

semaphore rsem, wsem = 1; //

semaphore x,y,z = 1; //

void main(){

int p = fork();

if(p) reader; // assume multiple instances

else writer; // assume multiple instances

}

void reader(){

while(1){

wait(z);

wait(rsem);

wait(x);

readcount++;

if (readcount==1)

wait(wsem);

signal(x);

signal(rsem);

signal(z);

doReading();

wait(x);

readcount--;

if (readcount==0)

signal(wsem);

signal(x);

}

}


void writer(){

while(1){

wait(y);

writecount++;

if (writecount==1)

wait(rsem);

signal(y);

wait(wsem);

doWriting();

signal(wsem);

wait(y);

writecount--;

if (writecount==0)

signal(rsem);

signal(y);

}

}