Readers/Writers Problem

Page last updated 08/23/99

 

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

 

 


Semaphore Solution: Readers have Priority

 

int readcount = 0;
semaphore wsem = 1; //
semaphore x = 1; //
void main(){
   int p = fork();
   if(p) reader; // assume multiple instances
   else  writer; // assume multiple instances
}
void reader(){
   while(1){
      wait(x);
        readcount++;
        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)
   }
}

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);
   }
}
Only Readers Only Writers Both w/ Reader First Both w/ Writer First
  • wsem set
  • no queues
  • wsem and rsem set
  • writers Q on wsem
  • wsem set by reader
  • rsem set by writer
  • writers Q on wsem
  • 2nd reader Q on rsem
  • other readers on z
  • wsem set by writer
  • rsem set by writer
  • writers Q on wsem
  • 1st reader Q on rsem
  • other readers on z

 

 


Message Passing Solution

Mailboxes are set up for Read requests, Write requests and each process a mailbox for permission to proceed.  The Controller() process performs the necessary coordination among the reader and writers giving writers priority.

void reader(int id){
   message rmsg;
   while(1){
     rmsg = id;
     send("ReadReq",rmsg);
     receive("Reader"+id,rmsg);
     DoReading();
     rmsg = id;
     send("Fini",rmsg);
   }
}
void writer(int id){
   message rmsg;
   while(1){
      rmsg = id;
      send("WriteReq",rmsg);
      receive("Writer"+id,rmsg);
      DoWriting();
      rmsg = id;
      send("Fini",rmsg);
   }
}
void controller(){
  while(1){
    if(count>0){  //no writer
      if (!empty("Fini")){
         receive("Fini",msg);
         count++;
      } else if(!empty("WriteReq")){
         receive("WriteReq",msg);
         id = msg.id; 
         count -= MAXREADERS;
      } else if(!empty("ReadReq")){
         receive("ReadReq",msg)
         count--;
         send("Reader"+msg.id, "OK");
      }
    }
    if(count==0){//only a writer
       send("Writer"+id, "OK");
       receive("Fini",msg);
       count = MAXREADERS;
    }
    while(count<0){ // 1 wrtr;n rdrs
       receive("Fini",msg);
       count++;
    }
  }
}