CAS到底是怎么回事
- 为什么需要CAS
- 如何实现CAS
- 关于CAS和ABA
- 关于应用层的锁和CPU的锁的关系
- 参考
为什么需要CAS
CAS全称为Compare And Set(比较并交换)
对于现代操作系统而言一般都是多核机器会存在好几个cpu,而每块cpu都单独有一套缓存和mmu等组件。
多核CPU的好处是能够实现线程级别的并发操作极大提高程序执行效率但是这也会导致并发问题的产生,如下面这个场景:
关于操作系统进程线程和时间片关系可以看这篇文章了解一下: Linux系统中 进程 、线程 、时间片的关系
两个cpu上并行运行着一个java进程中的两个线程这两个线程几乎同时从主存中读取变量i的值放入高速缓存中然后交给cpu进行自增操作操作完后再写回高速缓存,最后再写回主存。
如果cpu要修改的内存地址在高速缓存中存在那么称为写命中这种情况下有两种策略来将高速缓存中修改后的数据写回主存分别为:
- 全写法: 当CPU对Cache写命中时必须把数据同时写入Cache和主存一般使用一个缓存区来存放要写回主存的数据然后慢慢写回主存此时cpu可以干其他事情这个过程由硬件实现。
- 写回法: 当cpu对cache写命中时只修改cache的内容而不立即写入主存只有当此块被换出时才会写回主存。
上面多个cpu同时并发读写同一个内存单元显然会导致结果与预期不符其问题本质在于对于内存单元的读写操作是非原子性的如何保证对内存单元读写操作的原子性这就是CAS需要完成的使命。
原子性意味着不能允许多个cpu同时读写同一块内存单元
如何实现CAS
要避免多个cpu同时读写同一块内存单元对于从事上层应用开发的程序员而言最先想到的就是加锁但是cpu层面的加锁如何实现呢
- 更加接近机器层面的语言就是汇编语言了我们只需要通过x86汇编语言中提供的lock前缀的指令就可以完成上述加锁功能
- x86汇编中如果对一个指令加“lock”前缀会发生什么
对于早期的CPU总是采用的是锁总线的方式。具体方法是一旦遇到了Lock指令就由仲裁器选择一个核心独占总线。其余的CPU核心不能再通过总线与内存通讯。从而达到“原子性”的目的。
这种方式的确能解决问题但是非常不高效。为了个原子性结果搞得其他CPU都不能干活了。因此从Intel P6 CPU开始就做了一个优化改用Ringbus MESI协议也就是文档里说的cache conherence机制。这种技术被Intel称为“Cache Locking”。
根据文档原文如果是P6后的CPU并且数据已经被CPU缓存了并且是要写回到主存的则可以用cache locking处理问题。否则还是得锁总线。因此lock到底用锁总线还是用cache locking完全是看当时的情况。当然能用后者的就肯定用后者。
MESI大致的意思是若干个CPU核心通过ringbus连到一起。每个核心都维护自己的Cache的状态。如果对于同一份内存数据在多个核里都有cache则状态都为Sshared。一旦有一核心改了这个数据状态变成了M其他核心就能瞬间通过ringbus感知到这个修改从而把自己的cache状态变成IInvalid并且从标记为M的cache中读过来。同时这个数据会被原子的写回到主存。最终cache的状态又会变为S。
这相当于给cache本身单独做了一套总线要不怎么叫ring bus避免了真的锁总线。
回到CAS。
我们一般说的CAS在x86的大概写法是
lock cmpxchg a, b, c
对于一致性来讲“lock”前缀是起关键作用的指令。cas的实现用了lock cmpxchg指令。cmpxchg指令涉及一次内存读和一次内存写需要lock前缀保证中间不会有其它cpu写这段内存。
CAS的特性使得他称为实现任何高层“锁”的必要的构建。几乎所有的“锁”如MutexReentrantLock等都得用CAS让线程先原子性的抢到一个东西比如一个队列的头部然后才能维护其他锁相关的数据。并且很有意思的是如果一个竞争算法只用到了CAS却没有让线程“等待”就会被称为“无锁算法”。CPU会不会有点小郁闷……
关于CAS和ABA
实际上CAS和cmpxchg压根就没处理过ABA问题。严格来说CAS就不会有ABA的问题它只是一个简单的原子的"比较-设置值"的指令而已。
会出ABA问题的是这种CAS的用法
var curVal getValue();var newVal modify(curVal);compareAndSwap(getValueAddr(), curVal, newVal); // 这里是CAS
即这个代码的第一句和第三句可能看到的curVal是一样的但是有可能造这个curVal在另一个线程ABA了。
如果真的需要解决ABA问题需要上层代码来处理比如
- 把value和version放到一起形成一个变量的值比如 "62v1“然后对这个变量的值做CAS。这种比较适合值本身比较简单的场景。
- 把value和version包一个对象然后对对象的引用做CASJava的AtomicStampedReference就是这么干的。
现实工程当中绝大部分情况下都不需要考虑ABA问题。
关于应用层的锁和CPU的锁的关系
CPU锁和应用层的锁要解决的问题不一样。
CPU锁主要解决的是多个核心并发访问/修改同一块内存的问题。所以有锁总线和MESI协议来做。对于上层主要的抽象就是CAS。主要的招数就是用CAS循环来抢东西。如果抢不到就只能
- 继续循环下去玩命抢这时会空耗CPU
- 不抢了回复给上层代码“抢不到”。
应用层的锁存在了“进程/线程“的概念下文统一都说进程。解决的是多个进程并发访问同一块内存的问题。比起CPU的层级来说应用层的锁可以多一个招数叫做“让当前进程不可调度“。这个是OS提供的支持。
因此在应用层的层次上你可以定义一个高级的“锁”大概执行这样一个抢锁流程
而当某个进程释放锁时他就可以做释放锁的流程
简单来说CAS是应用层锁的building block。
参考
cas做了锁了总线或缓存行还是volatile做了锁总线或缓存行?