Mutex Lock Order Deadlock Detection

Problem

Detect the first deadlock in a sequence of mutex operations.

Each operation is ["lock", thread, lock] or ["unlock", thread, lock]. A request for a mutex held by another thread makes the requester wait; unlocking hands the mutex to the earliest waiting thread. After every request, check the wait-for graph for a cycle.

Return the 0-based index of the first operation that creates a deadlock, or -1 when none does.

Hint

A deadlock is exactly a cycle in the wait-for graph.

Test cases

case 1

in: [[["lock","t1","A"],["lock","t2","B"],["lock","t1","B"],["lock","t2","A"]]]

expected: 3

case 2

in: [[["lock","t1","A"],["unlock","t1","A"],["lock","t2","A"]]]

expected: -1

case 3

in: [[["lock","t1","A"],["lock","t1","A"]]]

expected: -1

case 4

in: [[["lock","t1","A"],["lock","t2","B"],["unlock","t1","A"],["lock","t2","A"]]]

expected: -1

case 5

in: [[]]

expected: -1

Starter codePython

def deadlock_detect(operations):
    # Your code here
    pass

5 test cases · run your code against them in the editor