CAS原理解析及源码分析

CAS锁

CAS是一种无锁算法;它的全称:Compare and Swap(比较和交换)

算法思想

CAS在操作的过程中主要有三个参数:一、内存中的值V(可以理解为实际当前时刻真实的值);二、旧值A(可以理解为上次记录的修改的值);三、要修改的新值B(可以理解为需要修改后的值)

CAS的整体思路是:它首先会将内存中的值V旧值A进行比较;如果一样就会将内存中的值V修改为要修改的新值B;如果不一样则就说明同一时刻该值被另一个线程修改过,此时就什么也不做。整个操作都属于原子操作。(下个循环继续)

拿案例说明

new Thread(()-->{
    int i = 10;
    i++;
})

假设此时有两个线程A、B同时执行上面代码;他们会有各自的工作内存;线程A、B竞争,假设线程A首先读取内存值,与就是比较符合预期,即10 == 10;此时就是将11更新到内存;但是此时线程B已经将10读入了工作内存,这个是作为旧值,此时再与内存中的值比较会发现11 != 10;说明共享数据已经被修改,放弃已经所做的操作,然后拿新的内存的作为旧值,重新执行刚才的操作。直至下一次的重新操作则会成功修改;

记住:CAS这里会有个不停的循环过程

Java中CAS的应用

在java.util.concurrent.atomic包下有一系列的类,这些类基本上都使用了CAS;

下面我们以AtomicInteger进行说明(代码主要是使用了20个线程进行自增10000次来证明原子性.运行结果是:200000):

public class MyThread {

    private static AtomicInteger race = new AtomicInteger(0);
    private static final int THREADS_COUNT = 20;

    private static void increase() {
        race.incrementAndGet();
    }

    public static void main(String[] args) throws InterruptedException {
        Thread[] threads = new Thread[THREADS_COUNT];
        for (int i = 0; i < THREADS_COUNT; i++) {
            threads[i] = new Thread(new Runnable() {
                @Override
                public void run() {
                    for (int i = 0; i < 10000; i++) {
                        increase();
                    }
                }
            });
            threads[i].start();
            threads[i].join();
        }
        System.out.println(race);
    }
}
//程序运行结果为:200000

程序输出正确结果,一切都要归功于AtomicInteger的incrementAndGet()方法的原子性,该方法无限循环,不断尝试将一个一个比当前值大1的新值赋给自己,如果失败了那说明在执行“获取-设置“操作的时候值已经有了修改,于是再次循环进行下一次操作,只带设置成功为止,它的原理实现其实非常简单。

下面我们看下AtomicInteger的incrementAndGet()方法的源码:

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

实际调用的是unsafe的getAndAddInt方法:

public final int getAndAddInt(Object var1, long var2, int var4) {
    int var5;
    do {
        var5 = this.getIntVolatile(var1, var2);
    } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));

    return var5;
}

由AtomicInteger源码我们可以看出;CAS的实现就是Unsafe类中的各个方法;Unsafe中的方法都是native本地方法;这是完全依赖于硬件的功能,通过他实现了原子操作。在执行过程中不允许被中断。同样这个内存的值value是用volatile关键字进行修饰这保证了可见性;防止了数据不一致问题。

CAS与synchronizedb比对

CAS如何保证原子性

这里我们先回已一下CAS的思想:

它首先会将内存中的值V旧值A进行比较;如果一样就会将内存中的值V修改为要修改的新值B;如果不一样则就说明同一时刻该值被另一个线程修改过,此时会将内存中的值V更新到旧值A;然后继续下面循环比较工作,直至成功。

这里其实存在一个问题,一个线程在进行内存中的值V旧值A进行比较的时候通过,当需要修改的前一时刻,内存中的值V内存中的值发生变化;这个时候就会出现线程安全的问题。所以CAS保证了这个比较与更新的过程是原子性的;这样就会线程安全。

那么CAS如何保证原子性?这里简单说下

public final int getAndAddInt(Object var1, long var2, int var4) {
    int var5;
    do {
        var5 = this.getIntVolatile(var1, var2);
	// CAS的实现就是	compareAndSwapInt方法;此方法是native方法
    } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));

    return var5;
}

所以说这里保证原子性就在本地方法,也就是C++进行实现的;再底层的最终实现是通过lock cmpxchg 指令;其中lock是一个锁总线的一个锁;保证了多核CPU下的指令同步。

CAS缺点

ABA问题

何为ABA问题? 如果一个内存中的值V初次读取的时候是A,当我们在准备更新的时候检查它的值还是A,在初次读取到开始检查之前我们不能确保内存中的值V有没有被其他线程改过!

因为在这段时间如果我们有一个线程将内存中的值V先改成B,然后又改成了A;那么CAS在前面的操作就会认为内存中的值V一直没有变过;这个就是ABA问题。 代码模拟ABA

public class AtomicTest extends Thread {
    private static AtomicInteger atomicInteger = new AtomicInteger(19);

    public static void main(String[] args) throws InterruptedException {
        AtomicTest thread01 = new AtomicTest();
        thread01.start();
        //  设置账户初始值小于20,这是一个需要被充值的客户
        System.out.println("主线程将19先修改20:" + atomicInteger.compareAndSet(19, 20));
        System.out.println("主线程将20又修改19:" + atomicInteger.compareAndSet(20, 19));
        thread01.join();
        System.out.println("atomicInteger最终结果:" + atomicInteger.get());
    }

    @Override
    public void run() {
        try {
            Thread.sleep(100);
            System.out.println("子线程将19修改21:" + atomicInteger.compareAndSet(19, 21));
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
    }
}
//程序输出:
主线程将19先修改20true
主线程将20又修改19true
子线程将19修改21true
atomicInteger最终结果21

如果需要解决ABA问题,原子引用类提供了一个带有标记的类 - AtomicStampedReference;或者改用传统的互斥同步(典型的就是synchronized 和Lock)可能会比原子类更高效。

AtomicStampedReference

AtomicStampedReference内部维护了一个stamp版本号,主要用来解决ABA问题。

示例代码

public class AtomicTest extends Thread {
    private static AtomicStampedReference<Integer> atomicStampedReference =
            new AtomicStampedReference<>(1, 1);

    public static void main(String[] args) throws InterruptedException {
        AtomicTest thread01 = new AtomicTest();
        thread01.start();

        Thread.sleep(100);
        System.out.println("主线程将AtomicStampedReference(1,1)修改为(2,2):" +
                atomicStampedReference.compareAndSet(1, 2, atomicStampedReference.getStamp(), atomicStampedReference.getStamp() + 1));
        System.out.println("主线程将AtomicStampedReference(2,2)又修改(1,3):" +
                atomicStampedReference.compareAndSet(2, 1, atomicStampedReference.getStamp(), atomicStampedReference.getStamp() + 1));


        thread01.join();
    }

    @Override
    public void run() {
        try {
            int stamp = atomicStampedReference.getStamp();
            System.out.println("子线程获取AtomicStampedReference版本号:" + stamp);
            Thread.sleep(300);
            System.out.println("子线程将AtomicStampedReference(1,1)修改(3,2):" +
                    atomicStampedReference.compareAndSet(1, 3, stamp, atomicStampedReference.getStamp() + 1));
            System.out.println("子线程获取AtomicStampedReference实际版本号:" + atomicStampedReference.getStamp());
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
    }
}
//程序输出:
子线程获取AtomicStampedReference版本号1
主线程将AtomicStampedReference(1,1)修改为(2,2)true
主线程将AtomicStampedReference(2,2)又修改(1,3)true
子线程将AtomicStampedReference(1,1)修改(3,2)false
子线程获取AtomicStampedReference实际版本号3

AtomicStampedReference内存需要自己手动去维护这个版本号stamp;如果版本号维护的有问题(类似值变化的问题)其实依旧也会出现ABA问题;所以注意版本号的维护,AtomicStampedReference其实是把ABA问题交由我们开发人员自己去控制了

AtomicReference其实就是与AtomicInteger内部实现一样,只不过AtomicReference自己定义泛型,AtomicStampedReference就是带版本号的自己定义泛型;