Subj : Re: Deadlock Calculator
To   : comp.programming.threads
From : Uenal Mutlu
Date : Tue May 17 2005 10:07 am

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

UPDATE:

--------------------------------------------------------------------
    DeadlockDetect.cpp  v3.00

    Author  ; U.Mutlu (uenal.mutlu at t-online.de)
    Compiler: tested in VC++6, should work with all C++ compilers
    AppType : Console

    Compile and Link:
      CL /GX /W3 /MD /O2 DeadlockDetect.cpp
      (Don't use /ZI in VC++ for debug build; use /Zi instead)

    History :
      050512Th v1.00  (v1.00 was buggy)
      050513Fr v2.00  Fixed, and added option fRecursiveLock.
      050514Sa v2.01c Added option fShowAllDeadlocks.
      050517Tu v3.00  List of objects is now generated internally from the entered thread data.
                      Fixed a bug.
                      Improved the deadlock detection algorithm.
                      Added more info in output.

    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 and detection.
      This program analyses object locks in multithread programming
      and detects deadlocks and violations of the theorem.

      The program asks whether recursive locking is to be used or not,
      and for the objects to be locked 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.

      You can put the input data also into a text file and feed this file to the program.
      For example into a file named mydata.txt:
        1
        1
        a b c
        a c b

      then use input redirection to read from the file:
        DeadlockDetect <mydata.txt

--------------------------------------------------------------------
Sample session:

Deadlock Detector v3.00. Written by U.Mutlu
INPUT:
fRecursiveLocks?  : 1
fShowAllDeadlocks?: 1
Enter objects to be locked (in lock order):
  Thread0: b d
  Thread1: b d a
  Thread2: d a b
  Thread3:

DATA:
ObjectList         : b d a
fRecursiveLocks    : 1
fShowAllDeadlocks  : 1
LockedObjects in T0: b d
LockedObjects in T1: b d a
LockedObjects in T2: d a b

ANALYSIS:
ViolatesTheorem: object 'b' in T2(ix=2) vs. object 'a' in T2(ix=1)
Deadlock       : object 'd' in T0(ix=1) vs. object 'd' in T2(ix=0)
Deadlock       : object 'd' in T1(ix=1) vs. object 'd' in T2(ix=0)
Deadlock       : object 'b' in T2(ix=2) vs. object 'b' in T0(ix=0)
Deadlock       : object 'b' in T2(ix=2) vs. object 'b' in T1(ix=0)
Result: Deadlock!

--------------------------------------------------------------------

FYI: the Windows executable is in the same archive (see main posting)

.