Would you explain lock ordering?

Question

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?

Solution 1

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)

Solution 2

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.

Solution 3

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();

Solution 4

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.

Solution 5

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

View more solutions

Comments

[starikoff]

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).

[Wampie Driessen]

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

[Warren Dew]

Not only is this the right answer, it points out that all the answers claiming that unlock order is irrelevant to deadlock are wrong.

[hansvb]

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."

[hansvb]

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." yarchive.net/comp/linux/lock_ordering.html

[Adrian McCarthy]

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.

[corporateAbaper]

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 ).

[Adrian McCarthy]

@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.

[corporateAbaper]

@AdrianMcCarthy Exactly. The majority of the lock implementations are non-recursive. Don't assume that they are without explicitly referring that assumption.

[Adrian McCarthy]

@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.

[benathon]

Is it possible get reverse unlock order with scope based locks?

[Adrian McCarthy]

@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.

[Vishal Sahu]

Torvalds was brutal and harsh in his comment here at yarchive.net/comp/linux/lock_ordering.html

[Adrian McCarthy]

@VishalSahu: That quote was already brought up and I addressed it higher up in the thread.