What are common reasons for deadlocks?

Question

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 1

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.

Answer 2

The classic deadlock scenario is A is holding lock X and wants to acquire lock Y, while B is holding lock Y and wants to acquire lock X. Since neither can complete what they are trying to do both will end up waiting forever (unless timeouts are used).

In this case a deadlock can be avoided if A and B acquire the locks in the same order.

Answer 3

No deadlock patterns to my knowledge (and 12 years of writing heavily multithreaded trading applications).. But the TimedLock class has been of great help in finding deadlocks that exist in code without massive rework.

http://www.randomtree.org/eric/techblog/archives/2004/10/multithreading_is_hard.html

basically, (in dotnet/c#) you search/replace all your "lock(xxx)" statements with "using TimedLock.Lock(xxx)"

If a deadlock is ever detected (lock unable to be obtained within the specified timeout, defaults to 10 seconds), then an exception is thrown. My local version also immediately logs the stacktrace. Walk up the stacktrace (preferably debug build with line numbers) and you'll immediately see what locks were held at the point of failure, and which one it was attempting to get.

In dotnet 1.1, in a deadlock situation as described, as luck would have it all the threads which were locked would throw the exception at the same time. So you'd get 2+ stacktraces, and all the information necessary to fix the problem. (2.0+ may have changed the threading model internally enough to not be this lucky, I'm not sure)