The GATE Grind

GATE 2016 CS – Question 60

Operating System · Concurrency and Synchronization · 2 marks · Multiple choice

Consider the following proposed solution for the critical section problem. There are $n$ processes: $P_0 \ldots 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?

  1. At most one process can be in the critical section at any time
  2. The bounded wait condition is satisfied
  3. The progress condition is satisfied
  4. It cannot cause a deadlock

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) At most one process can be in the critical section at any time

Explanation

This is a variant of Lamport's bakery algorithm. Each process takes a ticket one higher than the largest ticket in use and waits for every process holding a smaller ticket (or the same ticket with a smaller index) to finish. That ensures at most one process in the critical section. The official key marks this as the true statement.