edited by
10,296 views
36 votes
36 votes

Synchronization in the classical readers and writers problem can be achieved through use of semaphores. In the following incomplete code for readers-writers problem, two binary semaphores mutex and wrt are used to obtain synchronization

wait (wrt)
writing is performed
signal (wrt)
wait (mutex)  
readcount = readcount + 1
if readcount = 1 then S1
S2
reading is performed
S3
readcount = readcount - 1
if readcount = 0 then S4 
signal (mutex)

The values of $S1, S2, S3, S4,$ (in that order) are

  1. signal (mutex), wait (wrt), signal (wrt), wait (mutex)
  2. signal (wrt), signal (mutex), wait (mutex), wait (wrt)
  3. wait (wrt), signal (mutex), wait (mutex), signal (wrt)
  4. signal (mutex), wait (mutex), signal (mutex), wait (mutex)
edited by

5 Answers

Best answer
34 votes
34 votes

Answer is (C)

$S1$: if readcount is $1$ i.e., some reader is reading, DOWN on wrt so that no writer can write.

$S2$: After readcount has been updated, UP on mutex.

$S3$: DOWN on mutex to update readcount

$S4$: If readcount is zero i.e., no reader is reading, UP on wrt to allow some writer to write

edited by
28 votes
28 votes

Answer is C :

The reason for it since they said classical Reader Writer problem it mean First Reader Writer problem . 

The first Reader Writer problem says that : At any time, on a shared resources multiple reader can read it. In between if any writer comes then it wont be allowed unless last reader complete its reading. (so writer starves here )

So following the above thing :

S1= Wait(wrt) implies that as soon as the first reader come, it should lock resources so that no writer can access it.

S2 = signal (mutex ) implies that mutex is made to 1, so other reader can entry into entry section. Multiple reading are allowed. (only 1 at a time can be in entry section )

S3 = wait (mutex) implies that at a time only one process can be in Exit section and semaphore mutex is used to implement it (only 1 at a time can be in exit section)

S4 = signal (wrt ) implies that when last reader has completed reading, it should unlock resources so that any writer waiting for it can use it .

The above values of S1, S2, S3, and S4 are all nothing but implementing first reader writer problem :)

10 votes
10 votes

The question has mixed up code for writers and readers. The first three lines should be seperate from the rest of the code or else option c doesn't make sense. Because according to option C if we executed wait on wrt at s1 we do not release it until readcount is zero i.e. all the reader processes have moved out. 

If those first three lines are not seperate and exclusively for writers then option c is not going to allow multiple readers to read database or file at the same time. Here is how: Suppose a reader process R1 came in and executed wait on wrt at S1. Now another reader say R2 comes in and in line 1, tries to acquire wrt. R1 is yet to release wrt and hence R2 goes into a spinlock. A reader has prevented another reader from entering so this is a clear violation of required solution of reader writer problem which says any number of readers can read db at a time if only readers are accessing db and there is no writer. 

If the first three lines are taken away from this code and give only to writer processes and rest of code is kept only for reader processes then option c works. Something as follows...

void writer {

wait (wrt)
writing is performed
signal (wrt)

}

void reader {

wait (mutex)  
readcount = readcount + 1
if readcount = 1 then S1
S2
reading is performed
S3
readcount = readcount - 1
if readcount = 0 then S4 
signal (mutex)

}

I guess a simple printing mistake or copy paste mistake on part of the poster but still...

6 votes
6 votes

Actually the first three lines of code is for writers and remaining code is for readers.

writers(){

          wait (wrt);
          writing is performed;
          signal (wrt);

}

readers(){

        wait (mutex)                        line 1
        readcount = readcount + 1           line 2
        if readcount = 1 then S1            line 3
        S2                                  line 4
        reading is performed                line 5
        S3                                  line 6
        readcount = readcount - 1           line 7
        if readcount = 0 then S4 
        signal (mutex)

}

A) signal (mutex), wait (wrt), signal (wrt), wait (mutex)

writers:-

wait (wrt)
writing is performed
signal (wrt)

readers:-
wait (mutex)  
readcount = readcount + 1
if readcount = 1 then  signal (mutex)
wait (wrt)
reading is performed
signal (wrt)
readcount = readcount - 1
if readcount = 0 then wait (mutex) 
signal (mutex)

In readers sections, at line 7 readcount is shared variable between readers but its not getting protected by any lock, so lets consdier a case where there are n readers wants to read

then

  1. n readers executes wait(mutex) only one of them we will enter all other n-1 processes will get blocked/waiting state.
  2. now the process which has entered updates read count to 1 then satifies then IF condition so executes signal so it gonna wakeup a process from waiting list [ lets say its P2]
  3. now for P2 it updates read count to 2 and as of now value of mutex=0
  4. till signal(wrt) both P1 and P2 executes succesfully, here comes twist , lets take sequential case first P1 then P2 so now P1 changes readcount to 1 then preempts here then P2 changes read count to 0 and satifies IF condition so it calls wait(Mutex) as mutex value= 0 it gets blocked
  5. P1 resumes its execution as read count is 0, p1 also calls wait(mutex) so P1 also gets blocked

So n readers got blocked its deadlock and this code allows atmost one reader to read, this code wont allow more than one readers to read at same time which is not desirable so this option is incorrect

so its not gonna work.

option B)  signal (wrt), signal (mutex), wait (mutex), wait (wrt)

writers:-

wait (wrt)
writing is performed
signal (wrt)

readers:-
wait (mutex)  
readcount = readcount + 1
if readcount = 1 then  signal (wrt)
signal (mutex),
reading is performed
wait (mutex)
readcount = readcount - 1
if readcount = 0 then wait (wrt)  
signal (mutex)

 

consider case where a writer and reader wants to access critical section,

now

1)Writer calls wait(wrt) now value of wrt=0, and writer perfoms its respective operations

  1. reader calls wait(mutex) so its get insider and updates readcount to 1 and calls signal(wrt) then calls signal(mutex), it going to perform read operation now which is not a desirable result

so option B is also incorrect.

 

option D) signal (mutex), wait (mutex), signal (mutex), wait (mutex)

writers:-

wait (wrt)
writing is performed
signal (wrt)

readers:-
wait (mutex)  
readcount = readcount + 1
if readcount = 1 then  signal (mutex)
wait (mutex),
reading is performed
signal (mutex)
readcount = readcount - 1
if readcount = 0 then wait (mutex)  
signal (mutex)

Here also same issue both reader and writer perform there operations at same time which is not desirable

 

so Option C is correct one.

 

Answer:

Related questions