6,712 views

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.

 L1: int R = 0, W = 0; Reader () { wait (mutex); if (W == 0) { R = R + 1; ▭ ______________(1) } else { ▭ ______________(2) goto L1; } ..../* do the read*/ wait (mutex); R = R - 1; signal (mutex); }  L2: Writer () { 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?

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.

### Subscribe to GO Classes for GATE CSE 2022

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

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.

//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

signal(mutex);
goto L1;
}
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
//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

/*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.

Great Explaination ..+10 likes from me!
Best Answer for this Question. Don't know how to request admin to make this as the best answer?

@Gurdeep Saini-Ask @Arjun sir and I'll do it.

i think it should be best answer.
In Writer(), L2: if statement, it should be

if(R>1 || W == 1), in case of one process writing as W!=0 considers more than one processes also. Right? Please correct me if wrong.
From my side also some of likes if remaining. As u have already used 10 likes.... Lol
How reader starvation is not possibe ? Could somebody explain plzz

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.

@mithlesh , pls explain more in detail specially line 3 ...

goto label are starting of box naa??
ohk . thanks :)
 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).

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

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.
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
}
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);
}

### 1 comment

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.