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
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
, may be not lock-free.
1) do I understand correctly that if
std::atomic
is not lock-free
(std::atomic::is_lock_free()
returns false), then data
structure based on CAS operations on std::atomic
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?
No comments:
Post a Comment