Project ForgeConsider 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 ____.
Explanation
In the best possible ordering (all 12 V's issued before any of the 20 P's), the total available permits become S₀+12. If S₀+12 < 20, at least one P must block no matter how operations are ordered, since there simply aren't enough total permits ever available. This holds when S₀ < 8, i.e. S₀ ≤ 7. At S₀=8, the best ordering (12 V's first) provides exactly 20 permits, letting all 20 P's succeed without blocking. So the largest S₀ guaranteeing at least one block is 7.
Source: GATE CS 2016 (Session 2 / Set B) (2016)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.