Saturday 21 October 2017

multithreading - 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 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

php - file_get_contents shows unexpected output while reading a file

I want to output an inline jpg image as a base64 encoded string, however when I do this : $contents = file_get_contents($filename); print &q...