586之前的CPU, 会通过LOCK锁总线的形式来实现原子操作. 686开始则提供了存储一致性(Cache coherence), 这是多处理的基础, 也是原子操作的基础.
1. 存储的粒度
存储的组织形式(粒度)是以CacheLine为单位的, 通常为64字节甚至更高(早期也有32字节的). 然后几组CacheLine组成一个小的LRU(或者其他替换规则).
2. 协议
存储一致性(CC)一般是通过MESI协议, 以及后续的变种协议, 例如Intel的MESIF协议和AMD的MOESI协议, 来实现的.
以MESI协议为例:
Modified: 独占CacheLine, 已经修改了, 但是还未同步到主存
Exclusive: 独占, 并且和主存一致
Shared : 共享的, 其他core也拥有该CacheLine, 并且与主存中一致
Invalid: 表示该CacheLine不可用
3. 通讯
有了协议, 那么就需要通讯来实现协议(存储的状态). 通讯有两种, 一种是广播/侦听, 一种是目录式.
广播/侦听顾名思义就是存储状态的变更, 会被广播到其他core上面去, 进而去维护CacheLine的状态. 很明显这种方式会浪费大量的流量, 而且难以扩展, CPU核数多了, 总线就是明显的瓶颈.
目录式, 就是把改变通知给具体的core, 从而避免广播. 但是考虑一种极端情况, 如果很多个core都在访问同一个CacheLine, 那还是不能避免(事实上的)广播. 所以, 多线程编程时, 共享同一个CacheLine不是一个好的选择.
有了上面的东西, 现在我们来考虑原子操作的实现:
1. 原子的Load/Store
由于CPU对缓存的管理是以CacheLine为单位的, 所以在一个CacheLine内load/store实际上都是原子的. Load和Store一个8字节对象, 不可能高4位和低4位是分开操作的(从而搞成俩值).
但是光有这个实际上还不够, CPU对CacheLine的修改不是立即写到主存里面去, 所以其他Core看到的值就有可能是老的值, 所以这时候还需要fence来读到最新的值; 至于写, 那一定需要写权限, 即M或者E状态, 而这两个权限里面都有最新的值(只是你刚才读到的不一定是最新的, 所以有可能用老值覆盖了新值).
2. FetchAndAdd
这是比load和store稍微复杂的操作, 实际上是一个复合操作. 但是有了M和E状态, 就很好理解了:
lock(CacheLine) v := load(obj) v += add store(obj, v) release(CacheLine)
x86里面是xadd指令.
3. CompareAndSwap
那么CAS, 也就可以猜出来:
lock(CacheLine)
v := load(obj)
if v != expected {
store(obj, new_value)
}
release(CacheLine)
x86里面是xchg
这里说的lock和release均表示对该CacheLine独占和解出独占的意思.
关于原子操作的原理, 鲜有资料表表示其具体怎么做的, 很有可能是过于偏向于硬件. 但是对MESI等协议的思考, 实际上还是能猜到CPU内部的实现(至少七八不离十). 好在找到两个资料, 一个是<<并行多核体系结构基础>>和<<从鲲鹏920了解现代服务器实现和引用>>. 其中鲲鹏920内存模型章节这么写到:
并行多核体系结构这么写到:
参考:
1) 并行多核体系结构基础