VLSI DV Interview Puzzles · All levels

Lock Inversion with Two Semaphores

Two agents deadlock rarely under high parallel load. The failure disappears if either agent runs alone.

Puzzle

Difficulty: Hard · Puzzle 5 of 6 · Topic: Deadlock Scenario Puzzles: Objection and Phase Stalls

Two agents deadlock rarely under high parallel load. The failure disappears if either agent runs alone.

Code

systemverilog

semaphore cfg_sem = new(1);
semaphore bus_sem = new(1);

task agent_a();
  cfg_sem.get(1);
  #1ns;
  bus_sem.get(1);
  bus_sem.put(1);
  cfg_sem.put(1);
endtask

task agent_b();
  bus_sem.get(1);
  #1ns;
  cfg_sem.get(1);
  cfg_sem.put(1);
  bus_sem.put(1);
endtask

Hint

Classic AB-BA acquisition ordering bug.

Step-by-step solution

diagram

1) Capture semaphore acquisition timeline from both agents on failing seed.
2) Confirm agent_a holds cfg_sem waiting bus_sem while agent_b holds bus_sem waiting cfg_sem.
3) Enforce one global lock order across all users (for example cfg then bus everywhere).
4) Optionally merge locks if independent parallelism is not needed.
5) Add lock-order assertions in debug builds.

Answer

Answer: Bug: lock inversion causes circular wait (AB-BA deadlock). Fix: enforce consistent semaphore acquisition order across all threads.

Why candidates get it wrong

Random seed changes only shift timing; they do not remove the structural deadlock risk.

Interviewer follow-up

If lock ordering cannot be unified, what timeout/retry strategy would you choose and why?

Navigate