One Signal, One Permit

Initial count 0. Events: P(4), P(7), V(2).

Predict the available count and queue before advancing.

Transfer, don't duplicate

Acquired: [4]; available: 0; waiting: [7].

V handed its permit to 4. Incrementing the count as well would let a newcomer bypass 7.

Check every event

count = initial + signals - completed acquisitions

A blocked wait adds no acquisition. A handoff adds a signal and an acquisition together. A nonempty queue requires count 0.

FIFO is an admission policy

The oldest queued caller receives the next signal.

No signals means no progress. CPU scheduling and lock-order deadlocks are separate concerns.

Read the edge contract

u → v: u needs v to make progress.

Exclusive owners, mandatory waits, no timeout or external release: a cycle cannot resolve itself. Multiple interchangeable resource instances need more information.

Visited is not enough

0 → 1, 0 → 2, 2 → 1 has no cycle.

Gray = on this path; black = finished. Only an edge to gray closes the DFS path. Search disconnected components too.

Exit check

Initial 1: P(1), P(2), V(1), P(3).

Answer: acquisitions [1,2]; 3 waits; count is 0. Explain why calling P again for thread 2 would consume the permit twice.