CODEWITHSUNDEEP
c++multithreadingc++11atomiclock-free
undermind
undermind

Reputation: 1841

C++: How can lock-free data structures be implemented in C++ if std::atomic_flag is the only lock-free atomic type?

Typical way of implementing lock-free data structures is using atomic CAS operations, such as std::compare_exchange_strong or std::compare_exchange_weak. The example of this technique's usage can be seen in Antony Williams' "C++ Concurrency in Action", where a lock-free stack is implemented. The stack is implemented as a linked list with std::atomic<node*> head pointer. CAS operations are performed on this pointer during pushs and pops. But C++ standard guarantees that only std::atomic_flag is lock-free, other atomic types, including std::atomic<T*>, may be not lock-free.

1) do I understand correctly that if std::atomic<T*> is not lock-free (std::atomic::is_lock_free() returns false), then data structure based on CAS operations on std::atomic<T*> is not lock-free?

2) If yes, then, what are alternative ways to implement lock-free data structures on C++ if std::atomic_flag is the only lock-free atomic type for some compiler?

Upvotes: 3

Views: 546

Answers (1)

Alan Birtles
Alan Birtles

Reputation: 36389

The only likely reason for a compiler not to have a lock free implementation of an atomic type is if the processor doesn't have atomic operations. I'm not aware of a modern processor where this is the case.

If the processor doesn't support atomic operations you probably have no choice but to use mutexes, semaphores or similar synchronisation primitives

Upvotes: 5

Related Questions