C ++:如果std :: atomic_flag是唯一的无锁原子类型,那么如何在C ++中实现无锁数据结构? [英] C++: How can lock-free data structures be implemented in C++ if std::atomic_flag is the only lock-free atomic type?
问题描述
实现无锁数据结构的典型方法是使用原子CAS操作,例如std::compare_exchange_strong
或std::compare_exchange_weak
.在Antony Williams的"C ++ Concurrency in Action"中可以看到该技术的用法示例,该示例中实现了无锁堆栈.堆栈被实现为带有std::atomic<node*>
头指针的链表.在推入和弹出期间,对此指针执行CAS操作.但是C ++标准保证只有std::atomic_flag
是无锁的,其他原子类型(包括std::atomic<T*>
)可能不是无锁的.
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)我是否正确理解,如果std::atomic<T*>
不是非锁定的(std::atomic::is_lock_free()
返回false),那么基于std::atomic<T*>
的CAS操作的数据结构不是非锁定的吗?
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)如果是,那么,如果std::atomic_flag
是某些编译器唯一的无锁原子类型,那么在C ++上实现无锁数据结构的替代方法是什么?
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?
推荐答案
编译器不具有原子类型的无锁实现的唯一可能原因是处理器没有原子操作.我不知道是这种情况的现代处理器.
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
这篇关于C ++:如果std :: atomic_flag是唯一的无锁原子类型,那么如何在C ++中实现无锁数据结构?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!