Deadlock: the Problem and a Solution

This article is excerpted from the pre-release of Manning Publications’ book, C++ Concurrency in Action By Anthony Williams.

Imagine you’ve got a toy that comes in two parts, and you need both parts to play with it—a toy drum and drumstick, for example. Now imagine that you’ve got two small children, both of whom like playing with it. If one of them gets both the drum and the drumstick, they can merrily play the drum until they get fed up. If the other child wants to play, they have to wait, however sad that makes them. Now imagine that the drum and the drumstick are buried (separately) in the toy box, and your children both decide to play with it at the same time, so go rummaging in the toy box. One finds the drum and the other finds the drumstick. Now they’re stuck—unless the children are remarkably kind, each will hold onto whatever they’ve got and demand the other gives them the other bit, and neither gets to play.

Now imagine that you’ve not got children arguing over toys, but threads arguing over locks on mutexes: each of a pair of threads needs to lock both of a pair of mutexes to perform some operation, and each thread has one mutex and is waiting for the other. Neither thread can proceed, as each is waiting for the other to release its mutex. This scenario is called deadlock, and is the biggest problem with having to lock two or more mutexes in order to perform an operation.

The common advice for avoiding deadlock is to always lock the two mutexes in the same order: if you always lock mutex A before mutex B, then you’ll never deadlock. Sometimes this is straightforward, as the mutexes are serving different purposes, but other times it is not so simple, such as when the mutexes are each protecting a separate instance of the same class. Consider for example a comparison operation on two instances of the same class—in order to avoid the comparison being affected by concurrent modifications, the mutexes on both instances must be locked. However, if a fixed order is chosen (e.g. the mutex for the instance supplied as the first parameter, then the mutex for the instance supplied as the second parameter), then this can backfire: all it takes is for two threads to try and compare the same instances with the parameters swapped, and you’ve got deadlock!

Thankfully, the C++ Standard Library has a cure for this in the form of std::lock—a function that can lock two or more mutexes at once without risk of deadlock. The example in listing 4.6 shows how to use this for a comparison operator. First, the arguments are checked to ensure they are different instances, as locking the same mutex twice is undefined behaviour if it’s not recursive. Then, the call to std::lock() (#1) locks the two mutexes, and two std::lock_guard instances are constructed (#2, #3): one for each mutex. The std::adopt_lock parameter is supplied in addition to the mutex to indicate to the std::lock_guard objects that the mutexes are already locked, and they should just “adopt” the lock on the mutex rather than locking it in the constructor. This ensures that the mutexes are correctly unlocked on function exit in the general case where the protected operation might throw an exception, as well as allowing for a simple return with the comparison result in this case. Also, it’s worth noting that locking either of lhs.m or rhs.m inside the call to std::lock can throw an exception: in this case the exception is propagated out of std::lock. If std::lock had successfully acquired a lock on the other mutex, then this lock is released automatically.

listing A: Locking two mutexes with lock() in a comparison operator

class some_big_object;
bool operator<(some_big_object& lhs,some_big_object& rhs);

class X
{
private:
   some_big_object some_detail;
   mutable std::mutex m;
public:
   X(some_big_object const& sd):some_detail(sd){}

   friend bool operator<(X const& lhs, X const& rhs)
   {
      if(&lhs==&rhs)
         return false;
      std::lock(lhs.m,rhs.m);                                    #1
      std::lock_guard<std::mutex> lock_a(lhs.m,std::adopt_lock); #2
      std::lock_guard<std::mutex> lock_b(rhs.m,std::adopt_lock); #3
      return lhs.some_detail<rhs.some_detail;
   }
};

Cueballs in code and preceding text

Though std::lock can help us avoid deadlock in those cases where we need to acquire two or more locks together, it doesn’t help if they are acquired separately—in that case we have to rely on our discipline as developers to ensure we don’t get deadlock. This isn’t easy: deadlocks are one of the nastiest problems to encounter in multi-threaded code, and are often unpredictable, with everything working fine the majority of the time. There are, however, some relatively simple rules, which can help us to write deadlock-free code.

Further Guidelines for Avoiding Deadlock

Deadlock doesn’t just occur with locks, though that is the most frequent cause: you can create deadlock with two threads and no locks just by having each thread call join() on the std::thread object for the other. In this case, neither thread can make progress because it is waiting for the other to finish, just like the children fighting over their toys. This simple cycle can occur anywhere that a thread can wait for another thread to perform some action if the other thread can simultaneously be waiting for the first thread, and isn’t limited to two threads: a cycle of three or more threads will still cause deadlock. The guidelines for avoiding deadlock essentially all boil down to one idea: don’t wait for another thread if there’s a chance it’s waiting for you. The individual guidelines provide ways of identifying and eliminating the possibility that the other thread is waiting for you.

AVOID NESTED LOCKS

The first idea is the simplest: don’t acquire a lock if you already hold one. If you stick to this guideline completely, it’s impossible to get a deadlock from the lock usage alone as each thread only ever holds a single lock. You could still get deadlock from other things (like the threads waiting for each other), but mutex locks are probably the most common cause of deadlock. If you need to acquire multiple locks, do it as a single action with std::lock in order to acquire them without deadlock.

AVOID CALLING USER-SUPPLIED CODE WHILST HOLDING A LOCK

This is actually a very simple follow on from the previous guideline. Since it is user-supplied, you have no idea what that code could do: it could do anything, including acquiring a lock. If you call user-supplied code whilst holding a lock, and that code acquires a lock, then you’ve violated the guideline on avoiding nested locks, and could get deadlock. Sometimes this is unavoidable: if you’re writing generic code such as the stack in section 4.2.3, then every operation on the parameter type or types is user-supplied code. In this case, you need a new guideline.

ACQUIRE LOCKS IN A FIXED ORDER

If you absolutely must acquire two or more locks, and you cannot acquire them as a single operation with std::lock, then the next best thing is to acquire them in the same order in every thread. We touched on this in section 4.2.4 as one way of avoiding deadlock when acquiring two mutexes: the key is to define the order in a way that is consistent between threads. In some cases this is relatively easy. For example, if we look at the stack from section 4.2.3, the mutex is internal to each stack instance, but the operations on the data items stored in stack requires calling user-supplied code. However, we can just add the constraint that none of the operations on the data items stored in the stack should perform any operation on the stack itself. This puts the burden on the user of the stack, but its rather uncommon for the data stored in a container to access that container, and its quite apparent when this is happening, so it’s not a particularly difficult burden to carry.

In other cases, this is not so straightforward, as we discovered with the comparison operator in section 4.2.4. At least in that case we could lock the mutexes simultaneously, but that’s not always possible. If we look back at the linked list example from section 4.1, then one possibility for protecting the list is to have a mutex per node. Then, in order to access the list threads must acquire a lock on every node they are interested in. For a thread to delete an item it must then acquire the lock on three nodes: the node being deleted, and the nodes either side, since they are all being modified in some way. Likewise, to traverse the list a thread must keep hold of the lock on the current node whilst it acquires the lock on the next one in the sequence, in order to ensure that the next pointer is not modified in the mean time. Once the lock on the next node has been acquired, the lock on the first can be released as it is no longer necessary.

This “hand over hand” locking style allows multiple threads to access the list, provided each is accessing a different node. However, in order to prevent deadlock the nodes must always be locked in the same order: if two threads tried to traverse the list in reverse order using hand-over-hand locking, then they could deadlock with each other in the middle of the list. If nodes A and B are adjacent in the list, then the thread going one way will try be holding the lock on node A and try and acquire the lock on node B. A thread going the other way would be holding the lock on node B, and trying to acquire the lock on node A: a classic scenario for deadlock.

Likewise, when deleting a node B that lies between nodes A and C, if that thread acquires the lock on B before the locks on A and C then it has the potential to deadlock with a thread traversing the list. Such a thread would either try and lock A or C first (depending on the direction of traversal), but would then find that it couldn’t obtain a lock on B because the thread doing the deleting was holding the lock on B and trying to acquire the locks on A and C.

One way to prevent deadlock here is to define an order of traversal, so a thread must always lock A before B, and B before C. This would eliminate the possibility of deadlock, at the expense of disallowing reverse traversal. Similar conventions can often be established for other data structures.

USE A LOCK HIERARCHY

Though this is really a particular case of defining a lock ordering, a lock hierarchy can provide a means of checking that the convention is adhered to at run time. The idea is basically that you divide your application into layers, and identify all the mutexes that may be locked in any given layer. When code tries to lock a mutex then it is not permitted to lock that mutex if it already holds a lock from a lower layer. This can be checked at runtime by assigning layer numbers to each mutex and keeping a record of which mutexes are locked by each thread.

Though detection is a run-time check, it is at least not timing dependent—you don’t have to wait around for the rare conditions that cause deadlock to show up. Also, the design process required to divide up the application and mutexes in this way can help eliminate many possible causes of deadlock before they even get written. It might be worth performing the design exercise even if you then don’t go as far as actually writing the run-time checks.

EXTENDING THESE GUIDELINES BEYOND LOCKS

As I mentioned back at the beginning of this section, deadlock doesn’t just occur with locks: it can occur with any synchronization construct that can lead to a wait cycle. It is therefore worth extending these guidelines to cover those cases too. For example, just like acquiring nested locks should be avoided if possible, it is a bad idea to wait for a thread whilst holding a lock, since that thread might need to acquire the lock in order to proceed. Similarly, if you’re going to wait for a thread to finish it might be worth identifying a thread hierarchy, such that a thread only waits for threads lower down the hierarchy. One simple way to do this is to ensure that your threads are joined in the same function that started them, as described in sections 3.1.2 and 3.3.

Once you’ve designed your code to avoid deadlock, std::lock() and std::lock_guard cover most of the cases of simple locking, but sometimes more flexibility is required. For those cases, the Standard Library provides the std::unique_lock template. Like std::lock_ guard, this is a class template parameterized on the mutex type, and it also provides the same RAII-style lock management as std::lock_ guard, but with a bit more flexibility.


This article is based on C++ ISBN: 1933988770), to be published April, 2009. It is being reproduced here by permission from Manning Publications. Manning early access books and ebooks are sold exclusively through Manning. Visit the book’s page for more information.

More by Author

Get the Free Newsletter!

Subscribe to Developer Insider for top news, trends & analysis

Must Read