CAS指令如何保证原子性

Question

根据 Wiki，CAS 会这样做：

function cas(p : pointer to int, old : int, new : int) returns bool {
    if *p ≠ old {
        return false
    }
    *p ← new
    return true
}

嗯，在我看来，如果多个处理器将尝试使用相同的参数执行 CAS 指令，则可能会同时进行多个写入尝试，因此无论如何这样做都不安全。

我哪里错了？

Answer 1

如果您阅读 wiki，它会说您发布的代码的 CAS "is an atomic version of the following pseudocode"。原子意味着代码将在没有其他线程中断的情况下执行。因此，即使多个线程尝试使用相同的参数（如您建议的那样）同时执行此代码，也只有其中一个会 return 为真，因为实际上它们不会同时执行，因为原子性要求它们运行孤立无援。

既然你提到了 "x86 doesn't guarantee atomicity of writes for non-aligned DWORDs"，这也不是问题，因为 cas 函数的原子属性。

Answer 2

同时来自多个内核的原子读取-比较-写入指令确实相互竞争，但这取决于硬件来解决。 Hardware arbitration of atomic RMW instructions 在现代 CPU 中是真实存在的，它提供了一定程度的公平性，因此在 lock cmpxchg 上旋转的一个线程不会完全阻塞其他线程做同样的事情。（虽然这是一个糟糕的设计：最好在获取负载上旋转，并且只在应该成功时才执行 CAS）

无法保证它们发生的顺序，这就是为什么您需要仔细设计算法，以便正确性仅取决于比较和交换是原子的。（ABA problem 是一个常见的陷阱）。

顺便说一句，整个伪代码块作为单个原子操作发生。让读取-比较-写入或读取-修改-写入作为单个原子操作发生对于硬件来说比存储要困难得多，MESIF/MOESI 处理得很好。

are you sure? I thought that it's unsafe to do that because, for example, x86 doesn't guarantee atomicity of writes for non-aligned DWORDs

lock cmpxchg 使操作成为原子操作，而不管对齐方式如何。对于未对齐的情况，它可能会慢很多，尤其是在缓存行拆分时，原子地修改单个缓存行是不够的。

另请参阅，我在其中解释了原子操作的含义。

CAS指令如何保证原子性

How does CAS instructions guarantee atomicity

assembly

multithreading

atomic