【漫画】CAS原理剖析!无锁原子类也能处理并发问题!

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

在漫画并发编程体系博文中,咱们讲了N篇关于锁的常识,的确,锁是处理并发问题的万能钥匙,可是并发问题只需锁能处理吗?今日要进场一个大BOSS:CAS无锁算法,可谓是并发编程中心中的中心!

【漫画】CAS原理剖析!无锁原子类也能处理并发问题!

温故

首要咱们再回忆一下原子性问题的原因,参阅【漫画】JAVA并发编程 怎样处理原子性问题。
【漫画】CAS原理剖析!无锁原子类也能处理并发问题!

两个线程一起把count=0加载到自己的作业内存,线程B先履行count++操作,此刻主内存现已改动成了1,可是线程A仍旧以为count=0,这是导致问题的本源

所以处理方案便是:不能让线程A以为count=0,而是要和主内存进行一次compare(比较),假如内存中的值是0,阐明没有其他线程更新过count值,那么就swap(交流),把新值写回主内存。假如内存中的值不是0,比方本事例中,内存中count就现已被线程B更新成了1,比较0!=1,因而compare失利,不把新值写回主内存。

【漫画】CAS原理剖析!无锁原子类也能处理并发问题!

本文来源于微信大众号【胖滚猪学编程】、以漫画方法让编程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的思维,那能够手写一个简略的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 并发包里供给的原子类内容很丰厚,咱们能够将它们分为五个类别:原子化的根本数据类型、原子化的目标引证类型、原子化数组、原子化目标特点更新器和原子化的累加器。

【漫画】CAS原理剖析!无锁原子类也能处理并发问题!

原子类的运用可谓十分简略,信任只需看一下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代码:

【漫画】CAS原理剖析!无锁原子类也能处理并发问题!
【漫画】CAS原理剖析!无锁原子类也能处理并发问题!

个人以为没必要深究,究竟术业有专攻,你只需求知道其实中心代码便是一条 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

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