Skip to content
GATETECH
Official PYQ · 2016Set 1 · Q50Concurrency and SynchronizationMCQ1 mark

GATE CS 2016 Set 1 Q50 — Concurrency and Synchronization

Explain with AI

Consider the following proposed solution for the critical section problem. There are nn processes : P0....Pn−1P_0....P_{n-1}. In the code, function pmax\text{pmax} returns an integer not smaller than any of its arguments .For all i,t[i]i,t[i] is initialized to zero.

Code for PiP_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 of the following is TRUE about the above solution?

Choose one option
View worked solution

Answer: A

This algorithm is a modified version of Lamport's Bakery Algorithm. Let's analyze its properties:

  1. Mutual Exclusion (Option A):
    • The flag c[i]c[i] acts as the choosing flag. The loop while (c[j]); ensures that process PiP_i waits if PjP_j is currently choosing its ticket, preventing PiP_i from reading an incomplete ticket value.
    • If two processes PiP_i and PjP_j have different ticket values, say t[i]<t[j]t[i] < t[j], then PiP_i will pass the check for PjP_j (since t[j]≤t[i]t[j] \le t[i] is false), while PjP_j will block on PiP_i (since t[i]≤t[j]t[i] \le t[j] is true).
    • If they choose the identical ticket value (t[i]=t[j]t[i] = t[j]), then the condition t[j] <= t[i] is true for PiP_i, and t[i] <= t[j] is true for PjP_j. Consequently, both processes block each other.
    • In all scenarios, it is impossible for more than one process to reside in the critical section simultaneously. Thus, mutual exclusion is satisfied.
  2. Deadlock and Progress (Options B, C, and D):
    • Because there is no tie-breaker (like process ID comparison) when tickets are equal, if two processes obtain the same ticket value, they will deadlock.
    • Since a deadlock can occur, the algorithm does not satisfy progress, is not deadlock-free, and does not guarantee bounded waiting.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Concurrency and Synchronization questions