edited by
9,636 views
31 votes
31 votes

a. Fill in the boxes below to get a solution for the reader-writer problem, using a single binary semaphore, mutex (initialized to $1$) and busy waiting. Write the box numbers ($1$, $2$ and $3$), and their contents in your answer book.

 
int R = 0, W = 0;

Reader () {
 L1:   wait (mutex); 
    if (W == 0) {
        R = R + 1;
        ▭ ______________(1)
    }
    else {
      ▭ ______________(2)
        goto L1;
    }
    ..../* do the read*/
    wait (mutex);
    R = R - 1;
    signal (mutex);
}
 
Writer () {
 L2:    wait (mutex);
    if (▭) { _________ (3)
        signal (mutex);
        goto L2;
    }
    W=1;
    signal (mutex);
    ...../*do the write*/
    wait( mutex);
    W=0;
    signal (mutex);
}

b. Can the above solution lead to starvation of writers?

edited by

4 Answers

Best answer
101 votes
101 votes

There are four conditions that must be satisfied by any reader-writer problem solution

  1. When a reader is reading, no writer must be allowed.
  2. Multiple readers should be allowed.
  3. When a writer is writing, no reader must be allowed.
  4. Multiple writers$($more than $1)$ should not be allowed.

Now, here mutex is a semaphore variable that will be used to modify the variables $R$ and $W$ in a mutually exclusive way.

The reader code should be like below

Reader()
L1: wait(mutex);
if(w==0){ //no Writer present, so allow Readers to come.

R=R+1; //increment the number of readers presently reading by 1.

signal(mutex);//Reader is allowed to enter, 
            //number of readers present "R"
            //is incremented and now make mutex available so that other readers
            //can come.
}
else{  //means some writer is writing,so release mutex, and try to
      //gain access to mutex again by looping back to L1.

signal(mutex);
goto L1;
}
/*reading performed*/
wait(mutex);
R=R-1;
signal(mutex);

Value of variable $R$ indicates the number of readers presently reading and the value of $W$ indicates if $1,$ that some writer is present.

Writer code should be like below

Writer()
L2: wait(mutex);
if(R>0 || W!=0) //means if even one reader is present or one writer is writing
                //deny access to this writer process and ask this to release
                //mutex and loop back to L2.
{                
 signal(mutex);   
 goto L2;
}
//code will come here only if no writer or no reader was present.

W=1; //indicate that a writer has come.

signal(mutex); //now after updating W safely, release mutex, for other writers and
              //readers to place their request.

/*Write performed*/
//writer will leave so change Value of W in a mutual exclusive manner.
wait(mutex);
W=0;
signal(mutex);

This will satisfy all requirements of the solution to the reader-writer problem.

(B) Yes, writers can starve. There can be the scenario that whenever a writer tries to enter, it finds some reader $(R!=0),$ or another writer process $(W!=0)$ and it can keep waiting forever. Bounded Waiting for the writer's processes is not ensured.

edited by
18 votes
18 votes

My attempt :

  1.  
    1. Give the opportunity for other Readers , so that they can read the C.S. ; Release the mutex ,i.e., Signal(mutex).
     2. Similarly to case (1),i.e., Signal(mutex).
     3. Check if any Reader(s) or Writer in C.S.( Critical Section) , if there any ; i.e. , $R=>1$ or $W==1$.
     
  2. If at least one Reader is always present in critical section , then Writer can not be enter in critical section . Hence  readers-writers problem may starve writers in the queue.
edited by
2 votes
2 votes

when this code starts executing it initialize R=0 and W=0 , please note 'mutex' is binary semaphore & initialized to 1(given in question) 

L1:int R = 0, W = 0; //when this parts starts executing it initialize both R and W to zero.
 //Between execution of these two lines either another reader or writer can change value of R or W.
Reader () {
    wait (mutex); 
    if (W == 0) { //if W=0 means no writer in room.
        R = R + 1;//If existing value of R is 0, I am first reader,else there is already reader present
         signal(mutex)(1)//Irresptive of whether I am first reader or not I must make mutex=1, 
    }                     //because I made it 0
    else {                //means writer already present
         signal(mutex)(2)//I must make mutex = 1 , else writer can never execute 
        goto L1;         // wait(mutex);W=0; signal(mutex); and there will be deadlock
    }
    ..../* do the read*/
    wait (mutex);
    R = R - 1;
    signal (mutex);
}

for writer condition is simple just check if R=1 or W=1 

L2: Writer () {
    wait (mutex);           
    if (▭) { _________ (3)
        signal (mutex);
        goto L2;
    }
    W=1;
    signal (mutex);
    ...../*do the write*/
    wait( mutex);
    W=0;
    signal (mutex);
}

This offcourse leads to starvation of writer if already one reader entered room and reader processes keeps on coming 

Related questions

41 votes
41 votes
6 answers
2
Kathleen asked Sep 14, 2014
11,865 views
Which of the following need not necessarily be saved on a context switch between processes?General purpose registersTranslation look-aside bufferProgram counterAll of the...