CAS算法

作者: hcq0514 | 来源:发表于2019-08-22 16:01 被阅读0次

CAS 是什么

  • CAS 的全称 Compare-And-Swap,它是一条 CPU 并发语句。
  • 它的功能是判断内存某一个位置的值是否为预期,如果是则更改这个值,这个过程就是原子的。
  • CAS 并发原体现在 JAVA 语言中就是 sun.misc.Unsafe 类中的各个方法。调用 UnSafe 类中的 CAS 方法,JVM 会帮我们实现出 CAS 汇编指令。这是一种完全依赖硬件的功能,通过它实现了原子操作。由于 CAS 是一种系统源语,源语属于操作系统用语范畴,是由若干条指令组成,用于完成某一个功能的过程,并且原语的执行必须是连续的,在执行的过程中不允许被中断,也就是说 CAS 是一条原子指令,不会造成所谓的数据不一致的问题。

CAS实现例子,以AtomicInteger为例

// AtomicInteger初始化过程
AtomicInteger atomicInteger = new AtomicInteger(666);

public AtomicInteger(int initialValue) {
        value = initialValue;
}

private volatile int value;
// AtomicInteger执行getAndIncrement();
    public final int getAndIncrement() {
        return unsafe.getAndAddInt(this, valueOffset, 1); 
       //this:当前对象,valueOffset:value的内存地址
    }

    public final int getAndAddInt(Object var1, long var2, int var4) {
        int var5; //期望值
        do {
            var5 = this.getIntVolatile(var1, var2); 
//获取主内存中的value值(因为value为volatile,所以变化是实时可见的)
        } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));
// compareAndSwapInt里会重新再取一次主内存的值,跟var5我们传入的期望值相比较,
// 如果此时期望值跟我们主内存的值相等时(也就是值没有被修改过)才会退出循环,否则重新获取

        return var5;
    }

CAS 的缺点?

  • 循环时间长开销很大
    如果 CAS 失败,会一直尝试,如果 CAS 长时间一直不成功,可能会给 CPU 带来很大的开销(比如线程数很多,每次比较都是失败,就会一直循环),所以希望是线程数比较小的场景。
  • 只能保证一个共享变量的原子操作
    对于多个共享变量操作时,循环 CAS 就无法保证操作的原子性。
  • 引出 ABA 问题

ABA 问题(原子类 AtomicInteger 的 ABA 问题谈一谈?原子更新引用知道吗?)

  • 出现原因:
    CAS 判断的条件是 expect期望值跟当前值相等时,就交换
    假如两个线程同时获取一个值,一个线程T1将A值改为B值然后再改回A值,另一个线程T2执行的比较慢,
    再取的时候T1线程已经执行完了,查询到的还是A值,满足CAS 所以会交换,但其实已经发生了两次交换
  • 实例代码[ABAProblem.class]( AtomicReference为原子变量引用)
        User user = new User().setName("hcq").setAge(24);
        AtomicReference<User> atomicReference = new AtomicReference<>();
        //首先开一个线程来把这个值修改两次
        threadPool.submit(() -> {
            boolean firstCAS = atomicReference.compareAndSet(null, user);
            System.out.println(Thread.currentThread().getName() + ",第一次修改" + firstCAS + ",变量数据" + atomicReference.get());
            boolean secondCAS = atomicReference.compareAndSet(user, null);
            System.out.println(Thread.currentThread().getName() +",第二次修改" + secondCAS + ",变量数据" + atomicReference.get());

        });
        //休眠2秒,保证前面的执行完成
        Thread.sleep(2000);
        boolean threeCAS = atomicReference.compareAndSet(null, user);
        System.out.println(Thread.currentThread().getName() +",第三次修改" + threeCAS + ",变量数据" + atomicReference.get());
  • 执行结果
pool-1-thread-1,第一次修改true,变量数据User(name=hcq, age=24)
pool-1-thread-1,第二次修改true,变量数据null
main,第三次修改true,变量数据User(name=hcq, age=24)

由输出结果可见,thread-1已经将atomicReference改了两次,但是对main线程来说,他最后的值还是null,对于他来说是没有任何改变的。

  • ABA问题解决方案[ABASolution.class](原子时间戳变量)
AtomicStampedReference<Integer> atomicStampedReference = new AtomicStampedReference<>(1, 1);
//这个类的CAS方法是带时间戳判定的。
 public boolean compareAndSet(V   expectedReference,
                                 V   newReference,
                                 int expectedStamp,
                                 int newStamp) {
        Pair<V> current = pair;
        return
            expectedReference == current.reference &&
            expectedStamp == current.stamp &&
            ((newReference == current.reference &&
              newStamp == current.stamp) ||
             casPair(current, Pair.of(newReference, newStamp)));
    }

相关文章

  • 最简单的CAS机制说明

    CAS(Compare-And-Swap) 算法保证数据变量的原子性 CAS 算法是硬件对于并发操作的支持 CAS...

  • CAS(乐观锁)

    CAS乐观锁 CAS算法即是:Compare And Swap,比较并且替换CAS算法存在着三个参数,内存值V,旧...

  • 粒子群优化算法(PSO)基础

    粒子群算法 粒子群算法源于复杂适应系统(Complex Adaptive System,CAS)。CAS理论于19...

  • 深入理解自旋锁

    本文出自:http://blog.onlycatch.com/post/自旋锁 简单回顾一下CAS算法 CAS算法...

  • 自旋锁

    简单回顾一下CAS算法 CAS算法即compare and swap(比较与交换),是一种有名的无锁算法。无锁编程...

  • CAS机制

    CAS(Compare-And-Swap)算法保证数据操作的原子性。 CAS 算法是硬件对于并发操作共享数据的支持...

  • CAS算法和ABA问题

    CAS算法 CAS(Compare And Swap)比较并交换,它是一种算法,体现的是乐观锁的思想,总是认为自己...

  • 【java并发编程实战2】无锁编程CAS与atomic包

    1、无锁编程CAS 1.1、CAS CAS的全称是Compare And Swap 即比较交换,其算法核心思想如下...

  • android 多线程 — CAS 算法 + 原子性操作类

    CAS 也叫无锁算法(Compare and Swap),核心思想是:当多个线程尝试使用 CAS算法同时更新同一个...

  • Java并发基础

    volatile, CAS 非阻塞算法,Treiber 非阻塞算法,Unsafe Volatile volatil...

网友评论

      本文标题:CAS算法

      本文链接:https://www.haomeiwen.com/subject/tpinsctx.html