edited by
5,447 views
35 votes
35 votes

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?
edited by

3 Answers

Best answer
38 votes
38 votes
  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.
    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.
selected by
4 votes
4 votes
General Statement- "If there is no mutual exclusion, then Deadlock not possible and if there is Deadlock then there must be mutual exclusion.."
2 votes
2 votes
a. M.E is not satisfied
b. Deadlock is not Possible.
c. ME is satisfied and Deadlock is possible.
edited

Related questions

21 votes
21 votes
6 answers
3