GATE Overflow Test Series | Operating Systems | Test 1 | Question: 16

Question

Consider the following synchronization construct used by two the processes

turn1 = true;
turn2 = true;
Process 1
...
while(true)
{
    turn1 = true;
    while(turn2);
    /* Critical Section */
    turn1 = false;
}
...
Process 2
...
while(true)
{
    turn2 = true;
    while(turn1);
    /* Critical Section */
    turn2 = false;
}
...

Which one of the following statements is/are 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.

 

Answer 1

The given code guarantees mutual exclusion but since both turn1 and turn2 are initialized to TRUE both process $1$ and process $2$ will enter the infinite while loop without any progress. So, there is deadlock.

Correct answer: B.

Comments

If P1 then not P2 = NOT P1 OR NOT P2.

Now, (NOT P1 AND NOT P2) implies  (NOT P1 OR NOT P2).

Or in other words if no process in entering CS, mutual exclusion is satisfied.

---

Mutual exclusion, non preemption, hold and wait, and circular wait are necessary conditions for deadlock. So,
$~\neg \textrm{ME} \cup \neg \textrm{NP} \cup \neg \textrm{HW} \cup \neg \textrm{CW} \rightarrow \neg \textrm{DL} \Leftrightarrow \textrm{DL} \rightarrow \textrm{ME} \cap \textrm{NP} \cap \textrm{HW} \cap \textrm{CW}$.

If I can prove deadlock is there in the system, I don't need to check for ME (and other necessary condtions) separately.

Is my understanding correct @Arjun @Deepak Poonia sir?

---

yes