CAS基本概念：

CAS: 全称Compare and swap，字⾯意思:”⽐较并交换“，⼀个 CAS 涉及到以下操作：

1. ⽐较 A 与 V 是否相等。（⽐较）

2. 如果⽐较相等，将 B 写⼊ V。（交换）

3. 返回操作是否成功。 CAS 伪代码

下⾯写的代码不是原⼦的,真实的CAS是⼀个原⼦的硬件指令完成的.这个伪代码只是辅助理解CAS 的⼯作流程.

boolean CAS(address, expectValue, swapValue) {
   if (&address == expectedValue) {
     &address = swapValue;
   return true;
 }
 return false;
}

两种典型的不是"原⼦性"的代码

1. check and set (if 判定然后设定值)[上⾯的CAS伪代码就是这种形式]

2. readandupdate(i++)[之前我们讲线程安全的代码例⼦是这种形式]

当多个线程同时对某个资源进⾏CAS操作，只能有⼀个线程操作成功，但是并不会阻塞其他线程,其他 线程只会收到操作失败的信号。

CAS可以视为是⼀种乐观锁.(或者可以理解成CAS是乐观锁的⼀种实现⽅式)

CAS是怎么实现的：

针对不同的操作系统，JVM⽤到了不同的CAS实现原理，简单来讲：

• java的CAS利⽤的的是unsafe这个类提供的CAS操作；

• unsafe的CAS依赖了的是jvm针对不同的操作系统实现的Atomic::cmpxchg；

• Atomic::cmpxchg的实现使⽤了汇编的CAS操作，并使⽤cpu硬件提供的lock机制保证其原⼦ 性。

简⽽⾔之，是因为硬件予以了⽀持，软件层⾯才能做到。

CAS有哪些应⽤：

1)实现原⼦类

标准库中提供了java.util.concurrent.atomic 包,⾥⾯的类都是基于这种⽅式来实现的. 典型的就是AtomicInteger类.其中的getAndIncrement相当于i++操作.

AtomicInteger atomicInteger = new AtomicInteger(0);
// 相当于 i++ 
atomicInteger.getAndIncrement();

伪代码实现：

class AtomicInteger {
     private int value;
     public int getAndIncrement() {
        int oldValue = value;
        while ( CAS(value, oldValue, oldValue+1) != true) {
          oldValue = value;
        }
        return oldValue;
     }
}

假设两个线程同时调⽤getAndIncrement

1. 两个线程都读取value的值到oldValue中.(oldValue是⼀个局部变量,在栈上.每个线程有⾃⼰的 栈)

2. 线程1先执⾏CAS操作.由于oldValue和value的值相同,直接进⾏对value赋值.

注意:

• CAS是直接读写内存的,⽽不是操作寄存器.

• CAS的读内存,⽐较,写内存操作是⼀条硬件指令,是原⼦的.

3. 线程2再执⾏CAS操作,第⼀次CAS的时候发现oldValue和value不相等,不能进⾏赋值.因此需要 进⼊循环.

在循环⾥重新读取value的值赋给oldValue

4. 线程2接下来第⼆次执⾏CAS,此时oldValue和value相同,于是直接执⾏赋值操作.

5. 线程1和线程2返回各⾃的oldValue的值即可.

通过形如上述代码就可以实现⼀个原⼦类.不需要使⽤重量级锁,就可以⾼效的完成多线程的⾃增操作.

本来checkandset这样的操作在代码⻆度不是原⼦的.但是在硬件层⾯上可以让⼀条指令完成这个 操作,也就变成原⼦的了.

2)实现⾃旋锁

基于CAS实现更灵活的锁,获取到更多的控制权.

⾃旋锁伪代码

public class SpinLock {
       private Thread owner = null;
       public void lock(){
         // 通过 CAS 看当前锁是否被某个线程持有.  
         // 如果这个锁已经被别的线程持有, 那么就⾃旋等待.  
         // 如果这个锁没有被别的线程持有, 那么就把 owner 设为当前尝试加锁的线程.  
         while(!CAS(this.owner, null, Thread.currentThread())){
         }
     }
     public void unlock (){
         this.owner = null;
     }
}

CAS的ABA问题

什么是ABA问题

ABA的问题:

假设存在两个线程t1和t2.有⼀个共享变量num,初始值为A.

接下来,线程t1想使⽤CAS把num值改成Z,那么就需要

• 先读取num的值,记录到oldNum变量中.

• 使⽤CAS判定当前num的值是否为A,如果为A,就修改成Z.

但是,在t1执⾏这两个操作之间,t2线程可能把num的值从A改成了B,⼜从B改成了A

   线程t1的CAS是期望num不变就修改.

但是num的值已经被t2给改了.只不过⼜改成A了.这个时 候t1究竟是否要更新num的值为Z呢?

到这⼀步,t1线程⽆法区分当前这个变量始终是A,还是经历了⼀个变化过程.

这就好⽐,我们买⼀个⼿机,⽆法判定这个⼿机是刚出⼚的新⼿机,还是别⼈⽤旧了,⼜翻新过的⼿机.

ABA问题引来的BUG

⼤部分的情况下,t2线程这样的⼀个反复横跳改动,对于t1是否修改num是没有影响的.但是不排除⼀ 些特殊情况.

正常的过程

1. 存款100.线程1获取到当前存款值为100,期望更新为50;线程2获取到当前存款值为100,期望更 新为50.

2. 线程1执⾏扣款成功,存款被改成50.线程2阻塞等待中.

3. 轮到线程2执⾏了,发现当前存款为50,和之前读到的100不相同,执⾏失败.

异常的过程

1. 存款100.线程1获取到当前存款值为100,期望更新为50;线程2获取到当前存款值为100,期望更 新为50.

2. 线程1执⾏扣款成功,存款被改成50.线程2阻塞等待中.

3. 在线程2执⾏之前,滑稽的朋友正好给滑稽转账50,账⼾余额变成100!!

4. 轮到线程2执⾏了,发现当前存款为100,和之前读到的100相同,再次执⾏扣款操作 这个时候,扣款操作被执⾏了两次!!!都是ABA问题搞的⻤!!

解决⽅案

给要修改的值,引⼊版本号.在CAS⽐较数据当前值和旧值的同时,也要⽐较版本号是否符合预期.

• CAS操作在读取旧值的同时,也要读取版本号.

• 真正修改的时候,

◦ 如果当前版本号和读到的版本号相同,则修改数据,并把版本号+1.

◦ 如果当前版本号⾼于读到的版本号.就操作失败(认为数据已经被修改过了).

这就好⽐,判定这个⼿机是否是翻新机,那么就需要收集每个⼿机的数据,第⼀次挂在电商⽹站上的⼿ 机记为版本1,以后每次这个⼿机出现在电商⽹站上,就把版本号进⾏递增.这样如果买家不在意这是翻 新机,就买.如果买家在意,就可以直接略过.

1. 存款100.线程1获取到存款值为100,版本号为1,期望更新为50;线程2获取到存款值为100,版本 号为1,期望更新为50.

2. 线程1执⾏扣款成功,存款被改成50,版本号改为2.线程2阻塞等待中.

3. 在线程2执⾏之前,滑稽的朋友正好给滑稽转账50,账⼾余额变成100,版本号变成3.

4. 轮到线程2执⾏了,发现当前存款为100,和之前读到的100相同,但是当前版本号为3,之前读到的 版本号为1,版本⼩于当前版本,认为操作失败.

在Java标准库中提供了AtomicStampedReference 类.这个类可以对某个类进⾏包装,在内 部就提供了上⾯描述的版本管理功能.

关于AtomicStampedReference 的具体⽤法此处不再展开.有需要的同学⾃⾏查找⽂档了 解使⽤⽅法即可.

***

1. 讲解下你⾃⼰理解的CAS机制

全称Compareandswap,即"⽐较并交换".相当于通过⼀个原⼦的操作,同时完成"读取内存,⽐较是 否相等,修改内存"这三个步骤.本质上需要CPU指令的⽀撑.

1. ABA问题怎么解决？

给要修改的数据引⼊版本号.在CAS⽐较数据当前值和旧值的同时,也要⽐较版本号是否符合预期.如 果发现当前版本号和之前读到的版本号⼀致,就真正执⾏修改操作,并让版本号⾃增;如果发现当前版 本号⽐之前读到的版本号⼤,就认为操作失败.