我想知道经典的“原子计数器动态调度”习惯用法的正确内存顺序是什么。即:
1.使用fetch-add获取要处理的下一个元素的索引i
1.如果i
超过数组的末尾,则终止
1.线程安全地处理元素i
,因为没有其他线程可以具有i
1.转到1。
例如:
#include <atomic>
std::atomic_int counter = 0;
void foo(int *data, int size) {
// we could also write counter++
for (int i; (i = counter.fetch_add(1, std::memory_order::seq_cst)) < size;) {
data[i] *= 2;
}
}
// driver code
#include <thread>
#include <numeric>
#include <cassert>
int main() {
int data[1'000'000];
std::iota(std::begin(data), std::end(data), 0);
std::thread other{foo, data, std::size(data)};
foo(data, std::size(data));
other.join();
for (int i = 0; i < std::size(data); ++i) {
assert(data[i] == i * 2);
}
}
这段代码可以工作,而且应该是安全的,因为在获取下一个索引之前或之后,处理一个元素不能重新排序,并且所有线程都以一致的总顺序观察到所有获取-添加。这些要求对我来说似乎过于严格了,我相信我们可以使用一个更宽松的订购。
我相信std::memory_order_relaxed
和std::memory_order::acquire
太宽松了,因为所有线程最初都会观察counter = 0;
,我们必须确保data[0] *= 2
不会在第一个fetch_add
之前移动。这两个记忆顺序可以做到这一点。
答案必须是以下之一:
std::memory_order::seq_cst
std::memory_order::acq_rel
std::memory-order::release
在这种情况下,哪一个是正确的顺序?
3条答案
按热度按时间oknwwptz1#
relaxed
就足够了。每个
counter.fetch_add(1, relaxed)
都会返回一个不同的值,0
以上的每个值都会返回一次。原子性本身就保证了这一点,因为所有操作都在同一个原子对象上。不能保证哪个线程将获得哪个
i
值,并且data[i]
上的操作没有顺序,但这很好,因为只有一个线程将访问每个data[i]
,直到thread.join()
在writer和reader之间创建同步。C++标准中的相关措辞是说原子RMW必须看到“最新值”,并且每个原子对象单独存在一致的修改顺序。在单个线程中,对同一个原子对象的操作遵循sequenced-before程序顺序。(即一个
fetch_add
不能与另一个fetch_add
“重新排序”。)在硬件中,相关的行为是RMW的原子性和高速缓存一致性,高速缓存一致性保证在原子RMW可以进行其加载+添加+存储之前,该高速缓存行的所有其他副本必须无效。(这就是为什么同一地址上的原子RMWs是可序列化的。
如果不依赖
.join()
与读卡器同步否则,您将需要一个单独的
atomic<bool> done
标志,或者release
RMWs(如果其他线程只是查看counter
)。等待线程必须等待counter == size + nthreads
,以确保每个线程都按顺序完成了release
操作-在最后一次data[i] *= 2
之后。(这些线程形成一个释放序列,因此读取器将与所有线程同步。)每个线程在看到一个false
fetch_add() < size
后将停止执行增量。第一个线程(按照counter
的修改顺序)已经加载了i=size
并存储了i=size+1
。离开循环的第二个线程将加载size+1
并存储size+2
。因此,nthreads=1或2时,counter==size+nthreads
在它们作为RMW的一部分完成最终存储之后。因此,看到
counter == size+nthreads
的加载可以确保所有线程在最后一次data[i] *= 2;
之后都执行了fetch_add
。如果这些是release
fetch_add,而这是一个acquire
加载,则可以保证在此加载之前已经发生了对data[0..size-1]
对象的存储,因此此线程中的后续代码可以看到修改后的值。(You只能检查所有线程是否完成;在此之前,不能保证
data[0..counter-1]
已经完成写入或类似的事情。即使使用seq_cst
增量,您也可以让一个线程声明i
值,但在访问data[i]
之前,线程会延迟或被调度很长一段时间。因此,任何数组元素仍然可以被修改。)编译器能帮你批处理这个吗
...并在
i
值上循环?假设是的,但实际上不是。请参阅Why don't compilers merge redundant std::atomic writes?-编译器根本不优化原子,除非在允许的情况下重新排序非原子操作。假设,编译器甚至可以静态地决定编译它,这样它总是在一个线程执行所有增量而另一个线程不执行任何增量的情况下运行。(除了最后一个退出循环)。例如通过首先执行
+= 1 mil
,然后在那些i
值上循环。这不是一个正确性问题,对于编译器来说,实际上会非常疯狂。这不是你需要排除的。即使你使用了
seq_cst
,一个足够聪明的Deathstation 9000编译器也可以分析整个程序,发现没有任何东西与counter
的值同步,所以它仍然可以进行相同的转换。如果有任何东西观察到counter
的最终值,它还必须确保counter = size + nthreads
,这样它就不能在两个线程中只执行fetch_add(1'000'000)
。要手动使用大于1的批次
批处理大小像4096字节或整数可能是有意义的。声明要处理的4096个元素并在
i + 0..4095
上循环,允许内部循环使用SIMD,并且在下一个缓慢的原子RMW之前有大量的工作正在进行中,该原子RMW必须等待counter
缓存行在线程之间反弹。只有一个线程访问包含一系列
data[]
值的缓存行,可以避免这些缓存行来回跳动。因此,如果data[]
对齐,则一个64字节的缓存行是您可能想要使用的最小批处理大小,否则您需要更大的批处理,因此只有在批处理的末尾才有拆分。但无论如何,您都希望更大的批处理,因为64字节只是几个或几个SIMD加载/存储。如果
data[]
是页对齐的,那么页大小的块意味着只有一个线程需要dTLB未命中该页,并且现代x86 CPU上的硬件预取在页边界处停止(因为连续的虚拟页可能在物理上不连续)。因此,这是结束批处理的自然位置,硬件预取不会为处理下一个块的线程造成争用。特别是在x86上,每个原子RMW实际上都是
seq_cst
,并且asm中有一个完整的内存屏障,您希望使您的批处理大小足够大以分摊这些成本。如果一个线程停止或发生其他情况,则尽可能大,而不会在最后留下大量剩余工作。ig9co6j12#
relaxed
是可以的,因为不管内存顺序如何,每个单独的原子变量在所有线程中总是一致的。只有当你有多个变量(原子或非原子)在线程间共享时,内存顺序才是必要的,因为在
relaxed
中,线程可以不同意不同变量上的操作是如何交错的,更强的顺序解决了这个问题。mmvthczy3#
我认为你在这里混淆了CAS(比较和交换)操作。
fetch_add
不是CAS,它被定义为读修改写原子操作。它不等同于atomic_var.compare_exchange(i, i+1, relaxed)
。整个操作被认为是原子的,应该完全执行。存储器顺序参数被指定用于同时或顺序发生的其他原子操作的排序。它给编译器一些自由来重新排列操作。
当使用原子增量操作时,即使在
relaxed
模式下,执行顺序也将确保原子变量的第n个fetch_add
将返回n-1
。如果它不这样做,代码就会崩溃(可能宇宙也会崩溃,但这只是一个小小的不便)。换句话说,您永远不会连续观察到,例如,在线程A中,
i = 0
和在线程B中,i = 2
。一个线程将在任何线程观察i = 2
之前观察i = 1
。未知的是哪个线程将对这个变量执行第n次获取。当你处理内存顺序时,你允许编译器根据它允许的任何操作顺序重新排序。
由于这里没有使用其他变量,因此即使
relaxed
顺序也可以工作。如果你正在使用另一个变量(比如,在获取counter
后更改原子变量tmp
),那么这将产生影响,因为如果你没有限制顺序,变量tmp
的更改值的 * 顺序 * 在另一个线程中可能不一样。在这种情况下,即使线程A中的代码在
counter
之前更改了tmp
,线程B也可能看到以前的tmp
值。如果在
fetch_add
上设置seq_cst
,则不会发生此行为。