The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+17 votes
1.7k 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?

asked in Operating System by Veteran (59.6k points)
edited by | 1.7k views
+2
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
0
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.

4 Answers

+18 votes
Best answer

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.
answered by Loyal (6.1k points)
edited by
0

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

0
goto label are starting of box naa??
0
ohk . thanks :)
0
 if (▭) { _____R>=1 or W==1____ (3)
        signal (mutex);
        goto L2;
    }

@Mithilesh

Please explain this part in words

0
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
+1

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

+10 votes
1. signal mutex
2. signal mutex
3. R ¦¦ W (binary OR operator)
answered by Veteran (55.6k points)
+5 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 semaphore variable which 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
 signal(mutex);   mutex and loop back to L2.
 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 processes is not ensured.

 

 

 

 

answered by Boss (15.7k points)
0
Great Explaination ..+10 likes from me!
0
Best Answer for this Question. Don't know how to request admin to make this as the best answer?
+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 

answered by Active (2.3k points)
0
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.

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

42,416 questions
48,474 answers
154,483 comments
62,892 users