The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+17 votes
916 views

Two concurrent processes P1 and P2 want to use resources R1 and R2 in a mutually exclusive manner. Initially, R1 and R2 are free. The programs executed by the two processes are given below.

  Program for P1:   Program for P2:
S1: While (R1 is busy) do no-op; Q1: While (R1 is busy) do no-op;
S2: Set R1 $\leftarrow$ busy; Q2: Set R1 $\leftarrow$ busy;
S3: While (R2 is busy) do no-op; Q3: While (R2 is busy) do no-op;
S4: Set R2 $\leftarrow$ busy; Q4: Set R2 $\leftarrow$ busy;
S5: Use R1 and R2; Q5: Use R1 and R2;
S6: Set R1 $\leftarrow$ free; Q6: Set R2 $\leftarrow$ free;
S7: Set R2 $\leftarrow$ free; Q7: Set R1 $\leftarrow$ free;

 


 

  1. Is mutual exclusion guaranteed for R1 and R2? If not show a possible interleaving of the statements of P1 and P2 such mutual exclusion is violated (i.e., both P1 and P2 use R1 and R2 at the same time).
  2. Can deadlock occur in the above program? If yes, show a possible interleaving of the statements of P1 and P2 leading to deadlock.
  3. Exchange the statements Q1 and Q3 and statements Q2 and Q4. Is mutual exclusion guaranteed now? Can deadlock occur?
asked in Operating System by Veteran (68.8k points)
edited by | 916 views
Please solve this

I think que should be like this 

plz explain this......

I didn't understand the last question.

Exchange the statements Q1 and Q3 and statements Q2 and Q4. Is mutual exclusion guaranteed now? Can deadlock occur?

what is the difference between these two?

While R1 is busy do no-op

While (R1 is busy) do no-op

Please explain. 

There is some mistake in the question for the second part.

line q3 should be: while(r2 is busy) do no-op;
@Arjun sir,

Suppose both processes P1 and P2 reach S4 and Q4 respectively. Now in (b) part deadlock is not possible because whichever process executes its next line will use both of the resources first. Am I correct sir?

2 Answers

+17 votes
Best answer
a) Mutual exclusion is not guaranteed;

initially both R1=free and R2=free

now consider the scenario,

P1 will start and check the condition (R1==busy) it will be evaluated as false and P1 will be preempted

then P2 will start and check the condition (R1==busy) it will be evaluated as false and P2 will be preempted

now again P1 will start execution and set R1=busy then preempted again

then P2 will start execution and set R1=busy which was already updated by P1 and now p2 will be preempted

after that P1 will start execution and same scenario happen again with both P1 and P2

both set R2=busy and enter into critical section together.

hence Mutual exclusion is not guaranteed.

b)

here deadlock is not possible, because at least one process is able to proceed and enter into critical section.

c)

if Q1 and Q3 ; Q2 and Q4 will be interchanged then Mutual exclusion is guaranteed but deadlock is possible.

here, both process will not be able to enter critical section together.

for deadlock:

if P1 sets R1=busy and then preempted, and P2 sets R2=busy then preempted...

in this scenario no process can proceed further, as both holding the resource that is required by other to enter into CS.

hence deadlock will be there.
answered by Boss (8.4k points)
selected by

But their could be some miscommunication if the processes executes as

             P1                                                                        P2

S1 :while (R1 is busy) do nop;

                                                                            Q1 :while (R1 is busy) do nop;

S2: set R1 <- busy

                                                                            Q2: set R1 <- busy

Here both the process observe that R1 is free and tries to put R1 as busy 

b)  deadlock is possible

if Process p2 runs first then it will make R1 and R2 both busy and enter into critical section and after that it will free the R2 but not R1

Now both P1 and P2 will get stuck in while loop because R1 is busy

So it is deadlock

Am I correct???
@Arjun question and solution are not matching, seems someone updated the question after the soution was posted.

In this question, ME is satisfied as per the current question.
Fine now?
@Arjun I think there is a printing mistake in the question. please find some reliable source and match the question.
What is the mistake? I don't think there are any reliable sources for GATE questions before 2006.
@Arjun now given the above solution is correct, please select it as best!
+1 vote
a. M.E is not satisfied
b. Deadlock is not Possible.
c. ME is satisfied and Deadlock is possible.
answered by Veteran (38k points)
edited
in second part after exchanging, I think that mutual exclusion can still be violated. Please check.

Say if P1 executed S1 and then context switch happens now P2 executes its first 4 statements So P2 has got control over R1 and R2 but now again context switch happens and P1 resumes, it will hold R1. Won't it? please confirm.

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

32,443 questions
39,188 answers
108,802 comments
36,561 users