Puzzle

Difficulty: Medium · Puzzle 1 of 6 · Topic: Semaphore & Mailbox Puzzles

Find the deadlock cycle and propose the minimal fix without changing protocol intent.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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
endmodule

Hint

Producer blocks while still owning token that consumer needs.

Step-by-step solution

1) Producer acquires lock and sends request.
2) Producer blocks on rsp_mb.get while holding lock.
3) Consumer cannot acquire lock, so it cannot read request or send response.
4) Circular wait causes deadlock.
5) Fix: release lock before blocking mailbox call or reorder lock ownership.

Answer

Answer: Deadlock is lock -> rsp_mb.get -> lock cycle. Minimal fix: never hold semaphore across blocking mailbox operations.

Why candidates get it wrong

Mailbox get is still a blocking wait edge in deadlock analysis, not just 'message passing'.

Interviewer follow-up

Show a lock-free request/response pattern using mailbox-only synchronization.

Related topics

• Back to Semaphore & Mailbox Puzzles

• Concurrency & Timing Puzzles section