GATE CS 2016 Set 2 Q49 — Concurrency and Synchronization

To find the largest initial value of the counting semaphore $S$ (let it be $S_0$) for which at least one $P(S)$ operation remains blocked at the end of the execution:

• Each $P(S)$ operation decrements the semaphore and requires $1$ resource unit. Total $P(S)$ operations = $20$.
• Each $V(S)$ operation increments the semaphore and releases $1$ resource unit. Total $V(S)$ operations = $12$.

The total number of resource units available during the entire execution is the sum of the initial value and the units released by $V(S)$ operations:

For at least one $P(S)$ operation to remain blocked at the end, the total available resources must be strictly less than the total number of requested $P(S)$ operations:

Thus, the largest integer value of $S_0$ is $7$.