欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【并发编程】 --- Compare And Swap(CAS)原理分析

程序员文章站 2022-03-09 07:56:54
...

源码地址:https://github.com/nieandsun/concurrent-study.git


1 什么是CAS?


1.1 加锁和CAS解决原子性问题的不同原理

首先看如下代码:

package com.nrsc.ch2.cas;

import java.util.ArrayList;
import java.util.List;

public class CasDemo {

    //共享资源
    static int i = 0;

    public static void increase() {
        i++;
    }

    public static void main(String[] args) throws InterruptedException {
        Runnable r = () -> {
            for (int j = 0; j < 1000; j++) {
                increase();
            }
        };

        List<Thread> threads = new ArrayList<>();
        for (int j = 0; j < 10; j++) {
            Thread thread = new Thread(r);
            threads.add(thread);
            thread.start();
        }

        //确保前面10个线程都走完
        for (Thread thread : threads) {
            thread.join();
        }

        System.out.println(i);
    }
}

相信每个人都知道这段代码由于i++不是原子操作,因此会导致这10个线程执行后的最终结果不是10*1,000 = 10,000。
当然也相信几乎所有人都知道通过加锁可以解决这个问题,加锁方式解决该问题的原理基本可以用下图进行概况:
【并发编程】 --- Compare And Swap(CAS)原理分析
而其实除了加锁之外利用CAS机制也能解决这个问题。既然说它是除了加锁之外的另一种解决方式,那它肯定是无锁的,因此利用CAS机制解决该问题的方式大致可以用下图进行概况:
【并发编程】 --- Compare And Swap(CAS)原理分析
那到底啥是CAS呢?它又是是如何解决这个问题的呢?


1.2 CAS原理分析

先看定义(摘自百度百科):

compare and swap,解决多线程并行情况下使用锁造成性能损耗的一种机制,CAS操作包含三个操作数——内存位置(V)、预期原值(A)和新值(B)。如果内存位置的值与预期原值相匹配,那么处理器会自动将该位置值更新为新值。否则,处理器不做任何操作。无论哪种情况,它都会在CAS指令之前返回该位置的值。CAS有效地说明了“我认为位置V应该包含值A;如果包含该值,则将B放到这个位置;否则,不要更改该位置,只告诉我这个位置现在的值即可。"

再画个图解释一下:
【并发编程】 --- Compare And Swap(CAS)原理分析


2 CAS可能的问题


2.1 ABA问题

说实话刚接触CAS的时候,其实我就想到ABA这个问题了。☺☺☺

通过1.2可以知道,CAS需要在操作值的时候,检查值有没有发生变化,如果没有发生变化就更新,但是如果一个值原来是A,变成了B,又变成了A,那么使用CAS进行检查时会发现它的值没有发生变化,但是实际上却变化了 —> 这就是所谓的ABA问题。

举个通俗点的例子,你倒了一杯水放桌子上,干了点别的事,然后同事把你水喝了又给你重新倒了一杯水,你回来看水还在,拿起来就喝,如果你不管水中间被人喝过,只关心水还在,还好 ; 但是假若你是一个比较讲卫生的人,那你肯定就不高兴了。。。

ABA问题的解决思路其实也很简单,就是使用版本号。在变量前面追加上版本号,每次变量更新的时候把版本号加1,那么A→B→A就会变成1A→2B→3A了。


2.2 循环时间长开销大

自旋CAS如果长时间不成功,会给CPU带来非常大的执行开销。


2.3只能保证一个共享变量的原子操作

当对一个共享变量执行操作时,我们可以使用循环CAS的方式来保证原子操作,但是对多个共享变量操作时,循环CAS就无法保证操作的原子性,这个时候就可以用锁

还有一个取巧的办法,就是把多个共享变量合并成一个共享变量来操作。比如,有两个共享变量i=2,j=a,合并一下ij=2a,然后用CAS来操作ij。从Java 1.5开始,JDK提供了AtomicReference类来保证引用对象之间的原子性,就可以把多个变量放在一个对象里来进行CAS操作。


3 JDK中对CAS的支持 — unsafe类

java中提供了对CAS操作的支持,具体在sun.misc.unsafe类中,声明如下:

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

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

public final native boolean compareAndSwapLong(Object var1, long var2, long var4, long var6);

上面各个参数的含义:

  • 参数var1:表示要操作的对象
  • 参数var2:表示要操作对象中属性地址的偏移量
  • 参数var4:表示需要修改数据的期望的值
  • 参数var5/var6:表示雷要修改为的新值

注意:Unsafe类使Java拥有了像C语言的指针一样操作内存空间的能力,同时也带来了指针的问题。过度的使 用Unsafe类会使得出错的几率变大,因此Java官方并不建议使用的,官方文档也几乎没有。Unsafe对 象不能直接调用,只能通过反射获得。


4 JDK中的相关原子操作类简介 — 底层CAS机制


4.1 AtomicInteger

  • int addAndGet(int delta):以原子方式将输入的数值与实例中的值(AtomicInteger里的value)相加,并返回结果。
  • boolean compareAndSet(int expect,int update):如果输入的数值等于预期值,则以原子方式将该值设置为输入的值。
  • int getAndIncrement():以原子方式将当前值加1,注意,这里返回的是自增前的值。
  • int getAndSet(int newValue):以原子方式设置为newValue的值,并返回旧值。

4.2 AtomicIntegerArray

主要是提供原子的方式更新数组里的整型,其常用方法如下。

  • int addAndGet(int i,int delta):以原子方式将输入值与数组中索引i的元素相加。
  • boolean compareAndSet(int i,int expect,int update):如果当前值等于预期值,则以原子方式将数组位置i的元素设置成update值。

需要注意的是,数组value通过构造方法传递进去,然后AtomicIntegerArray会将当前数组复制一份,所以当AtomicIntegerArray对内部的数组元素进行修改时,不会影响传入的数组。


4.3更新引用类型

原子更新基本类型的AtomicInteger,只能更新一个变量,如果要原子更新多个变量,就需要使用这个原子更新引用类型提供的类。Atomic包提供了以下3个类。

  • AtomicReference
    原子更新引用类型。
  • AtomicStampedReference
    利用版本戳的形式记录了每次改变以后的版本号,这样的话就不会存在ABA问题了。这就是AtomicStampedReference的解决方案。AtomicMarkableReference跟AtomicStampedReference差不多, AtomicStampedReference是使用pair的int stamp作为计数器使用,AtomicMarkableReference的pair使用的是boolean mark。 还是那个水的例子,AtomicStampedReference可能关心的是动过几次,AtomicMarkableReference关心的是有没有被人动过,方法都比较简单。
  • AtomicMarkableReference:
    原子更新带有标记位的引用类型。可以原子更新一个布尔类型的标记位和引用类型。构造方法是AtomicMarkableReference(V initialRef,booleaninitialMark)。

4.4 原子更新字段类

如果需原子地更新某个类里的某个字段时,就需要使用原子更新字段类,Atomic包提供了以下3个类进行原子字段更新。
要想原子地更新字段类需要两步。第一步,因为原子更新字段类都是抽象类,每次使用的时候必须使用静态方法newUpdater()创建一个更新器,并且需要设置想要更新的类和属性。 第二步,更新类的字段(属性)必须使用public volatile修饰符。

  • AtomicIntegerFieldUpdater:
    原子更新整型的字段的更新器。
  • AtomicLongFieldUpdater:
    原子更新长整型字段的更新器。
  • AtomicReferenceFieldUpdater:
    原子更新引用类型里的字段。