50

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?

Improve this question
2

2 Answers 2

Reset to default
48

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

Out of interest, are there platforms that don't provide any lockless native atomics, or do you just mean that atomic<T> 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: it could be that you only have a 1-byte atomic on an embedded platform. So something like std::atomic<char> 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<int> won't be lock-free. However, you can make a mutex (e.g. a spin lock) with the byte atomic.
@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.
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).
How could mutex be implemented without using some atomic operation at least for mutex::lock?
16

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.

Improve this answer

11 Comments

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.
I removed my downvote btw. Your edit made more clear what you meant and I think we were discussing on other levels.
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.
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.
@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)
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.