Java多线程基础-12:详解CAS算法

简介: CAS(Compare and Swap)算法是一种无锁同步原语,用于在多线程环境中更新内存位置的值。

一、CAS算法的内容


1、基本思想和步骤


CAS算法的基本思想是,先比较内存M中的值与寄存器A中的值(旧的预期值,expectValue)是否相等,如果相等,则将寄存器B中的值(新值,swapValue)写入内存;如果不相等,则不做任何操作。整个过程是原子的,不会被其他并发操作中断。



这里虽然涉及到内存与寄存器值的“交换”,但更多时候我们并不关心寄存器中存的值是什么,而是更关心内存中的数值(内存中存的值即变量的值)。所以这里的“交换”可以不用看成交换,直接看成是赋值操作就行,即把寄存器B中的值直接赋值到内存M中了。


CAS 操作包括三个操作数:一个内存位置(通常是共享变量)、期望的值和新值。CAS 操作的执行过程如下:


1. 读取内存位置的当前值。


2.比较当前值与期望的值是否相等。


3.如果相等,将新值写入内存位置;否则,操作失败。


2、CAS伪代码(如果把CAS想象成一个函数


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



上面给出的代码只是伪代码,并不是真实的CAS代码。事实上,CAS操作是一条由CPU硬件支持的、原子的硬件指令,这一条指令就能完成上述这一段代码的功能。


“一条指令”和“一段代码”的最大区别在于原子性。上述这一段伪代码不是原子的,运行过程中可能随着线程的调度有概率产生线程安全问题;但原子的指令不会有线程安全问题。


同时,CAS也不会有内存可见性的问题,内存可见性相当于是编译器把一系列指令的进行了调整,把读内存的指令调整成读寄存器的指令。但CAS本身就是指令级别读取内存的操作,所以不会有内存可见性带来的线程不安全问题。


因此,CAS可以做到不加锁也能一定程度地保证线程安全。这样就引申出基于CAS算法的一系列操作。


二、CAS算法的应用


CAS可以用于实现无锁编程。实现原子类和实现自旋锁就是无锁编程的其中两个方式。


1、实现原子类


标准库 java.util.concurrent.atomic 包中有很多类使用了很高效的机器级指令(而不是使用锁) 来保证其他操作的原子性。


例如, Atomiclnteger 类提供了方法 incrementAndGet、getAndIncrement 和 decrementAndGet、getAndDecrement,它们分别以原子方式将一个整数自增或自减。


        AtomicInteger num = new AtomicInteger(0);
        Thread t1 = new Thread(()->{
                //num++
                num.getAndIncrement();
                //++num
                num.incrementAndGet();
                //num--
                num.getAndDecrement();
                //--num
                num.decrementAndGet();
        });


例如,可以安全地生成数值序列,如下所示


1.​
Plain Text
自动换行
xxxxxxxxxx
1
import java.util.concurrent.atomic.AtomicInteger;
2
 
3
public class Test2 {
4
    public static void main(String[] args) throws InterruptedException {
5
        AtomicInteger num = new AtomicInteger(0);
6
        Thread t1 = new Thread(()->{
7
            for (int i = 0; i < 50000; i++) {
8
                //num++
9
                num.getAndIncrement();
10
            }
11
        });
12
        Thread t2 = new Thread(()->{
13
            for (int i = 0; i < 50000; i++) {
14
                //num++
15
                num.getAndIncrement();
16
            }
17
        });
18
 
19
        t1.start();
20
        t2.start();
21
 
22
        t1.join();
23
        t2.join();
24
        System.out.println(num.get());
25
    }
26
}

为卡片添加间距 
删除卡片


运行结果:最终num的值正好是100000



这是因为 getAndIncrement() 方法以原子的方式获得 num 的值,并将 num 自增。也就是说, 获得值、 增 1 并设置然后生成新值的操作不会中断。可以保证即使是多个线程并发地访问同一个实例,也会计算并返回正确的值。


通过查看源码可以发现,getAndIncrement() 方法并没有用到加锁(synchronized):



但再进入 getAndAddInt 方法可以发现,其中用到了 CAS 算法:



再进入 compareAndSwapInt 方法后会发现,这是一个由 native 修饰的方法。CAS算法的实现依赖于底层硬件和操作系统提供的原子操作支持,因此它是更偏向底层的操作。


补充 - 与之形成对比的线程不安全的案例是:


下面就是一个线程不安全的例子。该代码中创建了一个counter变量,同时分别创建了两个线程t1和t2,让这两个线程针对同一个counter令其自增5w次。


class Counter {
    private int count = 0;
 
    //让count增加
    public void add() {
        count++;
    }
 
    //获得count
    public int get() {
        return count;
    }
}
public class Test {
    public static void main(String[] args) throws InterruptedException {
        Counter counter = new Counter();
 
        // 创建两个线t1和t2,让这两个线程分别对同一个counter自增5w次
        Thread t1 = new Thread(() -> {
            for (int i = 0; i < 50000; i++) {
                counter.add();
            }
        });
 
        Thread t2 = new Thread(() -> {
            for (int i = 0; i < 50000; i++) {
                counter.add();
            }
        });
 
        t1.start();
        t2.start();
 
        // main线程等待两个线程都执行结束,然后再查看结果
        t1.join();
        t2.join();
 
        System.out.println(counter.get());
    }
}


按理来说,最终输出counter的结果应当是10w次。但我们运行程序后发现,不但结果不是10w,而且每次运行的结果都不一样——实际结果看起来像一个随机值。



由于线程的随即调度,count++这一语句并不是原子的,它本质上是由3个CPU指令构成:


  1. load。把内存中的数据读取到CPU寄存器中。


  1. add。把寄存器中的值进行 +1 运算。


  1. save。把寄存器中的值写回到内存中。


CPU需要分三步走才能完成这一自增操作。如果是单线程中,这三步没有任何问题;但在多线程编程中,情况就会不同。由于多线程调度顺序是不确定的,实际执行过程中,这俩线程的count++操作的指令排列顺序会有很多种不同的可能:



上面只列出了非常小的一部分可能,实际中有更多可能的情况。而不同的排列顺序下,程序执行的结果可能是截然不同的!比如以下两种情况的执行过程:




因此, 由于实际中线程的调度顺序是无序的,我们并不能确定这俩线程在自增过程中经历了什么,也不能确定到底有多少次指令是“顺序执行”的,有多少次指令是“交错执行”的。最终得到的结果也就成了变化的数值,count一定是小于等于10w的


(来自文章:Java多线程基础-6:线程安全问题及解决措施)


*伪代码实现原子类


代码:


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



上面代码中,虽然看似刚刚把 value 赋值给 oldValue 后,就紧接着比较 value 和 oldvalue是否相等,但比较结果依然是可能不相等的。因为这是在多线程的环境下。value 是成员变量,如果两个线程同时调用 getAndIncrement 方法,就有可能出现不相等的情况。其实此处的 CAS 就是在确认当前 value 是否变过。如果没变过,才能自增;如果变过了,就先更新值,再自增。


之前的线程不安全,有一个很大的原因就是一个线程不能及时感知到另一个线程对内存的修改:




之前线程不安全,是因为t1在自增的时候先读后自增。此时在t1自增之前,t2已经自增过了,t1是却还是在一开始的0的基础上自增的,此时就会出现问题。


但CAS操作使得t1在执行自增之前,先比较一下寄存器和内存中的值是否一致,只有一致了才执行自增,否则就重新将内存中的值向寄存器同步一下。


这个操作不涉及阻塞等待,因此会比之前加锁的方案快很多。


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的ABA问题


CAS的ABA问题是使用CAS时遇到的一个经典的问题。


已知 CAS 的关键是对比内存和寄存器中的值,看二者是否相同,就是通过这个比较来判断内存中的值是否发生过改变。然而,万一对比的时候是相同的,但其实内存中的值并不是没变过,而是从A值变成B值后又变回了A值呢?


此时,有一定概率会出问题。这样的情况就叫做ABA问题。CAS只能对比值是否相同,但不能确定这个值是否中间发生过改变。




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


1、ABA问题引发的BUG


其实大部分的情况下ABA问题影响并不大。但是不排除一些特殊情况:


假设小明有 100 存款。他想从 ATM 取 50 块钱。取款机创建了两个线程,并发地来执行 -50


(从账户中扣款50块钱)这一操作。


我们期望两个线程中一个线程执行 -50 成功,另一个线程 -50 失败。如果使用 CAS 的方式来完成这个扣款过程,就可能出现问题。


正常的过程


存款 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 问题引起的。


2、解决ABA问题——使用版本号


ABA 问题的关键是内存中共享变量的值会反复横跳。如果约定数据只能单方向变化,问题就迎刃而解了。


由此引入“版本号” 这一概念。约定版本号只能递增(每次修改变量时,都会增加一个版本号)。而且每次 CAS 在对比的时候,对比的就不是数值本身,而是对比版本号。这样其他线程在进行 CAS 操作时可以检查版本号是否发生了变化,从而避免 ABA 问题的发生。


(以版本号为基准,而不以变量数值为基准。约定了版本号只能递增,就不会出现ABA这样的反复横跳问题。)


不过在实际情况中,大部分情况下即使遇到了ABA问题,也没有什么关系。知晓版本号可以用来解决ABA问题即可。


相关文章
|
25天前
|
存储 算法 安全
探究‘公司禁用 U 盘’背后的哈希表算法与 Java 实现
在数字化办公时代,信息安全至关重要。许多公司采取“禁用U盘”策略,利用哈希表算法高效管理外接设备的接入权限。哈希表通过哈希函数将设备标识映射到数组索引,快速判断U盘是否授权。例如,公司预先将允许的U盘标识存入哈希表,新设备接入时迅速验证,未授权则禁止传输并报警。这有效防止恶意软件和数据泄露,保障企业信息安全。 代码示例展示了如何用Java实现简单的哈希表,模拟公司U盘管控场景。哈希表不仅用于设备管理,还在文件索引、用户权限等多方面助力信息安全防线的构建,为企业数字化进程保驾护航。
|
4月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
115 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
11天前
|
算法 安全 Java
Java线程调度揭秘:从算法到策略,让你面试稳赢!
在社招面试中,关于线程调度和同步的相关问题常常让人感到棘手。今天,我们将深入解析Java中的线程调度算法、调度策略,探讨线程调度器、时间分片的工作原理,并带你了解常见的线程同步方法。让我们一起破解这些面试难题,提升你的Java并发编程技能!
47 16
|
5月前
|
安全 Java API
JAVA并发编程JUC包之CAS原理
在JDK 1.5之后,Java API引入了`java.util.concurrent`包(简称JUC包),提供了多种并发工具类,如原子类`AtomicXX`、线程池`Executors`、信号量`Semaphore`、阻塞队列等。这些工具类简化了并发编程的复杂度。原子类`Atomic`尤其重要,它提供了线程安全的变量更新方法,支持整型、长整型、布尔型、数组及对象属性的原子修改。结合`volatile`关键字,可以实现多线程环境下共享变量的安全修改。
|
2月前
|
算法 Java 数据库
理解CAS算法原理
CAS(Compare and Swap,比较并交换)是一种无锁算法,用于实现多线程环境下的原子操作。它通过比较内存中的值与预期值是否相同来决定是否进行更新。JDK 5引入了基于CAS的乐观锁机制,替代了传统的synchronized独占锁,提升了并发性能。然而,CAS存在ABA问题、循环时间长开销大和只能保证单个共享变量原子性等缺点。为解决这些问题,可以使用版本号机制、合并多个变量或引入pause指令优化CPU执行效率。CAS广泛应用于JDK的原子类中,如AtomicInteger.incrementAndGet(),利用底层Unsafe库实现高效的无锁自增操作。
理解CAS算法原理
|
2月前
|
安全 算法 Java
Java CAS原理和应用场景大揭秘:你掌握了吗?
CAS(Compare and Swap)是一种乐观锁机制,通过硬件指令实现原子操作,确保多线程环境下对共享变量的安全访问。它避免了传统互斥锁的性能开销和线程阻塞问题。CAS操作包含三个步骤:获取期望值、比较当前值与期望值是否相等、若相等则更新为新值。CAS广泛应用于高并发场景,如数据库事务、分布式锁、无锁数据结构等,但需注意ABA问题。Java中常用`java.util.concurrent.atomic`包下的类支持CAS操作。
71 2
|
4月前
|
算法 Java 数据中心
探讨面试常见问题雪花算法、时钟回拨问题,java中优雅的实现方式
【10月更文挑战第2天】在大数据量系统中,分布式ID生成是一个关键问题。为了保证在分布式环境下生成的ID唯一、有序且高效,业界提出了多种解决方案,其中雪花算法(Snowflake Algorithm)是一种广泛应用的分布式ID生成算法。本文将详细介绍雪花算法的原理、实现及其处理时钟回拨问题的方法,并提供Java代码示例。
131 2
|
4月前
|
算法 Java
介绍一下CAS算法的实现原理
【10月更文挑战第20天】介绍一下CAS算法的实现原理
66 0
|
4月前
|
安全
【多线程】CAS、ABA问题详解
【多线程】CAS、ABA问题详解
44 0
|
6月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
70 6