deadlock condition

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

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 welock resources in a consistent order, so changingdeadlockThreadBFunc()to lockresourceXbeforeresourceYensures 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.

See also:
Mutex

Race Condition

Multithreading vs Multiprocessing
IPC and Advance Tutorial using C and C++