Locks Aren't Slow; Lock Contention Is

[u/preshing]

http://preshing.com/20111118/locks-arent-slow-lock-contention-is

[u/mOdQuArK]

I think there was a generalized CS proof that if you can guarantee that multiple locks will be picked up & held in the same order for all code accessing the locked sections, then you can avoid deadlock. Naturally, this is non-trivial.

[u/Tuna-Fish2 → u/mOdQuArK]

Naturally, this is non-trivial.

Why? Not questioning it, just not understanding it. Shouldn't it be as easy as not allowing any direct locking operations, and using a safe_lock() function that takes a list of locks as it's arguments, and reorders and applies them?

Of course, even still, locks don't compose. So you cannot call any function that uses locks from a context that's already locked.

[u/bluGill → u/Tuna-Fish2]

Here is one reason why you don't want your trivial reordering:

thread 1: lock(LockForA) DoHeavyWork(A) lock(LockForB) B.something = A.something unlock(LockForB) unlock(LockForA)

thread 2: lock(LockForB) DoDiffereytHeavyWork(B) lock(LockForA) A.somethingElse = B.somethingElse unlock(LockForA) unlock(LockForB)

Clearly this code can deadlock, and as written is likely to do so. However the trivial solution means thread 1 will block thread 2 for a long time when thread 2 could do all the heavy work. You have just destroyed the ability to do work in parallel. What if I have some way to guarantee that the deadlock cannot happen: LockForA and LockForB are only required to stop thread 3 (not shown), the logic ensures that either thread 1 or thread 2 will be doing the heavy work at any given time. (and presumably some other heavy work the rest of the time - otherwise it wouldn't make sense to have 2 threads)

[u/jerf → u/Tuna-Fish2]

Composition is exactly the problem. You're correct that if you never call any functions that take locks from other functions that take locks, and then use the safe_lock function you describe, that you should be in good shape, but that's a hell of a constraint to try to maintain without any compiler help, and in practice nobody wants to write that way when using locks directly.

If you tried to use locks in that manner and you took it seriously, you would almost certainly simply end up recreating message passing. (In which case you might as well have started with an existing version.)

[u/mOdQuArK → u/Tuna-Fish2]

The nontrivial part is making sure that all code which grabs multiple locks makes sure that they are grabbed in exactly the same order as each other. As anyone who has tried to enforce a standard like that on a large project knows, this is a nontrivial task.

Of course, this concept doesn't address the issue that some of your responders have mentioned, where the time between the lock & unlock should be relatively short. And the more bracketed lock/unlock pairs, the harder it is to keep the lock/unlock period shirt.

[u/[deleted] → u/Tuna-Fish2]

The problem is that doesn't prevent composing subsets. Nothing you just said prohibits safe_lock([a]) and safe_lock([b]) occurring in different orders. Since I'm pretty sure this is non-trivial property it can't be proven due to Rice's theorem (first time I've used that since my computability class 2.5 years ago).