无锁有界堆栈C++11原子

Question

我正在考虑使用非常基本的有界(预分配)堆栈来按照正确的LIFO顺序跟踪我的线程in。所以我想知道我的实现是否是线程安全的：

// 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);
}

Answer 1

我不是无锁编程方面的专家，但我确信您的代码并不是线程安全的。

1. 让我们先来看看register_idle()： 这里可能发生的情况是，Thread1会增加idle_pos，但是在它存储id之前，另一个线程调用wakeup_once并使用过时的id (在最坏的情况下，甚至是无效的on，因为数组还没有初始化)。我也不知道为什么要用记忆栅栏。
2. 在wakeup_one()中，有一个类似的问题(称为ABA问题)：

- You load the current `idle_pos` and according `id`. 
- Another thread calls and completes `wakeup_one` (idle\_pos is decreased). 
- Yet another thread calls `register_idle` , which increases idle\_pos again to the same value as before.
- Now the first thread resumes, thinks `idle_pos` is unchanged and signals the wrong thread

​

我可能弄错了，但我认为通常不可能基于数组创建完全没有锁的堆栈，因为您必须在一个原子操作中做两件事:修改索引变量并在数组中存储或加载值。

除了这些逻辑错误之外，我强烈建议不要使用独立的内存栅栏(它们会降低代码的可读性，甚至会增加成本)。另外，我只会在确保程序与默认程序正确之后，才开始手动指定内存顺序。