Subj : Re: Deadlock theorem
To   : comp.programming.threads
From : Uenal Mutlu
Date : Thu May 12 2005 10:13 pm

Here's a deadlock detector applying the discussed deadlock theorem:

//--------------------------------------------------------------------
/*
    DeadlockDetect.cpp  v1.00

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

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

    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 means that deadlock will happen.
      The program asks for the list of all shared objects, and then asks for the
      objects used in each thread. It then does a mathematical analysis of the data
      and prints the result.
      The nbr of objects and threads is not fixed. A blank entry means end of input.

      It uses a static top-down analysis; a bottom-up, or any other ordering sequence
      is possible too, but these others are not coded here. The theorem also allows
      a dynamic determination of the list of objects and their sequence.


    A sample session:

      Deadlock Detector (here Static Analysis) using the Deadlock Theorem of Mutlu
      http://groups-beta.google.com/group/comp.programming.threads/msg/4e3f2c3a3452889d?dmode=source&hl=en

      INPUT:
      Enter list of objects seperated by blank: a b c d e f g
      Enter objects used in Thread0: a c
      Enter objects used in Thread1: a b c
      Enter objects used in Thread2: b c d a e f
      Enter objects used in Thread3: e f
      Enter objects used in Thread4: c
      Enter objects used in Thread5: b f g
      Enter objects used in Thread6: b c c d e f
      Enter objects used in Thread7:

      DATA:
      ObjectList: a b c d e f g
      Objects used in Thread0: a c
      Objects used in Thread1: a b c
      Objects used in Thread2: b c d a e f
      Objects used in Thread3: e f
      Objects used in Thread4: c
      Objects used in Thread5: b f g
      Objects used in Thread6: b c c d e f

      ANALYSIS:
      The lock order of object 'a' in Thread2 causes deadlock!
      Result: Deadlock!

 */

#include <vector>
#include <algorithm>
#include <string>
#include <iostream>

using namespace std;


struct TSItem
  {
    string sObject;
    int    ixInList;
  };

struct TSThreadData
  {
    vector<TSItem> vSharedObjects;

    int AddObjects(char* ApszObjects, vector<string>& AvListOfObjects)
      {
        int   cAdded    = 0;
        char* pszObject = 0;
        while ((pszObject = strtok(pszObject ? 0 : ApszObjects, " \t\n\r")))
          {
            TSItem SI;
            SI.sObject  = pszObject;
            SI.ixInList = -1;

            vector<string>::iterator result =
              find(AvListOfObjects.begin(), AvListOfObjects.end(), SI.sObject);
            if (result == AvListOfObjects.end())
              {
                cout << "Object '" << pszObject
                     << "' missing in object list. Ignored object." << "\n";
                continue;
              }
            SI.ixInList = result - AvListOfObjects.begin();
            vSharedObjects.push_back(SI);
            cAdded++;
          }
        return cAdded;
      }

    void Clear()
      { vSharedObjects.erase(vSharedObjects.begin(), vSharedObjects.end()); }

    int Analyse(int AiThread)
      {
        int cBad = 0;
        for (vector<TSItem>::iterator j = vSharedObjects.begin() + 1;
                                          j < vSharedObjects.end(); ++j)
          if (j->ixInList < (j - 1)->ixInList)
            {
              cout << "The lock order of object '" << j->sObject
                   << "' in Thread" << AiThread << " causes deadlock!\n";
              cBad++;
            }
        return cBad;
      }

    void Dump()
      {
        for (vector<TSItem>::iterator j = vSharedObjects.begin();
                                      j < vSharedObjects.end(); ++j)
          cout << " " << j->sObject;
        cout << "\n";
      }
  };

class TCDeadLockDetector
  {
    public:
      vector<string> vListOfObjects;

      TCDeadLockDetector()
        {}

      int AddObjectsToList(char* ApszObjects)
        {
          int   cAdded    = 0;
          char* pszObject = 0;
          while ((pszObject = strtok(pszObject ? 0 : ApszObjects, " \t\n\r")))
            vListOfObjects.push_back(string(pszObject)), cAdded++;
          return cAdded;
        }

      void AddThreadData(TSThreadData& AsThreadData)
        { vThreads.push_back(AsThreadData); }

      void Analyse()
        {
          cout << "\nDATA:\n";

          size_t i;
          cout << "ObjectList:";
          for (i = 0; i < vListOfObjects.size(); i++)
            cout << " " << vListOfObjects[i];
          cout << "\n";

          for (i = 0; i < vThreads.size(); i++)
            {
              cout << "Objects used in Thread" << i << ":";
              vThreads[i].Dump();
            }

          cout << "\nANALYSIS:\n";
          int cBad = 0;
          for (i = 0; i < vThreads.size(); i++)
            cBad += vThreads[i].Analyse(i) != 0;
          cout << "Result: " << (cBad ? "Deadlock!" : "No deadlock") << "\n";
        }

      void Test1();

    private:
      vector<TSThreadData> vThreads;
  };

void TCDeadLockDetector::Test1()
  {
    cout << "INPUT:\n";

    char szLine[512] = "";
    cout << "Enter list of objects seperated by blank: ";
    fgets(szLine, sizeof(szLine), stdin);
    AddObjectsToList(szLine);

    for (int i = 0; ; i++)
      {
        cout << "Enter objects used in Thread" << i << ": ";
        szLine[0] = 0;
        fgets(szLine, sizeof(szLine), stdin);

        TSThreadData SThr;
        if (!SThr.AddObjects(szLine, vListOfObjects))
          break;
        AddThreadData(SThr);
      }

    Analyse();
  }


int main(int argc, char* argv[])
  {
    cout << "Deadlock Detector (here Static Analysis) using the Deadlock Theorem of Mutlu\n";
    cout << "http://groups-beta.google.com/group/comp.programming"
            ".threads/msg/4e3f2c3a3452889d?dmode=source&hl=en\n\n";

    TCDeadLockDetector DD;
    DD.Test1();
    return 0;
  }

//--------------------------------------------------------------------

.