A nonnegative counting semaphore S uses P (decrement, blocking if unavailable) and V (increment). During execution twenty P and twelve V operations are issued in some order. Find the largest initial S for which a P remains blocked.
After all V operations there are S₀+12 total permits for twenty P operations. To leave at least one blocked, require S₀+12<20. Thus S₀<8 and the largest nonnegative integer is 7. With eight initially, all twenty P operations can eventually complete.
More Concurrency and Synchronization questions
GATE 2012 CS (CS1) Q42– Fetch And Add(L,i) atomically returns old L and increments L by i. Shared unsigned L…
GATE 2013 CS (CS1) Q44– x initially zero is shared by W,X,Y,Z. Each process waits on counting semaphore S=2, reads…
GATE 2013 CS (CS1) Q49– X computes a[i]=f(i), then ExitX(R,S), for i=0,…,n−1. Y calls EntryY(R,S), then computes…
GATE 2010 CS (CS1) Q33– Shared Boolean S1,S2 start with arbitrary values. P1 waits while S1==S2, enters its…
GATE 2010 CS (CS1) Q55– Binary semaphores S0,S1,S2 start at 1,0,0. Concurrent processes execute: How many times is…
GATE 2015 CS (CS3) Q31– Shared varP,varQ start false. These loops deliberately put the critical sections INSIDE…