What are common reasons for deadlocks?

guerda picture guerda · Feb 9, 2009 · Viewed 29.9k times · Source

Deadlocks are hard to find and very uncomfortable to remove.

How can I find error sources for deadlocks in my code? Are there any "deadlock patterns"?

In my special case, it deals with databases, but this question is open for every deadlock.

Answer

Mitch Wheat picture Mitch Wheat · Feb 9, 2009

Update: This recent MSDN article, Tools And Techniques to Identify Concurrency Issues, might also be of interest


Stephen Toub in the MSDN article Deadlock monitor states the following four conditions necessary for deadlocks to occur:

  • A limited number of a particular resource. In the case of a monitor in C# (what you use when you employ the lock keyword), this limited number is one, since a monitor is a mutual-exclusion lock (meaning only one thread can own a monitor at a time).

  • The ability to hold one resource and request another. In C#, this is akin to locking on one object and then locking on another before releasing the first lock, for example:


lock(a)
{
...
    lock(b)
    {
            ...
    }
}
  • No preemption capability. In C#, this means that one thread can't force another thread to release a lock.

  • A circular wait condition. This means that there is a cycle of threads, each of which is waiting for the next to release a resource before it can continue.

He goes on to explain that the way to avoid deadlocks is to avoid (or thwart) condition four.

Joe Duffy discusses several techniques for avoiding and detecting deadlocks, including one known as lock leveling. In lock leveling, locks are assigned numerical values, and threads must only acquire locks that have higher numbers than locks they have already acquired. This prevents the possibility of a cycle. It's also frequently difficult to do well in a typical software application today, and a failure to follow lock leveling on every lock acquisition invites deadlock.