3,444 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.

$$\begin{array}{|ll|ll|}\hline & \textbf{Program for P1:} && \textbf{Program for P2:} \\\hline \text{S1:} & \text{While (R1 is busy) do no-op;} & \text{Q1:} & \text{While (R1 is busy) do no-op;} \\ \text{S2:} & \text{Set R1 \leftarrow busy;} & \text{Q2:} & \text{Set R1 \leftarrow busy;} \\ \text{S3:} & \text{While (R2 is busy) do no-op;} & \text{Q3:} & \text{While (R2 is busy) do no-op;} \\ \text{S4:} & \text{Set R2 \leftarrow busy;} & \text{Q4:} & \text{Set R2 \leftarrow busy;} \\ \text{S5:} & \text{Use R1 and R2;} & \text{Q5:} & \text{Use R1 and R2;} \\ \text{S6:} & \text{Set R1 \leftarrow free;} & \text{Q6:} & \text{Set R2 \leftarrow free;} \\ \text{S7:} & \text{Set R2 \leftarrow free;} & \text{Q7:} & \text{Set R1 \leftarrow free;} \\\hline \end{array}$$

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?

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

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?
For partA, mutual exclusion is not guaranteed

For partB, W.r.t to deadlock prevention policies, if we dissatisfy mutual exclusion, deadlock does not occur

For partC, there exists an interleaved preemption in which deadlock can occur and so mutual exclusion holds.

### Subscribe to GO Classes for GATE CSE 2022

1. Mutual exclusion is not guaranteed;

Initially both $R1$ and $R2$ are 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 $P$1 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.

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

3. 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.

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.
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!
In C) ques. Mutual exclusion can be violated..
General Statement- "If there is no mutual exclusion, then Deadlock not possible and if there is Deadlock then there must be mutual exclusion.."

### 1 comment

@Nitesh Singh..Is this statement always valid for more than 2 processes as well or just in case of 2 processes..

plz respond I am confused
a. M.E is not satisfied
b. Deadlock is not Possible.
c. ME is satisfied and Deadlock is possible.

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.

For Part C:

Mutual Exclusion is violated. Consider the following sequence of execution after exchanging and see for yourself:

S1,Q1,Q2,Q3,S2,S3,Q4,Q5,Q6,S4,Q7,Q1,Q2,Q3,Q4,Q5,S5,....

As both processes are using the resources simultaneously in Q5 and S5, Mutual exclusion is violated.

doubt..for the case (c) When P1 and P2 is updating value of R2 simultanously isnt it considered as no mutual exclusion

like if the order of execution is P1 got executed till S3 and preempted and then P2 executed Q1 and got preempted and again P1 starts and executes  S4 and prempted and P2 executes Q2 and at this time both P1 and P2 have access to R2.

S4 will set R2 to busy. So how will the sequence ..., S4, Q7, Q1, Q2, Q3, Q4, ... be possible?

Also, since Deadlock is possible for this case, Mutual Exclusion has to be guaranteed right?

S1,Q1,Q2,Q3,S2,S3,Q4,Q5,Q6,S4,Q7,Q1,Q2,Q3,Q4,Q5,S5...

again when P2 executes these statements Q1,Q2,Q3,Q4  P2 will be stuck into the while loop. Because already P1 is set as R1 and R2 is busy.