Question 59

Let $S_0$ be the initial value of the counting semaphore $S$ ($S_0 \ge 0$).

During execution, 20 $P(S)$ and 12 $V(S)$ operations are issued in some order. Each successful $P(S)$ operation decrements $S$ by 1. Each $V(S)$ operation either increments $S$ by 1 or unblocks one waiting process.

The total number of available resources across the entire execution is the initial value plus all increments from $V(S)$:

To maximize the number of blocked operations, consider an order where all 20 $P(S)$ operations are issued before any $V(S)$ operation:

1. The first $S_0$ operations of $P(S)$ succeed without blocking, leaving $S = 0$.
2. The remaining $20 - S_0$ operations of $P(S)$ find $S = 0$ and become blocked.
3. Then the 12 $V(S)$ operations are issued, unblocking at most 12 waiting $P(S)$ operations.
4. The number of $P(S)$ operations that remain blocked is:

For at least one $P(S)$ operation to remain blocked:

If $S_0 = 7$, then $20 - 7 = 13$ operations block initially, and 12 $V(S)$ operations unblock 12 of them, leaving exactly 1 operation blocked.
If $S_0 \ge 8$, at most 12 operations block initially, and the 12 $V(S)$ operations will unblock all of them, so no operation remains blocked.
Thus, the largest initial value of $S$ is 7.