Hacker News Reader

Comment by sz4kerto | Hacker News Reader

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.

View on HN

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

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.

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.

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.

Reply on news.ycombinator.com