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

The typical scenario are mismatched update plans (tables not always updated in the same order). However it is not unusual to have deadlocks when under high processing volume.

I tend to accept deadlocks as a fact of life, it will happen one day or another so I have my DAL prepared to handle and retry a deadlocked operation.

Answer 2

Are you talking about database deadlocks or about deadlock in C#/Java etc etc?

Answer 3

Yes - deadlocks occur when processes try to acquire resources in random order. If all your processes try to acquire the same resources in the same order, the possibilities for deadlocks are greatly reduced, if not eliminated.

Of course, this is not always easy to arrange...

Answer 4

If it's database deadlocks, then what ocdecio said. Tables updates not updated in the same order. Sometimes they get out of sync and all messed up.

Answer 5

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 6

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 7

Making sure all transactions affect tables in the same order is the key to avoiding the most common of deadlocks.

For example:

Transaction A UPDATE Table A SET Foo = 'Bar' UPDATE Table B SET Bar = 'Foo'

Transaction B UPDATE Table B SET Bar = 'Foo' UPDATE Table A SET Foo = 'Bar'

This is extremely likely to result in a deadlock as Transaction A gets a lock on Table A, Transaction B gets a lock on table B, therefore neither of then get a lock for their second command until the other has finished.

All other forms of deadlocks are generally caused through high intensity use and SQL Server deadlocking internally whilst allocated resources.

Answer 8

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)

Answer 9

The most common (according to my unscientific observations) DB deadlock scenario is very simple:

• Two processes read something (a DB record for example), both acquire a shared lock on the associated resource (usually a DB page),
• Both try to make an update, trying to upgrade their locks to exclusive ones - voila, deadlock.

This can be avoided by specifying the "FOR UPDATE" clause (or similar, depending on your particular RDBMS) if the read is to be followed by an update. This way the process gets the exclusive lock from the start, making the above scenario impossible.

Answer 10

I recommend reading this article by Herb Sutter. It explains the reasons behind deadlocking issues and puts forward a framework in this article to tackle this problem.