Use lock addresses to enforce uniform locking order. Avoid deadlock

http://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/tree/kernel/sched.c?id=v3.2#n1811

by cvs268 • 11 years ago

31 22 11 years ago

git.kernel.org

jrerm• 11 years ago

Any explanation?

sz4kerto• 11 years ago

A very simple way of avoiding deadlock (circular dependencies) is to grab locks in a fixed order (if you want to get the N+1th lock then you have to acquire all of them from 1 to N. This way you avoid the situation where thread 1 has already acquired lock X, thread 2 has acquired Y, then thread 2 wants to acquire X and thread 1 wants Y.

The problem is that this strategy is only applicable in a very-very limited context, in most cases it's useless because the number of lockable resources changes dynamically and/or it's not feasible/scalable to get all locks up to N+1.

amelius2• 11 years ago

Also, this solution is anti-modular in the sense that it becomes near-infeasible if different parts of the code that may contain locking directives are in different modules, and solving this may mean exposing an interface that becomes increasingly more complicated with increasing number of locks.

Therefore, for large scale systems, locks are an anti-pattern.

jeremyjh• 11 years ago

If you are always going to grab locks in the same order, doesn't that mean you only need one lock?

Someone• 11 years ago

"if you want to get the N+1th lock then you have to acquire all of them from 1 to N."

It's not that limited. Rule is that, if you want to acquire locks N and M > N, you have to do it in the order N,M. That is sufficient to guarantee that the thread holding the highest numbered lock can make progress.

Main limitation, AFAIK, is that you do not always know which locks you need. Does your concurrent hash map use a lock? Can you tell whether library call X uses one? Which one? It a.so can degrade performance a bit. For example, your memory allocator may occasionally use a lock, but most of the time, it will give you memory out of a thread-local pool.

userbinator• 11 years ago

It is forcing locks to be acquired in an order to prevent deadlock. That is a well-known technique, but using their addresses is the interesting part here: it automatically provides a global ordering without needing to actually define one.

This is one of those things that seems baffling at first, but then once you see the rationale it's "why didn't I think of that!?" obvious. I'm guessing the one who submitted this experienced such a moment.

masklinn• 11 years ago

Rust has an interesting take on that: the lock simply owns whatever data is locked, and only releases it on locking. Lock ordering becomes a property of which lock owns the other one.

Ownership semantics make it safer (can't leak the internal object), but considering how unsafe and dependent on proper usage locks tend to be, I wonder why I've never seen that idea in e.g. Python or Ruby, it would make the right thing easier to do either way, even if there would remain a possibility of leaking the internal object (and even then, I CPython might be able to check the lockee's refcount on lock/unlock, possibly optionally).

cvs268• 11 years ago

OP here. Yes, it was a huge "aha moment" for me when i saw the implementation of this function and how simple it was.

Absolutely brilliant! Hats-off to the author of this snippet.

csdude1• 11 years ago

This is an old idea. Not sure why people are trying to give credit here where none is due.

sesquipedalian• 11 years ago

This is one of those things that seems obvious in hindsight. However, it never occurred to me that one could simply use the lock address to impose a consistent and unique ordering on the locks rather than some other explicit mechanism. It's a rather clever solution, the pointer is the sequence number!

Sharlin• 11 years ago

Interestingly, in C and C++ the ordering of two pointers not pointing to the same array is not well-defined because the address space may not be flat. In C++ the standard function object std::less is specifically guaranteed to impose a total order on pointers even thought the builtin less-than operator does not.

ajarmst2• 11 years ago

Lamport's Bakery Algorithm from the 1970's seems relevant, as is his frustration that people seem to keep rediscovering a solution to an already solved problem: http://research.microsoft.com/en-us/um/people/lamport/pubs/l...

lukesandberg2• 11 years ago

Is it? Isn't the bakery algorithm a demonstration of how to build a lock, not how to coordinate multiple locks?

ajarmst2• 11 years ago

Well, I was thinking about it as a particularly good example of how common it is for exciting "new" solutions to general problems of multithreading turn out to be cases of a classic algorithm that has been well-studied.

Animats• 11 years ago

This goes way, way back, all the way to early IBM JCL forcing the acquisition of file locks in alphabetical order when starting a batch job.

dwarman• 11 years ago

Interesting. Attempting to load this page deadlocks Safari on iOS 7.1.2 on my iPad Air.

Use lock addresses to enforce uniform locking order. Avoid deadlock

Related Stories