Puzzle

Difficulty: Hard · Puzzle 2 of 6 · Topic: Semaphore & Mailbox Puzzles

This hangs with mailbox depth 1. Explain exactly why depth matters and where progress stops.

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

module tb;
  semaphore lock = new(1);
  mailbox #(int) mb = new(1);

  initial mb.put(99); // fill mailbox

  task producer();
    lock.get(1);
    mb.put(100); // blocks because mailbox full
    lock.put(1);
  endtask

  task consumer();
    int v;
    lock.get(1); // waits for lock
    mb.get(v);
    lock.put(1);
  endtask

  initial fork
    producer();
    consumer();
  join_none
endmodule

Hint

Bounded put can block, creating wait dependency like get.

Step-by-step solution

1) mb starts full due to initial put(99).
2) Producer acquires lock then blocks on mb.put(100).
3) Consumer needs same lock before mb.get can free space.
4) Producer waits for mailbox space; consumer waits for lock -> deadlock.

Answer

Answer: Depth=1 makes put blocking when full. Holding lock during put causes circular wait and permanent hang.

Why candidates get it wrong

Many candidates only model get as blocking, forgetting bounded put is equally blocking.

Interviewer follow-up

Would increasing mailbox depth to 2 truly fix correctness or only mask the bug?

Related topics

• Back to Semaphore & Mailbox Puzzles

• Concurrency & Timing Puzzles section