1,000+ ASIC Interview Questions: SystemVerilog, UVM & RTL

DescriptionQ115

Page ↗

Q115DVASIC interview problem

Detect a deadlock in a wait graph

TechniquesGraphDeadlockThree-color DFS

DifficultyMedium

TopicVerification Utilities

LanguageSystemVerilog

Requirements4 checkpoints

Problem

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.

Class declarationSystemVerilog

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

Example input and output

Use this case to check your interpretation

Input

add waits 1->2 and 2->3; query; add 3->1; query

Output

no deadlock, then deadlock detected

Explanation

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

Requirements (4)

Add a directed dependency and create target-only nodes as needed.
Clear every outgoing dependency for one agent.
Detect a cycle anywhere in a disconnected graph.
Do not report a converging acyclic dependency chain as a deadlock.