Difficulty: Medium · Puzzle 1 of 6 · Topic: Semaphore & Mailbox Puzzles
Find the deadlock cycle. Does it depend on which of producer/consumer gets the lock first? Propose the minimal fix.
module tb;
semaphore lock = new(1);
mailbox #(int) req_mb = new();
mailbox #(int) rsp_mb = new();
task producer();
int rsp;
lock.get(1);
req_mb.put(7);
rsp_mb.get(rsp);
lock.put(1);
endtask
task consumer();
int req;
lock.get(1);
req_mb.get(req);
rsp_mb.put(req + 1);
lock.put(1);
endtask
initial fork
producer();
consumer();
join_none
endmoduleWhoever gets the lock first blocks on a mailbox that only the other side can feed.
1) If the producer wins the lock: it puts the request and then blocks on rsp_mb.get while holding the lock. The consumer is stuck on lock.get, so it never answers.
2) If the consumer wins the lock (start order swapped): it blocks on req_mb.get holding the lock, and the producer is stuck on lock.get, so it never sends. Verified in Verilator: either order hangs (only 'P got lock' or only 'C got lock' is reached).
3) The cycle is lock -> mailbox get -> the other side's lock acquisition.
4) Minimal fix: hold the lock only around the put (producer: lock.get; req_mb.put; lock.put; then rsp_mb.get) and do not hold it across req_mb.get in the consumer. Verified: the fixed version prints 'P done rsp=8'.Answer: Deadlock in both start orders: a thread holds the semaphore while blocked on a mailbox get that only the other thread can satisfy. Fix: never hold the lock across a blocking mailbox call.
Checked by running the code in Verilator 5; the printed output supports the answer above. Producer first: it holds the lock while blocked on rsp_mb.get, and the consumer never gets the lock. Consumer first: it holds the lock while blocked on req_mb.get, so the producer never gets the lock; both orders hang. Never hold the lock across a blocking mailbox call and the request/response completes.
Mailbox get is a blocking wait edge in the wait-for graph, not just message passing. And the deadlock does not need a particular start order, which is why it shows up as a flaky hang.
Show a lock-free request/response pattern using mailbox-only synchronization. Model answer: the producer does req_mb.put(7); rsp_mb.get(rsp); the consumer does req_mb.get(req); rsp_mb.put(req+1). Each mailbox has a single reader and a single writer, so no lock is needed; for several requesters, put a response mailbox handle in the request.
Yes, it deadlocks, and it does not depend on who gets the lock first. If the producer wins, it holds the lock while waiting for the response and the consumer is stuck on the lock; if the consumer wins, it holds the lock on the request get and the producer is stuck. A blocking mailbox get is a wait edge, so the cycle is the lock, the get and the other side's lock. The trap is thinking only one start order hangs, which is why it shows up as a flaky hang. The fix is to hold the lock only around the put and never across a blocking call.