3

我正在根据论文实现 Chase-lev 双端队列：“Correct and Efficient Work-Stealing for Weak Memory Models”。在论文中，它要求双端队列有一个带有原子元素的缓冲区：

struct Deque {
  std::atomic<size_t> size;
  std::atomic<int> buffer[];
}

为什么缓冲区中的元素是 typestd::atomic<int>而不是 plain int？

4

1 回答 1

0

好吧，因为缓冲区元素是由不同的线程读取/写入的，并且您并不总是在写入和后续读取之间存在先发生关系。因此，如果缓冲区元素不是原子的，就会出现数据竞争。

如果你有兴趣，你可以看看我的chas-lev-deque实现：https ://github.com/mpoeter/xenium/blob/master/xenium/chase_work_stealing_deque.hpp

更新

问题是索引可以环绕。假设调用steal 的线程在读取topand之后可能会被挂起bottom，但在它可以从缓冲区中读取项目之前。如果同时索引环绕，则该项目可能会被某些推送操作覆盖。因此，steal 中的加载操作不会与该存储具有发生前的关系。

该标准对数据竞争的定义如下：

如果程序的执行在不同的线程中包含两个冲突的操作，则程序的执行包含数据竞争，其中至少一个不是原子的，并且两者都不是先于另一个。

由于所描述的示例没有提供缓冲区上的读取和写入操作之间的发生前关系，因此如果缓冲区不是原子的，这将是数据竞争。但是，原子永远不会参与数据竞争，因此通过使缓冲区原子化，我们完全防止了由不同步访问引起的任何数据竞争（即使此类操作被放松）。

请注意，这只需要防止缓冲区操作的数据竞争。推送和窃取操作之间的实际同步是通过底部的操作发生的。

于 2020-02-02T18:06:47.327 回答