Consider a non-negative counting semaphore $S$. The operation $P(S)$ decrements $S$, and $V(S)$ increments $S$. During an execution, 20 $P(S)$ operations and 12 $V(S)$ operations are issued in some order. The largest initial value of $S$ for which at least one $P(S)$ operation will remain blocked is __________.

Let $S_0$ be the initial non-negative value of the counting semaphore $S$.

• Each successful $P(S)$ (wait) operation consumes $1$ permit from the semaphore.

• Each $V(S)$ (signal) operation adds $1$ permit to the semaphore.

• Total $P(S)$ operations issued = $20$.

• Total $V(S)$ operations issued = $12$.

The maximum possible number of permits available across the entire execution (even under the most favorable ordering where all $12$ $V(S)$ operations execute before blocked $P(S)$ operations) is:

For at least one $P(S)$ operation to remain blocked, the total available permits must not be enough to satisfy all $20$ $P(S)$ operations:

Since $S_0$ must be an integer, the largest possible initial value is:

With $S_0 = 7$, at most $7 + 12 = 19$ $P(S)$ operations can succeed, guaranteeing that at least $1$ $P(S)$ operation remains blocked [CS-2, Q49].