Skip to question
ASIC.FYI

Q115FreeDesign Verification

Detect a deadlock in a wait graph

Difficulty
Medium
Topic
Verification Utilities
Language
SV
Interview prompt

Question

Maintain runtime wait dependencies among agents or queues. A directed edge from A to B means A is waiting on B. Return whether any dependency cycle exists.

Two directed wait graphs showing an acyclic chain from one to two to three and a cycle from one to two to three to one
An edge from A to B means A waits on B; adding the edge from three to one closes the cycle in the public example.
Starting point

Question code

class DeadlockDetector;
  function void wait_on(int from, int to);
  function void clear_wait(int from);
  function bit has_deadlock();
endclass
Reviewed example

Trace one case

Input
add waits 1->2 and 2->3; query; add 3->1; query
Expected output
no deadlock, then deadlock detected

The first graph is an acyclic chain; the final edge closes the directed cycle 1->2->3->1.

What to cover

Requirements

  1. Add a directed dependency and create target-only nodes as needed.
  2. Clear every outgoing dependency for one agent.
  3. Detect a cycle anywhere in a disconnected graph.
  4. Do not report a converging acyclic dependency chain as a deadlock.
Continue practicing
Q074 · Reference ModelsCheck delayed and reordered memory writesQ121 · Verification UtilitiesMonitor a credit-based linkQ101 · Verification UtilitiesDirect Programming Interface (DPI) 4-state data mapping