Semaphore

Precedence Graph

A precedence graph expresses statement-level ordering constraints across concurrent tasks. Each edge Si → Sj means Sj must not start until Si finishes. Semaphores realize the graph: one counting semaphore per dependency edge, initialized to 0; the predecessor Vs, the successor Ps.

Why semaphores per edge rather than per node?

Because an edge is a synchronization event: “Si is done; now Sj may run.” Per-edge semaphores let you express arbitrary DAGs, fan-out (one V unblocks many waiters only if you use multiple semaphores) and fan-in (multiple Ps in the successor). Per-node would conflate distinct dependencies.

Canonical example (Buhr)

Dependencies: S1 → {S2, S3}; S2 → S4; {S3, S4} → S5.

uSemaphore L1(0), L2(0), L3(0), L4(0);
 
_Task T1 { void main() { S1; L1.V(); L2.V(); } };   // S1 done ⇒ unblock S2 and S3
_Task T2 { void main() { L1.P(); S2; L3.V(); } };   // wait for S1, then run S2
_Task T3 { void main() { L2.P(); S3; L4.V(); } };   // wait for S1, then run S3
_Task T4 { void main() { L3.P(); S4; L4.V(); } };   // wait for S2, then S4; note L4 V'd twice
_Task T5 { void main() { L4.P(); L4.P(); S5; } };   // wait for BOTH S3 and S4 (two P's)

Optimal M-thread traversal

The 5-task COBEGIN above uses one thread per statement. The optimal solution uses the minimum number of threads and traverses the graph as M paths, folding independent chains into single threads. For the same graph, two threads suffice: one walks S1 → S4, the other walks S2 → S3 → S5, exchanging via fewer semaphores.

uSemaphore L1(0), L2(0);
COBEGIN
    BEGIN a = 1;   V(L1);  d = 2*a; V(L2); END     // thread 1: S1 then S4
    BEGIN b = 2;   P(L1);  c = a+b; P(L2); e = c+d; END  // thread 2: S2, S3, S5
COEND

Fewer threads ⇒ fewer context switches; fewer edges that cross threads ⇒ fewer semaphores. A precedence graph is different from a process graph: the process graph shows thread fan-out (the COBEGIN/COEND shape), the precedence graph shows statement dependencies.

Rules of thumb

• Fan-out of k ⇒ predecessor does k distinct Vs on k distinct semaphores.
• Fan-in of k ⇒ successor does k Ps (on distinct semaphores, or k Ps on one semaphore if predecessors all V the same one).
• Initialize all edge-semaphores to 0.

Related

• Semaphore
• COEND
• WAIT