Question

Consider the following proposed solution for the critical section problem. There are n processes P0...Pn-1. Function pmax returns an integer not smaller than any of its arguments. For all i, t[i] is initialized to zero.

Code for Pi:
do {
  c[i]=1; t[i]=pmax(t[0],...,t[n-1])+1; c[i]=0;
  for every j≠i: { 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?

Accepted Answer

The correct answer is (A) At most one process can be in the critical section at any time. This is a ticket/Bakery-style algorithm: each process computes a timestamp t[i] strictly greater than every other process's currently-visible timestamp (via pmax+1), then waits for every other active process to either finish (t[j]=0) or have a strictly larger timestamp (t[j]>t[i]). Because timestamps assigned this way are always distinct once fully computed (each new one exceeds all others seen so far) and the wait condition (t[j]<=t[i]) forces the higher-timestamp process to wait for the lower one, mutual exclusion (at most one process in the critical section) IS guaranteed — but the solution can still starve individual processes under adversarial timing and doesn't strictly satisfy bounded-waiting or deadlock-freedom guarantees in every interleaving.

Explanation