edited by
821 views
1 votes
1 votes

Reader Writer's problem

How is deadlock possible in this?

edited by

2 Answers

Best answer
7 votes
7 votes
Normally, in correct implementation first reader performs down(db) (bcoz for this only rc is 1)
and last reader performs up(db)(bcoz for this only rc is 0)

If you see correct implementation of this problem then "rc = rc+1" is protected by semaphore.
You probably know the reason, because it is not atomic operation therefore leaving it without protection may give u wrong count of variable rc (this situation is race condition)

for eg:- If there are 10 readers execute rc = rc+1, then final value of rc can be anywhere between [1,10].

this is wrong implementation, as u will see that it may lead to deadlock.

Idea to check deadlock- Can i somehow SKIP performing up(db) ?

Now I am showing possible sequence for which deadlock arises-

1. reader1 came, performs down(db)and then CS then 'rc = rc-1' (makes rc =0), but it preempts just before executing 'if(rc == 0)'

2. all other readers come and make final value of rc as 1 by executing 'rc = rc +1' in some order. (this is NEVER possible in correct implementation bcoz 'rc = rc +1' is protected by sophomore there )

NOW rc is ONE. (rc = 1)

3. reader1 schedules again, it finds rc is one so 'if' condition is false. it exits WITHOUT performing up(db).

4. Now one of the reader (say reader_i) will go and stuck (blocked) in down(db) bcoz rc is 1.
all other readers will stuck in down(mutex) bcoz above reader (reader_i) just made down on mutex.

5. Now writer comes, it can not also proceed because down(db) is already down.

6. reader1 comes again it will stuck in down(mutex), bcoz reader_i made the 'mutex' down. (at this point it makes rc = 2, but it doesnt matter now)

All readers are blocked, writer is blocked, This is deadlock for system.
selected by
4 votes
4 votes
1. Two readers arrive.
2. Both read rc=0
3. Both increment rc to 1 in their registers. 1 of them writes rc into memory. Then it makes db=0 and enters critical section.
3. Second reader overwrites rc=1 into memory, executes wait(mutex) and then waits at db.
4. Reader currently inside CS tries to execute down(mutex). Hence, waits on it.
Both readers waiting, writer cannot enter CS.
DEADLOCK!!!

Related questions

0 votes
0 votes
0 answers
1
Hopealways asked Dec 1, 2018
418 views
In these type of questions “Will we NOT consider CONTEXT SWITCHING unless mentioned???”If context switching is ALLOWED, minimum value will be 8...Correct me if I’m ...