GATE CSE 2001 | Question: 19

Question

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}$$

• A. 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).
• B. Can deadlock occur in the above program? If yes, show a possible interleaving of the statements of $P1$ and $P2$ leading to deadlock.
• C. Exchange the statements $Q1$ and $Q3$ and statements $Q2$ and $Q4$. Is mutual exclusion guaranteed now? Can deadlock occur?

Comments

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.

Answer 1

• A. 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.
   
• 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.

Comments

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

Answer 2

General Statement- "If there is no mutual exclusion, then Deadlock not possible and if there is Deadlock then there must be mutual exclusion.."

Comments

@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

---

I think it’s valid for more than two processes  because MUTUAL EXCLUSION is a necessary condition for deadlock to occur

Answer 3

a. M.E is not satisfied
b. Deadlock is not Possible.
c. ME is satisfied and Deadlock is possible.

Comments

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.

---

@Pratik Gawali 

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.