原子操作

文档状态：编辑中....

Table of Contents

源头

在阅读unix系列丛书发现原子性操作的概念实在不清晰,有时候认为指令在执行过程中不能被打断(软硬中断,上下文切换行为，比如任务切换，中断处理),有的时候又被一些其他的网络文章误导,离真相越来越远.又有的时候被别人引入锁同步(重量级锁)和临界区的概念与原子操作概念混淆在一块,大多数时间考虑原子操作与锁同步的概念上的区别,后来参阅一些文献和专家博客才逐渐开朗.

知识介绍

[应用场景]某些场景下，可以用原子操作来替换重量级的锁同步，从而提高程序性能。原子操作可以保障多个线程或进程在更新某块共享内存区时，可以避免同步原语。
对于原子操作的实现来说，需要分开考虑单处理器单核系统，和多处理器系统，多核系统.
单处理器单核系统某一时刻只会有一个事件在执行.所以系统预定义的单个原子指令或spinlock+指令序列即可.
多处理器系统则要考虑更多的限制.
对于单处理器单核系统来说，只要保证操作指令序列不被打断即可实现原子操作。对于简单的原子操作，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问题。

在继续深入以前，需要了解MESI缓存协议[4]。当然，还存在其他的MESI变种，不过这里只会简单解释下MESI。每个cacheline存在四种状态，Modified代表该cacheline为该cpu核独有，且尚未写回（write back）到内存（对缓存一致性不了解的看这里[5].Exclusive代表该cache line为该cpu核独有，且与内存一致。Shared代表该cache line为多核共享，且与内存一致。Invalid代表缓存失效。系统中多个核之间通过快速通道直接通信，比如intel家的QPI，amd家的Hypertransport。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状态即可，此时就可以阻止其他cpu核对该块内存的修改，而不用去锁住整个总线。

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

问题解决

以下问题的回答肯定存在一定的纰漏,会在以后的学习过程中进行解决.
1. 原子操作是什么
某组操作在执行过程中不会被上下文切换行为，比如任务切换，中断处理等行为打断.
2. 原子操作与锁同步和临界区的关联性是什么?[从概念上揭示]
[总结]一个是从时间上限制(某段时间只能做这件事),一个是从空间上限制,即在某段时间虽然能做多件事,但是这多件事只能有一个占用某段空间.
两者可以说是不相关的,但是两者都能够实现一个功能,即多线程或进程之间的同步,但是两者实现的原理不太相似,原子操作是通过控制指令序列执行的原子性,使得指令序列的执行过程中不会出现上下文切换行为，比如任务切换，中断处理,以确保此段指令序列(包括数据操作指令)在某段时间内处理数据操作时只会有一个进程或线程执行该段指令序列,而锁同步则是通过操作系统原语对一段代码空间进行进入性限制.一个是从时间上限制(某段时间只能做这件事),一个是从空间上限制,即在某段时间虽然能做多件事,但是这多件事只能有一个占用某段空间.

文献


[1].spinlock
[2].CAS
[3].Load-link/store-conditional
[4].MESI protocol
[5].Cache coherence
[6].并发编程