详解CAS及ABA问题

简介: 详解CAS及ABA问题


一、什么是CAS

CAS: 全称Compare and swap,字面意思:”比较并交换,一个CAS 涉及到以下操作:

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

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

1.1 CAS 伪代码

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

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

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

CAS 可以视为是一种乐观锁。(或者可以理解成 CAS 是乐观锁的一种实现方式)

1.2 CAS是怎么实现的

针对不同的操作系统,JVM 用到了不同的CAS 实现原理,简单来讲:

  • java CAS 利用的的是 unsafe 这个类提供的 CAS 操作
  • unsafe CAS 依赖了的是 jvm 针对不同的操作系统实现的 Atomic::cmpxchg
  • Atomic::cmpxchg 的实现使用了汇编的 CAS 操作,并使用 cpu 硬件提供的 lock 机制保证其原子性。

简而言之,是因为硬件予以了支持,软件层面才能做到

二、CAS有哪些应用

2.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

① 两个线程都读取value 的值到oldValue 中。(oldValue 是一个局部变量, 在栈上. 每个线程有自己的栈)

线程1 先执行 CAS 操作,由于 oldValue value 的值相同, 直接进行对 value 赋值。

注意:

  • CAS 是直接读写内存的, 而不是操作寄存器
  • CAS 的读内存、 比较、 写内存操作是一条硬件指令, 是原子的

线程2 再执行 CAS 操作, 第一次 CAS 的时候发现 oldValue value 不相等, 不能进行赋值,因此需要进入循环,在循环里重新读取 value 的值赋给 oldValue

线程2 接下来第二次执行 CAS, 此时 oldValue value 相同, 于是直接执行赋值操作

线程1 和 线程2 返回各自的 oldValue 的值即可。

通过形如上述代码就可以实现一个原子类,不需要使用重量级锁, 就可以高效的完成多线程的自增操作。

2.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 问题

3.1 什么是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, 还是经历了一个变化过程:

这就好比, 我们买一个手机, 无法判定这个手机是刚出厂的新手机, 还是别人用旧了, 又翻新过的手机。

3.2 ABA问题引来的BUG

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

假设滑稽老哥有 100 存款, 滑稽想从 ATM 取 50 块钱。取款机创建了两个线程, 并发的来执行 -50 操作,我们期望一个线程执行 -50 成功, 另一个线程 -50 失败。

正常的过程

  • 存款 100,线程1 获取到当前存款值为 100, 期望更新为 50; 线程2 获取到当前存款值为 100, 期望更新为 50。
  • 线程1 执行扣款成功, 存款被改成 50,线程2 阻塞等待中。
  • 轮到线程2 执行了, 发现当前存款为 50, 和之前读到的 100 不相同, 执行失败。

异常的过程

  • 存款 100. 线程1 获取到当前存款值为 100, 期望更新为 50; 线程2 获取到当前存款值为 100, 期望更新为 50
  • 线程1 执行扣款成功, 存款被改成 50,线程2 阻塞等待中
  • 在线程2 执行之前, 滑稽的朋友正好给滑稽转账 50, 账户余额变成 100
  • 轮到线程2 执行了, 发现当前存款为 100, 和之前读到的 100 相同, 再次执行扣款操作

这个时候, 扣款操作被执行了两次!!! 都是 ABA 问题搞的鬼!!

3.3 ABA问题的解决方案

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

  • CAS 操作在读取旧值的同时, 也要读取版本号
  • 真正修改的时候, 如果当前版本号和读到的版本号相同, 则修改数据, 并把版本号 + 1。
  • 如果当前版本号高于读到的版本号,就操作失败(认为数据已经被修改过了)。

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

对比理解上面的转账例子:

假设 滑稽老哥 有 100 存款,滑稽想从 ATM 取 50 块钱,取款机创建了两个线程, 并发的来执行 -50 操作。我们期望一个线程执行 -50 成功, 另一个线程 -50 失败。

为了解决 ABA 问题, 给余额搭配一个版本号, 初始设为 1。

  • 存款 100。 线程1 获取到 存款值为 100, 版本号为 1, 期望更新为 50; 线程2 获取到存款值为 100, 版本号为 1, 期望更新为 50。
  • 线程1 执行扣款成功, 存款被改成 50, 版本号改为2,线程2 阻塞等待中。
  • 在线程2 执行之前, 滑稽的朋友正好给滑稽转账 50, 账户余额变成 100, 版本号变成3。
  • 轮到线程2 执行了, 发现当前存款为 100, 和之前读到的 100 相同, 但是当前版本号为 3, 之前读到的版本号为 1, 版本小于当前版本, 认为操作失败。

🌈🌈🌈好啦,今天的分享就到这里!

🛩️🛩️🛩️希望各位看官读完文章后,能够有所提升。

🎉🎉🎉创作不易,还希望各位大佬支持一下!

✈️✈️✈️点赞,你的认可是我创作的动力!

⭐⭐⭐收藏,你的青睐是我努力的方向!

✏️✏️✏️评论:你的意见是我进步的财富!

目录
相关文章
|
7月前
|
算法 Java
浅谈一下CAS和ABA问题
浅谈一下CAS和ABA问题
74 0
|
存储 资源调度 安全
H3C CAS系列 一、CAS初认识
对于虚拟化,可能第一时间大家想到的是虚拟机,而对于虚拟机大家可能第一时间想到的就是我们大多数人都可能比较熟悉的VMware系列产品,比如常用VMware Workstation Pro 、VMware esxi。 而今天我带大家一起认识一款我们国产的虚拟化软件 H3C CAS。
1779 0
|
2月前
|
安全
【多线程】CAS、ABA问题详解
【多线程】CAS、ABA问题详解
22 0
|
4月前
|
Java
JUC(10)深入理解CAS和ABA
这篇文章深入探讨了Java中的CAS(Compare-And-Swap,比较并交换)操作,解释了CAS的工作原理、应用场景以及存在的循环耗时、单变量原子性保证和ABA问题等缺点,并介绍了如何使用原子引用和版本号来解决ABA问题。
JUC(10)深入理解CAS和ABA
|
7月前
|
Java API
CAS的超~详细介绍
CAS的超~详细介绍
|
7月前
|
算法 Java 关系型数据库
CAS
本文主要讲解java中cas的概念及原理
68 0
解决CAS机制中ABA问题的AtomicStampedReference详解
AtomicStampedReference是一个带有时间戳的对象引用,能很好的解决CAS机制中的ABA问题,这篇文章将通过案例对其介绍分析。
306 0
解决CAS机制中ABA问题的AtomicStampedReference详解
什么是 CAS? CAS 有哪些缺点?ABA 问题是什么?
什么是 CAS? CAS 有哪些缺点?ABA 问题是什么?
211 0
|
安全 API
对CAS的理解
对CAS的理解