48

When we talk about atomic variables, such as C++11's atomic<>, is it lock free? Or is lock-freeness something different? If I manage a queue with atomic variables, will it be slower than a lock-free queue?

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
pythonic
  • 20,589
  • 43
  • 136
  • 219
  • http://stackoverflow.com/questions/930897/c-atomic-operations-for-lock-free-structures –  Apr 11 '12 at 13:33
  • It's also answered here: http://www.open-std.org/JTC1/sc22/wg21/docs/papers/2007/n2427.html#DiscussOperations it seems they are lock-free. –  Apr 11 '12 at 13:36

2 Answers2

45

The standard does not specify if atomic objects are lock-free. On a platform that doesn't provide lock-free atomic operations for a type T, 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 does provide a way to check if an atomic<T> variable is lock-free: you can use var.is_lock_free() or atomic_is_lock_free(&var). These functions are guaranteed to always return the same value for the same type T on a given program execution. For basic types such as int, There are also macros provided (e.g. ATOMIC_INT_LOCK_FREE) which specify if lock-free atomic access to that type is available.

interjay
  • 107,303
  • 21
  • 270
  • 254
  • 2
    Out of interest, are there platforms that don't provide _any_ lockless native atomics, or do you just mean that `atomic` may not be natively atomic for all sizes of `T`? I can't see how a platform with no genuine native atomics would implement mutexes in the first place ... – Useless Apr 11 '12 at 13:51
  • 3
    @Useless: it could be that you only have a 1-byte atomic on an embedded platform. So something like `std::atomic` would be lock-free. However, if 32-bit integers are simulated by doing 4 byte-operations that isn't atomic. So most likely `std::atomic` won't be lock-free. However, you can make a mutex (e.g. a spin lock) with the byte atomic. – KillianDS Apr 11 '12 at 13:54
  • @Useless: I meant that lock-free operations would not be supported for all object sizes - I've edited to clarify. I suppose in theory a platform could provide native lock/unlock operations without having lockless atomic operations, but I'm not aware of such platforms. – interjay Apr 11 '12 at 14:02
  • 4
    Some platforms only have atomic **exchange** instructions. You can use this for a mutex, and `std::atomic_flag` (which **is** required to be lock-free), but not for a general atomic (as it can't do a plain load). – Anthony Williams Apr 11 '12 at 16:38
  • How could mutex be implemented without using some atomic operation at least for mutex::lock? – muaz Jan 21 '21 at 21:45
15

Lock-free usually applies to data structures shared between multiple threads, where the synchronisation mechanism is not mutual exclusion; the intention is that all threads should keep making some kind of progress instead of sleeping on a mutex.

atomic<T> variables don't use locks (at least where T is natively atomic on your platform), but they're not lock-free in the sense above. You might use them in the implementation of a lock-free container, but they're not sufficient on their own.

Eg, atomic<queue<T>> wouldn't suddenly make a normal std::queue into a lock-free data structure. You could however implement a genuinely lock-free atomic_queue<T> whose members were atomic.

Note that even if atomic<int> is natively atomic and not emulated with a lock on your platform, that does not make it lock-free in any interesting way. Plain int is already lock-free in this sense: the atomic<> wrapper gets you explicit control of memory ordering, and access to hardware synchronisation primitives.

Useless
  • 64,155
  • 6
  • 88
  • 132
  • So a spinlock is lock-free when I implement it using atomic operations? I guess you never yield to the scheduler, but I'm not sure that's what _lock-free_ means in normal use. – Useless Apr 11 '12 at 14:04
  • I removed my downvote btw. Your edit made more clear what you meant and I think we were discussing on other levels. – KillianDS Apr 11 '12 at 14:18
  • Cheers - maybe I'm conflating _lock-free_ with _non-blocking_, it definitely feels ambiguous when talking about the primitives themselves, rather than the algorithm using them. – Useless Apr 11 '12 at 14:23
  • The term "wait-free" is used to differentiate lock-free algorithms that always make forward progress on all threads (ie. don't block). Spinlocks are certainly lock-free but not wait-free - in fact, the same atomic value check (CAS) is used commonly in lock-free algorithms. – ex0du5 Apr 11 '12 at 16:11
  • I disagree with your last paragraph: Since plain `int` is not thread-safe, it is meaningless to say that it is lock-free. But `atomic` is thread-safe, and so it is certainly meaningful whether it is lock-free or not. – interjay Apr 11 '12 at 16:24
  • 1
    Plain `int` is thread-safe on x86 with a single writer for example, if the reader(s) have only weak requirements on how up-to-date their view is. So, for some application logic, plain `int` may be perfectly thread-safe. – Useless Apr 12 '12 at 10:06
  • I think the last comment requires a bit of qualification. reads and writes are guaranteed to be atomic and reads are always appropriately ordered, but writes may occur out of order(albeit atomically). If the int's value doesn't imply logically that some other action is complete, then yes, you are safe. Otherwise you need atomic<> to provide a fence on writes to ensure causality. – Tim Seguine Oct 15 '13 at 12:55
  • 1
    @Tim, Re: `writes may occur out of order` - no, x86 ordering explicitly guarantees that stores are ordered within the same thread, and maintain TSO-like memory ordering rules on multiple threads. It's unrelated though - ordered and atomic loads and stores still require locking since operation atomicity does not guarantee inter-op atomicity of any kind (i.e. - `inc [x]` may have an atomic load and an atomic store, but the memory may change between these two) – Leeor Jan 12 '14 at 12:25
  • @Leeor I think I need to qualify a bit what I meant. On x86, word sized loads and stores are always atomic. Read operations on x86 are atomic "acquire/release" operations. Write operations on x86 are atomic but are not "release" operations, unless they are "locked", in which case they are "acquire/release". This is enough to guarantee causality. If you look at my comment, I didn't make any claims about inter-op atomicity. I only claimed that one can guarantee causality in a lock free manner. That is enough to write some parallel algorithms correctly without locks or races. – Tim Seguine Jan 13 '14 at 11:09
  • The statement _"atomic variables don't use locks"_ is incorrect and misleading. They can and do use locks, e.g. if the type is bigger than what the biggest atomic instruction of the architecture can handle. And even though those locks are only held for a very short time, this can cause significant problems. Stuff like priority inversion. Or, if stuff like `fork`ing is involved, even deadlocks. – Paul Groke Feb 05 '20 at 14:38
  • The statement _"atomic variables don't use locks"_ comes from you selectively quoting the first third of a sentence that already contains exactly the qualification you provide. kthxbye. – Useless Feb 05 '20 at 14:46