Is std::lock() ill-defined, unimplementable, or useless?

Question

(Note: Much of this is redundant with commentary on Massive CPU load using std::lock (c++11), but I think this topic deserves its own question and answers.)

I recently encountered some sample C++11 code that looked something like this:

std::unique_lock<std::mutex> lock1(from_acct.mutex, std::defer_lock);
std::unique_lock<std::mutex> lock2(to_acct.mutex, std::defer_lock);
std::lock(lock1, lock2); // avoid deadlock
transfer_money(from_acct, to_acct, amount);

Wow, I thought, std::lock sounds interesting. I wonder what the standard says it does?

C++11 section 30.4.3 [thread.lock.algorithm], paragraphs (4) and (5):

template void lock(L1&, L2&, L3&...);

4 Requires: Each template parameter type shall meet the Lockable requirements, [ Note: The unique_lock class template meets these requirements when suitably instantiated. — end note ]

5 Effects: All arguments are locked via a sequence of calls to lock(), try_lock(), or unlock() on each argument. The sequence of calls shall not result in deadlock, but is otherwise unspecifed. [ Note: A deadlock avoidance algorithm such as try-and-back-off must be used, but the specifc algorithm is not specifed to avoid over-constraining implementations. — end note ] If a call to lock() or try_lock() throws an exception, unlock() shall be called for any argument that had been locked by a call to lock() or try_lock().

Consider the following example. Call it "Example 1":

Thread 1                    Thread 2
std::lock(lock1, lock2);    std::lock(lock2, lock1);

Can this deadlock?

A plain reading of the standard says "no". Great! Maybe the compiler can order my locks for me, which would be kind of neat.

Now try Example 2:

Thread 1                                  Thread 2
std::lock(lock1, lock2, lock3, lock4);    std::lock(lock3, lock4);
                                          std::lock(lock1, lock2);

Can this deadlock?

Here again, a plain reading of the standard says "no". Uh oh. The only way to do that is with some kind of back-off-and-retry loop. More on that below.

Finally, Example 3:

Thread 1                          Thread 2
std::lock(lock1,lock2);           std::lock(lock3,lock4);
std::lock(lock3,lock4);           std::lock(lock1,lock2);

Can this deadlock?

Once again, a plain reading of the standard says "no". (If the "sequence of calls to lock()" in one of these invocations is not "resulting in deadlock", what is, exactly?) However, I am pretty sure this is unimplementable, so I suppose it's not what they meant.

This appears to be one of the worst things I have ever seen in a C++ standard. I am guessing it started out as an interesting idea: Let the compiler assign a lock ordering. But once the committee chewed it up, the result is either unimplementable or requires a retry loop. And yes, that is a bad idea.

You can argue that "back off and retry" is sometimes useful. That is true, but only when you do not know which locks you are trying to grab up front. For example, if the identity of the second lock depends on data protected by the first (say because you are traversing some hierarchy), then you might have to do some grab-release-grab spinning. But in that case you cannot use this gadget, because you do not know all of the locks up front. On the other hand, if you do know which locks you want up front, then you (almost) always want simply to impose an ordering, not to loop.

Also, note that Example 1 can live-lock if the implementation simply grabs the locks in order, backs off, and retries.

In short, this gadget strikes me as useless at best. Just a bad idea all around.

OK, questions. (1) Are any of my claims or interpretations wrong? (2) If not, what the heck were they thinking? (3) Should we all agree that "best practice" is to avoid std::lock completely?

[Update]

Some answers say I am misinterpreting the standard, then go on to interpret it the same way I did, then confuse the specification with the implementation.

So, just to be clear:

In my reading of the standard, Example 1 and Example 2 cannot deadlock. Example 3 can, but only because avoiding deadlock in that case is unimplementable.

The entire point of my question is that avoiding deadlock for Example 2 requires a back-off-and-retry loop, and such loops are extremely poor practice. (Yes, some sort of static analysis on this trivial example could make that avoidable, but not in the general case.) Also note that GCC implements this thing as a busy loop.

[Update 2]

I think a lot of the disconnect here is a basic difference in philosophy.

There are two approaches to writing software, especially multi-threaded software.

In one approach, you throw a bunch of stuff together and run it to see how well it works. You are never convinced that your code has a problem unless someone can demonstrate that problem on a real system, right now, today.

In the other approach, you write code that can be rigorously analyzed to prove that it has no data races, that all of its loops terminate with probability 1, and so forth. You perform this analysis strictly within the machine model guaranteed by the language spec, not on any particular implementation.

Advocates of the latter approach are not impressed by any demonstrations on particular CPUs, compilers, compiler minor versions, operating systems, runtimes, etc. Such demonstrations are barely interesting and totally irrelevant. If your algorithm has a data race, it is broken, no matter what happens when you run it. If your algorithm has a livelock, it is broken, no matter what happens when you run it. And so forth.

In my world, the second approach is called "Engineering". I am not sure what the first approach is called.

As far as I can tell, the std::lock interface is useless for Engineering. I would love to be proven wrong.

Answer 1

I think you are misunderstanding the scope of the deadlock avoidance. That's understandable since the text seems to mention lock in two different contexts, the "multi-lock" std::lock and the individual locks carried out by that "multi-lock" (however the lockables implement it). The text for std::lock states:

All arguments are locked via a sequence of calls to lock(), try_lock(),or unlock() on each argument. The sequence of calls shall not result in deadlock

If you call std::lock passing ten different lockables, the standard guarantees no deadlock for that call. It's not guaranteed that deadlock is avoided if you lock the lockables outside the control of std::lock. That means thread 1 locking A then B can deadlock against thread 2 locking B then A. That was the case in your original third example, which had (pseudo-code):

Thread 1     Thread 2
lock A       lock B
lock B       lock A

As that couldn't have been std::lock (it only locked one resource), it must have been something like unique_lock.

The deadlock avoidance will occur if both threads attempt to lock A/B and B/A in a single call to std::lock, as per your first example. Your second example won't deadlock either since thread 1 will be backing off if the second lock is needed by a thread 2 already having the first lock. Your updated third example:

Thread 1                  Thread 2
std::lock(lock1,lock2);   std::lock(lock3,lock4);
std::lock(lock3,lock4);   std::lock(lock1,lock2);

still has the possibility of deadlock since the atomicity of the lock is a single call to std::lock. For example, if thread 1 successfully locks lock1 and lock2, then thread 2 successfully locks lock3 and lock4, deadlock will ensue as both threads attempt to lock the resource held by the other.

So, in answer to your specific questions:

1/ Yes, I think you've misunderstood what the standard is saying. The sequence it talks about is clearly the sequence of locks carried out on the individual lockables passed to a single std::lock.

2/ As to what they were thinking, it's sometimes hard to tell :-) But I would posit that they wanted to give us capabilities that we would otherwise have to write ourselves. Yes, back-off-and-retry may not be an ideal strategy but, if you need the deadlock avoidance functionality, you may have to pay the price. Better for the implementation to provide it rather than it having to be written over and over again by developers.

3/ No, there's no need to avoid it. I don't think I've ever found myself in a situation where simple manual ordering of locks wasn't possible but I don't discount the possibility. If you do find yourself in that situation, this can assist (so you don't have to code up your own deadlock avoidance stuff).

---

In regard to the comments that back-off-and-retry is a problematic strategy, yes, that's correct. But you may be missing the point that it may be necessary if, for example, you cannot enforce the ordering of the locks before-hand.

And it doesn't have to be as bad as you think. Because the locks can be done in any order by std::lock, there's nothing stopping the implementation from re-ordering after each backoff to bring the "failing" lockable to the front of the list. That would mean those that were locked would tend to gather at the front, so that the std::lock would be less likely to be claiming resources unnecessarily.

Consider the call std::lock (a, b, c, d, e, f) in which f was the only lockable that was already locked. In the first lock attempt, that call would lock a through e then "fail" on f.

Following the back-off (unlocking a through e), the list to lock would be changed to f, a, b, c, d, e so that subsequent iterations would be less likely to unnecessarily lock. That's not fool-proof since other resources may be locked or unlocked between iterations, but it tends towards success.

In fact, it may even order the list initially by checking the states of all lockables so that all those currently locked are up the front. That would start the "tending toward success" operation earlier in the process.

That's just one strategy, there may well be others, even better. That's why the standard didn't mandate how it was to be done, on the off-chance there may be some genius out there who comes up with a better way.

Answer 2

Perhaps it would help if you thought of each individual call to std::lock(x, y, ...) as atomic. It will block until it can lock all of its arguments. If you don't know all of the mutexes you need to lock a-priori, do not use this function. If you do know, then you can safely use this function, without having to order your locks.

But by all means order your locks if that is what you prefer to do.

Thread 1                    Thread 2
std::lock(lock1, lock2);    std::lock(lock2, lock1);

The above will not deadlock. One of the threads will get both locks, and the other thread will block until the first one has released the locks.

Thread 1                                  Thread 2
std::lock(lock1, lock2, lock3, lock4);    std::lock(lock3, lock4);
                                          std::lock(lock1, lock2);

The above will not deadlock. Though this is tricky. If Thread 2 gets lock3 and lock4 before Thread1 does, then Thread 1 will block until Thread 2 releases all 4 locks. If Thread 1 gets the four locks first, then Thread 2 will block at the point of locking lock3 and lock4 until Thread 1 releases all 4 locks.

Thread 1                          Thread 2
std::lock(lock1,lock2);           std::lock(lock3,lock4);
std::lock(lock3,lock4);           std::lock(lock1,lock2);

Yes, the above can deadlock. You can view the above as exactly equivalent to:

Thread 1                          Thread 2
lock12.lock();                    lock34.lock();
lock34.lock();                    lock12.lock();

Update

I believe a misunderstanding is that dead-lock and live-lock are both correctness issues.

In actual practice, dead-lock is a correctness issue, as it causes the process to freeze. And live-lock is a performance issue, as it causes the process to slow down, but it still completes its task correctly. The reason is that live-lock will not (in practice) sustain itself indefinitely.

<disclaimer> There are forms of live-lock that can be created which are permanent, and thus equivalent to dead-lock. This answer does not address such code, and such code is not relevant to this issue. </disclaimer>

The yield shown in this answer is a significant performance optimization which significantly decreases live-lock, and thus significantly increases the performance of std::lock(x, y, ...).

Update 2

After a long delay, I have written a first draft of a paper on this subject. The paper compares 4 different ways of getting this job done. It contains software you can copy and paste into your own code and test yourself:

http://howardhinnant.github.io/dining_philosophers.html

Answer 3

Your confusion with the standardese seems to be due to this statement

5 Effects: All arguments are locked via a sequence of calls to lock(), try_lock(), or unlock() on each argument.

That does not imply that std::lock will recursively call itself with each argument to the original call.

Objects that satisfy the Lockable concept (§30.2.5.4 [thread.req.lockable.req]) must implement all 3 of those member functions. std::lock will invoke these member functions on each argument, in an unspecified order, to attempt to acquire a lock on all objects, while doing something implementation defined to avoid deadlock.

Your example 3 has a potential for deadlock because you're not issuing a single call to std::lock with all objects that you want to acquire a lock on.

Example 2 will not cause a deadlock, Howard's answer explains why.

Answer 4

Did C++11 adopt this function from Boost?

If so, Boost's description is instructive (emphasis mine):

Effects: Locks the Lockable objects supplied as arguments in an unspecified and indeterminate order in a way that avoids deadlock. It is safe to call this function concurrently from multiple threads with the same mutexes (or other lockable objects) in different orders without risk of deadlock. If any of the lock() or try_lock() operations on the supplied Lockable objects throws an exception any locks acquired by the function will be released before the function exits.