1.2k 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?
edited | 1.2k views
0
+4

I think que should be like this

0
plz explain this......
0

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

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

line q3 should be: while(r2 is busy) do no-op;
0
@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?

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.

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.

edited by
0

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

+1

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

Am I correct???
0
@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.
0
Fine now?
0
@Arjun I think there is a printing mistake in the question. please find some reliable source and match the question.
0
What is the mistake? I don't think there are any reliable sources for GATE questions before 2006.
0
@Arjun now given the above solution is correct, please select it as best!
+1 vote
a. M.E is not satisfied
c. ME is satisfied and Deadlock is possible.
edited
+1
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.
0

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.