#OS Reader Writer User Gate 2000 Doubt

Question

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?

Comments

@Shaik Sorry to bother ou again! :(

---

it's my pleasure BRO

Answer 1

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 R₁,R₂,R₃ and one Writer W₁

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.

Comments

@Shaik Masthan Brother, is in this reader writer problem, Mutual Exclusion is Guranteed?

My Take - I think yes, but how about when more than one readers are present in CS, but (R-R) is not a conflict.So, can we ignore that and call it as ME?

Also, how about bounded waiting and progress?

---

can we ignore that and call it as ME

Generally we don't ignore it, But in the question He says, R-R is not a conflict, then We say it is ME

 

how about bounded waiting ?

If starvation is there, it's doesn't satisfy Bounded Waiting.... Read my solution for Starvation

 

how about progress? 

If a process either reader or writer, doesn't want to enter into CS.... Then also Some interested reader can enter into CS, entering into CS of those interested Processes can not stop by Un-interested processes.

therefore Progress is guarenteed 

---

@Shaik Masthan Awesome brother, makes perfect sense. Thank you! :)