CAS到底是怎么回事

CAS全称为Compare And Set(比较并交换)

对于现代操作系统而言&＃xff0c;一般都是多核机器&＃xff0c;会存在好几个cpu,而每块cpu都单独有一套缓存和mmu等组件。

多核CPU的好处是能够实现线程级别的并发操作&＃xff0c;极大提高程序执行效率&＃xff0c;但是这也会导致并发问题的产生,如下面这个场景:

关于操作系统进程&＃xff0c;线程和时间片关系&＃xff0c;可以看这篇文章了解一下: Linux系统中 进程 、线程 、时间片的关系&＃xff1f;

两个cpu上并行运行着一个java进程中的两个线程&＃xff0c;这两个线程几乎同时从主存中读取变量i的值&＃xff0c;放入高速缓存中&＃xff0c;然后交给cpu进行自增操作&＃xff0c;操作完后再写回高速缓存,最后再写回主存。

如果cpu要修改的内存地址在高速缓存中存在&＃xff0c;那么称为写命中&＃xff0c;这种情况下&＃xff0c;有两种策略来将高速缓存中修改后的数据写回主存&＃xff0c;分别为:

• 全写法: 当CPU对Cache写命中时&＃xff0c;必须把数据同时写入Cache和主存&＃xff0c;一般使用一个缓存区来存放要写回主存的数据&＃xff0c;然后慢慢写回主存&＃xff0c;此时cpu可以干其他事情&＃xff0c;这个过程由硬件实现。
• 写回法: 当cpu对cache写命中时&＃xff0c;只修改cache的内容&＃xff0c;而不立即写入主存&＃xff0c;只有当此块被换出时才会写回主存。

上面多个cpu同时并发读写同一个内存单元&＃xff0c;显然会导致结果与预期不符&＃xff0c;其问题本质在于对于内存单元的读写操作是非原子性的&＃xff0c;如何保证对内存单元读写操作的原子性&＃xff0c;这就是CAS需要完成的使命。

原子性意味着不能允许多个cpu同时读写同一块内存单元

要避免多个cpu同时读写同一块内存单元&＃xff0c;对于从事上层应用开发的程序员而言&＃xff0c;最先想到的就是加锁&＃xff0c;但是cpu层面的加锁如何实现呢&＃xff1f;

• 更加接近机器层面的语言就是汇编语言了&＃xff0c;我们只需要通过x86汇编语言中提供的lock前缀的指令就可以完成上述加锁功能
• x86汇编中&＃xff0c;如果对一个指令加“lock”前缀&＃xff0c;会发生什么 &＃xff1f;

对于早期的CPU&＃xff0c;总是采用的是锁总线的方式。具体方法是&＃xff0c;一旦遇到了Lock指令&＃xff0c;就由仲裁器选择一个核心独占总线。其余的CPU核心不能再通过总线与内存通讯。从而达到“原子性”的目的。

这种方式的确能解决问题&＃xff0c;但是非常不高效。为了个原子性结果搞得其他CPU都不能干活了。因此从Intel P6 CPU开始就做了一个优化&＃xff0c;改用Ringbus &＃43; MESI协议&＃xff0c;也就是文档里说的cache conherence机制。这种技术被Intel称为“Cache Locking”。

根据文档原文&＃xff1a;如果是P6后的CPU&＃xff0c;并且数据已经被CPU缓存了&＃xff0c;并且是要写回到主存的&＃xff0c;则可以用cache locking处理问题。否则还是得锁总线。因此&＃xff0c;lock到底用锁总线&＃xff0c;还是用cache locking&＃xff0c;完全是看当时的情况。当然能用后者的就肯定用后者。

MESI大致的意思是&＃xff1a;若干个CPU核心通过ringbus连到一起。每个核心都维护自己的Cache的状态。如果对于同一份内存数据在多个核里都有cache&＃xff0c;则状态都为S&＃xff08;shared&＃xff09;。一旦有一核心改了这个数据&＃xff08;状态变成了M&＃xff09;&＃xff0c;其他核心就能瞬间通过ringbus感知到这个修改&＃xff0c;从而把自己的cache状态变成I&＃xff08;Invalid&＃xff09;&＃xff0c;并且从标记为M的cache中读过来。同时&＃xff0c;这个数据会被原子的写回到主存。最终&＃xff0c;cache的状态又会变为S。

这相当于给cache本身单独做了一套总线&＃xff08;要不怎么叫ring bus&＃xff09;&＃xff0c;避免了真的锁总线。

回到CAS。

我们一般说的CAS在x86的大概写法是

lock cmpxchg a, b, c


对于一致性来讲&＃xff0c;“lock”前缀是起关键作用的指令。cas的实现用了lock cmpxchg指令。cmpxchg指令涉及一次内存读和一次内存写&＃xff0c;需要lock前缀保证中间不会有其它cpu写这段内存。

CAS的特性使得他称为实现任何高层“锁”的必要的构建。几乎所有的“锁”&＃xff0c;如Mutex&＃xff0c;ReentrantLock等都得用CAS让线程先原子性的抢到一个东西&＃xff08;比如一个队列的头部&＃xff09;&＃xff0c;然后才能维护其他锁相关的数据。并且很有意思的是&＃xff0c;如果一个竞争算法只用到了CAS&＃xff0c;却没有让线程“等待”&＃xff0c;就会被称为“无锁算法”。CPU会不会有点小郁闷……

实际上CAS和cmpxchg压根就没处理过ABA问题。严格来说CAS就不会有ABA的问题&＃xff0c;它只是一个简单的&＃xff0c;原子的"比较-设置值"的指令而已。

会出ABA问题的是这种CAS的用法&＃xff1a;

var curVal &＃61; getValue();
var newVal &＃61; modify(curVal);
compareAndSwap(getValueAddr(), curVal, newVal); // 这里是CAS


即这个代码的第一句和第三句可能看到的curVal是一样的&＃xff0c;但是有可能造这个curVal在另一个线程ABA了。

如果真的需要解决ABA问题&＃xff0c;需要上层代码来处理&＃xff0c;比如

• 把value和version放到一起形成一个变量的值&＃xff08;比如 "62&＃64;v1“&＃xff09;&＃xff0c;然后对这个变量的值做CAS。这种比较适合值本身比较简单的场景。
• 把value和version包一个对象&＃xff0c;然后对对象的引用做CAS&＃xff08;Java的AtomicStampedReference就是这么干的&＃xff09;。

现实工程当中&＃xff0c;绝大部分情况下&＃xff0c;都不需要考虑ABA问题。

CPU锁和应用层的锁要解决的问题不一样。

CPU锁主要解决的是多个核心并发访问/修改同一块内存的问题。所以有锁总线和MESI协议来做。对于上层主要的抽象就是CAS。主要的招数就是用CAS&＃43;循环来抢东西。如果抢不到就只能&＃xff1a;

• 继续循环下去玩命抢&＃xff08;这时会空耗CPU&＃xff09;
• 不抢了&＃xff0c;回复给上层代码“抢不到”。

应用层的锁存在了“进程/线程“的概念&＃xff08;下文统一都说进程&＃xff09;。解决的是多个进程并发访问同一块内存的问题。比起CPU的层级来说&＃xff0c;应用层的锁可以多一个招数&＃xff0c;叫做“让当前进程不可调度“。这个是OS提供的支持。

因此在应用层的层次上你可以定义一个高级的“锁”&＃xff0c;大概执行这样一个抢锁流程

1. 尝试用CAS抢到锁
2. 如果抢不到&＃xff0c;则回到1重试
3. 如果抢了几十次都还抢不到&＃xff0c;就把当前进程&＃xff08;的信息&＃xff09;尝试挂到一个等待队列上&＃xff08;当然挂的过程还是要CAS&＃xff09;
4. 把当前进程设定为不可调度&＃xff0c;这样OS就不会把当前进程调度给CPU执行。&＃xff08;这种情况因为需要做一次系统调用&＃xff0c;所以有比较大的损耗&＃xff0c;一般被称为“重量级锁”)

而当某个进程释放锁时&＃xff0c;他就可以做释放锁的流程

1. 找到释放锁的那个等待队列
2. 把等待队列里第一个等待的进程信息取出来&＃xff0c;并且告诉OS&＃xff0c;这个进程程可以执行了&＃xff08;这里也要做一次系统调用&＃xff09;
3. 这个被复活了的进程一般需要在做一次循环尝试抢锁&＃xff0c;然后就回到了上面的抢锁流程。

简单来说&＃xff0c;CAS是应用层锁的building block。

cas做了锁了总线或缓存行还是volatile做了锁总线或缓存行?