使用 std::atomic fetch_add 的结果来索引数组仍然是原子的吗？

Question

所以我想尝试使用 fetch_add 和 fetch_sub 原子指令实现一个固定大小的等待空闲堆栈。假设我有一个基本的堆栈，有两个操作，push 和 pop。

struct WaitFreeStack {
    std::atomic<size_t> cur;
    std::atomic<int>* buf;

    void push(int i) {
        buf[cur.fetch_add(1)].store(i);
    }

    int pop() {
        return buf[cur.fetch_sub(1) - 1].load();
    }
};

我的问题是，操作是否采用 B[X] 的形式，其中 B 是一个数组，X 是一个整数原子？例如，在我的示例中，是否有可能在执行 push() 方法的 fetch_add 调用之后，在执行 B[X] 之前，整个 pop 和 push 可以在单独的线程中执行，导致 push 覆盖另一个 push ?

Answer 1

are operations in the form of B[X], where B is an array and X is an integer atomic ?

没有

In my example for instance, is it possible that after a fetch_add call for the push() method is executed, and before the B[X] is executed, that a whole pop and push in separate threads could be executed, causing a push to overwrite another push ?

是的。

您的示例可以等同于：

void push(int i) {
    size_t index = cur.fetch_add(1);
    // execution time interval
    buf[index].store(i);
}

int pop() {
    size_t index = cur.fetch_sub(1) - 1;
    // execution time interval
    return buf[index].load();
}

上面两个注释位置都会有一个执行时间间隔，虽然这个时间间隔非常非常短，但是如果此时另一个线程调用了push或者pop并完成了调用，绝对不安全。

实现线程安全容器的最简单方法是使用 std::mutex，还有一些无锁实现（如 boost）。

Answer 2

B[X] 不是原子的。但即使它是原子的，也无济于事。

问题是您有表达式 多个原子操作。虽然操作是原子的，但整个表达式不是原子的。

或者：包含多个原子操作的表达式不需要是原子的。

这里的class不变量应该是cur指向buf中的当前对象。但是这个不变量在 2 个原子操作 fetch_add 和 store.

之间被打破了

如果 B[X] 是原子的（实际上不是），那么推送的原子操作顺序如下：

X = cur.fetch_add(1);  // atomic
// 1. dT
ref = B[X];             // let's assume atomic
// 2. dT
ref.store(i);           // atomic

例如，在时间间隔 2.dT 中，假设第二个线程弹出 2 个项目，第三个线程推送 1 个项目，所有这些都在 ref.store(i) 之前执行。此时 ref 引用下的值会发生变化。

使用 std::atomic fetch_add 的结果来索引数组仍然是原子的吗？

Is using the result of an std::atomic fetch_add to index an array still atomic?

c++

multithreading

atomic