并发策略-CAS算法
2019-11-30 16:01:06来源:博客园 阅读 ()
并发策略-CAS算法
对于并发控制而言,我们平时用的锁(synchronized,Lock)是一种悲观的策略。它总是假设每一次临界区操作会产生冲突,因此,必须对每次操作都小心翼翼。如果多个线程同时访问临界区资源,就宁可牺牲性能让线程进行等待,所以锁会阻塞线程执行。
与之相对的有一种乐观的策略,它会假设对资源的访问是没有冲突的。既然没有冲突也就无需等待了,所有的线程都在不停顿的状态下持续执行。那如果遇到问题了无锁的策略使用一种叫做比较交换(CAS Compare And Swap)来鉴别线程冲突,一旦检测到冲突产生,就重试当前操作直到没有冲突。CAS算法是非阻塞的,它对死锁问题天生免疫,而且它比基于锁的方式拥有更优越的性能。
CAS算法的过程是这样:它包含三个参数 CAS(V,E,N)。V表示要更新的变量,E表示预期的值,N表示新值。仅当V值等于E值时,才会将V的值设置成N,否则什么都不做。最后CAS返回当前V的值。CAS算法需要你额外给出一个期望值,也就是你认为现在变量应该是什么样子,如果变量不是你想象的那样,那说明已经被别人修改过。你就重新读取,再次尝试修改即可。
JDK并发包有一个atomic包,里面实现了一些直接使用CAS操作的线程安全的类型。其中最常用的一个类应该就是AtomicInteger。我们以此为例来研究一下没有锁的情况下如何做到线程安全。
private volatile int value;
这是AtomicInteger类的核心字段,代表当前实际取值,借助volatile保证线程间数据的可见性。
获取内部数据的方法:
public final int get() {
return value;
}
我们从源码的实现看看incrementAndGet()
的内部实现
public final int incrementAndGet() {
for (;;) {
int current = get();
int next = current + 1;
if (compareAndSet(current, next))
return next;
}
}
代码第二行使用了一个死循环,原因是:
CAS的操作未必都是成功的,因此对于不成功的情况,我们就需要进行不断的尝试。
第三行取得当前值,接着+1得到新值next。
这里我们使用CAS必需的两个参数:期望值以及新值。
使用compareAndSet()将新值next写入。成功的条件是在写入的时刻当前的值应该要等于刚刚取到的current。如果不是这样则说明AtomicInteger的值在第3行到第5行之间被其他线程修改过了。当前看到的状态是一个过期的状态,因此返回失败,需要进行下一次重试,直到成功为止。
public final boolean compareAndSet(int expect, int update) {
return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}
整体的过程就是这样子,利用CPU的CAS指令,同时借助JNI来完成Java的非阻塞算法。其它原子操作都是利用类似的特性完成的。大概的逻辑应该是这样:
if (this == expect) {
this = update return true;
} else {
return false;
}
CAS虽然能高效的解决原子问题,但是CAS也会带来1个经典问题即ABA问题:
因为CAS需要在操作值的时候检查下值有没有发生变化,如果没有发生变化则更新,但是如果一个值原来是A,变成了B,又变成了A,那么使用CAS进行检查时会发现它的值没有发生变化,但是实际上却变化了。
ABA问题的解决思路就是使用版本号。在变量前面追加上版本号,每次变量更新的时候把版本号加一,那么A-B-A 就会变成1A-2B-3A。
从Java1.5开始JDK的atomic包里提供了一个类AtomicStampedReference来解决ABA问题。这个类在内部不仅维护了对象值,还维护了一个时间戳(可以是任意的一个整数来表示状态值)。当设置对象值时,对象值和状态值都必须满足期望值才会写入成功。因此即使对象被反复读写,写会原值,只要状态值发生变化,就能防止不恰当的写入。
/**
* @param expectedReference 期望值
* @param newReference 写入新值
* @param expectedStamp 期望状态值
* @param newStamp 新状态值
* @return true if successful
*/
public boolean compareAndSet(V expectedReference,
V newReference,
int expectedStamp,
int newStamp) {
Pair<V> current = pair;
return expectedReference == current.reference &&
expectedStamp == current.stamp &&
((newReference == current.reference &&
newStamp == current.stamp) ||
casPair(current, Pair.of(newReference, newStamp)));
}
个人公众号:JAVA日知录 , javadaily.cn
原文链接:https://www.cnblogs.com/jianzh5/p/11964079.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 如何干掉 if else 策略+工厂 2020-06-11
- 设计模式-委派/策略模式 2020-06-09
- 从聚合支付业务的设计来聊聊策略模式 2020-06-03
- 那些面试官必问的JAVA多线程和并发面试题及回答 2020-05-28
- 架构设计 | 缓存管理模式,监控和内存回收策略 2020-05-26
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash