CMSC 412

NOTE 13

March 17, 1999

Readers-Writers Problem

1. Problem statement

A variable X is shared between several processes that do read and write operations on X. We want to ensure the following:
  1. Single write: If a write is ongoing, then no other operation should be ongoing.

  2. Multiple reads: If a read is ongoing, then other reads should be allowed to be ongoing.

  3. No starvation for reads: If a process wants to read then it eventually reads provided no read or write lasts forever.

  4. No starvation for writes: If a process wants to write then it eventually writes provided no read or write lasts forever.

  5. No busy waiting.

2. Attempted solution 1 using Semaphores

Clearly we cannot solve this by making X into a critical section, because that would violate the Multiple Reads requirement. So we come up with functions that users call before and after each access, namely, StartRead(), EndRead(), StartWrite(), EndWrite(). 
Semaphore xLock initially 1;  // controls access to X
integer rc initially 0;   // number of processes reading or waiting to read
Semaphore rcMutex initially 1;  // protects rc

StartRead( ) {
  P( rcMutex );
  rc := rc + 1;
  if rc = 1 then { P( xLock ) };
  V( rcmutex );
}

EndRead( ) {
  P( rcMutex );
  rc := rc - 1;
  if rc = 0 then { V( xLock ) };
  V( rcmutex );
}

StartWrite( ) {
  P( xLock );
}

EndWrite( ) {
  V( xLock );
}
}
NOTE: