How commonly do deadlock issues occur in programming?

Question

I've programmed in a number of languages, but I am not aware of deadlocks in my code.

I took this to mean it doesn't happen.

Does this happen frequently (in programming, not in the databases) enough that I should be concerned about it?

Answer 1

Deadlocks could arise if two conditions are true: you have mutilple theads, and they contend for more than one resource.

Do you write multi-threaded code? You might do this explicitly by starting your own threads, or you might work in a framework where the threads are created out of your sight, and so you're running in more than one thread without you seeing that in your code.

An example: the Java Servlet API. You write a servlet or JSP. You deploy to the app server. Several users hit your web site, and hence your servlet. The server will likely have a thread per user.

Now consider what happens if in servicing the requests you want to aquire some resources:

if ( user Is Important ){
     getResourceA();
}

getResourceB();

if (today is Thursday ) {
    getResourceA();
} 


// some more code

releaseResourceA();
releaseResoruceB();

In the contrived example above, think about what might happen on a Thursday when an important user's request arrives, and more or less simultaneously an unimportant user's request arrives.

The important user's thread gets Resoruce A and wants B. The less important user gets resource B and wants A. Neither will let go of the resource that they already own ... deadlock.

This can actually happen quite easily if you are writing code that explicitly uses synchronization. Most commonly I see it happen when using databases, and fortunately databases usually have deadlock detection so we can find out what error we made.

Defense against deadlock:

1. Acquire resources in a well defined order. In the aboce example, if resource A was always obtained before resource B no deadlock would occur.
2. If possible use timeouts, so that you don't wait indefinately for a resource. This will allow you to detect contention and apply defense 1.

Answer 2

It would be very hard to give an idea of how often it happens in reality (in production code? in development?) and that wouldn't really give a good idea of how much code is vulnerable to it anyway. (Quite often a deadlock will only occur in very specific situations.)

I've seen a few occurrences, although the most recent one I saw was in an Oracle driver (not in the database at all) due to a finalizer running at the same time as another thread trying to grab a connection. Fortunately I found another bug which let me avoid the finalizer running in the first place...

Basically deadlock is almost always due to trying to acquire one lock (B) whilst holding another one (A) while another thread does exactly the same thing the other way round. If one thread is waiting for B to be released, and the thread holding B is waiting for A to be released, neither is willing to let the other proceed.

Make sure you always acquire locks in the same order (and release them in the reverse order) and you should be able to avoid deadlock in most cases.

There are some odd cases where you don't directly have two locks, but it's the same basic principle. For example, in .NET you might use Control.Invoke from a worker thread in order to update the UI on the UI thread. Now Invoke waits until the update has been processed before continuing. Suppose your background thread holds a lock with the update requires... again, the worker thread is waiting for the UI thread, but the UI thread can't proceed because the worker thread holds the lock. Deadlock again.

This is the sort of pattern to watch out for. If you make sure you only lock where you need to, lock for as short a period as you can get away with, and document the thread safety and locking policies of all your code, you should be able to avoid deadlock. Like all threading topics, however, it's easier said than done.