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?

Answer 1

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.

Answer 2

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.