TAOCP 7.2.2.2 Exercise 100

Exercise 100. [22] [22] Show that the following protocol can starve one player but not the other:


A0. Maybe go to A1.	B0. Maybe go to B1.
A1. Set $a \leftarrow 1$, go to A2.	B1. Set $b \leftarrow 1$, go to B2.
A2. If $b$ go to A2, else to A3.	B2. If $a$ go to B3, else to B4.
A3. Critical, go to A4.	B3. If $a$ go to B4, else to B1.
A4. Set $a \leftarrow 0$, go to A0.	B4. If $a$ go to B4, else to B1.
	B5. Critical, go to B6.
	B6. Set $b \leftarrow 0$, go to B0.

Verified: no
Solve time: 1m48s

Solution

A process is starved if it is enabled infinitely often but never reaches its critical state.

Starvation of A is possible

Construct an infinite execution in which B repeatedly prevents A from leaving state $A_2$.

Start with B executing

$$ B0 \to B1 \to B2 \to B3 \to B4 \to B1 \to B2 \to B3 \to B4 \to \cdots $$

whenever $a=1$ at $B2$. In this behavior, B remains perpetually in the region ${B1,B2,B3,B4}$ and repeatedly executes $B1$, which sets $b \leftarrow 1$.

Meanwhile, A executes

$$ A0 \to A1 \to A2 $$

and then remains in $A2$. The transition rule at $A2$ is

$$ \text{if } b \text{ go to } A2,\quad \text{else to } A3. $$

Since B keeps executing $B1$, the value $b=1$ holds at every visit of A to $A2$. Therefore A never leaves $A2$ and never reaches $A3$ (its critical state). Thus A is starved.

Starvation of B is impossible

Assume B is starved, so B visits its critical state infinitely often but never reaches it. Then B must be prevented infinitely often from progressing beyond $B2$.

At $B2$, the behavior depends on $a$. If $a=0$, B proceeds toward $B4$ and eventually continues its cycle. If $a=1$, B is delayed in ${B3,B4}$, but neither $B3$ nor $B4$ permanently blocks progress of A, since A can only keep $a=1$ by repeatedly executing $A1$.

If A executes $A1$, then $a \leftarrow 1$. If A later reaches $A3$, it must have passed $A2$ with $b=0$, which forces B to have released control of the shared blocking condition. After A reaches $A4$, it executes $a \leftarrow 0$, removing the only condition that can indefinitely prevent B from advancing past $B2$.

Therefore, any attempt by A to keep $a=1$ forever requires A to remain in the loop

$$ A0 \to A1 \to A2 $$

without reaching $A4$. In this situation A never resets $a$ to $0$ again, so $a$ remains permanently $1$. Then B cannot be permanently blocked at $B2$, since the only blocking action of A is to alternate between setting $a$ and leaving it unchanged; A has no mechanism to force repeated reactivation of $a=1$ after B has progressed beyond $B2$.

Thus B cannot be prevented indefinitely from reaching its critical region by any execution consistent with the transition structure. Hence B is not subject to starvation.

This completes the proof. ∎