【多线程】CAS、ABA问题详解

一、什么是 CAS

CAS：全称 Compare and swap，字⾯意思：⽐较并交换

比较内存和 CPU 中的内容，如果发现相同，就进行交换

• 交换的是内存和另一个寄存器的内容

一个内存的数据和两个寄存器中的数据进行操作（寄存器 1 和寄存器 2）

• 比较内存和寄存器 1 中的值是否相等
• 如果不相等，就无事发生
• 如果相等，就交换内存和寄存器 2 的值
  此处我们只关心内存交换后的内容，不关系寄存器 2 交换后的内容，此处虽说叫做“交换”，实际上，希望达成的效果是“给内存赋值”

二、CAS 伪代码

并不能执行，只是用来表示一下执行的逻辑

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

• address—内存、expectValue—寄存器 1、swapValue—寄存器 2

CAS 的关键不在于这个逻辑是干什么的，而是在于通过“一个 CPU 指令”完成上述一系列的操作

• 一个 CPU 指令说明这是一个原子性的操作，不怕线程安全
• 因此，CAS 给我们编写多线程代码，带来了新的思路——“无锁化编程”

三、CAS 具体使用场景

1. 基于 CAS 实现“原子类”

int/long 等类型在进行 ++ 的时候，都不是原子的

基于 CAS 实现的原子类，可以看作是对 int/Long 等类型进行了封装，从而可以原子的完成++–`的操作

实现 count++操作：

public class Demo1 {  
    //private static int count = 0;  
    private static AtomicInteger count = new AtomicInteger();  
  
    public static void main(String[] args) throws InterruptedException {  
        Thread t1 = new Thread(() -> {  
            for (int i = 0; i < 5000; i++){  
                count.getAndIncrement();  //count++  
//              count.incrementAndGet();  //++count  
//              count.decrementAndGet();  //count--  
//              count.getAndDecrement();  //--count  
//              count.getAndAdd(10);//count+=10  
            }  
        });        
        Thread t2 = new Thread(() -> {  
            for (int i = 0; i < 5000; i++) {  
                count.getAndIncrement();  
            }        
        });        
        t1.start();  
        t2.start();  
        t1.join();  
        t2.join();  
        System.out.println(count);  
    }
}

通过 CAS 实现自增伪代码实现：

class AtomicInteger { 
  private int value; 
  public int getAndIncrement() { 
    //先把内存数据读取到寄存器
    int oldValue = value; 
    //通过CAS比较内存和寄存器1的值是否一样
    while ( CAS(value, oldValue, oldValue+1) != true) { 
      oldValue = value; 
    } 
    return oldValue;
  }
}

• value—内存数据、oldValue—寄存器的数据
• 对比value和oldValue是否相同，若相同，就意味着没有其他线程穿插到这两个代码之间执行，此时就可以安全地修改变量的内容

• 将内存的值和 oldValue+1 进行交换（将+1 后的值赋给内存）

• 如果不相同，那么在上方的赋值和此处的CAS之间有其他的线程穿插执行，并且其他的线程修改了value的值

• 这时，就不会进行 `` 交换操作，而是通过 while 循环再读取一次内存中更新的值，再进行是否相同判断
• 直到相等，完成交换为止

• 之前的线程安全问题，就是别的线程穿插进来，在本线程修改完毕之前，抢先一步修改了值。
• 但是此处，通过 CAS 可以感知到是否有修改
• 直到发现某一次没有人插队，才会进行自增操作

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; 
  } 
}

• owner —用来让锁记录哪个线程持有这个锁，如果为 null，则是处于解锁状态
• Thread.currentThread () —获取到调用 lock 的线程引用
• 对this. owner, null进行比较

• 若相等，则证明此时这个锁处于解锁状态，把 owner 设为当前调用 lock 的这个线程
• 若不相等，则证明此时这把锁已经被别的线程持有了，就进行自旋等待，持续循环等待（直到这把锁被解开，使 owner 变为 null）

三、ABA 问题

CAS 确实很好用，但也存在很关键的问题—— ABA 问题

什么是 ABA

CAS 之所以能保证线程安全，其中很重要的点就是

• 在通过 CAS 比较的过程中，可以确定当前是否有其他线程插入进来执行
• 此处我们是通过判定值是否相同，来区分是否有其他线程修改过
  但值相同 != 没有修改过，因为存在这样的可能，
• 一个线程将值修改变了
• 但又有一个线程将值又修改回去了

和“翻新机”是类似的效果，外表看起来和新的一样，但是内部早已是别人的形状

新机 => 别人使用变成旧的机器 => 商家进行翻新之后变成新的机器

A => B => A

CAS 中确实存在 ABA 问题，但是大多数情况下，ABA 问题并不会带来 bug，但有还是有少数情况会产生 bug

一个非常极端的例子：

考虑实现 ATM 的转账功能，转账过程中，通过 CAS 的方式来实现。

void func(int n) {
  int oldValue = value; //value 就是账户余额
  if(!(CAS(value, oldValue, oldValue - n))) {
    System.out.println("转账失败");
  }else {
    System.out.println("转账成功");
  }
}

按照这个逻辑执行取钱操作，此时账户上有 1000 元，我需要转出 500 元

在实际执行取钱动作的时候，由于响应慢，我多按了几下，就导致在 ATM 中出现了多个线程来执行上述逻辑

如何解决

对于这样的情况，可以通过 CAS 解决——引入“版本号”

ABA 是因为“余额”能加也能减，才会有 ABA 问题

• 如果只能加，不能减，就能解决问题
• 但对于余额来说，本身就是能加能减，就不好对它进行限制
• 我们可以引入“版本号”，是一个整数，但只能增加

void func() {
  int oldVersion = version; //版本号
  if(!CAS(version, oldVersion, oldVersion+1)) {
    转账失败
  }else{
    value-=n;
    转账成功
  }
}

四、相关面试题