سوال ۱۰۲ کنکور ارشد مهندسی کامپیوتر ۱۴۰۰

To impose a strict execution order on statements that live in different concurrent processes, we build a precedence chain with counting semaphores initialized to $0$. A semaphore initialized to $0$ acts as a one-shot baton: a Wait on it blocks until some other process does a matching Signal.

The desired order is $S_1 \to S_2 \to S_3 \to S_4.$ Each arrow $S_i \to S_{i+1}$ is enforced by one semaphore: the successor Waits on it before running its statement, and the predecessor Signals it after running its statement.

Option 1 (correct):

P1:  S1; Signal(a)
P2:  Wait(a); S2; Signal(b)
P3:  Wait(b); S3; Signal(c)
P4:  Wait(c); S4

Trace with $a=b=c=0$:

• $P_2$ hits Wait(a) and blocks (because $a=0$). Only after $P_1$ runs $S_1$ and then Signal(a) does $a$ become $1$ and $P_2$ proceed. Hence $S_1$ executes before $S_2$.
• Symmetrically Wait(b) blocks $P_3$ until $P_2$ has finished $S_2$ and signalled $b$, so $S_2 \prec S_3$.
• Wait(c) blocks $P_4$ until $P_3$ has finished $S_3$ and signalled $c$, so $S_3 \prec S_4$.

The three constraints compose into the total order $S_1 \prec S_2 \prec S_3 \prec S_4$, exactly as required.

Why the others fail:

• Option 2 places each statement before its Wait (S2; Wait(a)…). The statement is no longer guarded, so $S_2,S_3,S_4$ can run before their predecessors — no ordering is enforced.
• Option 3 Signals before $S_1$ runs and lumps all the Waits into $P_4$; nothing serializes $S_1,S_2,S_3$ relative to each other.
• Option 4 puts the Signal of a semaphore in the successor and the Wait in the predecessor, reversing the baton direction; with the semaphores at $0$ this deadlocks ($P_1$ blocks on Wait(a) while the Signal(a) that would release it sits behind it in $P_2$), and even ignoring that it never produces the forward order.

So only Option 1 guarantees $S_1 \to S_2 \to S_3 \to S_4$.

Exam trick: For a precedence chain, initialize the sync semaphores to $0$ and read each one as an arrow: the producer of the arrow does Signal after its statement, the consumer does Wait before its statement. A statement that sits before its Wait, or a Signal placed before the guarded statement, never enforces ordering.