The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+16 votes
1.5k 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.5k points)
edited by | 1.5k 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

4 Answers

+17 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 (6k 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.4k points)
+1 vote

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 (1.9k 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.
0 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 ago by Boss (12.6k points)

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

39,828 questions
46,802 answers
140,987 comments
58,944 users