39

I learned that I should unlock reverse order to lock order. For example.

A.lock();
B.lock();
B.unlock();
A.unlock();

But, what happen if I did like this :

A.lock();
B.lock();
A.unlock();
B.unlock();

I try to make a deadlock scenario, but if I always lock A earlier then B, then I don't know how deadlock would happen. Would you help me?

Petr
  • 62,528
  • 13
  • 153
  • 317
P-P
  • 1,670
  • 5
  • 18
  • 35

7 Answers7

66

In the simple case given, unlocking in the reverse order is not necessary to avoid a deadlock.

However, as the code gets more complicated, unlocking in the reverse order helps you maintain proper lock ordering.

Consider:

A.lock();
B.lock();
Foo();
A.unlock();
Bar();
B.unlock();

If Bar() attempts to reacquire A, you've effectively broken your lock ordering. You're holding B and then trying to get A. Now it can deadlock.

If you unlock in the reverse order style (which is very natural if you use RAII):

A.lock();
B.lock();
Foo();
B.unlock();
Bar();
A.unlock();

then it doesn't matter if Bar() attempts to take a lock, as lock ordering will be preserved.

Adrian McCarthy
  • 45,555
  • 16
  • 123
  • 175
  • 1
    This is _the_ right answer IMO: if you accept the rule of taking locks in the same order throughout your system on different levels (inside functions etc.) and don't release in the reverse order then scenario from Adrian's answer leads to a deadlock possibility. I wish this "**can deadlock**" was a bit more visible being below the "good style" argument (which I fully agree with as well). – starikoff Dec 22 '15 at 10:50
  • 1
    Not only is this the right answer, it points out that all the answers claiming that unlock order is irrelevant to deadlock are wrong. – Warren Dew May 27 '16 at 03:34
  • 1
    Well, that problem only occurs if you re-acquire locks that you have previously released (without first also releasing the "later" locks). My supposedly wrong answer defines lock ordering as "obtaining locks in a fixed order and not obtaining locks again after you start unlocking." – Thilo May 27 '16 at 07:13
  • 2
    To quote the always eloquent Linus Torvalds on the matter: "The FACT is, that unlocks do not have to nest cleanly. That's a rock solid *FACT*. The locking order matters, and the unlocking order does not. And if you cannot accept that as a fact, and you then say "unlock order should matter just to keep things nice and clean", then you end up being screwed and/or confused when you can't hold to the unlock order. There are many perfectly valid reasons not to unlock in reverse order." http://yarchive.net/comp/linux/lock_ordering.html – Thilo May 27 '16 at 07:16
  • 3
    I did not claim anyone else's answer was wrong, nor did I say that you must unlock in the reverse order. I pointed out that unlocking in the reverse order makes it easier to ensure that the lock order is always maintained, even as your code evolves. – Adrian McCarthy Jun 03 '16 at 17:20
  • 1
    I don't think it is a good example the second case, as you say "it doesn't matter if Bar() attempts to lock A again, as lock ordering will be preserved", but if you try to lock A inside a scope with A already locked, that will hang. The remaining of the answer is good (i.e., first case) and the comment regarding its deadlock is very relevant. I would suggest editing this answer in the second case and replacing the code by an example of a code that does deadlock and is in reverse order to show that that is not the relevant point here (perhaps equal to the one given by @don-neufeld ). – corporateAbaper Jul 03 '16 at 00:00
  • @DavidNogueira: Locking A when you already have A locked will hang only if you have non-recursive locks. Aside from that, I don't understand what you're trying to say. – Adrian McCarthy Jul 06 '16 at 18:25
  • @AdrianMcCarthy Exactly. The majority of the lock implementations are non-recursive. Don't assume that they are without explicitly referring that assumption. – corporateAbaper Jul 06 '16 at 22:08
  • @David Norgueira: Citation needed. I'm happy with my answer as is. Feel free to add your own if you want to draw the recursive/non-recursive distinction. – Adrian McCarthy Jul 06 '16 at 22:34
  • Is it possible get reverse unlock order with scope based locks? – benathon Sep 24 '18 at 03:45
  • @portforwardpodcast: Yes, scope-based locks naturally lend themselves to reverse unlock order. That's what I was trying to allude to with my comment about using RAII. – Adrian McCarthy Nov 19 '18 at 22:00
  • Torvalds was brutal and harsh in his comment here at https://yarchive.net/comp/linux/lock_ordering.html – Vishal Sahu Feb 18 '19 at 20:51
  • @VishalSahu: That quote was already brought up and I addressed it higher up in the thread. – Adrian McCarthy Feb 18 '19 at 23:37
31

Lock ordering just means that you prevent deadlocks by obtaining locks in a fixed order, and do not obtain locks again after you start unlocking.

I do not think the order of unlocks makes any difference here (in fact, it should be beneficial to release a lock as soon as possible, even if out of order)

Thilo
  • 257,207
  • 101
  • 511
  • 656
12

Your example isn't going to deadlock with itself ever. Unlocking in reverse order isn't important, it's locking in a consistent order. This will dead lock, even though unlocks are in reverse order

Thread 1

A.lock();
B.lock();
B.unlock();
A.unlock();

Thread 2

B.lock();
A.lock();
A.unlock();
B.unlock();
Don Neufeld
  • 22,720
  • 11
  • 51
  • 50
2

I do not think deadlock would happen here. The general deadlock concept is one thread waits for some resource locked by other thread, while other thread needs resource locked by first thread to finish and release resource needed by first.

Further reading

ironic
  • 8,368
  • 7
  • 35
  • 44
2

The order of unlock will not affect how prone your system is to deadlock, however there's one reasons to think about the order of unlock:

In order to avoid deadlocks you must make sure that your lock/unlocks are paired, in that you never miss an unlock. As a stylistic approach, by conspicuosly having blocks of code that are responsible for a particualr lock it's much easier to visually identifiy that locks and unlocks are paired. The end-effect is that clearly correct code will probably take and release the locks as you describe.

djna
  • 54,992
  • 14
  • 74
  • 117
0

And for Java, unlocking is in the reverse order if synchronized keyword is used for locking. There is no way to unlock in a different order for using synchronized keyword. 

synchronized(a) {
  synchronized(b) {
    // statements
  }
}
Jingguo Yao
  • 7,320
  • 6
  • 50
  • 63
  • 3
    I want to express that I do not agree witht the downvotes on this answer. Altough it is not the most elaborate one on this question, it does show another perspective, perhaps helping in understanding the matter – Wampie Driessen Jan 07 '16 at 10:00
0
      > lock(B)                                                                                                                                                                                                 
      >  ----------    lock(C)
      >  ----------    lock(B)    >>>> would block here 
      >  ----------    release(B)
      >  ----------    release(C)
      > lock(C)       >>>>>> would block here 
      > release(B)
      > release(C)

Their answer is great, here is another situation a deadlock may occur if unordered lock & release is performed. One word, Unordered release & lock break the assumption which we used to design our shared resource management and critical zone.

Frank Wang
  • 788
  • 7
  • 23