Why only std::atomic_flag is guaranteed to be lock-free?

Question

From C++ Concurrency in Action:

difference between std::atomic and std::atomic_flag is that std::atomic may not be lock-free; the implementation may have to acquire a mutex internally in order to ensure the atomicity of the operations

I wonder why. If atomic_flag is guaranteed to be lock-free, why isn't it guaranteed for atomic<bool> as well? Is this because of the member function compare_exchange_weak? I know that some machines lack a single compare-and-exchange instruction, is that the reason?

Rostand

Because std::atomic<T> has a type argument, std::atomic_flag does not. Whether T updates are atomic depends on the processor architecture. The library writer can pick any suitable type for atomic_flag. – Endothermic

Okay. However my question is rather about this essential difference between std::atomic<bool> and std::atomic_flag – Rostand

I think no difference – Shaunteshave

Answer 1

First of all, you are perfectly allowed to have something like std::atomic<very_nontrivial_large_structure>, so std::atomic as such cannot generally be guaranteed to be lock-free (although most specializations for trivial types like bool or int probably could, on most systems). But that is somewhat unrelated.

The exact reasoning why atomic_flag and nothing else must be lock-free is given in the Note in N2427/29.3:

Hence the operations must be address-free. No other type requires lock-free operations, and hence the atomic_flag type is the minimum hardware-implemented type needed to conform to this standard. The remaining types can be emulated with atomic_flag, though with less than ideal properties.

In other words, it's the minimum thing that must be guaranteed on every platform, so it's possible to implement the standard correctly.

Slag

Correctly and uselessly – Selfrighteous

@Selfrighteous : I wouldn't say that. On most platforms, all types (including compound types) smaller than 16 bytes are lockfree. On almost all, except some microcontrollers or 35 year old crapware, everything up to 8 bytes is. You can query your implementation if you need to know, but more importantly you can write code that will work regardless, and will work as fast as possible on most architectures. It's actually pretty cool. – Slag

Yes. "you are perfectly allowed to have something like std::atomic<very_nontrivial_large_structure>" You can, but it isn't very useful. – Selfrighteous

@curiousguy: Again, I wouldn't necessarily say that. There's situations where you have more than just one value (explict waiter count, for example), and you may want to compare-exchange one of them or both at the same time, depending on what you do. So it's pretty nice that as long as size is below some two-pointer-sized magic constant, you can just do what you want, and it works. I wish there were something like cacheline-sized atomics (why not actually...). Now that would really be cool. – Slag

Yes but "where you have more than just one value", with one ptr and one use count, is not a very large structure. very_nontrivial_large_structure has a "size in the hundreds of bytes" connotation. Or may it's just me. – Selfrighteous

Answer 2

The standard does not garantee atomic objects are lock-free. On a platform that doesn't provide lock-free atomic operations for a type T, std::atomic<T> objects may be implemented using a mutex, which wouldn't be lock-free. In that case, any containers using these objects in their implementation would not be lock-free either.

The standard provide an opportunity to check if an std::atomic<T> variable is lock-free: you can use var.is_lock_free() or atomic_is_lock_free(&var). For basic types such as int, there is also macros provided (e.g. ATOMIC_INT_LOCK_FREE) which specify if lock-free atomic access to that type is available.

std::atomic_flag is an atomic boolean type. Almost always for boolean type it's not needed to use mutex or another way for synchronization.

Shaunteshave