无锁有界堆栈 C++11 原子
Lock Free Bounded Stack C++11 atomics
我正在考虑使用非常基本的有界(预分配)堆栈以正确的后进先出顺序跟踪我的线程 ID。所以我想知道我的实现是否是线程安全的:
// we use maximum 8 workers
size_t idle_ids_stack[8];
// position current write happening at
std::atomic_uint_fast8_t idle_pos(0);
// this function is called by each thread when it is about to sleep
void register_idle(size_t thread_id)
{
std::atomic_thread_fence(std::memory_order_release);
idle_ids_stack[idle_pos.fetch_add(1, std::memory_order_relaxed)] = thread_id;
}
// this function can be called from anywhere at anytime
void wakeup_one()
{
uint_fast8_t old_pos(idle_pos.load(std::memory_order_relaxed));
std::atomic_thread_fence(std::memory_order_acquire);
size_t id;
do
{
if(old_pos == 0) return; // no idle threads in stack; exit;
id = idle_ids_stack[old_pos-1];
}
while (!idle_pos.compare_exchange_weak(old_pos, old_pos-1, std::memory_order_acquire, std::memory_order_relaxed));
// wakeup single thread
signal_thread(id);
}
我不是无锁编程方面的专家,但我很确定您的代码不是线程安全的。
先来看看register_idle()
:
这里可能发生的是 Thread1 递增 idle_pos
但在它存储其 id 之前,另一个线程调用 wakeup_once
并使用过时的 id(在最坏的情况下甚至是无效的,因为数组尚未初始化)。我也没有看到内存栅栏的原因。
在 wakeup_one()
你有一个类似的问题(称为 ABA problem):
- 您加载当前
idle_pos
并根据 id
。
- 另一个线程调用并完成
wakeup_one
(idle_pos减少)。
- 另一个线程调用
register_idle
,它再次将 idle_pos 增加到与以前相同的值。
- 现在第一个线程恢复,认为
idle_pos
没有变化并向错误的线程发出信号
我可能错了,但我相信通常不可能基于数组创建完全无锁的堆栈,因为您必须在单个原子操作中做两件事:修改索引变量和存储或加载数组中的值。
除了那些逻辑错误之外,我强烈建议不要使用独立的内存栅栏(它们会降低代码的可读性,甚至可能成本更高)。此外,在确保程序与默认程序正确之后,我只会开始手动指定内存顺序。
我正在考虑使用非常基本的有界(预分配)堆栈以正确的后进先出顺序跟踪我的线程 ID。所以我想知道我的实现是否是线程安全的:
// we use maximum 8 workers
size_t idle_ids_stack[8];
// position current write happening at
std::atomic_uint_fast8_t idle_pos(0);
// this function is called by each thread when it is about to sleep
void register_idle(size_t thread_id)
{
std::atomic_thread_fence(std::memory_order_release);
idle_ids_stack[idle_pos.fetch_add(1, std::memory_order_relaxed)] = thread_id;
}
// this function can be called from anywhere at anytime
void wakeup_one()
{
uint_fast8_t old_pos(idle_pos.load(std::memory_order_relaxed));
std::atomic_thread_fence(std::memory_order_acquire);
size_t id;
do
{
if(old_pos == 0) return; // no idle threads in stack; exit;
id = idle_ids_stack[old_pos-1];
}
while (!idle_pos.compare_exchange_weak(old_pos, old_pos-1, std::memory_order_acquire, std::memory_order_relaxed));
// wakeup single thread
signal_thread(id);
}
我不是无锁编程方面的专家,但我很确定您的代码不是线程安全的。
先来看看
register_idle()
:这里可能发生的是 Thread1 递增
idle_pos
但在它存储其 id 之前,另一个线程调用wakeup_once
并使用过时的 id(在最坏的情况下甚至是无效的,因为数组尚未初始化)。我也没有看到内存栅栏的原因。在
wakeup_one()
你有一个类似的问题(称为 ABA problem):- 您加载当前
idle_pos
并根据id
。 - 另一个线程调用并完成
wakeup_one
(idle_pos减少)。 - 另一个线程调用
register_idle
,它再次将 idle_pos 增加到与以前相同的值。 - 现在第一个线程恢复,认为
idle_pos
没有变化并向错误的线程发出信号
- 您加载当前
我可能错了,但我相信通常不可能基于数组创建完全无锁的堆栈,因为您必须在单个原子操作中做两件事:修改索引变量和存储或加载数组中的值。
除了那些逻辑错误之外,我强烈建议不要使用独立的内存栅栏(它们会降低代码的可读性,甚至可能成本更高)。此外,在确保程序与默认程序正确之后,我只会开始手动指定内存顺序。