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

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

Answer 2

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