Synchronization: Account for Every Permit

The semaphore exercise models atomic events in a supplied order. There are no actual threads or scheduler races: a blocked thread joins a queue, and a signal can complete that pending acquisition. Keeping these two events separate is the key to implementing it.

Count available permits, not blocked threads

Use a nonnegative count and a FIFO queue. P consumes one available permit or queues the caller if none exists. V either transfers one permit directly to the oldest waiter, or adds one available permit if the queue is empty. A transfer does not also increment count. The awakened thread has already acquired; it must not issue another P to claim the same permit.

Other presentations use a signed semaphore count whose negative magnitude tracks waiters. That is a different representation of the same synchronization idea. Do not combine its decrement-on-every-wait arithmetic with this exercise's separate queue. OSTEP: Semaphores

Let I be the initial count, S the number of signals processed, and A the number of completed acquisitions. After every event:

available count = I + S - A
available count >= 0
queue nonempty implies available count == 0

A blocked P changes neither S nor A. A V with a waiter increments both S and A, leaving the count unchanged. This proves conservation for the simulator, even when a signal is sent by a thread that never acquired. A semaphore is also useful for event notification; this API does not enforce mutex ownership or a maximum count.

A handoff trace

Start with one permit. The queue contains only blocked acquisitions.

Event	Available	Queue after event	Completed acquisitions
P(8)	0	[]	[8]
P(3)	0	[3]	[8]
P(6)	0	[3,6]	[8]
V(8)	0	[6]	[8,3]
P(9)	0	[6,9]	[8,3]
V(3)	0	[9]	[8,3,6]

The final count is 1 + 2 - 3 = 0. Thread 9 remains blocked. An incorrect increment-and-wake implementation leaves one available permit after V(8), so thread 9 bypasses thread 6. That produces an extra acquisition and violates the invariant.

FIFO determines admission order among queued callers. It does not promise wall-clock progress: there must be enough signals, and real runnable threads must eventually receive CPU time. Neither FIFO nor an empty queue alone rules out application deadlock.

When does a graph cycle mean deadlock?

For this exercise, an edge u → v is a mandatory current dependency: u is blocked until v can release what u needs. Think of exclusive locks with one owner, no timeout or external release, and no preemption. In this model a cycle is sufficient: every process around it needs another blocked process to move first. A self-loop is a cycle too.

For example, process 0 holds lock A and requests B, while process 1 holds B and requests A. The graph is 0 → 1 → 0. Process 2 waiting on process 1 may also be unable to progress without itself belonging to the cycle.

The interpretation matters. Suppose resource R has two interchangeable units: process 0 holds one, and runnable process 2 holds another. Process 1 waits for either unit while holding a lock needed by process 0. A naive 0 → 1 → 0 picture omits the fact that process 2 can release R and allow both to finish. Multi-instance resources or “wait for any one” requests require a richer model; potential dependencies are not mandatory waits. Deadlock also assumes mutual exclusion, holding resources while waiting, and no forced reclamation. OSTEP: Concurrency Bugs, UW resource-allocation models

Derive a cycle detector

Use three colors: white means unvisited, gray means on the current DFS path, and black means that path has finished. An edge to gray closes a cycle. An edge to black does not: 0 → 1, 0 → 2, 2 → 1 is a DAG even if 1 was visited first. Start DFS from every white vertex so a disconnected cycle is not missed. Each vertex and edge is examined a constant number of times: O(n + e) time and O(n + e) graph/stack space. Very deep graphs can motivate an explicit stack or Kahn's algorithm.

Detection only reports a cycle. Recovery needs an application policy such as aborting one participant and releasing its locks. Prevention instead removes a necessary condition: a global lock acquisition order forbids circular wait, provided every path obeys it.

Reconstruct before coding

1. With initial count 0, process P(4), P(7), V(2), P(5), V(4). Which acquisitions complete? 4 then 7; 5 remains queued. Two signals supplied exactly two permits.
2. Add 2 → 0 to the DAG above. Why does the answer change? DFS encounters a gray ancestor through 0 → 2 → 0. Reaching a previously finished vertex was harmless; closing the current path is not.
3. Does the graph API prove that a real service is deadlocked? Only if its caller built edges under the mandatory-wait assumptions. The function itself decides directed cyclicity.