3.1 About Deadlocks

The term deadlock describes a condition in which two or more threads are blocked forever because they are waiting for each other. There are many causes of deadlocks such as erroneous program logic and inappropriate use of synchronizations such as locks and barriers. This tutorial focuses on deadlocks that are caused by the inappropriate use of mutexes, or mutual exclusion locks. This type of deadlock is commonly encountered in multithreaded applications.

A process with two or more threads can enter deadlock when the following three conditions hold:

• Threads that are already holding locks request new locks

• The requests for new locks are made concurrently

• Two or more threads form a circular chain in which each thread waits for a lock which is held by the next thread in the chain

Here is a simple example of a deadlock condition:

• Thread 1 holds lock A and requests lock B

• Thread 2 holds lock B and requests lock A

A deadlock can be of two types: A potential deadlock or an actual deadlock and they are distinguished as follows:

• A potential deadlock does not necessarily occur in a given run, but can occur in any execution of the program depending on the scheduling of threads and the timing of lock requests by the threads.

• An actual deadlock is one that occurs during the execution of a program. An actual deadlock causes the threads involved to hang, but may or may not cause the whole process to hang.