Subj : Deadlock Calculator
To   : comp.programming.threads
From : Uenal Mutlu
Date : Fri May 13 2005 03:44 pm

Here's an interactive deadlock calculator/detector (C++ source using STL):
http://www.nogashi.com/um/DeadlockDetect.cpp

A Compiled Exe for Windows incl. the source can be found
here: http://www.nogashi.com/um/DeadlockDetect_v2_00.zip  (9 KB)

If you find any bugs let me know.


What it does:
      In http://groups-beta.google.com/group/comp.programming.threads/msg/4e3f2c3a3452889d?dmode=source&hl=en
      a theorem was formulated about deadlock prevention & detection. This program
      tests for violation of the theorem. A violation of the theorem causes deadlock.

      The program asks for the list of all shared objects, whether recursive locking
      is to be used, and for the objects used in each thread (in lock order).
      It then does a mathematical analysis of the data and prints the result.
      Deadlock can be detected algebraically, ie. no need to have real threads running.

      The nbr of objects and threads is theoretically unlimited. A blank entry means end of input.

A sample session:
      Deadlock Detector v2.00 using the Deadlock Theorem of Mutlu

      INPUT:
      Enter list of objects seperated by blank: 0 1 2 3 4 5
      fRecursiveLocks?: 1
      Enter objects going to be locked (in lock order):
        Thread0: 1 3
        Thread1: 1 3 0
        Thread2: 3 0 1
        Thread3:

      DATA:
      ObjectList: 0 1 2 3 4 5
      fRecursiveLocks: 1
      Objects in T0: 1 3
      Objects in T1: 1 3 0
      Objects in T2: 3 0 1

      ANALYSIS:
      Deadlock: object '1' in T2(ix=2) vs. T0(ix=0)
      Result: Deadlock!

----------

.