提问者:小点点

CAS指令如何保证原子性


根据维基,CAS这样做:

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

好吧,在我看来,如果几个处理器试图用相同的参数执行CAS指令,可能会同时有几次写入尝试,所以无论如何都不安全。

我哪里错了?


共2个答案

匿名用户

来自多个内核同时(在同一缓存线上)的原子读-比较-写指令确实会相互竞争,但这取决于硬件来解决这个问题。原子RMW指令的硬件仲裁在现代CPU中是真实的,并且提供了一定程度的公平性,以便在lock cmpxchg上旋转的一个线程不能完全阻止其他线程做同样的事情。

(虽然这是一个糟糕的设计,除非你的重试可以成功,而不等待另一个线程修改任何东西,例如,实现fetch_or或类似的重试循环可以使用预期的更新值重试。但是如果等待锁或标志改变,在初始CAS失败后,最好在获取或放松负载上旋转,只有在可能成功的情况下才CAS。)

不能保证它们发生的顺序,这就是为什么你需要仔细设计你的算法,这样正确性只取决于比较和交换是原子的。(ABA问题是一个常见的陷阱)。

BTW,整个伪代码块是作为单个原子操作发生的。对硬件来说,使读-比较-写或读-修改-写作为单个原子操作比仅仅存储要困难得多,MESIF/MOESI可以很好地处理存储。

你确定吗?我认为这样做是不安全的,因为例如,x86不能保证不对齐DWORD的写入原子性

lock cmpxchg使操作原子化,而不考虑对齐。对于未对齐的情况,它可能会慢得多,尤其是在缓存行拆分中,原子修改单个缓存行是不够的。

另请参阅x86上的原子性,其中我解释了操作是原子的含义。

匿名用户

如果你阅读维基,它说CAS是你发布的代码的“以下伪代码的原子版本”。原子意味着代码将在没有其他线程中断的情况下执行。因此,即使几个线程尝试使用相同的参数同时执行此代码(如您所建议的那样),其中只有一个将返回true,因为实际上它们不会同时执行,因为原子性要求它们隔离运行。

由于您提到“x86不保证不对齐DWORD的写入原子性”,这在这里也不是问题,因为cas函数的原子属性。