GATE CSE 2015 Set 3 | Question: 10

Question

Two processes $X$ and $Y$ need to access a critical section. Consider the following synchronization construct used by both the processes

$$\begin{array}{|l|l|}\hline \text{Process X}  &  \text{Process Y}  \\ \hline  \text{/* other code for process X*/} & \text{/* other code for process Y */} \\  \text{while (true)} & \text{while (true)} \\ 
\text{\{} & \text{\{} \\
\quad\text{varP = true;} & \quad \text{varQ = true;} \\
\quad\text{while (varQ == true)} &\quad \text{while (varP == true)}\\ 
\quad\text{\{} & \quad\text{\{}  \\ 
\quad\quad\text{/* Critical Section */} & \quad\quad\text{/* Critical Section */} \\ 
\quad\quad\text{varP = false;} &\quad\quad \text{varQ = false;} \\
\quad\text{\}} & \quad\text{\}} \\
\text{\}} & \text{\}} \\
\text{/* other code for process X */} & \text{/* other code for process Y */}\\
\\ \hline  \end{array}$$

Here varP and varQ are shared variables and both are initialized to false. Which one of the following statements is true?

• A. The proposed solution prevents deadlock but fails to guarantee mutual exclusion
• B. The proposed solution guarantees mutual exclusion but fails to prevent deadlock
• C. The proposed solution guarantees mutual exclusion and prevents deadlock
• D. The proposed solution fails to prevent deadlock and fails to guarantee mutual exclusion

Comments

Why progress is not satisfied :

Px	Py
P=1
	Q=1
	CS
	Q=0
//Px is not in its CS
	//Py is not in its CS
//Px wishes to enter its CS but cant as Q needs to be 1
	//Cannot set Q to 1, hence stalls the decision indefinitely.

 

---

@Deepak Poonia@Sachin Mittal 1 
consider the following execution process X runs and makes varP = true and preempts now process Y runs makes varQ = true as varP is already true enters the critical section and makes varQ = false. After this, process Y keeps executing the critical section as varP will always be true and it's not possible for process X to enter the critical section as varQ is false...won’t it be a deadlock?

---

@Aaru_2023

why are you assuming $varQ$ will remain $false$? It will switch between $True$ and $False$ and $X$ can execute then. 

For deadlock both processes should follow hold and wait which is clearly not the case in your example. 

morever since ME is not satisfied we can rule out deadlock instantly.

Answer 1

When both processes try to enter critical section simultaneously, both are allowed to do so since both shared variables varP and varQ are true. So, clearly there is NO mutual exclusion. Also, deadlock is prevented because mutual exclusion is one of the necessary condition for deadlock to happen. Hence, answer is (A).

Comments

@Sachin Mittal 1 sir i think bounded waiting is satisfied here bcz 

Bounded waiting: there exists a bound on the number of times that other processes are allowed to enter their critical section after a process has made a request to enter its critical section and before that request is granted.

Initially, varP and varQ are false. Let’s Process Y wants to enter the CS. So it makes varQ true. Preemption has occurred and Process X has been scheduled.  Process X wants to enter the CS and make varP true. Process Y has been scheduled. It also enter the CS. So, there exist a bound.

---

@samarpita

Initially, varP and varQ are false. Let’s Say Process Y wants to enter the CS. So it makes varQ =true and Suppose it gets preempted. X starts – goes in CS as Q = true – makes varP = false – Exits – again X tries to execute ( assume Y is  still preempted after making varQ = true) – makes varP = true – pass the while Condition – enters critical section again.

This can goes on infinite time, So No Bound on how many times X can execute after Y gets preempted at varQ = True. X can Request CPU infinite time and it will get the CPU always.

Therefore Bounded Waiting Not Satisfied.

But I’m not sure about Y getting preempted Indefinitely. @Arjun Sir, Is it possible that Y just being preempted indefinitely

---

@Harish Hatmode

yes correct unbounded waiting is there. 
My approach was if $X$ wants to enter in CS but the while condition is false and the process ends. We don't even execute $Y$ still its not letting $X$ to enter in CS.

Answer 2

the answer is A.. the main thing here to watch in question is that there is no semicolon after while loop. and so When both processes try to enter critical section simultaneously,both are allowed to do so since both shared variables varP and varQ are true. So, clearly there is NO mutual exclusion. Also,deadlock is prevented because mutual exclusion is one of the conditions for deadlock to happen. 

Comments

Nice !!!

I was considering semi-colon and got (B).I was shocked seeing A to be the correct one.

---

Select this as Best answer.

---

best answer..

Answer 3

With having context switch at every instance, we can see that at one time, both X and Y are in Critical section, and after one such iteration of the while loop either of X or Y depending on the order of context switches, one of them, will move out from The Critical section.

And only one of them will be there forever.

This clearly shows that initially, there was no mutual exclusion as we got one case where both P and Q were in the critical section.

 

There is essentially no deadlock

But there is no progress and no bounded waiting.

Answer 4

Answer=D

Can anyone please explain how two processes arrive into deadlock?

Comments

sir process x can't run unless var q is true(which will happen only if process y runs and gets prempted before it's way out.). similarly process y can't run unless var p is true.(which will happen only if process x runs and gets prempted before it's way out.)

 

so in order run one process needs the other to run and the other one needs the former one . which is a deadlock.

---

How this cannot make a deadlock?

X:- varP =true;

Y :-  varQ=true: while (varP==true) { cs; varQ = false; }

X :- While(varQ==true) (this cond. Will be false and will not go in while loop and process X will leave

Y:- stucked in while loop as varP will be always true until X again come. Thus it has deadlock

---

Y:- stucked in while loop as varP will be always true until X again come.

There's no ; in while loop. When Y runs again, it will make varQ=true and at that time X can run b/c it's while loop will be true. So, there's no deadlock!