GATE CSE 2000 | Question: 20

Question

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?

Comments

for L1 if writer is 0, then more than one reader can enter into critical section

so (1) ........signal(mutex);

for unsuccessful operation it directly gives signals in else part

(2)............signal(mutex)

and it goes into loop

but I am not getting writer part. plz help

---

Better go with examples. Try all possible combinations.

for 3rd blank go with order of process like P1(reader), p2(writer), p3(writer)

when p3 enters there are two cases either we have many reader processes already inside CS or one writer process before this writer process. We have to allow writing in CS only when there is no process in CS this can be ensured by if(reader processes are !=0 OR writer processes !=0) keep looping and don't let any writer process to write.

Difficult to understand during exam but taking few sequence of processes and ensuring criteria of the problem we can deal with it.

---

question should be posted perfectly...positions of L1 and L2 are creating unnecessary confusion.Please update the question.

Answer 1

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.

Comments

How reader starvation is not possibe ? Could somebody explain plzz

---

@Ajit_Singh , One reader does not block other Reader from accessing the data so they can access data at the same time!

---

@jiminpark a writer can also execute any number of times there is no bound.

so, readers can also starve i think

Answer 2

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.

Comments

 if (▭) { _____R>=1 or W==1____ (3)
        signal (mutex);
        goto L2;
    }

@Mithilesh

Please explain this part in words

---

I can understand this.but plz xplain in terms of the code snippet,wats happening?

:'(

when multiple reader or one writer is present,then why goto L2 and and up on mutex which was previously made 0 by wait

---

For (3). If Many reader or Single writer is already doing some work with the file. Then no other  Writer is allowed to do write operation.

(3) is ( R || W). 

Answer 3

1. signal mutex
2. signal mutex
3. R ¦¦ W (binary OR operator)

Answer 4

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 

Comments

Shouldn't L1 start from Reader( ) since reader was blocked because a writer was already writing as W==0 failed? Why is the assignment of W=0 taking place again? What if some writer was preempted while it was doing the writing to execute the Reader code that made R = 0 and W = 0 since the goto statement in Reader is only executed if W=1. And after assignment of W=0, a new writer can also start writing or the same reader can start reading if it continues even when the first writer is already doing the writing.