首页 科技正文

新阳泉:【漫画】CAS原理剖析!无锁原子类也能解决并发问题!

admin 科技 2020-05-19 30 0

本文来源于微信民众号【胖滚猪学编程】、转载请注明出处

在漫画并发编程系统博文中,我们讲了N篇关于锁的知识,确实,锁是解决并发问题的万能钥匙,可是并发问题只有锁能解决吗?今天要进场一个大BOSS:CAS无锁算法,可谓是并发编程焦点中的焦点!

温故

首先我们再回首一下原子性问题的缘故原由,参考【漫画】JAVA并发编程 若何解决原子性问题。

两个线程同时把count=0加载到自己的事情内存,线程B先执行count++操作,此时主内存已经转酿成了1,然则线程A依旧以为count=0,这是导致问题的泉源

以是解决方案就是:不能让线程A以为count=0,而是要和主内存举行一次compare(对照),若是内存中的值是0,说明没有其他线程更新过count值,那么就swap(交流),把新值写回主内存。若是内存中的值不是0,好比本案例中,内存中count就已经被线程B更新成了1,对照0!=1,因此compare失败,不把新值写回主内存。

本文来源于微信民众号【胖滚猪学编程】。一个集颜值与才气于一身的女程序媛、以漫画形式让编程so easy and interesting!转载请注明出处

CAS观点

CAS (compareAndSwap),中文叫对照交流,一种无锁原子算法

CAS算法包罗 3 个参数 CAS(V,E,N),V示意要更新变量在内存中的值,E示意旧的预期值,N示意新值。
仅当 V值即是E值时,才会将V的值设为N
若是V值和E值差别,则说明已经有其他线程做两个更新,那么当前线程不做更新,而是自旋。

模拟CAS实现

既然我们领会了CAS的头脑,那可以手写一个简朴的CAS模子:

    // count必须用volatile修饰 保证差别线程之间的可见性
    private volatile static int count;
    
    public void addOne() {
        int newValue;
        do {
            newValue = count++;
        } while (!compareAndSwapInt(expectCount, newValue)); //自旋 循环
    }

    public final boolean compareAndSwapInt(int expectCount, int newValue) {
        // 读现在 count 的值
        int curValue = count;
        // 对照现在 count 值是否 == 期望值
        if (curValue == expectCount) {
            // 若是是,则更新 count 的值
            count = newValue;
            return true;

        }
        //否则返回false 然后循环
        return false;
    }

这个简朴的模拟代码,实在基本上把CAS的头脑体现出来了,但实际上CAS原理可要庞大许多哦,我们照样看看JAVA是怎么实现CAS的吧!

原子类

要领会JAVA中CAS的实现,那不得不提到赫赫有名的原子类,原子类的使用异常简朴,而其中深奥的原理就是CAS无锁算法。

Java 并发包里提供的原子类内容很厚实,我们可以将它们分为五个种别:原子化的基本数据类型、原子化的工具引用类型、原子化数组、原子化工具属性更新器和原子化的累加器。

原子类的使用可谓异常简朴,信赖只要看一下api就知道若何使用,因此不外多注释,若有需要可以参考本人github代码。
此处只以AtomicInteger为例子,测试一下原子类是否名副实在可以保证原子性:

    private static AtomicInteger count = new AtomicInteger(0);
    private static int count1 = 0;
    //省略代码 同时启动10个线程 划分测试AtomicInteger和通俗int的输出效果
    private static void add10K() {
        int idx = 0;
        while (idx++ < 10000) {
            //使用incrementAndGet实现i++功效
            count.incrementAndGet();
        }
        countDownLatch.countDown();
    }
    private static void add10K1() {
        int idx = 0;
        while (idx++ < 10000) {
            count1++;
        }
        countDownLatch.countDown();
    }

通过测试可以发现,使用AtomicInteger可以保证输出效果为100000,而通俗int则不能保证。

本文来源于微信民众号【胖滚猪学编程】。一个集颜值与才气于一身的女程序媛、以漫画形式让编程so easy and interesting!转载请注明出处

CAS源码剖析

据此,我们又可以回归正题,JAVA是怎么实现CAS的呢?跟踪一下AtomicInteger中的incrementAndGet()方式,信赖就会有谜底了。
首先关注一下AtomicInteger.java中这么几个器械:

    private static final Unsafe unsafe = Unsafe.getUnsafe();
    private static final long valueOffset;//数据在内存中的地址偏移量,通过偏移地址可以获取数据原值

    static {
        try {
            //盘算变量 value 在类工具中的偏移量
            valueOffset = unsafe.objectFieldOffset
                (AtomicInteger.class.getDeclaredField("value"));
        } catch (Exception ex) { throw new Error(ex); }
    }

    private volatile int value;//要修改的值 volatile保证可见性

    public final int incrementAndGet() {
        return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
    }

Unsafe,是CAS的焦点类,由于Java方式无法直接接见底层系统,需要通过内陆(native)方式来接见,Unsafe相当于一个后门,基于该类可以直接操作特定内存的数据。
变量valueOffset,示意该变量值在内存中的偏移地址,由于Unsafe就是凭据内存偏移地址获取数据的。
变量value必须用volatile修饰,保证了多线程之间的内存可见性。

固然详细实现我们照样得瞧瞧getAndAddInt方式:

    //内部使用自旋的方式举行CAS更新(while循环举行CAS更新,若是更新失败,则循环再次重试)
    public final int getAndAddInt(Object var1, long var2, int var4) {
         //var1为当前这个工具,如count.getAndIncrement(),则var1为count这个工具
        //第二个参数为AtomicInteger工具value成员变量在内存中的偏移量
        //第三个参数为要增添的值
        int var5;
        do {
            //var5 获取工具内存地址偏移量上的数值v 即预期旧值
            var5 = this.getIntVolatile(var1, var2);
        } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));//循环判断内存位置的值与预期原值是否相匹配

        return var5;
    }

此时我们还想继续领会compareAndSwapInt的实现,点进去看,首先映入眼帘的是四个参数:1、当前的实例 2、实例变量的内存地址偏移量 3、预期的旧值 4、要更新的值

    public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);

还想继续刨根问底,会发现点不动了。由于用native修饰的方式代表是底层方式,固然若是你非得一探事实你也可以找找对应的unsafe.cpp 文件举行深度剖析C代码:


个人以为没必要深究,究竟术业有专攻,你只需要知道实在焦点代码就是一条 cmpxchg 指令
cmpxchg: 即“对照并交流”指令。与我们上面说的头脑是一样的:将 eax 寄存器中的值(compare_value)与 [edx] 双字内存单元中的值举行对比,若是相同,则将 ecx 寄存器中的值(exchange_value)存入 [edx] 内存单元中。

总之:你只需要记着:CAS是靠硬件实现的,从而在硬件层面提升效率。实现方式是基于硬件平台的汇编指令,在intel的CPU中,使用的是cmpxchg指令。 焦点头脑就是:对照要更新变量的值V和预期值E(compare),相等才会将V的值设为新值N(swap)。

CAS真有这么好吗?

CAS和锁都解决了原子性问题,和锁相比,由于其非壅闭的,它对死锁问题天生免疫,而且,线程间的相互影响也异常小。更为重要的是,使用无锁的方式完全没有锁竞争带来的系统开销,也没有线程间频仍调剂带来的开销,因此,他要比基于锁的方式拥有更优越的性能

然则,CAS真的有那么好吗?又到挑刺时间了!

要让我们失望了,CAS并没有那么好,主要显示在三个方面:

  • 1、循环时间太长
  • 2、只能保证一个共享变量原子操作
  • 3、ABA问题。

循环时间太长
若是CAS长时间地不乐成,我们知道会连续循环、自旋。一定会给CPU带来异常大的开销。在JUC中有些地方就限制了CAS自旋的次数,例如BlockingQueue的SynchronousQueue。

只能保证一个共享变量原子操作
看了CAS的实现就知道这只能针对一个共享变量,若是是多个共享变量就只能使用锁了,固然若是你有设施把多个变量整成一个变量,行使CAS也不错。例如读写锁中state的高低位。

ABA问题
这可是个面试重点问题哦!认真听好!

CAS需要检查操作值有没有发生改变,若是没有发生改变则更新。然则存在这样一种情形:若是一个值原来是A,酿成了B,然后又酿成了A,那么在CAS检查的时刻会发现没有改变,然则实质上它已经发生了改变,这就是所谓的ABA问题。
某些情形我们并不体贴 ABA 问题,例如数值的原子递增,但也不能所有情形下都不体贴,例如原子化的更新工具很可能就需要体贴 ABA 问题,由于两个 A 虽然相等,然则第二个 A 的属性可能已经发生转变了。

对于ABA问题其解决方案是加上版本号,即在每个变量都加上一个版本号,每次改变时加1,即A —> B —> A,酿成1A —> 2B —> 3A。

原子类之AtomicStampedReference可以解决ABA问题,它内部不仅维护了工具值,还维护了一个Stamp(可把它理解为版本号,它使用整数来示意状态值)。当AtomicStampedReference对应的数值被修改时,除了更新数据本身外,还必须要更新版本号。当AtomicStampedReference设置工具值时,工具值以及版本号都必须知足期望值,写入才会乐成。因此,纵然工具值被频频读写,写回原值,只要版本号发生转变,就能防止不适当的写入。

    // 参数依次为:期望值 写入新值 期望版本号 新版本号
    public boolean compareAndSet(V expectedReference, V
            newReference, int expectedStamp, int newStamp);

    //获得当前工具引用
    public V getReference();

    //获得当前版本号
    public int getStamp();

    //设置当前工具引用和版本号
    public void set(V newReference, int newStamp);

说理论太多也没用,照样亲自实验它是否能解决ABA问题吧:

    private static AtomicStampedReference<Integer> count = new AtomicStampedReference<>(10, 0);

    public static void main(String[] args) {
        Thread main = new Thread(() -> {
            int stamp = count.getStamp(); //获取当前版本

            log.info("线程{} 当前版本{}",Thread.currentThread(),stamp);
            try {
                Thread.sleep(1000); //守候1秒 ,以便让滋扰线程执行
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            boolean isCASSuccess = count.compareAndSet(10, 12, stamp, stamp + 1);  //此时expectedReference未发生改变,然则stamp已经被修改了,以是CAS失败
            log.info("CAS是否乐成={}",isCASSuccess);
        }, "主操作线程");

        Thread other = new Thread(() -> {
            int stamp = count.getStamp(); //获取当前版本
            log.info("线程{} 当前版本{}",Thread.currentThread(),stamp);
            count.compareAndSet(10, 12, stamp, stamp + 1);
            log.info("线程{} 增添后版本{}",Thread.currentThread(),count.getStamp());

            // 模拟ABA问题 先更新成12 又更新回10
            int stamp1 = count.getStamp(); //获取当前版本
            count.compareAndSet(12, 10, stamp1, stamp1 + 1);
            log.info("线程{} 削减后版本{}",Thread.currentThread(),count.getStamp());
        }, "滋扰线程");

        main.start();
        other.start();
    }

输出效果如下:

线程Thread[主操作线程,5,main] 当前版本0
[滋扰线程] INFO - 线程Thread[滋扰线程,5,main] 当前版本0
[滋扰线程] INFO  - 线程Thread[滋扰线程,5,main] 增添后版本1
[滋扰线程] INFO - 线程Thread[滋扰线程,5,main] 削减后版本2
[主操作线程] INFO  - CAS是否乐成=false

总结

JAVA博大精深,解决并发问题可不仅仅是锁才气担此大任。CAS无锁算法对于解决原子性问题同样是势在必得。而原子类,则是无锁工具类的典型,原子类包罗五大类型(原子化的基本数据类型、原子化的工具引用类型、原子化数组、原子化工具属性更新器和原子化的累加器)。

CAS 是一种乐观锁,乐观锁会以一种加倍乐观的态度看待事情,以为自己可以操作乐成。而消极锁会让线程一直壅闭。因此CAS具有许多优势,好比性能佳、可以制止死锁。然则它没有那么好,你应该考虑到ABA问题、循环时间长的问题。因此需要综合选择,适合自己的才是最好的。

附录:并发编程全系列代码github

本文来源于微信民众号【胖滚猪学编程】。一个集颜值与才气于一身的女程序媛、以漫画形式让编程so easy and interesting!迎接关注与我一起交流!

本文转载自民众号【胖滚猪学编程】 用漫画让编程so easy and interesting!迎接关注!形象来源于微信脸色包【胖滚家族】喜欢可以下载哦~

,

Sunbet 申博

Sunbet 申博致力于服务,多方面拓展合作,欢迎莅临指导、合作。

版权声明

本文仅代表作者观点,
不代表本站Allbet的立场。
本文系作者授权发表,未经许可,不得转载。

评论