Question 60

Examine the entry protocol for process $P_i$:

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]);
}

Key observation on the waiting condition:
while (t[j] != 0 && t[j] <= t[i]);
In Lamport's Bakery algorithm, tie-breaking between identical tickets is done by comparing process IDs: (t[j] < t[i]) || (t[j] == t[i] && j < i). In this code, however, the strict <= condition is used without process ID tie-breaking.

Deadlock scenario:

• Suppose two processes $P_i$ and $P_k$ attempt to enter their critical sections simultaneously and obtain the exact same ticket value: $t[i] = t[k] = v > 0$.
• When $P_i$ examines $P_k$, it sees $t[k] \ne 0$ and $t[k] \le t[i]$ (since $v \le v$), so $P_i$ waits for $P_k$.
• Simultaneously, when $P_k$ examines $P_i$, it sees $t[i] \ne 0$ and $t[i] \le t[k]$ (since $v \le v$), so $P_k$ waits for $P_i$.
• Both processes wait on each other indefinitely, resulting in a deadlock. Consequently, progress is not guaranteed, bounded waiting is not satisfied, and deadlock can occur.

Mutual Exclusion check:

• Suppose process $P_i$ enters the critical section. This means that for every other process $j$, when $P_i$ checked $j$, either $t[j] = 0$ or $t[j] > t[i]$.
• If another process $P_j$ tries to enter while $P_i$ is inside, it will find $t[i] \ne 0$ and $t[i] \le t[j]$ (or it will wait in while (c[i])), preventing $P_j$ from entering.
• Even in the tie case $t[i] = t[j]$, neither process can enter the critical section.
• Therefore, two processes can never be simultaneously in the critical section. Mutual exclusion is preserved: at most one process can be in the critical section at any time.