MadeEasy Subject Test: Operating System - Process Synchronization

Question

Reader Writer's problem

How is deadlock possible in this?

Comments

In this mutual exclusion is not satisfied as it is given that increament/decreament is performed in three phase . Suppose their is 2 reader R1 and R2, Now r1 enter into DB and increament rc by 1 so RC=1 and perform the rest of statement now R1 perform down(mutex) and load decreament rc by 1 now before R1 reader store the rc vvariable back into the memory it is preempted, At tghe same time reader R2 came and load the RC variable which is still RC=1 (bcoz yet R1 didnt store the updated value back into the memory) and R@ increament the RC variable by 1 and store it in the memory AT this moment R1 is made alive and R1 store RC variable back into the memory which RC=0 and the IF condition will also get satisfied and UP operation is done on "DB" variable but reader R2 is still in DB and At this time a writer can also enter into the DB because for R2 condition IF(RC==1) will be false so it will not perform DOWN operation "DB" variable .....so mutual exclusion is not satisfied as both reader and writer are in data base at same time.

plz make me correct if i did any wrong assumption

---

Plz check my answer too, its bit lengthy But you can read it once in case of doubt.

Answer 1

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.

Answer 2

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!!!