Don't grow dreadlocks over code deadlocks

bridgwatera | No Comments
| More

In software application development, a so-called "deadlock" is a situation where two or more tasks permanently block each other by each task having a lock on a resource (within the software system), which other tasks are also trying to lock. Think of two people who both need two spanners to tighten some bolts, if each grabs one spanner, then neither can finish his/her work - hence a deadlock ensures.

At the risk of getting locked into this situation and starting to grow dreadlocks over a code deadblock -- consultant Alex Guryeva with independent provider of software testing and quality management services SQS (Software Quality Systems) explains the big picture here.

Dread.JPG

Guryeva says that because neither task in the above example can continue until a resource is available and neither resource can be released until a task continues, a deadlock state exists. The most common forms of deadlock that occur in systems are:

• Database deadlocks
• Deadlocks in multithreaded applications (e.g. Java, C#, C++)

The following text is taken from Guryeva's own analysis of this common coding conundrum...

Example A:

Database deadlock occurs when two users or sessions have locks on separate objects and each process is trying to acquire a lock on the object that the other process has. SQL Server will identify the problem and ends the deadlock by automatically choosing one process and aborting the other process, allowing the other process to continue. The aborted transaction is rolled back and an error message is sent to the user of the aborted process.

To avoid deadlocks, try to develop the application so that it grabs locks at the latest possible time and then releases them at the very earliest time. Also, do not allow any user input during transactions and try to collect it before transaction begins. Keep transactions as short as possible and use stored procedures or keep transactions with a single batch [1].

Thinking about the tools analogy again: each person needing the spanners should ensure that their work is set up so that they use their spanners for the minimum time required and should avoid being distracted by other things (e.g. 'user input') while using the spanners.

Example B:

Multithreaded programs can execute more than one task at a time. They allow the programmer to take advantage of multiple CPU machines (where they exist) by using each CPU to execute a different thread of control.

But writing multithreaded code that works correctly every time is really hard.

(Editor's note: it is worth remembering that Intel who advocates the use of parallel programming and concurrency in code structure says that it's really not so hard once you get your mindset wrapped around the concept.)

The most common reason for the cause of deadlocks in multithreaded applications is an inconsistent locking sequence. The threads in deadlock wait for resources, which are in turn locked by some other thread [2]. In effect this is a kind of circular dependency, for example: X can't complete its work until Y releases a resource, Y can't complete until Z releases some other resource, but Z is waiting for a resource that X has already grabbed - so everything is deadlocked.

The following is a small Java code fragment ,which can give rise to a deadlock.

Thread 1:
              synchronized (A){
                 synchronized (B){
                                     }
           }


Thread 2:
              synchronized (B){
                 synchronized (C){
                                      }
           }
Thread 3:

              synchronized (C){
                  synchronized (A){
                                       }
           }

Usually, the simplest and most efficient way to avoid deadlock is to ensure that resources are always acquired in some well-defined order.

References:
[1] http://www.sql-server-performance.com/tips/deadlocks_p1.aspx
[2] Dawson Engler. Racerx: Effective, static detection of race conditions and deadlocks.


Author: Alex Guryeva

Leave a comment

About this Entry

This page contains a single entry by Adrian Bridgwater published on January 27, 2011 10:46 AM.

When In Doubt, Check Them Out: CodeCompare Tools was the previous entry in this blog.

About Face! Developing Sudoko for Apple Mac: from mobile-to-desktop is the next entry in this blog.

Find recent content on the main index or look in the archives to find all content.