1,060 views
0 votes
0 votes

Original Question - https://gateoverflow.in/691/gate2000-20

 

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

 

===============xxxxxx=========================================================

 

How, two or more readers can be present in Critical Section?

 

wait (mutex);
    R = R - 1; ///// This is Critical Section, right////
    signal (mutex);
}

Also, how starvation is happening?

1 Answer

2 votes
2 votes
Reader () {
1.    wait (mutex); 
2.    if (W == 0) {
3.        R = R + 1;
4.       signal(mutex); (1)
5.    else {
6.     signal(mutex); (2)
7.        goto L1;
    }
8.    ..../* do the read*/
    wait (mutex);
    R = R - 1;
    signal (mutex);
}

How, two or more readers can be present in Critical Section?

 

 Every Reader has same code of copy. let there are three readers R1,R2,R3 and one Writer W1

wait(mutex) performed by R1, then no reader or no writer enter into it, then Global value is R=1, W=0

By line 4, signal(mutex), either reader or writer can access Mutex now, R1 enters into CS

If R2 comes, line 1 executes, successful and make mutex=0, line2 executes and get in to if block, increase R from 1 to 2, therefore R=2,W=0, line 4 executes and entered into CS

 

Why Morethan one Reader can enter into CS

Due to we are checking the condition W=0 or not only ( i.e., Writer is present or not in the critical section  only, need not worry about Reader present in the CS or not.

 

How to stop more than one reader enter into CS?

replace line2 by    if (W == 0 && R==0) {


 Can the above solution lead to starvation of writers?

 

Should be the solution leads to starvation of writers.

 

WHY?

assume there are 1 lack Readers, initially a Reader (R1) comes and enter into CS, now writer Comes

After that remaining all readers come and left one by one ( i.e., R2 comes and enter into CS, R1 leaves the CS, R3 Comes and enter into CS and R2 leaves.......

If atleast one reader present in the CS, Writer can't enter into CS..


R = R - 1; ///// This is Critical Section, right////

Do you Strict Alternation Method or any other method?

In Strict Alternation method, TURN variable equivalent to R in this question

In Bakery Algorithm,  CHOOSING, NUM arrays are equivalent to R in this question


starvation is happening for readers?

Starvation can happens for readers also, due to we are not maintaining queue for which writer or reader comes first...

i mean, let there are 1 lack writers and  1 lack readers and first writer (W1) come and enter into cs,

next reader or writer trying to enter into CS, those are going to busy waiting... but W1 exit from CS.....

if Writer2 or Reader1 can enter... We are not maintaing queue therefore Writer 2 can enter... next Writer 3 can enter......

Therefore Starvation possible for Readers also.

Related questions