原子操作传播/可见性(原子负载与原子RMW负载)

问题描述 投票:3回答:3

上下文

我正在用C ++编写一个线程安全的protothread/coroutine library,我正在使用atomics来使任务切换无锁。我希望它尽可能高效。我对原子和无锁编程有一般的了解,但我没有足够的专业知识来优化我的代码。我做了很多研究,但很难找到我特定问题的答案:不同内存顺序下不同原子操作的传播延迟/可见性是多少?

目前的假设

我读到内存的更改是从其他线程传播的,这样它们可能会变得可见:

  1. 以不同的顺序向不同的观察者,
  2. 有一些延迟。

我不确定这种延迟可见性和不一致传播是否仅适用于非原子读取或原子读取,可能取决于使用的内存顺序。当我在x86机器上开发时,我无法在弱有序系统上测试行为。

无论操作类型和使用的内存顺序如何,所有原子读取是否始终读取最新值?

我很确定所有读 - 修改 - 写(RMW)操作总是读取任何线程写入的最新值,而不管使用的内存顺序如何。对于顺序一致的操作似乎也是如此,但前提是对变量的所有其他修改也是顺序一致的。据说两者都很慢,这对我的任务不利。如果并非所有原子读取都获得最新的值,那么我将不得不使用RMW操作来读取原子变量的最新值,或者在while循环中使用原子读取,这是我目前的理解。

写入的传播(忽略副作用)是否取决于内存顺序和使用的原子操作?

(这个问题只有在上一个问题的答案是否并非所有原子读数总是读取最新值时才重要。请仔细阅读,我不会在这里询问副作用的可见性和传播。我只关心原子变量本身的值。)这意味着根据用于修改原子变量的操作,可以保证任何后续原子读取都接收变量的最新值。因此,我必须在保证始终读取最新值的操作或使用轻松的原子读取之间进行选择,与此特殊写入操作相结合,以保证对其他原子操作的修改的即时可见性。

c++ multithreading atomic propagation memory-visibility
3个回答
4
投票

Is atomic lock-free ?

首先,让我们摆脱房间里的大象:在你的代码中使用atomic不保证无锁实现。 atomic只是无锁实现的推动者。 is_lock_free()会告诉你它是否对C ++实现和你正在使用的底层类型真的无锁。

What's the latest value ?

在多线程领域,术语“最新”是非常模糊的。因为操作系统可能会睡眠的一个线程的“最新”是什么,可能不再是另一个活动线程的最新版本。

std::atomic唯一的保证是对赛车条件的保护,通过确保在一个线程中对一个原子执行的R, M and RMW以原子方式执行,没有任何中断,并且所有其他线程看到之前的值或之后的值,但绝不会介于两者之间。因此,atomic通过在同一原子对象上的并发操作之间创建顺序来同步线程。

您需要将每个线程视为具有自己时间的并行Universe,并且不知道并行Universe中的时间。就像在量子物理学中一样,你可以在一个线程中知道关于另一个线程的唯一事情是你可以观察到的(即宇宙之间的“之前发生过的”关系)。

这意味着你不应该设想多线程时间,好像在所有线程中都存在绝对的“最新”。你需要将时间设想为相对于其他线程。这就是为什么原子不会创建一个绝对最新的,但只能确保原子将具有的连续状态的顺序排序。

Propagation

传播不依赖于内存顺序,也不依赖于执行的原子操作。 memory_order是关于围绕原子操作的非原子变量的顺序约束,就像栅栏一样。对于如何工作的最好的解释肯定是Herb Sutters presentation,如果你正在进行多线程优化,这肯定值得一小时一半。

尽管特定的C ++实现可能以影响传播的方式实现某些原子操作,但您不能依赖于您将要执行的任何此类观察,因为无法保证传播在下一版本中以相同的方式工作编译器或另一个CPU架构上的另一个编译器。

But does propagation matter ?

designing lock-free algorithms时,很有可能阅读原子变量以获得最新状态。但是,虽然这种只读访问是原子的,但后面的操作却不是。因此,以下指令可能假设已经过时的状态(例如,因为线程在原子读取后立即发送为睡眠状态)。

if(my_atomic_variable<10)为例,假设您阅读了9.假设您处于最佳状态,9将是所有并发线程设置的绝对最新值。将它的值与<10进行比较并不是原子的,因此当比较成功并且if分支时,my_atomic_variable可能已经有了10的新值。无论传播速度有多快,这种问题都可能发生,即使读取也是如此保证始终获得最新价值。我甚至没有提到ABA problem

读取的唯一好处是避免数据竞争和UB。但是如果要跨线程同步决策/操作,则需要使用RMW,例如compare-and-swap(例如atomic_compare_exchange_strong),以便原子操作的排序产生可预测的结果。


1
投票

多线程是一个令人惊讶的领域。首先,写入后不会对原子读取进行排序。我读一个值并不意味着它之前写过。有时这样的读取可能会看到(间接的,通过其他线程)由同一线程进行的某些后续原子写入的结果。

顺序一致性显然是关于可见性和传播。当一个线程写入原子“顺序一致”时,它使其所有先前的写入对其他线程(传播)可见。在这种情况下,相对于写入排序(顺序一致的)读取。

通常,性能最高的操作是“放松”的原子操作,但它们在订购时提供最小的保证。原则上有一些因果关系悖论...... :-)


0
投票

经过一番讨论后,我的发现如下:首先,让我们定义一个原子变量的最新值意味着什么:在挂钟时间内,从外部观察者的角度来看最近对原子变量的写入。如果有多个同时的最后写入(即,在同一周期内的多个核心上),那么选择它们中的哪一个并不重要。

  1. 任何内存顺序的原子加载都不能保证读取最新值。这意味着必须先传播,然后才能访问它们。相对于它们的执行顺序,这种传播可能是乱序的,并且对于不同的观察者,顺序也不同。 这创造了相对论效应(如在爱因斯坦的物理学中),每个线程都有自己的“真理”,这正是我们需要使用顺序一致性(或获取/释放)来恢复因果关系的原因:如果我们只是使用宽松的负载,那么我们甚至可以破坏因果关系和明显的时间循环,这可能是由于指令重新排序与无序传播相结合而发生的。内存排序将确保由不同线程感知的那些单独的现实至少是因果关系。
  2. 原子读 - 修改 - 写(RMW)操作(例如exchange,compare_exchange,fetch_add,...)保证在上面定义的最新值上运行。这意味着强制写入传播,并在内存上产生一个通用视图(如果您所做的所有读取都来自使用RMW操作的原子变量),与线程无关。因此,如果您使用atomic.compare_exchange_strong(value,value, std::memory_order_relaxed)atomic.fetch_or(0, std::memory_order_relaxed),那么您可以保证感知一个包含所有原子变量的全局修改顺序。请注意,这并不能保证您对非RMW读取的任何排序或因果关系。

现在,何时使用哪种读取?

如果你在每个线程中只需要因果关系(对于发生在哪个顺序的事情,可能仍然存在不同的观点,但至少每个读者都有一个因果关系一致的世界观),那么原子加载和获取/释放或顺序一致性就足够了。

但是如果你还需要新的读取(这样你就不能读取除全局(跨所有线程)最新值之外的值),那么你应该使用RMW操作进行读取。仅那些不会为非原子和非RMW读取创建因果关系,但所有线程上的所有RMW读取共享完全相同的视图,这始终是最新的。

因此,得出结论:如果允许不同的世界观,则使用原子载荷,但如果您需要客观现实,请使用RMW加载。

© www.soinside.com 2019 - 2024. All rights reserved.