GATE IT 2007 | Question: 10

Question

Processes $P1$ and $P2$ use critical_flag in the following routine to achieve mutual exclusion. Assume that critical_flag is initialized to FALSE in the main program.

get_exclusive_access ( )
{
    if (critical _flag == FALSE) {
        critical_flag = TRUE ;
        critical_region () ;
        critical_flag = FALSE;
    }
}

Consider the following statements.

1. It is possible for both $P1$ and $P2$ to access critical_region concurrently.
2. This may lead to a deadlock.

Which of the following holds?

• A. (i) is false (ii) is true
• B. Both (i) and (ii) are false
• C. (i) is true (ii) is false
• D. Both (i) and (ii) are true

Comments

For Deadlock the necessary condition is Mutual Exclusion..isn't it?

---

Progress isn’t guaranteed because P2 will depend on P1 for critical_flag = FALSE if only enters the IF block. P1 will perform critical_flag = TRUE, access critical region, and then P2 will be blocked again at its IF block as critical_flag = TRUE. Thus, P2 will be depending on P1 (which is no more inside the critical region) for its further execution. Correct me if I am wrong.

---

All questions related to critical section & solution requirements(ME, Progress, Bounded waiting)

Operating System: GATE CSE 1987 | Question: 1-xvi

Operating System: GATE CSE 1996 | Question: 1.19, ISRO2008-61

Operating System: GATE CSE 2007 | Question: 58

Operating System: GATE CSE 2010 | Question: 23

Operating System: GATE CSE 2015 Set 3 | Question: 10

Operating System: GATE CSE 2016 Set 2 | Question: 48

Operating System: GATE IT 2007 | Question: 10

Answer 1

(C) Both process can run the critical section concorrently. Lets say $p_{1}$ starts and it enters inside if clause and just after its entrance and before execution of critical_flag = TRUE, a context switch happens and $p_{2}$ also gets entrance since the flag is still false. So, now both process are in critical section! So, (i) is true. (ii) is false there is no way that flag is true and no process' are inside the if clause, if someone enters the critical section, it will definetly make flag = true . So , no deadlock.

Comments

(i) is true then we say mutual exclusion property is violated . Since one of the necessary comdition for deadlock is mutal erxclusion we say (ii) is false

---

The line "If no Mutual Exclusion is the case how can deadlock happen in the first place as Mutual Exclusion is one of the four pillars of deadlock" might be wrong here. Mutual Exclusion for deadlock is for resources not like in a code.

Check: https://gateoverflow.in/8405/gate-cse-2015-set-3-question-10?show=93533#c93533

---

Exactly, this Mutual Exclusion is for resources, not for this.

Answer 2

Say P1 starts first and executes statement 1, after that system context switches to P2 (before executing statement 2), and it enters inside if statement, since the flag is still false.
So now both processes are in critical section!! so (i) is true.. (ii) is false
By no way it happens that flag is true and no process’ are inside the if clause, if someone enters the critical section, it will definitely make flag = false. So no deadlock.

Answer 3

here deadlock won't occur as the condition here is "if(critical_flag==false)"  not while(critical_flag==false);.

consider process P1 currently in critical section  preempts before setting critical _flag=False.

process P2 performs condition (True==false) gives false and hence comes out of the if condition and hence its execution is completed.there is no loop here (unlike while();)and hence no dependency on other processes.

Hence no deadlock.

for first answer both can enter critical sections as preemption could be done after if condition and before setting critical_flag as true  resulting multiple processes accessing critical sections at same time.

Answer 4

 

Answer 5

a)For Mutual Exclusion:

1)If One process is in critical section then other process is not able to get into Critical Section.

2) If Both the process want to get into CS then atmost one process can get into Critical Section.

In the question It ensures the first condition we know that intial value of critical_flag=false, Let us consider p1  make if condition true and make

critical_flag=true and enter in CS and p2 wants to enter into Cs it cannot enter as it stops at if condition because the p1 has already updated the variable value as

true.

Now to satisfy second condition if Both the process want to enter into CS then both the process satisfy if condition and enter into CS.Now there are more two processes in the

Cs,so it violates the condition of mutual exclusion and hence P1 and P2 access critical section concurrently.

b)It doesnt leads to leadlock as atleast one process can enter into CS.

Answer 6

2) not deadlock, even with `critical_flag = TRUE` initially. It becomes a progress violation (indefinite postponement), which is a different liveness failure.

 hypothetical

Initial state: `critical_flag = TRUE`, nobody has ever entered the CS.

Step    Process    Action    Result   
1    P1    `if (critical_flag == FALSE)` → FALSE    skips CS, moves on   
2    P2    `if (critical_flag == FALSE)` → FALSE    skips CS, moves on   

The flag is stuck at TRUE forever, because the only place it gets reset to FALSE is at the end of the critical region — and nobody ever reaches there. So no process can ever enter the CS.

Why this is NOT deadlock (check Coffman conditions)

Condition    Holds here?   
Mutual exclusion    (vacuously) yes   
Hold and wait    ❌ No — nobody holds any resource while waiting   
No preemption    n/a   
Circular wait    ❌ No — P1 isn't waiting for P2, and P2 isn't waiting for P1   

Two conditions fail ⇒ deadlock is impossible. Crucially: the processes are not blocked on each other — they're not even blocked at all. A failed `if` means skip and continue, not wait.

What it actually is

- Progress violated: no process is in the CS, processes want to enter, yet the "decision" of who enters is postponed indefinitely. Progress is one of the three required CS properties (mutual exclusion, progress, bounded waiting) — this construction kills it.
- If `get_exclusive_access()` is called in a loop, both processes keep testing and skipping forever — this is closer to starvation/livelock (active, but zero progress), still not deadlock.

Traps

- "Nobody ever enters" ≠ deadlock. Deadlock = a set of processes blocked, waiting for events only each other can trigger. Here the wait isn't on another process — it's on a flag nobody can reset. GATE marks these differently.
- Deadlock needs waiting — a plain `if` never waits. If the code had `while (critical_flag == TRUE);` instead, then your scenario would freeze both processes and the deadlock discussion would change.
- Note the original question initializes the flag to FALSE, so this stuck-TRUE state can't arise from the given code — it's purely a (valid) what-if.