Semaphores and Process Ordering in OS: P/V Traces, Worked Examples and GATE Traps

Semaphore traces get confusing when the scheduler starts an inconvenient process and zero can mean either no permit or an event not yet signalled. Use one convention throughout: wait consumes an available permit and otherwise blocks; signal transfers a permit to a waiter or leaves it available. For critical-section requirements and primitive choice, use Process Synchronization in Operating Systems: Semaphores, Critical Sections and Worked Examples. For an ordering question, translate each precedence edge into a zero-initialised event, then trace every blocked wait and shared-state change.

Semaphore fundamentals: permits, atomic operations and initial values

A semaphore changes only through atomic wait and signal. wait(S) consumes a permit when S > 0; at 0, the caller blocks. signal(S) adds a permit, consumed on resumption or left available.

Some books store negative values for waiters. The blocking model is compatible, but never mix trace representations. P or down means wait; V or up means signal.

Mutexes impose ownership; semaphores need not be signalled by their waiter.

Process ordering with semaphores: translate every precedence edge

For A before B, set aDone = 0, put signal(aDone) after A, and wait(aDone) before B. Zero prevents an early pass.

s12 = 0; s23 = 0
P1: x = x + 2; signal(s12)
P2: wait(s12); x = 3*x; signal(s23)
P3: wait(s23); x = x - 4

The chain serialises all accesses without another mutex. For A -> C and B -> C, set aDone = bDone = 0. Each source signals; C waits on both. A and B may swap, but C follows both. One semaphore per edge exposes the guarantee.

Worked semaphore trace: a hostile scheduler still gives x = 5

Start x = 1, s12 = 0, s23 = 0; schedule P3, P2, P1.

The operation order is P1, P2, P3, and x = 5.

With only s12 wrongly set to 1, schedule P2, P3, P1. P2 passes: 1 -> 3; P3 follows: 3 -> -1; P1 finishes: -1 -> 1. Final value 1, not 5, proves the event must start at 0.

Counting semaphore worked example: a two-slot bounded buffer

For capacity 2, start empty = 2, full = 0, mutex = 1, buffer [].

Producer: wait(empty); wait(mutex); insert(item); signal(mutex); signal(full)
Consumer: wait(full); wait(mutex); remove(item); signal(mutex); signal(empty)

C consumes the permit when its wait completes. Every edit takes mutex: 1 -> 0 -> 1. empty prevents overflow, full prevents underflow, and mutex serialises updates. After operations, empty + full = 2.

Semaphore patterns: mutual exclusion, fan-in and rendezvous

Let x = 10 and two processes run non-atomic x = x + 1. A mutex gives 10 -> 11 -> 12. Without it, both may read 10 and write 11. Only enclosed code is protected.

Use A1; signal(aDone); wait(bDone); A2 and B1; signal(bDone); wait(aDone); B2. This guarantees A1 before B2 and B1 before A2, but fixes neither the A1/B1 nor A2/B2 order. Signalling first avoids circular wait.

Semaphore traps: wrong initialisation, assumed fairness and circular wait

wait and signal are atomic; intervening statements are not. Implementations may block rather than spin. Wake-up order and starvation freedom need a stated policy. Binary semaphores need not enforce ownership.

Start s = t = 1. P1 waits on s, making s = 0; P2 waits on t, making t = 0. P1 then waits on t and P2 on s. Both block. Acquire s before t, or avoid holding one while awaiting another.

GATE-style semaphore questions: trace guarantees before arithmetic

Practice forms ask for an initial value, required precedence, a final shared value, a pass or block count, or deadlock and lost-wake-up detection. These are GATE-style forms, not an official blueprint.

Trace quickly: write initial values; stop at a wait on 0; treat each signal as a transfer or increment; record values only on execution; separate guaranteed from scheduler order. Check x = 5, wrong-initialisation x = 1, and [B,C] with (empty,full) = (0,2).

Continue with Process Synchronization MCQs: 12 Solved GATE Questions. Use GATE CS Exam Preparation to place P/V traces inside the wider Operating Systems syllabus.

Semaphores and ordering: the short version and next step

Remember five points: wait consumes or blocks; signal wakes or adds a permit; mutual exclusion starts at 1; a fresh ordering event starts at 0; every precedence edge needs a signal after its source and a wait before its destination. Keep resource counting separate from event ordering.

Now redraw P1 -> P2 -> P3, calculate 1 -> 3 -> 9 -> 5, and explain why s12 = 1 permits the wrong execution. Then replay (2,0,[]) to (0,2,[B,C]). Use GATE Guidance by Sanchit Sir for a sequenced Operating Systems route and timed practice.