CAS算法-实现原理

逍遥壮士

发布于 2022-12-01 15:39:41

3050

发布于 2022-12-01 15:39:41

文章被收录于专栏：技术趋势

CAS是什么？

CAS的全称为Compare and swap 比较并交换。CAS又经常被称为乐观锁，主要的三个变量，内存值V，旧的预期值P，需要修改的新值N，原理就是：当 P等于V ，则将 N值赋给 V;

（个人理解：当你修改密码时，你的旧密码跟你输入的一致才能更换！）

‍

CAS解决了什么问题？

解决并发访问中无锁的非阻塞算法的实现。

CAS存在什么问题？

ABA问题：添加版本号解决;其实就是乐观锁;

解决方案:通过添加版本号来解决。

内存开销大：若并发过大，会导致内存开销很大;

CAS有哪些应用场景？

jdk默认自带的Atomick开头的实现类底层都是使用了CAS算法;

自旋锁的实现，底层也是通过CAS轮询的方式进行实现;

cas的实现

存在ABA问题的实现方式:

/**
 * @author: csh
 * @Date: 2022/8/6 21:05
 * @Description: cas工具类 该类存在一个缺陷，没有版本控制会导致aba问题
 */
public class CasV1 {
    //内存的值
    private int value;
    //获取值
    public synchronized int getValue() {
        return value;
    }

    //对比值并且设置值
    public synchronized int compareAndSwap(int defaultValue,int newValue){
        int oldValue = value;
        if(oldValue == defaultValue){
            this.value = newValue;
        }
        return oldValue;
    }

    //对比值
    public synchronized boolean compareAndSet(int defaultValue,int newValue){
        return defaultValue==compareAndSwap(defaultValue,newValue);
    }
}
}

验证

/**
 * @author: csh
 * @Date: 2022/8/6 21:03
 * @Description:cas实现验证
 */
public class CasStudy {
    public static void main(String[] args) {
        CasV1 casV1 = new CasV1();
        for (int i = 0; i < 100; i++) {
            new Thread(new Runnable() {
                @Override
                public void run() {
                    int defaultValue = casV1.getValue();
                    int newValue = (int) (Math.random() * 10000);
                    boolean setResult = casV1.compareAndSet(defaultValue,newValue );
                    System.out.println("新值："+newValue+"设置结果为：" + setResult);
                }
            }).start();
        }
    }
}

结果

新值：2558设置结果为：true
新值：6016设置结果为：true
新值：6498设置结果为：false
新值：5326设置结果为：false
新值：9294设置结果为：true
新值：7897设置结果为：true
新值：6352设置结果为：true
新值：8844设置结果为：false
新值：1935设置结果为：true
新值：1502设置结果为：false
新值：8283设置结果为：false
新值：943设置结果为：true
新值：1600设置结果为：false
新值：7259设置结果为：true
新值：8898设置结果为：false
新值：9597设置结果为：false
新值：8883设置结果为：true
新值：4458设置结果为：true
新值：7120设置结果为：true
新值：5546设置结果为：false
新值：2138设置结果为：true
新值：8985设置结果为：false
新值：5666设置结果为：true
新值：3799设置结果为：false
新值：2267设置结果为：true
新值：1585设置结果为：false
新值：4961设置结果为：false
新值：9770设置结果为：false
新值：4449设置结果为：true
新值：4370设置结果为：true
新值：7385设置结果为：true
新值：9800设置结果为：true
新值：7130设置结果为：true
新值：7106设置结果为：true
新值：8088设置结果为：true
新值：894设置结果为：false
新值：639设置结果为：true
新值：7351设置结果为：true
新值：1438设置结果为：true
新值：2947设置结果为：true
新值：9486设置结果为：true
新值：845设置结果为：true
新值：7280设置结果为：true
新值：664设置结果为：true
新值：1971设置结果为：true
新值：6174设置结果为：true
新值：3707设置结果为：true
新值：8093设置结果为：true
新值：3523设置结果为：true
新值：8760设置结果为：true
新值：5516设置结果为：true
新值：4813设置结果为：true
新值：9809设置结果为：true
新值：6009设置结果为：true
新值：9110设置结果为：true
新值：4006设置结果为：true
新值：5954设置结果为：true
新值：4544设置结果为：true
新值：3239设置结果为：true
新值：7333设置结果为：true
新值：3658设置结果为：true
新值：5678设置结果为：true
新值：3892设置结果为：true
新值：1269设置结果为：true
新值：139设置结果为：true
新值：5508设置结果为：true
新值：4191设置结果为：true
新值：2466设置结果为：true
新值：319设置结果为：true
新值：1743设置结果为：true
新值：9549设置结果为：true
新值：75设置结果为：true
新值：4112设置结果为：true
新值：334设置结果为：true
新值：5523设置结果为：true
新值：3719设置结果为：true
新值：2367设置结果为：true
新值：2669设置结果为：true
新值：819设置结果为：true
新值：6787设置结果为：true
新值：2509设置结果为：true
新值：4291设置结果为：true
新值：735设置结果为：true
新值：6104设置结果为：true
新值：354设置结果为：true
新值：6324设置结果为：true
新值：6938设置结果为：true
新值：630设置结果为：true
新值：2881设置结果为：true
新值：6367设置结果为：true
新值：7941设置结果为：true
新值：3855设置结果为：true
新值：7853设置结果为：true
新值：6457设置结果为：true
新值：901设置结果为：true
新值：6800设置结果为：true
新值：9424设置结果为：true
新值：1911设置结果为：true
新值：1131设置结果为：true
新值：91设置结果为：true

解决ABA问题的版本。

package com.hong.arithmetic.cas;

import java.util.concurrent.atomic.AtomicReference;

/**
 * @author: csh
 * @Date: 2022/8/6 21:05
 * @Description: cas工具类 通过jdk自带AtomicReference 实现
 */
public class CasV2 {

    public CasV2() {
    }

    public CasV2(AtomicReference<Integer> value) {
        this.value = value;
    }

    //内存的值
    AtomicReference<Integer> value;

    //获取值
    public Integer getValue() {
        return value.get();
    }

    //对比值
    public boolean compareAndSet(int defaultValue, int newValue) {
        return value.compareAndSet(defaultValue, newValue);
    }


}

运行

//解决ABA问题的版本
CasV2 casV2 = new CasV2(new AtomicReference<>(10));
for (int i = 0; i < 100; i++) {
    new Thread(new Runnable() {
        @Override
        public void run() {
            int defaultValue = casV2.getValue();
            int newValue = (int) (Math.random() * 10000);
            boolean setResult = casV2.compareAndSet(defaultValue,newValue );
            System.out.println("ABA版本新值："+newValue+"设置结果为：" + setResult);
        }
    },"ABA").start();
}

结果

ABA版本新值：8648设置结果为：false
ABA版本新值：1194设置结果为：false
ABA版本新值：7614设置结果为：false
ABA版本新值：2322设置结果为：false
ABA版本新值：7366设置结果为：true
ABA版本新值：1427设置结果为：false
ABA版本新值：2877设置结果为：false
ABA版本新值：5098设置结果为：false
ABA版本新值：1592设置结果为：false
ABA版本新值：2739设置结果为：false
ABA版本新值：1654设置结果为：false
ABA版本新值：8171设置结果为：false
ABA版本新值：2893设置结果为：false
ABA版本新值：3774设置结果为：false
ABA版本新值：8768设置结果为：false
ABA版本新值：3924设置结果为：false
ABA版本新值：397设置结果为：false
ABA版本新值：6727设置结果为：false
ABA版本新值：1518设置结果为：false
ABA版本新值：2734设置结果为：false
ABA版本新值：5193设置结果为：false
ABA版本新值：9006设置结果为：false
ABA版本新值：2832设置结果为：false
ABA版本新值：1447设置结果为：false
ABA版本新值：2595设置结果为：false
ABA版本新值：1559设置结果为：false
ABA版本新值：3129设置结果为：false
ABA版本新值：2254设置结果为：false
ABA版本新值：420设置结果为：false
ABA版本新值：2362设置结果为：false
ABA版本新值：3229设置结果为：false
ABA版本新值：4724设置结果为：false
ABA版本新值：5974设置结果为：false
ABA版本新值：4991设置结果为：false
ABA版本新值：1195设置结果为：false
ABA版本新值：4314设置结果为：false
ABA版本新值：9551设置结果为：false
ABA版本新值：1287设置结果为：false
ABA版本新值：4683设置结果为：false
ABA版本新值：1418设置结果为：false
ABA版本新值：3393设置结果为：false
ABA版本新值：7038设置结果为：false
ABA版本新值：7149设置结果为：false
ABA版本新值：5323设置结果为：false
ABA版本新值：3281设置结果为：false
ABA版本新值：5904设置结果为：false
ABA版本新值：8933设置结果为：false
ABA版本新值：5726设置结果为：false
ABA版本新值：8065设置结果为：false
ABA版本新值：5671设置结果为：false
ABA版本新值：2667设置结果为：false
ABA版本新值：1780设置结果为：false
ABA版本新值：9494设置结果为：false
ABA版本新值：664设置结果为：false
ABA版本新值：264设置结果为：false
ABA版本新值：7175设置结果为：false
ABA版本新值：3667设置结果为：false
ABA版本新值：8690设置结果为：false
ABA版本新值：3084设置结果为：false
ABA版本新值：3851设置结果为：false
ABA版本新值：1720设置结果为：false
ABA版本新值：9836设置结果为：false
ABA版本新值：4408设置结果为：false
ABA版本新值：308设置结果为：false
ABA版本新值：1583设置结果为：false
ABA版本新值：5942设置结果为：false
ABA版本新值：8630设置结果为：false
ABA版本新值：4310设置结果为：false
ABA版本新值：502设置结果为：false
ABA版本新值：1471设置结果为：false
ABA版本新值：6506设置结果为：false
ABA版本新值：5214设置结果为：false
ABA版本新值：9084设置结果为：false
ABA版本新值：4223设置结果为：false
ABA版本新值：2937设置结果为：false
ABA版本新值：2837设置结果为：false
ABA版本新值：4354设置结果为：false
ABA版本新值：811设置结果为：false
ABA版本新值：7374设置结果为：false
ABA版本新值：125设置结果为：false
ABA版本新值：8256设置结果为：false
ABA版本新值：9112设置结果为：false
ABA版本新值：9827设置结果为：false
ABA版本新值：8817设置结果为：false
ABA版本新值：1897设置结果为：false
ABA版本新值：3784设置结果为：false
ABA版本新值：1233设置结果为：false
ABA版本新值：1902设置结果为：false
ABA版本新值：7025设置结果为：false
ABA版本新值：5885设置结果为：false
ABA版本新值：5254设置结果为：false
ABA版本新值：4337设置结果为：false
ABA版本新值：9677设置结果为：false
ABA版本新值：1991设置结果为：false
ABA版本新值：7234设置结果为：false
ABA版本新值：1155设置结果为：false
ABA版本新值：861设置结果为：false
ABA版本新值：9570设置结果为：false
ABA版本新值：9935设置结果为：false
ABA版本新值：1030设置结果为：false

可以看到只有一个成功，所以底层可以通过while循环方式进行重新获取最新进行判断。

看看jdkAtomicInteger底层的实现

//这里底层通过 unsafe来实现，这个是由c++来写的所以看不到。
public final boolean compareAndSet(int expect, int update) {
    return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}

但是可以通过其他方法发现，很多都是通过先获取当前值，然后去判断是否设置成功，如果没成功通过轮训方式进行设置，直到成功为止，所以用这个CAS会导致cpu飙高的原因就在这里。

public final int getAndUpdate(IntUnaryOperator updateFunction) {
    int prev, next;
    do {
        prev = get();
        next = updateFunction.applyAsInt(prev);
    } while (!compareAndSet(prev, next));
    return prev;
}

最后

cas在算法在很多一些基础的开发都会用到，只是现在Jdk默认有Atomic这个包，通过这个包已经为我们实现了功能，我们可以很方便引用已封装好的包进行实现，本文主要讲解原理。不过在使用cas上面有一点需要特别注意，因为cas如果很多处同时在包循环会导致cpu飙高，所以这点特别重要，一些公司有cpu监控的，要特别注意，避免频繁告警或者因为原来已经很高的cpu导致打到100%，那就很可能引发事故。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2022-08-06，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自技术趋势微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度

CAS算法-实现原理

CAS算法-实现原理

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐