The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+23 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.

  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 (59.9k points)
edited by | 1.5k 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?

3 Answers

+21 votes
Best answer
  1. 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 $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.
answered by Loyal (8.1k points)
edited 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..
+1 vote
a. M.E is not satisfied
b. Deadlock is not Possible.
c. ME is satisfied and Deadlock is possible.
answered by Boss (42.4k points)
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:


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.
+1 vote
General Statement- "If there is no mutual exclusion, then Deadlock not possible and if there is Deadlock then there must be mutual exclusion.."
answered by Active (1.5k points)

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

47,261 questions
51,485 answers
66,770 users