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关键字进行修饰这保证了可见性;防止了数据不一致问题。
- 1、Unsafe。是CAS的核心类,由于Java方法无法直接访问底层系统,需要通过本地(native)方法来访问,Unsafe相当于一个后门,基于该类可以直接操作特定内存的数据。Unsafe类存在于sun.misc包中,其内部方法操作可以像C指针一样直接操作内存。
- 2、保证原子性的atmicInteger中的incrementAndGet方法中使用了Unsafe的getAndAddInt方法,包含三个参数,this指当前操作对象,valueOffset表示该变量值在内存中的偏移地址,因为Unsafe就是根据内存偏移地址去获取数据的,最后一个参数是增加值,固定为1。
- 3、在compareAndSwapInt方法中,var1就是AtomicInteger对象本身,var2是该对象值的引用地址,var4是指需要变动的数量,而var5指的是用var1、var2找出的主内存中真实的值。用该对象当前的值与var5(也就是预期值)比较,如果相同,则更新值并返回true,如果不同,继续取值然后再比较,直至更新完成。
- 4、变量value用volatile修饰,保证了多线程之间的内存可见性。
CAS与synchronizedb比对
- synchronized是属于独占资源,同一时间段只允许有一个线程来访问,一致性得到了保障,但是并发性下降。
- CAS并没有加锁而是进行多次地取值并比较,这样既保障了一致性,又提高了并发性。
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缺点
- 循环时间长,开销很大。如果CAS失败,会一直进行尝试,如果长时间一直不成功,可能会给CPU带来很大的开销。
- 只能保证一个共享变量的原子操作。
- 引发ABA问题
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先修改20:true
主线程将20又修改19:true
子线程将19修改21:true
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