Deadlocks

A deadlock can occur when using two or more locks and different strands acquire the locks in different orders. It is possible for two or more strands to become deadlocked when each strand acquires a mutex that the other strand attempts to acquire.

Following is a simple example, with two strand fragments, where the aim is to move a list element from one list to another in such a way that the element is always in exactly one of the two lists. L1 and L2 are the two lists, and sm1 and sm2 are two cilk::mutex objects, protecting L1 and L2, respectively.

// Code Fragment A. Move the beginning of L1 to the end of
L2.
sm1.lock();
sm2.lock();
L2.push_back(*L1.begin);
L1.pop_front();
sm2.unlock();
sm1.unlock();
...
...
// Code Fragment B. Move the beginning of L2 to the end of L1.
sm2.lock();
sm1.lock();
L1.push_back(*L2.begin);
L2.pop_front();
sm2.unlock();
sm1.unlock();

The deadlock would occur if one strand, executing Fragment A, were to lock sm1 and, in another strand, Fragment B were to lock sm2 before Fragment A locks sm2. Neither strand could proceed.

The common solution is to acquire the locks in exactly the same order in both fragments; for example, switch the first two lines in Fragment B. You can release the locks in the opposite order, but doing so is not necessary to avoid deadlocks.