Use lock addresses to enforce uniform locking order. Avoid deadlock(git.kernel.org)
git.kernel.org
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
6 comments
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...
Is it? Isn't the bakery algorithm a demonstration of how to build a lock, not how to coordinate multiple locks?
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.
This is an old idea. Not sure why people are trying to give credit here where none is due.
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!
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.
[deleted]
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.
Interesting. Attempting to load this page deadlocks Safari on iOS 7.1.2 on my iPad Air.
Any explanation?
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.
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.
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).
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).
The idea that Mutex<T> owns T and provides access to T only when locked is a really nice design, but...
Does it solve the case here? The two locks ordered by the address check are otherwise unordered, i.e., one is not inherently owned by the other. One could imagine the same data structure in a Rust program: a vector of runqueues, all on equal footing, and the programmer wants to lock an arbitrary pair (i, j) of them. This would have to look something like:
Does it solve the case here? The two locks ordered by the address check are otherwise unordered, i.e., one is not inherently owned by the other. One could imagine the same data structure in a Rust program: a vector of runqueues, all on equal footing, and the programmer wants to lock an arbitrary pair (i, j) of them. This would have to look something like:
{
let mut guard1 = locks[i].lock().unwrap();
let mut guard2 = locks[j].lock().unwrap();
do_work(*guard1, *guard2);
}
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.
Absolutely brilliant! Hats-off to the author of this snippet.
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.
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.
"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.
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.
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.
Therefore, for large scale systems, locks are an anti-pattern.
This solution is brilliant. No interface is exposed. The observation is that locks themselves have addresses, and these addresses have an order. That gives the order that locking is to be done in to ensure no deadlocking.
Indeed, this extends quite naturally to locks that are not related from modules that are not aware of each other.
I repeat, just brilliant.
Indeed, this extends quite naturally to locks that are not related from modules that are not aware of each other.
I repeat, just brilliant.
Sorry, but this is a too simplistic view of the problem. In reality, libraries perform locks, then invoke callback functions, which might perform other locks. Hence, you cannot always control the order of the locking without refactoring your code and messing up modularity.
Which is why the maxim "don't hold locks while calling untrusted code" exists. Holding a lock while invoking a callback is extremely dangerous. Some situations demnd doing this (but not that often), in which case you need to document it like crazy.
If you are always going to grab locks in the same order, doesn't that mean you only need one lock?
Different places in the code may take a different set of locks. Its about granularity, letting different threads continue while different locks are held.
It works as long as you know which locks you need in advance. You'll get much better concurrency than with the one-lock model when there's a low probability that two processes need any of the same locks (e.g. locking a whole table vs. locking individual records).
It fails you if you have a monadic rather than applicative requirement on the computation; that is, if intermediate computations can require you to take more locks that you couldn't have predicted needing in advance. In that case, you're going to need a transactional-memory system that can abort and retry computations, and that is powerful but hard to get right.
It fails you if you have a monadic rather than applicative requirement on the computation; that is, if intermediate computations can require you to take more locks that you couldn't have predicted needing in advance. In that case, you're going to need a transactional-memory system that can abort and retry computations, and that is powerful but hard to get right.