CAS(比较与交换,Compare and swap) 是一种有名的无锁算法,它是乐观锁的一种实现方式。所以在进行CAS原理分析的时候,我们先来了解什么是乐观锁,什么是悲观锁~
乐观锁与悲观锁
乐观锁和悲观锁是在数据库中引入的名词,但是在我们Java的JUC里面的锁也引入类似的思想!我们来看看两种锁的概念
悲观锁
悲观锁指对数据被外界修改持保守态度,认为数据很容易就会被其他线程修改,所有在数据被处理前先对数据进行加锁,并在整个数据处理过程中,使数据处于锁定状态。我们的传统数据库就会用到这种排它锁的机制,比如行锁,表锁等,读锁,写锁等,都是在操作之前上锁,操作结束提交事务之后释放锁!在Java中像Synchronized同步术语,ReentrantLock等也是悲观锁!而像volatile关键字虽然是synchronized关键字的轻量级实现,但是其无法保证原子性,所以一般也要搭配锁使用。
乐观锁
乐观锁是相对悲观锁来说,它认为数据在一般情况下不会造成冲突,别人不会去修改,所以在访问记录前不会加排它锁。但是在更新的时候会判断一下在此期间别人有没有去更新这个数据,可以使用版本号,时间戳来等记录。因为不加锁,所以乐观锁在多读的情况下,可以极大的提升我们的吞吐量。在我们的数据库中提供了类似write_condition机制,在Java中JUC下的原子变量类也是使用了乐观锁的一种实现方式CAS,也就是我们下面即将介绍的!
CAS(Compare And Swap)原理解析
Java中,锁在并发处理中占据了一席之地,但是使用锁有一个不好的地方,就是当一个线程没有获取到锁时会被阻塞挂起,这会导致线程上下文的切换和重新调度开销。Java提供了非阻塞的volatile关键字来解决共享变量的可见性问题,这在一定程度上弥补了锁带来的开销问题,但是volatile只能保证共享变量的可见性,不能解决读改一写等的原子性问题。
CAS就是是JDK提供的非阻塞原子性操作,通过硬件保证了比较-更新操作的原子性。它的主要原理如下:
CAS有三个操作数
- 内存值v
- 旧的预期值A
- 要修改的新值B
当多个线程尝试使用CAS同时更新一个变量的时候,只有一个能够更新成功。那就是当我们的内存值V和旧的预期值A相等的情况下,才能将内存值V修改成B!然后失败的线程不会挂起,而是被告知失败,可以继续尝试(自旋)或者什么都不做!
尝试重试
我们可以假设有两个线程,一个线程1,一个线程2,同时对我们的内存值进行自增!我们的内存值刚开始是0,旧的预期值也是0。
- 这个时候线程1进来了,由于我们的内存值和旧的预期值相等,所以更新我们的内存值为要修改的新值1
- 当线程1结束之后,线程2进来了,要对我们的内存值进行修改。但是发现我们的内存A(此时为1)和我们的旧的预期值不相等(此时为0)不相等,所以不能将内存值更新为我们的预期值(预期值为2),所以只能进行将旧的预期值更新为内存值(此时旧的预期值 == 内存值),并告知下一次再试试!
- 当我们的线程2重试更新内存值,此时内存值(此时为1)与我们的旧的预期值(此时为1)相等,所以可以将我们的内存值更新为我们的预期值(2)。
所以,哪怕没有加锁,我们也能实现线程安全。
什么都不做
同样的,我们举例有两个线程,一个线程1,一个线程2;我们两个线程都要对内存进行更新为10。
- 我们假设线程1先进来,此时内存值与我们的旧的预期值都为0,所以可以更新,将我们要修改的新值10赋值给了内存值,完成了更新
- 当线程1完成之后,线程2进来要对我们的内存值进行修改为10,但是发现内存值与旧的预期值不相同(此时一个为10,一个为0),所以只能将旧的预期值更新为内存值,同时被告知了下次不用重试了。(因为我们的目的是将内存值更新为10,显然我们的目的已经完成了)
原子变量类简单分析
我们在开头也提到了,在我们JUC下的原子变量类也是使用CAS来保证操作的原子性。而我们的具体原子变量类有以下这些:
我们以AtomicInteger为例,找一个其中自增的方法分析一下:
public final int getAndIncrement() {
return unsafe.getAndAddInt(this, valueOffset, 1);
}
该方法主要为了自增,它调用了getAndAddInt方法。这个是方法是我们的Unsafe类下面
//var1 是this指针
//var2 是地址偏移量
//var4 是自增的数值,是自增1还是自增N
public final int getAndAddInt(Object var1, long var2, int var4) {
int var5;
do {
//获取我们的的期望值赋值给var5
var5 = this.getIntVolatile(var1, var2);
//调用了Unsafe下面的另一个方法,是一个native方法
//如果期望值var5与内存值var2相等的话,更新内存值为var5+var4,否则更新期望值为期望值为内存值
} while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));
return var5;
}
compareAndSwapInt方法是我们的调用native方法
// 第一和第二个参数代表对象的实例以及地址,第三个参数代表期望值,第四个参数代表更新值
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);
它是由我们的底层c代码调用汇编使用的,最后生成出一条CPU指令cmpxchg,完成操作。这也就为啥CAS是原子性的,因为它是一条CPU指令,不会被打断。这个指令在我们早期的硬件厂商就在芯片大量使用了,比如intel。
ABA 问题
关于CAS还有一个比较典型的问题,那就是ABA问题。
ABA问题的产生是因为变量的状态值产生了环形转换,就是变量的值可以从A到B,然后再从B到A。举个例子:
- 现在我有一个变量
count=10
,现在有三个线程,分别为A、B、C - 线程A和线程C同时读到count变量,所以线程A和线程C的内存值和预期值都为10
- 此时线程A使用CAS将count值修改成100
- 修改完后,就在这时,线程B进来了,读取得到count的值为100(内存值和预期值都是100),将count值修改成10
- 线程C拿到执行权,发现内存值是10,预期值也是10,将count值修改成11
我们重点放在C上面,虽然我们的C成功的修改了值。但是内存值和预期值和我们原来的相同,C就不知道之前这个变量已经被两个线程操作过了。所以就会有一定的风险。举个风险通俗的例子:
小明在提款机,提取了50元,因为提款机问题,有两个线程,同时把余额从100变为50。
- 线程1(提款机):获取当前值100,期望更新为50
- 线程2(提款机):获取当前值100,期望更新为50
- 线程1成功执行,线程2某种原因block了,这时,某人给小明汇款50
- 线程3(默认):获取当前值50,期望更新为100。这时候线程3成功执行,余额变为100
- 线程2从Block中恢复,获取到的也是100,compare之后,继续更新余额为50!!!
此时可以看到,实际余额应该为100(100-50+50),但是实际上变为了50(100-50+50-50)这就是ABA问题带来的成功提交。
我们针对这个思考,如果变量的值只能朝着一个方向转换,比如A到B,B再到C,不构成环形,就不会存在问题。在我们的Java中提供了两个原子类,为我们提供了版本号(时间戳)的方法解决了该问题!
(AtomicStampedReference
和AtomicMarkableReference
)。
这样我们的A-B-A就会变成1A-2B-3A这种存在,就不存在环形问题了。
总结
我们的CAS虽然解决了原子性,避免了锁的不必要开销。但是还是存在三个问题。
第一个问题就是自旋时间长开销大!有时候自旋时间过长,消耗CPU资源,如果资源竞争激烈,多线程自旋长时间消耗资源。所以我们通过具体场景来选择加锁还是通过CAS来解决,CAS是适用于多读的环境的,如果是大量读写的操作的话,还是加锁吧!
第二个问题就是我们的ABA问题!在上面已经具体介绍了,以及给上了解决方法。
第三个问题就是我们的CAS只能保证一个共享变量的原子操作。也就是说我们只能对一个变量进行赋值,不能同时更新多个。 解决的方法:把多个共享变量合并成一个共享变量。然后使用我们的AtomicReference类来保证引用对象之间的原子性。
参考资料
标签:CAS,50,更新,乐观,线程,内存,原理,解析,我们 From: https://www.cnblogs.com/zhou111f/p/17740034.htmlJava并发编程之美
公众号《Java3y》多线程系列文章