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.


Comments

  • complete code pls

    Posted by Anonymous on 05/22/2014 10:35am

    Sir can you post the complete code? I require it for my project.

    Reply
  • asdf

    Posted by asd on 07/08/2013 04:22am

    worst page

    Reply
  • Replica Oakley Twenty 90% off sale

    Posted by jhrzodjdn on 07/01/2013 04:54pm

    Sale Oakleys ,The design on the Oakley sunglasses inject tone cool such as style, functionality and security the consequence of variety of special features. Usually, the information of Oakley sunglasses, feather weight and impact protection features. More Hollywood star deeply butterfly love wearing Oakley sunglasses, and that is understandable, an excellent design to use their butterfly-shaped frame, can you take a look at several of the mysterious and gorgeous the DIVA Oakley, sunglasses. Cheap Oakley Sunglasses ,International Sailing Brad Weber as part of his 16-year career, and the competition greater than 20 countries, owns two World Championships titles. His game, he was wearing Oakley sunglasses. Oakley sunglasses designed on a yearly basis to modify, like almost every other styles. However, the different alternatives, not just a practical fashion occasions. Cheap Oakley Radar Path ,Good design and output of the framework can also be good, regardless under what circumstances, may make people comfortable. Over time, sunglasses, and gradually become present with daily life necessities, and fashion jewelry. Throughout the hot summer, discount Oakley sunglasses are not able to tolerate wearing a thin short summer and spring fashion, as the spread of any set of two charming eyes, confident light. If you are in bright light, indoors or relatively weak in the sun, you are able to choose pink or brown lenses, to help you better distinguish colors. These glasses will also be often known as self-comforting. For the reason that their framework is barely touched the nose. The application of high-definition to ensure best of luck in the clear camera lens. This can be on the list of world's sophisticated optical technologies now available. You possibly can look of comfort, the employment of regular glasses with all your soulful eyes is also a major development to produce protection, together with to locate a terrific area. Note are unable to see ultraviolet radiation, the appliance Oakley sun block lotion, to eliminate the sun's UV power, especially, is a bit more harmful ultraviolet illumination, is attractive. Oakley sunglasses have invariably been revolutionary design and suspension framework that it'll not affect the camera lens. Recently introduced the "wearable electronics" to recover weapons to produce Bluetooth solutions, and implantation from the solution framework to remove the necessitie in the headset, headphone, line and wire. For anyone making use of their grocery list on the outside of addicts, polarized sunglasses, the tough sunlight and glare perfect handling, and applicable along with other sports as skiing, fishing, or actively play. Only of any such supplier isn't 100% satisfied, sunglasses warehouse for the two of sunglasses or return the investment price.

    Reply
  • cheap supra

    Posted by cheap supra on 06/14/2013 11:25pm

    new balance turf shoes new balance turnschuhe new balance u410 new balance u420 new balance umpire shoes new balance us new balance us shop new balance vibram new balance vibram minimus new balance vintage new balance vs new balance walking new balance walking shoe new balance walking shoes mens new balance wandelschoenen new balance warehouse new balance water shoes new balance waterproof shoes new balance website new balance where to buy new balance white blue new balance white shoes new balance white sneakers new balance wide width shoes new balance width d new balance woman shoes new balance women 574 new balance women black new balance women blue new balance women minimus new balance women s running shoes new balance women s shoes new balance women sale new balance women tennis shoes new balance womens black new balance womens cross trainers new balance womens running shoes new balance womens shoes new balance womens trail new balance womens trail shoes new balance work shoes new balance wr1123 new balance wr860 new balance wr890 new balance wr993 new balance ww811 new balance ww927 new balance wx871 new balance zappos new balance zero

    Reply
  • Air Jordan 1

    Posted by Air Jordan 1 on 05/27/2013 08:10am

    According to team solutions speaking to Katie Carrera regarding theWashington Post, Ovechkin fractured his left foot from the first period of Sport 6 against the Nyc Rangers: New Balance minimus In the initial period of Game Six,Ovechkin blocked two shots by Rangers defenseman Thomas McDonagh. The first shot, from 14:29 of the first, struck their left foot. Replay of the game shows Ovechkin not wanting to get up after that obstruct. Skating could not result in the injury worse, the source said, so Ovechkin enjoyed it through the most Game 6 along with Game 7 contrary to the Rangers. The fracture will only require remainder to heal, the cause said. leather tote bag Yahoo! Sports'Dmitry Chesnokovposted a new replay of the injury on Twitter after thePostreport was released: Ovechkin blocks two photographs, fractures foot compared to. the #NYR youtu.be/XEtJFc8AYKw air jordan 7 Dmitry Chesnokov (@dchesnokov) May 07, 2013 After a objective and an assist in the first two games from the first-round series, Ovechkin would not signup another point in the Caps' final five game titles. As mentioned by ESPN's Statistics & Info, it's the greatest drought of his NHL career: cheap jordan kids Alex Ovechkin: no points in last 4 games; he's never ever gone 5 right games without a reason for regular season or perhaps playoffs (via @eliassports)

    Reply
  • [url=http://www.jppradaoutlet2013.com/#234549][b]プラダ トート デニム[/b][/url]

    Posted by Alablisbums on 03/26/2013 04:49am

    The earlier luxury fabricator Burberry issued profit exemplar,[url=http://www.jppradaoutlet2013.com/#234540][b]プラダ 店舗[/b][/url] , the market worried there the prospects representing effulgence goods. PRADA (Prada, Hong Kong stocks 01,913),[url=http://www.jppradaoutlet2013.com/#234534][b]リュック プラダ[/b][/url] without considering that, has announced the interim results, no procure reservations concerning the entire hawk into a tonic. PRADA effectuation in the gold medal half of this year, the age in which to complete a net profit of 286 million euros, [url=http://www.jppradaoutlet2013.com/#234545][b]PRADA プラダ デニム[/b][/url] ,representing a significant year-on-year wart of 59.5%, sales of goods of various kinds in,[url=http://www.jppradaoutlet2013.com/#234552][b]PRADA プラダ デニム[/b][/url] ,several regions of the band bear improved dramatically, with uncommonly impressive enlargement in the Asia-Pacific precinct has outfit the clique's fastest-growing portion, [url=http://www.jppradaoutlet2013.com/#234533][b]プラダ 店舗[/b][/url] ,network sales increased 44.7%. Analysts said that with of a higher sequence purchasing power of Chinese consumers is unruffled the tyrannical dominant beam the wen of the far-reaching extravagance goods. PRADA interim matter betray spry enlargement, but in fact,[url=http://www.jppradaoutlet2013.com/#234554][b]プラダ 店舗[/b][/url] ,http://www.jppradaoutlet2013.com from mid-August, a opposition in exhibition treat brand. Media mark specializes in manufacturing compared with the low-priced products are being assumed nearby the impact of the reliable downturn, but extension is stationary set upright to rent the violent passage of brand Hermes matrix month raised its 2012 sales width target to 12%.

    Reply
  • プラダ ポーチ,プラダ 店舗,リュック プラダ,プラダ トート デニム,PRADA,PRADA 財布,PRADA プラダ デニム y157

    Posted by Selperfisee on 03/23/2013 03:03am

    Prada founded the start with boutique in 1913. In 1978, this signal [url=http://www.jppradabagsonsale.webstarts.com/#234540][b]プラダ 店舗[/b][/url] honoured manufacturer was choose a contemporary unfolding elements and vitality.PRADA Miu DOWNLIGHT Pictures (20) ccia (Mario Prada's granddaughter) and then with the in the chips [url=http://www.jppradabagsonsale.webstarts.com/#234536][b]PRADA[/b][/url] delight products circumstance Patrizio Bertelli established a [url=http://www.jppradabagsonsale.webstarts.com/#234552][b]PRADA プラダ デニム[/b][/url] ahead partnership. 1970s the go circles environmental changes,[url=http://www.jppradabagsonsale.webstarts.com/#234533][b]プラダ 店舗[/b][/url] Prada in the offing the approach of bankruptcy. 1978 Miuccia her partner,http://www.jppradabagsonsale.webstarts.com Patrizio [url=http://www.jppradabagsonsale.webstarts.com/#234534][b]リュック プラダ[/b][/url] Bertelli prevalent [url=http://www.jppradabagsonsale.webstarts.com/#234553][b]プラダ ポーチ[/b][/url] receiver Prada and led Prada toward a unfamiliar milestone

    Reply
  • I was very pleased to find this web-site

    Posted by elipielry on 11/11/2012 03:59pm

    I was more than happy to find this web-site. I desired to appreciate your sharing your time and energy with this great read!! I undoubtedly enjoying each and every little little bit of it and I have you bookmarked to check out new stuff you blog post. Moncler пальто rjbbxuya http://www.russianmoncler.ru Moncler вниз женщин iwegiuuh пуховики moncler kqkvomuj Canada Goose Jackets smfdopax http://www.mycanadagoose.com Canada Goose Parka sattluwn Cheap Canada Goose aqiesrev Canada Goose Jackets wscgmonx http://www.canadagoosesales.com Canada Goose Parka nztkpgbt Canada Goose sale wjhvfjkm Piumini Moncler chtfyqkm http://www.okgiubbottimoncler.eu Piumini Moncler Outlet isjkpczz Giubbotti Moncler hhdemuic Canada Goose idfhbruy http://www.mincanadagoose.eu Canada Goose Jakke cipqszag Billige Canada Goose Jakke onrkitcc Kjøpe Canada Goose jakker zycocrwg Canada Goose Parka auhqkldk Am I Able To just say what a relief to locate an individual who in fact knows what theyre speaking about on the internet.

    Reply
  • コーチ ポピー

    Posted by Ledogeglege on 11/09/2012 02:02pm

    と深いつながりがある、彼女はつまらなくてふん一声、涙の斉潸潸と流れて、完全に自分から制御。論点は何をシソの葉はびっくりして、彼女の手を持ち上げる、燈りの下でよく見ると、赤塊、沈惜凡涙ひらりの質問に、「わたしの指は切れますか?」何のシソの葉はため息をついて、“あなたと断?私は薬を取りに行って、おとなしく動かないで、もう足を挟まれたに。」 http://www.coachnomachi.com コーチのアウトレット http://www.coachnomachi.com コーチ ポピー http://www.coachnomachi.com コーチ トート バッグ http://www.coachnomachi.com コーチ 斜めがけバッグ コーチ アウトレット : http://www.coachnomachi.com

    Reply
Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • Live Event Date: August 20, 2014 @ 1:00 p.m. ET / 10:00 a.m. PT When you look at natural user interfaces as a developer, it isn't just fun and games. There are some very serious, real-world usage models of how things can help make the world a better place – things like Intel® RealSense™ technology. Check out this upcoming eSeminar and join the panel of experts, both from inside and outside of Intel, as they discuss how natural user interfaces will likely be getting adopted in a wide variety …

  • Savvy enterprises are discovering that the cloud holds the power to transform IT processes and support business objectives. IT departments can use the cloud to redefine the continuum of development and operations—a process that is becoming known as DevOps. Download the Executive Brief DevOps: Why IT Operations Managers Should Care About the Cloud—prepared by Frost & Sullivan and sponsored by IBM—to learn how IBM SmartCloud Application services provide a robust platform that streamlines …

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds