c++ - 具有非原子大小项目的无锁双端队列

Question

我正在使用一个 worker 双端队列，如“针对弱内存模型的正确和高效的工作窃取”中所述。我希望队列项的大小为 16 个字节，并且我只关心 Intel/AMD Windows x64 和 VS 2019。

我知道 16 字节(比如 __m128)对齐的加载/存储在现代处理器中通常是原子的，但它们不受规范保证。

双端队列的类型是:

typedef struct {
    atomic_size_t size;
    atomic_int buffer[];
} Array;


typedef struct {
    atomic_size_t top, bottom;
    Atomic(Array *) array;
} Deque;

重要的是，数组缓冲区项特别具有原子类型。如果我用 VS2019 编译它，我可以看到它使用自旋锁使缓冲区项大小膨胀——我不想要这个。有可能预防吗？特别是因为我只关心带有某些保证的 x64。

deque 上的操作由函数给出:

int take(Deque* q) {
    size_t b = load_explicit(&q->bottom, relaxed) - 1;
    Array* a = load_explicit(&q->array, relaxed);
    store_explicit(&q->bottom, b, relaxed);
    thread_fence(seq_cst);
    size_t t = load_explicit(&q->top, relaxed);
    int x;
    if( t <= b ) {
        /* Non-empty queue. */
        x = load_explicit(&a->buffer[b % a->size], relaxed);
        if( t == b ) {
            /* Single last element in queue. */
            if( !compare_exchange_strong_explicit(&q->top, &t, t + 1, seq_cst, relaxed) )
                /* Failed race. */
                x = EMPTY;
            store_explicit(&q->bottom, b + 1, relaxed);
        }
    } else { /* Empty queue. */
        x = EMPTY;
        store_explicit(&q->bottom, b + 1, relaxed);
    }
    return x;
}


void push(Deque* q, int x) {
    size_t b = load_explicit(&q->bottom, relaxed);
    size_t t = load_explicit(&q->top, acquire);
    Array* a = load_explicit(&q->array, relaxed);
    if( b - t > a->size - 1 ) { /* Full queue. */
        resize(q);
        a = load_explicit(&q->array, relaxed);
    }
    store_explicit(&a->buffer[b % a->size], x, relaxed);
    thread_fence(release);
    store_explicit(&q->bottom, b + 1, relaxed);
}


int steal(Deque* q) {
    size_t t = load_explicit(&q->top, acquire);
    thread_fence(seq_cst);
    size_t b = load_explicit(&q->bottom, acquire);
    int x = EMPTY;
    if( t < b ) {
        /* Non-empty queue. */
        Array* a = load_explicit(&q->array, consume);
        x = load_explicit(&a->buffer[t % a->size], relaxed);
        if( !compare_exchange_strong_explicit(&q->top, &t, t + 1, seq_cst, relaxed) )
            /* Failed race. */
            return ABORT;
    }
    return x;
}

其中很多都是多余的，应该在 x64 上进行优化。事实上，该论文指定在 thread_fence(seq_cst) 行的 take 函数中只需要一个内存栅栏。虽然我不确定如果队列项类型的大小是 16 个字节，这是否属实？

看起来take()/push() 必须发生在同一个线程中，所以它们之间没有问题。因此，危险在于任何调用 steal() 的线程都会读取部分写入的 16 字节项目。但是由于 push() 仅在写入所有 16 个字节后才执行内存栅栏，并且仅在此之后更新底部，因此在 x64 上似乎这不是问题？

我做了一个实验，我删除了缓冲区项上的原子限定符，并通过 volatile 指针对缓冲区使用简单的赋值。它似乎工作正常，但显然这并不确定!

如果这是不可能的，那么也许使用 cmpxchg16b 是加载/存储 16 字节我的具体情况的更好选择？或者通过将队列项作为索引并无锁地分配索引的 16 字节槽来使这一切复杂化。

所以我的问题的简化版本是:在 x64 上，我可以简单地将 Array 缓冲区类型的定义更改为指向非原子限定 16 字节结构项数组的 volatile 指针，并更改将上述函数中的那些项目加载和存储到简单的非原子赋值表达式？

Answer 1

这可能只是部分答案，因为我试图回答关于 16 字节原子的问题，但我不知道为什么你需要队列的元素是原子的，而不仅仅是计数器。

---

使用 MSVC 2019 完成此操作同时仍编写可能可移植的代码的最简单方法是:

• 使用std::atomic_ref<16 bytes type>
• #define _STD_ATOMIC_ALWAYS_USE_CMPXCHG16B
• static_assert在 atomic_ref<...>::is_always_lock_free确保你有真正的无锁原子

或:

• 使用boost::atomic<16 bytes type>或 boost::atomic_ref<16 bytes type>
• 再次，static_assert在 is_always_lock_free确保你有真正的无锁原子

MSVC 可能已经为 std::atomic<16 bytes type> 实现了同样的事情，但由于 ABI 兼容性问题，它仍然没有。 (预计在未来的某个版本中实现此功能，将打破当前的 ABI)

这会给你 cmpxchg16b对于每一个操作，即使是轻松的负载和轻松的存储。这是您可以在任何 CPU 上保证获得的最佳结果。

128 位类型有单指令加载/存储，但它们保证是原子的。参见 SSE instructions: which CPUs can do atomic 16B memory operations?

---

关于 volatile

在 MSVC 中 volatile读取和分配由 /volatile:ms 控制//volatile:iso .参见 /volatile (volatile Keyword Interpretation) .那就是 /volatile:ms ，这是 x86-64 上的默认设置，应该获取负载，应该释放存储。

但是:

• 对于任何 CPU 上的 128 位类型，不能保证简单的加载/存储是原子的(请参阅上面的链接答案)
• 即使对于 CPU 它们是原子的，128 位类型对于编译器来说也不是原子的，因此它不一定会生成单指令访问。

因此，如果您仍然希望在 objective-c PU 上依赖 128 位加载/存储作为原子操作，您最好使用内部函数 _mm_load_si128/_mm_store_si128 , 使用 alignas(16)以确保正确对齐，并使用 _ReadWriteBarrier以防止编译器重新排序。这可能有效(编译器可能会生成 128 位加载/存储，如所要求的那样，并且这些加载/存储在给定 CPU 上可能确实是原子的)。