Consider the following proposed solution for the critical section problem.…
2016
Consider the following proposed solution for the critical section problem. There are \(n\) processes: \(P_0 ...P_{n−1}\). In the code, function pmax returns an integer not smaller than any of its arguments. For all i, t[i] is initialized to zero.
Code for \(P_i\) :
do { c[i]=1; t[i]= pmax (t[0],....,t[n-1])+1; c[i]=0; for every j != i in {0,....,n-1} { while (c[j]); while (t[j] != 0 && t[j] <=t[i]); } Critical Section; t[i]=0; Remainder Section; } while (true);
Which one of the following is TRUE about the above solution?
- A.
At most one process can be in the critical section at any time
- B.
The bounded wait condition is satisfied
- C.
The progress condition is satisfied
- D.
It cannot cause a deadlock
Attempted by 114 students.
Show answer & explanation
Correct answer: A
Key insight: the waiting condition enforces mutual exclusion, but the algorithm can deadlock when two processes obtain the same ticket.
Why mutual exclusion holds: A process enters the critical section only after for every other process j either t[j] == 0 or t[j] > t[i]. That prevents two processes from simultaneously satisfying the entry condition, so at most one process can be in the critical section at any time.
Why bounded waiting and progress can fail (deadlock counterexample):
Step 1: Two processes i and j set c[i]=c[j]=1 and simultaneously compute t[i]=pmax(...)+1 and t[j]=pmax(...)+1, reading the same values, so they get the same ticket value.
Step 2: Both set their choosing flags to 0 and proceed to the waiting loops. Each checks while(t[other] != 0 && t[other] <= t[self]); because the tickets are equal the condition is true for both.
Step 3: Both processes spin forever in that loop, producing a deadlock. This shows progress and bounded waiting are not guaranteed.
Root cause: the algorithm allows equal ticket values and uses "<=" without a tie-breaker (such as comparing process IDs), so equal tickets cause mutual blocking.
Conclusion: The statement that at most one process can be in the critical section at any time is true. The statements that bounded waiting is satisfied, that progress is satisfied, and that the algorithm cannot cause a deadlock are all false.
A video solution is available for this question — log in and enroll to watch it.