是否可以使用 std::memory_order_relaxed
作为跳过标志,如 iterate
:
constexpr static const std::size_t capacity = 128;
std::atomic<bool> aliveness[capacity];
T data[capacity]; // immutable/atomic/etc.
template<class Closure>
void iterate(Closure&& closure){
for(std::size_t i = 0; i<capacity; i++){
if (!aliveness[i].load(std::memory_order_relaxed)) continue;
closure( data[i] );
}
}
void erase(std::size_t index){
aliveness[index].store(false, std::memory_order_relaxed);
}
或者我应该改用发布/获取?
aliveness[i]
可能再次“活着”。
iterate
和 erase
从多个线程同时调用。考虑 data
在其他一些外部锁下不可变/原子/同步。
最佳答案
假设:当您使用erase
时,其他线程可以随时运行iterate()
。 (问题的早期版本没有指定不可变。如果未按顺序更新 data[i]
的锁定(或缺少锁定),则此答案仍然相关。写入 活着[i]
.)
如果数据确实是不可变的,那么 mo_relaxed
肯定没问题,除非您需要根据线程正在做的事情其他对这些商店的全局可见性进行排序. mo_relaxed
存储最终将始终对其他线程可见(并且在当前的 CPU 上,将很快完成)。
如果你要在 alive[i]
为 false 时修改非原子 data[i]
,你需要确保其他线程不是在修改时使用它的值。那将是 C++ 中的 UB,以及取决于 T
和 closure
的实际硬件上的实际正确性问题。
获取语义将适用于iterate
。访问 data[i]
逻辑上发生在 alive[i]
之后,因为单向屏障的方向正确。 The acquire-load won't reorder with later loads or stores, only earlier ones .
但是erase
中的store是个问题。在对 data[i]
进行任何修改之前,它需要全局可见。但是允许发布商店与以后的商店重新订购。你需要的是a release fence to block reordering of stores in both directions .
void erase(std::size_t index){
aliveness[index].store(false, std::memory_order_relaxed);
std::atomic_thread_fence(std::memory_order_release);
// or don't do that, this probably wouldn't be enough synchronization
// and whatever you do that syncs the data might make this unnecessary.
}
如果 T
是一个原子类型,那么 data[i]
的发布存储就可以了。但是不要那样做;如果 T
太大而不能成为无锁原子,那将很糟糕。
(更新:我不确定这是否完全有效。ISO C++ 内存排序规则是根据同步/发生之前定义的,以及允许给定负载的值看看。不是在原子和非原子操作之间重新排序本身。
此外,这就像您为 SeqLock 所做的一样,但这也取决于读取的数据争用 UB。如果另一个线程要读取 data[i]
,如果它检查 alive[i]
然后读取,就会出现 TOCTOU 竞赛:我们写入 alive
可能在那次读取之后发生,然后我们对 data[i]
的写入可能与另一个线程读取同时发生。
所以这可能不足以删除/修改/取消删除一个元素,即使在像 x86 这样的强顺序非怪异机器上也是如此。)
在某些实现中,seq-cst 存储也可以工作,但我认为仅作为实现细节。它通常会产生一个存储 + 一个全屏障 asm 指令。 (例如 x86 MFENCE)。所以它起作用只是因为编译器将 seq-cst 存储实现为存储 + thread_fence(seq_cst)
。在 AArch64 上情况并非如此,其中 STLR 只是一个释放操作;只有与 LDAR 的交互才能给出 SC-DRF。 (无数据争用程序的 seq_cst)。
请注意,如果 closure
修改了 data[]
,则 iterate
是不安全的,除非一次只有一个线程可以调用它。在这种情况下,这样做的意义何在?所以你可能应该使用
void iterate(Closure&& closure) const
{ ... }
因此 iterate
仅适用于容器的 const
对象。
关于C++ std::memory_order_relaxed 和跳过/停止标志,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46680842/