代码编织梦想

目录

1. 什么是 CAS

2. CAS伪代码 

3. CAS 的应用

3.1 实现原子类

3.2 实现自旋锁

4. CAS的ABA问题(面试常问) 

4.1 ABA 问题

4.2 ABA问题解决方案


1. 什么是 CAS

CAS: 全称Compare and swap,字面意思:”比较并交换“.

一个 CAS 涉及到以下操作:

我们假设内存中的原数据V,旧的预期值A,需要修改的新值B。

  • 1. 比较 A 与 V 是否相等。(比较)
  • 2. 如果比较相等,将 B 写入 V。(交换)
  • 3. 返回操作是否成功。

2. CAS伪代码 

下面写的代码不是原子的, 真实的 CAS 是一个原子的硬件指令完成的. 这个伪代码只是辅助理解CAS 的工作流程.

 

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

3. CAS 的应用

3.1 实现原子类

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

public class AtomicIntegerTest {
    public static void main(String[] args) throws InterruptedException {
        AtomicInteger num = new AtomicInteger(0);
        Thread t1 = new Thread(()->{
            for (int i = 0; i < 5000; i++) {
                // num++
                num.getAndIncrement();

                // num--
                // num.getAndDecrement();

                // --num
                //num.decrementAndGet();

                // ++num
                //num.incrementAndGet();
            }
        });

        Thread t2 = new Thread(()->{
            for (int i = 0; i < 5000; i++) {
                // num++
                num.getAndIncrement();
            }
        });
        t1.start();
        t2.start();
        t1.join();
        t2.join();
        System.out.println(num.get());
    }
}

两个线程同时调用 getAndIncrement

  • 1) 两个线程都读取 value 的值到 oldValue 中. (oldValue 是一个局部变量, 在栈上. 每个线程有自己的栈)
  • 2) 线程1 先执行 CAS 操作. 由于 oldValue 和 value 的值相同, 直接进行对 value 赋值.
  • 3) 线程2 再执行 CAS 操作, 第一次 CAS 的时候发现 oldValue 和 value 不相等, 不能进行赋值. 因此需要进入循环.在循环里重新读取 value 的值赋给 oldValue
  • 4) 线程2 接下来第二次执行 CAS, 此时 oldValue 和 value 相同, 于是直接执行赋值操作.
  • 5) 线程1 和 线程2 返回各自的 oldValue 的值即可.

3.2 实现自旋锁

 伪代码:

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本身就是一个CPU指令,编译器是操作不了的,因而不会有什么内存可见性问题的出现.

内存可见性是:编译器将指令进行调整,把读内存的指令调整为读编译器的指令.

4. CAS的ABA问题(面试常问) 

4.1 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 呢?

生活中的例子

假设 滑稽老哥 有 100 存款. 滑稽想从 ATM 取 50 块钱. 取款机创建了两个线程, 并发的来执行 -50
操作.
我们期望一个线程执行 -50 成功, 另一个线程 -50 失败.
如果使用 CAS 的方式来完成这个扣款过程就可能出现问题.


正常的过程
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 问题搞的鬼!! 

4.2 ABA问题解决方案

1.约定数据只能进行单方向进行操作 (这个约束性太强)

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

  1. CAS 操作在读取旧值的同时, 也要读取版本号.
  2. 真正修改的时候
  •                 如果当前版本号和读到的版本号相同, 则修改数据, 并把版本号 + 1.
  •                 如果当前版本号高于读到的版本号. 就操作失败(认为数据已经被修改过了).
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_46114074/article/details/130843092