The Gateway to Computer Science Excellence
+21 votes
2.4k views

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)
in Operating System by Boss (16.3k points)
edited by | 2.4k views
+1

Similar question (on reader's writer's problem) with different implementation is there..look at it :

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

0
Since mutex is binary semaphore so can multiple readers read?? I think only one reader can read at a time.
0
This code for the reader-writer solution must be separated else it is too confusing to understand what "read_count" variable is for.

3 Answers

+19 votes
Best answer

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

by Loyal (7.8k points)
edited by
0
I understand the answer but just to know what problem may the code have if S3 was not there.
0
then may be 2 reader same time decrement the rc value so .. it will give wrong ans ... so to maintain these type of inconsistency ..s3 must
+1

@sid1221 please consider this situation and say whether my understanding was correct or not.

L1:wait (mutex)  
L2:readcount = readcount + 1
L3:if readcount = 1 then wait(wrt)
L4:signal(mutex)
L5:reading is performed
L6:wait(mutex)
L7:readcount = readcount - 1
L8:if readcount = 0 then signal(wrt)
L9:signal (mutex)

Initially, mutex=1. wrt=1. rc=0.

  • Suppose now rc=3 (3 readers R1, R2, R3 are reading).
  • Now R1 wants to exit. It directly goes to L7 (as L6 is not there hence mutex=1).
  • Before it executes L7 suppose another reader R4 wants to enter into the reading section (till now rc=3 as L7 was not executed).
  • As mutex=1 R4 can enter making mutex=0 and increase the rc to 4.
  • Before entering into the CS R4 makes mutex=1.
  • Now finally the state is mutex=1, wrt=0, rc=4.
  • But going through the situation above we can know that only R2,R3 and R4 are there in the reading section while R1 has already exited. Hence this rc=4 gives a wrong information that there are 4 readers in the CS.
0
yes this case possible but you did not executed r1 line 7 ?

what i was saying ... r1 and r2 in reading ok, then if mutex is not there , both r2 and r1 can execute same time so both will exit but decrement done only once ...so this time in reading no reader but it shows 1 ....so if i add mutex only 1 reader at a time decrement the value ...right
0
I understand that both r1 and r2 are trying to execute at the same time but my doubt is somebody must win this competition and execute first and then the other will execute after that. So L7 will get executed twice (either r1-->r2 or r2-->r1).

And to answer to your question, r1 did execute L7 but that happened later after r4 has already entered the reading section.
0
If S3 wasn't there ..there will be race conditions! and the value of the shared variable may be inconsistent means not correct it..isn't it?
+20 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 :)

by Active (1k points)
+6 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...

by (295 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
50,647 questions
56,508 answers
195,518 comments
100,939 users