Is the meaning of "lock-free" even defined by the C++ standard?

Question

I can't find a semantic difference between lock-based and lock-free atomics. So far as I can tell, the difference is semantically meaningless as far as the language is concerned, since the language doesn't provide any timing guarantees. The only guarantees I can find are memory ordering guarantees, which seem to be the same for both cases.

(How) can the lock-free-ness of atomics affect program semantics?

i.e., aside from calling is_lock_free or atomic_is_lock_free, is it possible to write a well-defined program whose behavior is actually affected by whether atomics are lock-free?
Do those functions even have a semantic meaning? Or are they just practical hacks for writing responsive programs even though the language never provides timing guarantees in the first place?

Giavani

As far as I understand it (disclaimer: I haven't done C++ for ages, but have looked at the documentation a bit out of curiosity), the difference is that a thread accessing a lock-free object will never be blocked, whereas a lock-based object may cause the thread to block if there are other threads accessing that object (basically, use of transactional memory or pure atomic operations, vs. use of mutexes or similar locking methods). Not posting as answer since I don't know if it really makes much of a difference in practice. – Acroter

@Jcl: But what does "blocked" mean though...? (I mean from a C++ standard standpoint. What does it mean for a call to block?) – Giavani

From a C++ standpoint, like most things, I guess (again, just guessing, I don't know, that's why I didn't write an answer), it should be implementation/target-platform dependant... but more likely a spinwait of some short (pause or rep nop in a checking loop for x86/x64 more likely) – Acroter

@Jcl: Yeah, I mean I certainly understand what "blocking" means on the typical implementation, but I don't understand what it means in the context of an abstract machine such as the one C++ is used to program for. It's a question about language semantics not a question about the implementation. – Giavani

Answer 1

In C++11 Standard, the term "lock-free" was not defined well as reported in issue LWG #2075.

C++14 Standard define what lock-free executions is in C++ language (N3927 approved).

Quote C++14 1.10[intro.multithread]/paragraph 4:

Executions of atomic functions that are either defined to be lock-free (29.7) or indicated as lock-free (29.4) are lock-free executions.

• If there is only one unblocked thread, a lock-free execution in that thread shall complete. [ Note: Concurrently executing threads may prevent progress of a lock-free execution. For example, this situation can occur with load-locked store-conditional implementations. This property is sometimes termed obstruction-free. -- end note ]
• When one or more lock-free executions run concurrently, at least one should complete. [ Note: It is difficult for some implementations to provide absolute guarantees to this effect, since repeated and particularly inopportune interference from other threads may prevent forward progress, e.g., by repeatedly stealing a cache line for unrelated purposes between load-locked and store-conditional instructions. Implementations should ensure that such effects cannot indefinitely delay progress under expected operating conditions, and that such anomalies can therefore safely be ignored by programmers. Outside this International Standard, this property is sometimes termed lock-free. -- end note ]

Above definition of "lock-free" depends on what does unblocked thread behave. C++ Standard does not define unblocked thread directly, but 17.3.3[defns.blocked] defines blocked thread:

a thread that is waiting for some condition (other than the availability of a processor) to be satisfied before it can continue execution

---

(How) can the lock-free-ness of atomics affect program semantics?

I think the answer is NO, except signal handler as paxdiablo's answer, when "program semantics" mean the side effects of atomic operations. The lock-free-ness of atomic affect the strength of progress guarantee for whole multithreading program. When two (or more) threads concurrently execute lock-free atomic operations on same object, at least one of these operations should complete under any worst thread scheduling. In other words, 'evil' thread scheduler could intentionally block progress of lock-based atomic operations in theory.

Infinitesimal

+1 Is the word "blocking" also defined? Because if not, then it's still not clear what this should mean. – Giavani

Please refer C++14 (also C++11) 17.3.2[defns.block] define block and 17.3.3[defns.blocked] define blocked thread. 17.3.3 says "a thread that is waiting for some condition (other than the availability of a processor) to be satisfied before it can continue execution." – Infinitesimal

Interesting... but is blocking then semantically any different from a generic function call? It seems to me that the difference isn't semantically meaningful from the point of the view of the program -- I don't see any way for a program to differentiate between a blocking function call versus a nonblocking function call. Am I missing something? – Giavani

Answer 2

There is at least one semantic difference.

As per C++11 1.9 Program execution /6:

When the processing of the abstract machine is interrupted by receipt of a signal, the values of objects which are neither of type volatile std::sig_atomic_t nor lock-free atomic objects are unspecified during the execution of the signal handler, and the value of any object not in either of these two categories that is modified by the handler becomes undefined.

In other words, it's safe to muck about with those two categories of variables but any access or modification to all other categories should be avoided.

Of course you could argue that it's no longer a well defined program if you invoke unspecified/undefined behaviour like that but I'm not entirely sure whether you meant that or well-formed (i.e., compilable).

But, even if you discount that semantic difference, a performance difference is worth having. If I had to have a value for communicating between threads, I'd probably choose, in order of preference:

• the smallest adequate data type that was lock-free.
• a larger data type than necessary, if it was lock-free and the smaller one wasn't.
• a shared region fully capable of race conditions, but in conjunction with an atomic_flag (guaranteed to be lock-free) to control access.

This behaviour could be selected at compile or run time based on the ATOMIC_x_LOCK_FREE macros so that, even though the program behaves the same regardless, the optimal method for that behaviour is chosen.

Lapierre

I never realized the C++ standard even talks about (C-style?) signals in the first place. Thanks, that's really interesting! +1 And btw, what I meant by 'well-defined' was indeed basically "not undefined", but I honestly wasn't thinking about this scenario -- I wasn't meaning to exclude this possibility, so you indeed answered the question I intended to ask. – Giavani

It doesn't sound too unlikely to have a lock-free int yet no smaller lock-free char. – Shaving

@MSalters, have removed that now. It was originally based on my understanding how it would most likely work under the covers and, while I was preparing to wax lyrical about it, I realised that the standard itself doesn't dictate how it works, only that it does work, something I've chastised people about here before :-) So, you're quite right, the likelihood is not really relevant here. – Lapierre

So the question this answer leaves me with is: does the only semantic difference occur when we have asynchronous signals? Or is there some other difference too? – Giavani

Answer 3

Paxdiablo has answered pretty well, but some background might help.

"Lock-free atomic" is a bit of redundant terminology. The point of atomic variables, as they were originally invented, is to avoid locks by leveraging hardware guarantees. But, each platform has its own limitations, and C++ is highly portable. So the implementation has to emulate atomicity (usually via the library) using fine-grained locks for atomic types that don't really exist at the hardware level.

Behavioral differences are minimized between hardware atomics and "software atomics," because differences would mean lost portability. On the other hand, a program should be able to avoid accidentally using mutexes, hence introspection through ATOMIC_x_LOCK_FREE which is available to the preprocessor.

Happenstance

I thought lock free basic data types are not that hard, the real problem is creating lock free algorithms on top of them. One might think that once you have atomics you can write lock free code, but even writing a lock free stack is ridiculously hard and error prone. – Divisionism

@Divisionism I'm not aware of any lock-free implementation of C++ standard library structures, or any proposal to standardize a new lock-free structure interface. That's a separate discussion. std::atomic might never be particularly complex, but the topic here is whether and when it's completely trivial. – Happenstance