Method for detecting and solving deadlocks in multithreading applications

• Download demo project - 32 Kb

Introduction

In this article we are presenting a method for solving thread deadlock problems. We applied this method in a real life multithreading project. We are presenting the solution we gave to the deadlock problem when using critical sections as synchronization objects, but the presented ideas can be easily extended for other synchronization objects. The main idea of the method is to develop our own critical section class derived from MFC CCriticalSection class, and inside this class to implement a static container in which to keep state information for every created instance object. In the overridden functions Lock() and Unlock() the static container is accessed and the state information pertaining to the current object is updated. The information in the static container can be saved in a file from a special thread. This special thread is put to wait for a system event to be set in order to save the state information and to unlock all the critical section objects in the container. The system event is set externally to the application from a distinct small console application.

Implementation

In order to make the work with worker threads easier and more object oriented we developed our own worker thread class in which we wrapped some threading Windows API functions:

class CWThread
{
public:
  //Constructor
  CWThread() : m_hThread(NULL), m_bSuspended(TRUE) {}

  //Destructor
  virtual ~CWThread()
  {
    Stop();
  }

  //Create
  BOOL Create(LPTHREAD_START_ROUTINE lpStartAddress, LPVOID lpParameter=NULL);

  //Resume the thread
  BOOL Resume();

  //Start the thread
  BOOL Start()
  {
    //Technically is the same as Resume()
    return Resume();
  }

  //Suspend the thread
  BOOL Suspend();

  //Get thread priority
  int GetPriority()
  {
    return GetThreadPriority(m_hThread);
  }

  //Set thread priority
  BOOL SetPriority(int iPriority)
  {
    return (TRUE == SetThreadPriority(m_hThread, iPriority));
  }

  //Stop the thread
  BOOL Stop();

  //Check if is created
  BOOL IsCreated()
  {
    return (m_hThread != NULL);
  }

  //Check if is suspended
  BOOL IsSuspended()
  {
    return m_bSuspended;
  }

private:
  CWThread& operator=(const CWThread&); //disallow copy
  //Handle to the thread
  HANDLE m_hThread;
  //Suspension Flag
  BOOL m_bSuspended;
};

//Create
BOOL CWThread::Create(LPTHREAD_START_ROUTINE lpStartAddress, LPVOID lpParameter)
{
  if(NULL == m_hThread)
  {
    DWORD dwThreadID;
    //Always created in a Suspended State
    m_hThread = CreateThread((LPSECURITY_ATTRIBUTES)NULL, (DWORD)0, lpStartAddress,
      lpParameter, (DWORD)CREATE_SUSPENDED, (LPDWORD)&dwThreadID);
    if(m_hThread != NULL)
    {
      //Initialized to Normal Priority
      SetThreadPriority(m_hThread, THREAD_PRIORITY_NORMAL);
      return FALSE; //OK
    }
  }
  return TRUE; //ERROR
}

//Resume the thread
BOOL CWThread::Resume()
{
  if((m_hThread!=NULL)&&(TRUE==m_bSuspended))
  {
    if(ResumeThread(m_hThread)!=0xFFFFFFFF)
    {
      m_bSuspended = FALSE;
      return FALSE; //OK
    }
  }
  return TRUE; //ERROR
}

//Suspend the thread
BOOL CWThread::Suspend()
{
  if((m_hThread!=NULL)&&(FALSE==m_bSuspended))
  {
    //Set the Flag before suspending (otherwise is not working)
    m_bSuspended = TRUE;
    if(SuspendThread(m_hThread)!=0xFFFFFFFF)
      return FALSE; //OK
    //If not successfull Reset the flag
    m_bSuspended = FALSE;
  }
  return TRUE; //ERROR
}

//Stop the thread
BOOL CWThread::Stop()
{
  if(m_hThread != NULL)
  {
    TerminateThread(m_hThread, 1);
    //Closing the Thread Handle
    CloseHandle(m_hThread);
    m_hThread = NULL;
    m_bSuspended = TRUE;
    return FALSE; //OK
  }
  return TRUE; //ERROR
}

In our critical section class we are using as a container an STL map in which we are mapping a unique instance IDs to a data structure. In the data structure we keep some information string and a pointer to the object instance. The pre-processor flag __INFOCRITSECT_DEBUG__ is used to activate the state updating operations in the Lock() and Unlock() functions.

Our critical section class:

#define __INFOCRITSECT_DEBUG__

#pragma warning(disable:4786)

#include "Afxmt.h"
#include "WThread.h"
#include <string>
#include <strstream>
#include <fstream>
#include <map>

using namespace std;

struct SData
{
  //CONSTRUCTOR
  SData(string const& rostrBeforeLock="No Init", string const& rostrAfterLock="No Init",
    string const& rostrBeforeUnlock="No Init", string const& rostrAfterUnlock="No Init",
    string const& rostrDesc="No Desc") : m_ostrBeforeLock(rostrBeforeLock), 
    m_ostrAfterLock(rostrAfterLock), m_ostrBeforeUnlock(rostrBeforeUnlock), 
    m_ostrAfterUnlock(rostrAfterUnlock), m_ostrDesc(rostrDesc),
    m_poCriticalSection(NULL) {}
  string m_ostrBeforeLock;
  string m_ostrAfterLock;
  string m_ostrBeforeUnlock;
  string m_ostrAfterUnlock;
  string m_ostrDesc;
  CCriticalSection* m_poCriticalSection;
};

//CInfoCritSect class - Implementing the Singleton Design Pattern
class CInfoCritSect : public CCriticalSection
{
public:
  //CONSTRUCTOR
  CInfoCritSect(string const& rostrDesc="No Desc")
  {
    //Add a new data element in the map
    sm_oCritSect.Lock();
      m_iIndex = sm_iCount;
      sm_iCount++;
      sm_oMap[m_iIndex] = SData();
      sm_oMap[m_iIndex].m_ostrDesc = rostrDesc;
      sm_oMap[m_iIndex].m_poCriticalSection = this;
    sm_oCritSect.Unlock();
  }

  void SetDescription(string const& rostrDesc)
  {
    //Remove the data element from the map
    map<unsigned int, SData>::iterator it;
    sm_oCritSect.Lock();
      it = sm_oMap.find(m_iIndex);
      if(it != sm_oMap.end())
        it->second.m_ostrDesc = rostrDesc;
    sm_oCritSect.Unlock();
  }

  //DESTRUCTOR
  ~CInfoCritSect()
  {
    //Remove the data element from the map
    map<unsigned int, SData>::iterator it;
    sm_oCritSect.Lock();
      it = sm_oMap.find(m_iIndex);
      if(it != sm_oMap.end())
        sm_oMap.erase(it);
    sm_oCritSect.Unlock();
  }
	
  void Lock(unsigned int uiLine=0, string const& rostrFileName="");

  void Unlock(unsigned int uiLine=0, string const& rostrFileName="");

  void BeforeLock(unsigned int uiLine, string const& rostrFileName)
  {
    //Find the position in map
    map<unsigned int, SData>::iterator it;
    sm_oCritSect.Lock();
    it = sm_oMap.find(m_iIndex);
    if(it != sm_oMap.end())
    {
      DWORD dwId = ::GetCurrentThreadId();
      ostrstream ostr;
      ostr << "Trying to Lock: ID=" << ::GetCurrentThreadId()
        << ", File=" << rostrFileName << ", Line=" << uiLine 
        << ", Time=" << ::GetTickCount();
      ostr << ends;
      it->second.m_ostrBeforeLock = ostr.str();
      ostr.freeze(0);
    }
    sm_oCritSect.Unlock();
  }

  void AfterLock(unsigned int uiLine, string const& rostrFileName)
  {
    //Find the position in map
    map<unsigned int, SData>::iterator it;
    sm_oCritSect.Lock();
    it = sm_oMap.find(m_iIndex);
    if(it != sm_oMap.end())
    {
      DWORD dwId = ::GetCurrentThreadId();
      ostrstream ostr;
      ostr << "Locked: ID=" << ::GetCurrentThreadId()
        << ", File=" << rostrFileName << ", Line=" << uiLine 
        << ", Time=" << ::GetTickCount();
      ostr << ends;
      it->second.m_ostrAfterLock = ostr.str();
      ostr.freeze(0);
    }
    sm_oCritSect.Unlock();
  }

  void BeforeUnlock(unsigned int uiLine, string const& rostrFileName)
  {
    //Find the position in map
    map<unsigned int, SData>::iterator it;
    sm_oCritSect.Lock();
    it = sm_oMap.find(m_iIndex);
    if(it != sm_oMap.end())
    {
      DWORD dwId = ::GetCurrentThreadId();
      ostrstream ostr;
      ostr << "Trying to Unlock: ID=" << ::GetCurrentThreadId()
        << ", File=" << rostrFileName << ", Line=" << uiLine 
        << ", Time=" << ::GetTickCount();
      ostr << ends;
      it->second.m_ostrBeforeUnlock = ostr.str();
      ostr.freeze(0);
    }
    sm_oCritSect.Unlock();
  }

  void AfterUnlock(unsigned int uiLine, string const& rostrFileName)
  {
    //Find the position in map
    map<unsigned int, SData>::iterator it;
    sm_oCritSect.Lock();
      it = sm_oMap.find(m_iIndex);
      if(it != sm_oMap.end())
      {
        DWORD dwId = ::GetCurrentThreadId();
        ostrstream ostr;
        ostr << "Unlocked: ID=" << ::GetCurrentThreadId()
          << ", File=" << rostrFileName << ", Line=" << uiLine 
          << ", Time=" << ::GetTickCount();
        ostr << ends;
        it->second.m_ostrAfterUnlock = ostr.str();
        ostr.freeze(0);
      }
    sm_oCritSect.Unlock();
  }

  static void PrintInfo()
  {
    //Open Output File
    ofstream fout("Deadlocks.out");
    if(!fout)
      return;
    sm_oCritSect.Lock();
      map<unsigned int, SData>::iterator it = sm_oMap.begin();
      while(it != sm_oMap.end())
      {			
        fout << "Critical Section: " << it->second.m_ostrDesc << endl;
        fout << " " << it->second.m_ostrBeforeLock << endl;
        fout << " " << it->second.m_ostrAfterLock << endl;
        fout << " " << it->second.m_ostrBeforeUnlock << endl;
        fout << " " << it->second.m_ostrAfterUnlock << endl;
        fout << endl;
        it++;
      }
    sm_oCritSect.Unlock();
    fout.close();
  }

  static void UnlockAll()
  {
    sm_oCritSect.Lock();
      map<unsigned int, SData>::iterator it = sm_oMap.begin();
      while(it != sm_oMap.end())
      {
        it->second.m_poCriticalSection->Unlock();
        it++;
      }
    sm_oCritSect.Unlock();
  }

private:
  static CCriticalSection sm_oCritSect;
  static map<unsigned int, SData> sm_oMap;
  static unsigned int sm_iCount;
  unsigned int m_iIndex;
};

inline void CInfoCritSect::Lock(unsigned int uiLine, string const& rostrFileName)
{
#ifdef __INFOCRITSECT_DEBUG__
  BeforeLock(uiLine, rostrFileName);
#endif
  CCriticalSection::Lock();
#ifdef __INFOCRITSECT_DEBUG__
  AfterLock(uiLine, rostrFileName);
#endif
}

inline void CInfoCritSect::Unlock(unsigned int uiLine, string const& rostrFileName)
{
#ifdef __INFOCRITSECT_DEBUG__
  BeforeUnlock(uiLine, rostrFileName);
#endif
  CCriticalSection::Unlock();
#ifdef __INFOCRITSECT_DEBUG__
  AfterUnlock(uiLine, rostrFileName);
#endif
}

unsigned int CInfoCritSect::sm_iCount = 0;

map<unsigned int, SData> CInfoCritSect::sm_oMap;

CCriticalSection CInfoCritSect::sm_oCritSect;

The special unlocking thread is derived from our general worker thread class we presented above and implements the Singleton design pattern:

class CDeadlocksThread : public CWThread
{
private:
  //CONSTRUCTOR - Private to prevent Construction from outside
  CDeadlocksThread();
	
public:
  //Create
  bool Create();
  //DESTRUCTOR
  ~CDeadlocksThread();
  //Getting the address of the unique instance
  static CDeadlocksThread* GetInstance();
	
private:
};

#include "stdafx.h"
#include "DeadlocksThread.h"
#include "InfoCritSect.h"

//Thread Function
UINT DeadlocksThreadProc(LPVOID pParam);

//CONSTRUCTOR
CDeadlocksThread::CDeadlocksThread()
{
}

//DESTRUCTOR
CDeadlocksThread::~CDeadlocksThread()
{
}

//Getting the address of the unique instance
CDeadlocksThread* CDeadlocksThread::GetInstance()
{
  static CDeadlocksThread soDeadlocksThread;
  return &soDeadlocksThread;
}

//Create
bool CDeadlocksThread::Create()
{
  if(TRUE == CWThread::Create((LPTHREAD_START_ROUTINE)DeadlocksThreadProc))
    return true;
  else
    return false;
}

//The Thread Function
UINT DeadlocksThreadProc(LPVOID pParam)
{
  HANDLE hEv = ::CreateEvent(NULL, FALSE, FALSE, "DeadlockDetection");
  while(true)
  {
    ::WaitForSingleObject(hEv, INFINITE);
    CInfoCritSect::PrintInfo();
    CInfoCritSect::UnlockAll();
  }
  return 0;
}

In DeadlocksThreadProc() when the system event is set the static functions PrintInfo() and UnlockAll() are called for saving the state information in a file and respectively unlock all the instance objects. The console application used for fireing the event is very simple:

#include "windows.h"
#include <iostream>

using namespace std;

void main(int argc, char* argv[])
{
  HANDLE hEv = ::OpenEvent(EVENT_ALL_ACCESS, FALSE, "DeadlockDetection");
  if(hEv != NULL)
  {
    ::SetEvent(hEv);
    cout << "DeadlockDetection event set" << endl;
  }
  else
    cout << "Cannot open DeadlockDetection event" << endl;
  ::CloseHandle(hEv);
}

The same name is used for the system event.

In the example project TestDeadlocks.zip associated to this article is a simple dialog based MFC application. When the Start Thread button is pressed a separate thread is started in which we intentionally forget to unlock the critical section of a data reservoir after locking. Since the data reservoir is also accessed by the user interface thread in the OnPaint() handler, the effect will be that the application's user interface will be frozen. The thread is also derived from our general worker thread class:

class CThread1 : public CWThread
{
public:
  //CONSTRUCTOR
  CThread1();
  //Create
  bool Create();
  //DESTRUCTOR
  ~CThread1();
	
private:
};

//Thread Function
UINT Thread1Proc(LPVOID pParam);

//CONSTRUCTOR
CThread1::CThread1()
{
}

//DESTRUCTOR
CThread1::~CThread1()
{
}

//Create
bool CThread1::Create()
{
  if(TRUE == CWThread::Create((LPTHREAD_START_ROUTINE)Thread1Proc))
    return true;
  else
    return false;
}

//The Thread Function
UINT Thread1Proc(LPVOID pParam)
{
  CDataReservoir* poDataReservoir = CDataReservoir::GetInstance();
  poDataReservoir->Lock(__LINE__, __FILE__);
  //Forgets to Unlock()
  //poDataReservoir->Unlock(__LINE__, __FILE__);
  TRACE("\nThread1");
  return 0;
}

//Or in an Infinite Loop
/*
//The Thread Function
UINT Thread1Proc(LPVOID pParam)
{
  //Infinite loop
  while(TRUE)
  {
    CDataReservoir* poDataReservoir = CDataReservoir::GetInstance();
    poDataReservoir->Lock(__LINE__, __FILE__);
    //Forgets to Unlock()
    //poDataReservoir->Unlock(__LINE__, __FILE__);
    TRACE("\nThread1");
    Sleep(50);		
  }
  return 0;
}
*/

Our data reservoir class is not containing any real data, having only for demonstrative purposes. Specific data can be easily added in real applications. The access to this real data will be protected by the m_oInfoCritSect critical section member.

//CDataReservoir class - Implementing the Singleton Design Pattern
class CDataReservoir
{
private:
  //CONSTRUCTOR - Private to prevent Construction from outside
  CDataReservoir();
	
public:
  //DESTRUCTOR
  ~CDataReservoir();
  //Getting the address of the unique instance
  static CDataReservoir* GetInstance();
  void Lock(unsigned int uiLine=0, string const& rostrFileName="");
  void Unlock(unsigned int uiLine=0, string const& rostrFileName="");

private:
  CInfoCritSect m_oInfoCritSect;
};

inline void CDataReservoir::Lock(unsigned int uiLine, string const& rostrFileName)
{
  m_oInfoCritSect.Lock(uiLine, rostrFileName);
}

inline void CDataReservoir::Unlock(unsigned int uiLine, string const& rostrFileName)
{
  m_oInfoCritSect.Unlock(uiLine, rostrFileName);
}

//CONSTRUCTOR
CDataReservoir::CDataReservoir()
{
  m_oInfoCritSect.SetDescription("DataReservoir CS");
}

//DESTRUCTOR
CDataReservoir::~CDataReservoir()
{
}

//Getting the address of the unique instance
CDataReservoir* CDataReservoir::GetInstance()
{
  static CDataReservoir soDataReservoir;
  return &soDataReservoir;
}

The unlocking thread is created and started in the OnInitDialog() handler:

CDeadlocksThread::GetInstance()->Create();
CDeadlocksThread::GetInstance()->Start();

The freezing thread is started by pressing the Start Thread button:

void CTestDlg::OnButton1()
{
  m_oThread1.Stop();
  m_oThread1.Create();
  m_oThread1.Start();
}

We can start running the application and press the Start Thread button. After that we will see that the user interface is not updated anymore. To unlock the application we should run the FireEvent.exe console application. After that the user interface will be updated and the file Deadlocks out will be written on the disk. The information in this file is similar to:

Critical Section: DataReservoir CS
 Trying to Lock: ID=1104, 
    File=C:\CodeProject\Deadlocks\TestDeadlocks\TestDlg.cpp, Line=168, Time=9481373
 Locked: ID=1100, 
    File=C:\CodeProject\Deadlocks\TestDeadlocks\Thread1.cpp, Line=34, Time=9479530
 Trying to Unlock: ID=1104, 
    File=C:\CodeProject\Deadlocks\TestDeadlocks\TestDlg.cpp, Line=169, Time=9477357
 Unlocked: ID=1104, 
    File=C:\CodeProject\Deadlocks\TestDeadlocks\TestDlg.cpp, Line=169, Time=9477357

and can be easily interpreted. We can easily see that the user interface thread with ID=1104 is trying to lock the critical section but cannot do it because the critical section was locked by the worker thread with ID=1100 and after that was never unlocked, so we have a deadlock because the resource is not released by the thread with ID=1100.

We hope that you will find the information presented in this article useful!