Click here to Skip to main content
15,867,308 members
Articles / Programming Languages / C#
Article

Deadlock Detection in Existing Code

Rate me:
Please Sign up or sign in to vote.
5.00/5 (14 votes)
11 Jan 2008CPOL4 min read 139.1K   2.6K   75   33
The article briefly discusses deadlocks behavior, and presents an easy way to detect them.

Introduction

Deadlocks are common problems in multi-threaded programming. When it comes to multithreading development, the most common problem developers are facing is critical sections. It is not uncommon to use more than a single lock, but if one does not pay attention to the order of the locks, or to the context in which they are being called (e.g., from within a callback), deadlocks will form. (There are many reasons for deadlocks to occur other than the obvious critical section, e.g., two threads that are waiting for each other to signal an event, but we will not discuss them here).

As with anything that is related to threads, timing is everything. The most problematic deadlocks are those which occur rarely, they have this amazing nature of occurring at your client's site...

What if we could make the rare case the normal case? Recall that the reason a deadlock does not occur has to do with the fact that two threads that might deadlock happen not to be at the problematic places at the same time. So, all we have to do is record their "visits" at the problematic places, then we need to verify that the locks order is always the same, and if not, output the stack trace and notify the developer that we found a mismatch in the locks order.

The attached ZIP file contains a DLL that does exactly that. The DLL hacks all common (Enter, Exit, TryEnter methods, but it can be extended easily to support others, if used) monitor calls (including, of course, the .NET lock keyword) and keeps track of the locks order. Once it finds a problem in the order, it creates two stack traces, and directs you to a sample of the problematic locks (after fixing the error, repeat the test and see if there is another problem with the detected locks in another flow).

Note that there is no need for the deadlock to really occur; rather, it is only important that suspected flows (or all flows) will be performed at least once.

Using the code

  • Add the file incslock.cs to your project
  • Add a reference to the slockimp.dll
  • Compile your component and execute it

Analyzing the stacks (slockimp based)

  1. Once a problem is detected, the console (if one exists) will output the last lock conflicts with the nth of the stack
  2. Two files are being created in the working directory: first_xxx.txt and now_yyy (xxx and yyy represent numbers)
  3. Go to the "now" file – find the last lock (prior to the last four calls that are inner to the DLL)
  4. This is the lock that when locked caused the problem

  5. In order to find the other problematic lock, you can either:
    1. Spot the nth lock from the beginning of the stack (not counting locks that were recursively locked, and locks that were locked and released)
    2. Find the last lock in the "first" file
  6. Go over the "first" file stack, and find the place in which the lock from 3.a was locked

This is the second version of the implementation, which now supports more complex scenarios like the dining philosophers (thanks to Sergey's question below). The stack files are numbered as follows: 0_xxx.txt, 1_xxx.txt, and so on...

0_xxx points to the lock that when locked caused the problem. Other files point to other locks that created a kind of circular waiting.

Points of interest

Notice that you do not need to change a single existing line of code. Rather, you add two files to your project. The trick here is to cause the compiler to use our reference for implementing monitor calls rather then .NET's. (In the DLL itself, the locks are being locked and released properly, so your program should work fine critical-section wise). This trick is similar to replacing a header file in C.

Notice that the DLL is not meant for production, since it affects performance. Also, notice that the DLL allows recursive locks of the same lock. The DLL, however, will notify about possible deadlocks even if the waiting time is not infinite. (Despite the fact this is a false alarm, it indicates bad behavior, since such a behavior might influence performance and will deadlock if the time would be set to infinite).

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Team Leader
Israel Israel
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
Generalslockimp.dll Pin
ComplexityChaos19-Nov-09 9:03
ComplexityChaos19-Nov-09 9:03 
Questionno stack trace files are being generated Pin
PMD17-Jun-09 4:48
PMD17-Jun-09 4:48 
AnswerRe: no stack trace files are being generated Pin
eransha17-Jun-09 9:43
eransha17-Jun-09 9:43 
GeneralHello Eran Pin
evytre201-Apr-09 11:01
evytre201-Apr-09 11:01 
GeneralRe: Hello Eran Pin
eransha17-Jun-09 9:46
eransha17-Jun-09 9:46 
GeneralSimple enhancement to imitate lock() statement Pin
cwienands15-Feb-09 17:45
cwienands15-Feb-09 17:45 
GeneralRe: Simple enhancement to imitate lock() statement Pin
eransha23-Feb-09 8:53
eransha23-Feb-09 8:53 
GeneralRe: Simple enhancement to imitate lock() statement Pin
RobJHull28-Aug-13 2:44
RobJHull28-Aug-13 2:44 
Generalwhat's the "trick" Pin
jdstuart25-Nov-08 22:09
jdstuart25-Nov-08 22:09 
GeneralRe: what's the "trick" Pin
eransha29-Nov-08 3:40
eransha29-Nov-08 3:40 
GeneralCant download Pin
naveed20-Dec-07 11:21
naveed20-Dec-07 11:21 
GeneralRe: Cant download Pin
eransha24-Dec-07 9:44
eransha24-Dec-07 9:44 
GeneralNo, dining philosophers did not get any help [modified] Pin
Sergey Alexandrovich Kryukov20-Sep-07 6:42
mvaSergey Alexandrovich Kryukov20-Sep-07 6:42 
GeneralRe: No, dining philosophers did not get any help [modified] Pin
eransha20-Sep-07 21:48
eransha20-Sep-07 21:48 
GeneralRe: No, dining philosophers did not get any help Pin
eransha20-Sep-07 22:02
eransha20-Sep-07 22:02 
QuestionHow about dining philosophers? Pin
Sergey Alexandrovich Kryukov18-Sep-07 6:11
mvaSergey Alexandrovich Kryukov18-Sep-07 6:11 
AnswerRe: How about dining philosophers? Pin
eransha18-Sep-07 9:49
eransha18-Sep-07 9:49 
GeneralRe: How about dining philosophers? Pin
Sergey Alexandrovich Kryukov18-Sep-07 9:59
mvaSergey Alexandrovich Kryukov18-Sep-07 9:59 
GeneralRe: How about dining philosophers? [modified] Pin
eransha18-Sep-07 10:11
eransha18-Sep-07 10:11 
Question'System.Threading.Monitor' is defined in multiple assemblies Pin
mickridgway217-Sep-07 19:25
mickridgway217-Sep-07 19:25 
AnswerRe: 'System.Threading.Monitor' is defined in multiple assemblies Pin
eransha17-Sep-07 20:48
eransha17-Sep-07 20:48 
GeneralRe: 'System.Threading.Monitor' is defined in multiple assemblies Pin
mickridgway218-Sep-07 11:53
mickridgway218-Sep-07 11:53 
GeneralRe: 'System.Threading.Monitor' is defined in multiple assemblies [modified] Pin
eransha18-Sep-07 20:26
eransha18-Sep-07 20:26 
GeneralRe: 'System.Threading.Monitor' is defined in multiple assemblies Pin
jeffb4218-Oct-07 8:44
jeffb4218-Oct-07 8:44 
GeneralRe: 'System.Threading.Monitor' is defined in multiple assemblies Pin
eransha18-Oct-07 10:24
eransha18-Oct-07 10:24 
Hi Jeff,

I guess your code uses the "lock" clause, as I suggested in my previous answer you should be able to automatically search and replace all "lock" keywords into a kind of TimeLock pattern using the using keyword.

e.g. if your code looks like this:

lock(someobject)
{
}

It will look like this:

using (TimedLock.Lock(someobject))
{
}

with the VS2005 IDE search & replace it should be done easily.

In your implementation of the TimedLock, use explicitly the _Monitor version rather than the Monitor of mscorlib.

Hope that helped,
Eran

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.