3

我正在使用“用于弱内存模型的正确和高效的工作窃取”中描述的工作人员双端队列。我希望队列项目的大小为 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。

双端队列上的动作由函数给出：

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 指针，并在上述函数中更改这些项目的加载和存储到简单的非原子赋值表达式？

4

1 回答 1

2

这可能只是部分答案，因为我试图回答大约 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 指令：哪些 CPU 可以进行原子 16B 内存操作？

关于volatile

在 MSVCvolatile中，读取和分配由/volatile:ms/控制/volatile:iso。请参阅/volatile（易失性关键字解释）。即/volatile:msx86-64 上的默认设置，加载应该是获取，存储应该是释放。

然而：

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

因此，如果您仍想依赖 128 位加载/存储在目标 CPU 上作为原子工作，您最好使用内在函数_mm_load_si128/ _mm_store_si128，用于alignas(16)确保正确对齐，并使用_ReadWriteBarrier防止编译器重新排序。这可能会起作用（编译器可能会生成 128 位加载/存储，如所要求的，并且这些加载/存储在给定的 CPU 上可能确实是原子的）。

于 2021-09-03T13:04:35.203 回答