Skip to question

Q173FreeDesign 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.
Candidate starting point

Implementation scaffold

class DeadlockDetector;
  int edges[int][$];
  int status[int]; // 0 = unseen, 1 = visiting, 2 = done

  function void wait_on(int from, int to);
    // Implement here: wait_on.
  endfunction

  function void clear_wait(int from);
    // Implement here: clear_wait.
  endfunction

  function bit dfs(int node);
    // Implement here: dfs.
  endfunction

  function bit has_deadlock();
    // Implement here: has_deadlock.
  endfunction
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
Q403 · Verification UtilitiesDetect a cycle created by one new waitMediumPQ404 · Verification UtilitiesRemove one wait dependencyEasyPQ405 · Verification UtilitiesReturn one concrete deadlock cycleMediumPQ123 · Hardware AlgorithmsValidate micro-operation dependenciesMediumQ1138 · SystemVerilog & UVMIsolate per-agent configuration and queued observationsHardP