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

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 them 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 4

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 5

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 6

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 7

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 8

A condition that occure whene two process are each waiting for the othere to complete befoure preceding.the result is both procedure is hang. its most comonelly multitasking and clint/server.

Answer 9

Deadlock occurs mainly when there are multiple dependent locks exist. In a thread and another thread tries to lock the mutex in reverse order occurs. One should pay attention to use a mutex to avoid deadlocks.

Be sure to complete the operation after releasing the lock. If you have multiple locks, such as access order is ABC, releasing order should also be ABC.

Answer 10

In my last project I faced a problem with deadlocks in an sql Server Database. The problem in finding the reason was, that my software and a third party software are using the same Database and are working on the same tables. It was very hard to find out, what causes the deadlocks. I ended up writing an sql-query to find out which processes an which sql-Statements are causing the deadlocks. You can find that statement here: Deadlocks on SQL-Server