原子操作是如何实现的？

原子操作对于我们来说，是非常熟悉的概念。从用户角度，可以用原子操作来替换重量级的锁同步，从而提高程序性能。底层实现角度，原子操作可以用于构建各种更重量级的同步操作，比如锁或屏障之类的。

对于原子操作的实现来说，需要分开考虑单处理器单核系统，和多处理器系统，多核系统。

对于单处理器单核系统来说，只要保证操作指令序列不被打断即可实现原子操作（当然，对于内存的读写操作，需要地址对齐，否则就不是一次的内存读写了，当然也就不是原子操作）。对于简单的原子操作，cpu实现上会提供单条指令，比如INC和XCHG。对于复杂的原子操作，需要包含多条指令。执行过程中，出现上下文切换行为，比如任务切换，中断处理等。这里的行为会影响原子操作的原子性。因此需要自旋锁spinlock[1]来保证操作指令序列不会在执行的中途受干扰。

但是如果对于多处理器或者多核的系统，原子操作的实现除了需要spinlock来保证外，还需要保证不会受到同处理器上其他核，或者其他处理器的影响。当其他核上执行的指令访问的内存空间，与当前原子操作需要访问的内存空间存在冲突时，就会破坏原子操作的正确性。

在x86架构中，提供了指令前缀LOCK。LOCK保证了指令不会受其他处理器或cpu核的影响。在PentiumPro之前，LOCK的实现，是通过锁住bus（总线），从而阻止其他cpu核的内存访问。可想而知，这种实现是非常低效的。从PentiumPro开始，LOCK只会阻塞其他cpu核对相关内存的缓存块的访问。

现在，大多数的x86处理器都支持了CAS[2]的硬件实现，保证了多处理器多核系统下的原子操作的正确性。CAS的实现同样无需锁住总线，只会阻塞其他cpu核对相关内存的缓存块的访问。同样的，在MIPS和ARM架构下，还支持了LL/SC的实现[3]。LL/SC不会出现CAS中的ABA问题，而且基于LL/SC可以实现CAS FAA等原子操作。

在继续深入以前，需要了解MESI缓存协议[4]。当然，还存在其他的MESI变种，不过这里只会简单解释下MESI。每个cache line存在四种状态，Modified代表该cache line为该cpu核独有，且尚未写回（write back）到内存（对缓存一致性不了解的看这里[5]）。Exclusive代表该cache line为该cpu核独有，且与内存一致。Shared代表该cache line为多核共享，且与内存一致。Invalid代表缓存失效。处理器系统中多个处理器之间通过快速通道直接通信，比如intel家的QPI，amd家的Hypertransport。而处理器内多核直接通过共享的缓存比如L3总线进行通信。cpu核之间通信的消息包括读消息，以及读消息的响应消息。使无效消息，以及使无效消息的响应消息。当运行在某个cpu核的线程准备读取某个cache line的内容时，如果状态处于M,E,S，直接读取即可。如果状态处于I，则需要向其他cpu核广播读消息，在接受到其他cpu核的读响应后，更新cache line，并将状态设置为S。而当线程准备写入某个cache line时，如果处于M状态，直接写入。如果处于E状态，写入并将cache line状态改为M。如果处于S，则需要向其他cpu核广播使无效消息，并进入E状态，写入修改，后进入M状态。如果处于I，则需要向其他cpu核广播读消息核使无效消息，在收集到读响应后，更新cache line。在收集到使无效响应后，进入E状态，写入修改，后进入M状态。

从上面的说明可知，LOCK的实现，只需要保持cache line的M和E状态即可，此时就可以阻止其他cpu核对该块内存的修改，而不用去锁住整个总线。

(2018/2/24补充说明)
在比较早期的cpu型号中（intel486，pentium系列），多核处理器下阻止其他核对某块内存区域的修改，是通过锁住bus来实现的。但是在最近的cpu型号中，如果数据缓存在一个cache line上，而且memory type是write back的，则可以通过cache coherency机制来实现“cache locking”的功能，而不用锁住整个bus。

同理，CAS和LL/SC的实现，您应该可以猜出来了吧？

更多相关文章

随机推荐