14,088 views

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?

1. The proposed solution prevents deadlock but fails to guarantee mutual exclusion
2. The proposed solution guarantees mutual exclusion but fails to prevent deadlock
3. The proposed solution guarantees mutual exclusion and prevents deadlock
4. The proposed solution fails to prevent deadlock and fails to guarantee mutual exclusion

@bikram is it bounded waiting?
edited
What if process Y doesn't execute at all? Process X will never find varq to be true? Can we call this as deadlokd?

And what if process X execute and at in exit section set value of varp as false now process Y will not find value of varp as true?

And process never execute again. Well I think deadlock is possible.someone please clear this doubt!! I am reposting the question

@vupadhayayx86 If y doesn't execute at all and x never gets varq=True then it's violating Progress. I don't think it's called deadlock. Deadlock means both the processes want to enter CS but both of them (or any of them is) are unable to enter CS.

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.

### Subscribe to GO Classes for GATE CSE 2022

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

by

@Bikram sir. Thanks for the beautiful explanation!

Correct me if I am wrong .

Mutual Exclusion NOT Satisfied ==> No Deadlock Possible

Is the above statement always true ?

sir i think there is spin lock in this synchronization , but no deadlock . correct me if i im wrong . as when both variables are true and when x enters into cs then y cannot enter into cs and also now x will go in infinite loop.
@kashyaprparmer

Mutual Exclusion is one of the necessary conditions to occur deadlock. So if atleast one of the necessary conditions is not satisfied then there’ll be no deadlock.

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.

Nice !!!

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

Select this as Best answer.

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.

by

Can anyone please explain how two processes arrive into deadlock?

Yes, there isn't any possibility of deadlock.
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!

There will be dead lock, but mutual exclusion is satisfied.

suppose X executes and sets p to true then preempts,  now Y executes and sets q to true, now when Y goes to while statement it will loop forever, same happens with X.

Most answers are misinterpreting the definition of deadlock and misunderstanding the mutual exclusion condition of Deadlock characteristics with mutual exclusion of critical section.

The definition of Deadlock is :Deadlock is any situation in which no member of some group of entities can proceed because each waits for another member, including itself, to take action, such as sending a message or, more commonly, releasing a lock.

Also if we find even a single case in which deadlock occurs then the solution is said to not prevent deadlock.

Mutual exclusion in synchronization means only one process should enter cs, while mutual exclusion of deadlock characteristics is about a resouurce being owned by only a single process. Take printer for example, only one computer can use it at a time, so this ME can not alwasy be dissatisfied. which now brings me to another point:

ME of synchronization is property that must be enforced by a solution, while ME of deadlock characteristics is a property that should be removed to prevent deadlock. Do you see the difference? in one case we need ME to be present while in another case we need it to go away.

Students are confusing Mutual exclusion in both cases, when working with semaphore mutual exclusion doesn’t have anything to do with deadlock, both are different.

So answer is B

by

There will be dead lock, but mutual exclusion is satisfied.

suppose X executes and sets p to true then preempts,  now Y executes and sets q to true, now when Y goes to while statement it will loop forever, same happens with X.

Most answers are misinterpreting the definition of deadlock and misunderstanding the mutual exclusion condition of Deadlock characteristics with mutual exclusion of critical section.

The definition of Deadlock is :Deadlock - Wikipedia

Also if we find even a single case in which deadlock occurs then the solution is said to not prevent deadlock.

Mutual exclusion in synchronization means only one process should enter cs, while mutual exclusion of deadlock characteristics is about a resource being owned by only a single process. Take printer for example, only one computer can use it at a time, so this ME can not always be dissatisfied. which now brings me to another point:

ME of synchronization is property that must be enforced by a solution, while ME of deadlock characteristics is a property that should be removed to prevent deadlock. Do you see the difference? in one case we need ME to be present while in another case we need it to go away.

Students are confusing Mutual exclusion in both cases, when working with semaphore mutual exclusion doesn’t have anything to do with deadlock, both are different.

So answer is B

by