Deadlock is where one or more threads wait for resources that can never become available.

The classic case (illustrated below) is where two threads both require two shared resources, and they use blocking mutexes to lock them in opposite order. Thread A locks resource X while thread B locks resource Y. Next, thread A attempts to lock resource Y and thread B attempts to lock resource X: since both resources are already locked (by the other thread), both threads wait indefinitely.

The following diagram should make the sequence clear.

Figure 1. Classic deadlock

It is easy to write code where deadlock is inevitable, here is the classic case:

Listing 1. Classic deadlock

boost::mutex resourceX;
boost::mutex resourceY;

void deadlockThreadAFunc()
{
    uint counter = 0;
    while(true)
    {
        boost::mutex::scoped_lock lockX(resourceX);
        boost::thread::yield(); // to encourage deadlock
        boost::mutex::scoped_lock lockY(resourceY);

        std::cout << "threadA working: " << ++counter << "\n";
    }
}

void deadlockThreadBFunc()
{
    uint counter = 0;
    while(true)
    {
        boost::mutex::scoped_lock lockY(resourceY);
        boost::thread::yield(); // to encourage deadlock
        boost::mutex::scoped_lock lockX(resourceX);

        std::cout << "threadB working: " << ++counter << "\n";
    }
}

The yield statements in the above example force the current thread to stop executing and allow another thread to continue. They are for demonstration purposes only, to encourage the deadlock to occur quickly. Without them, a single core machine may run for some time without having a context switch between the two resource locking statements (and thus triggering the deadlock).
For this toy example the fix is simple but non-intuitive. All we need to do is ensure we lock resources in a consistent order, so changing deadlockThreadBFunc() to lock resourceX before resourceY ensures there will be no deadlock. Unlock order is not significant.
One valuable technique to ensure strict lock-order discipline is to always lock a group of resources in the order of their memory address. However, it should be clear that deadlock will become much more of a problem in non-trivial code with complex data sharing requirements where resources are being locked at multiple levels and in many different contexts. This is one of the main reasons multi-threaded programming is so difficult - it sometimes requires coordination between multiple levels in your code, and this is the enemy of encapsulation.


Self Deadlock



Another problem is self-deadlock. Self-deadlock occurs when a single thread attempts to lock a mutex twice: the second attempt will block indefinitely. This can easily happen when the same resource is used at multiple levels within an algorithm.
In particular, consider a class that attempts to provide a threadsafe interface by synchronising all member function calls with a single internal mutex. The mutex is locked at the beginning of every method, and unlocked on method return. If that class now calls a member function from within a member function, there will be a self-deadlock.
To counter this problem there is the concept of recursive mutexes. A recursive mutex will allow multiple locks from within a single thread to succeed, though that thread must unlock the mutex as many times as it has locked it. The disadvantage of a recursive mutex is a slight performance decrease.

‹ MutexesupLivelock ›