CAS
CAS(Compare And Swap)直译过来就是比较和交换,JAVA中很多地方的实现都有CompareAndSwap的叫法,比如AomticInteger的内部实现,但CAS底层却也是可以叫Compare And Exchange。
i++为什么不是原子性?
一串很简单的代码:
public static void main(String[] args) {
int i = 99;
i++;
System.out.println(i);
}
我们通过javap -v
反编译一下这串代码,看到"真实"的代码:
0: bipush 99
2: istore_1
3: iinc 1, 1
6: getstatic #2 // Field java/lang/System.out:Ljava/io/PrintStream;
9: iload_1
10: invokevirtual #3 // Method java/io/PrintStream.println:(I)V
13: return
查阅资料,对这些指令做一下翻译:
- bitpush:将单字节的常量值-128~127压栈
- istore_1:将栈顶元素存入本地变量1中,变量1是个int类型
- iinc:将指定int型变量增加指定值
i++主要就是这3行代码了。
首先bitpush 99
会将99压栈,istore_1
将99赋值给"本地变量1",底层是没有变量名这个概念的,这些变量会按次序存放至本地变量表中,所以这里"本地变量1"就是i,istore_1
会使i=1。iinc会让"本地变量1"也就是i的值加1。最后实现i++。
从字节码上看,i++至少经历了2个指令istore
和iinc
,并没要保证并发执行的原子性。如果两个线程,AB同时读取i的值,然后自己加一,再同时写回去。这个时候i的值并不会向预想的那样。
AtomicInteger
AtomicInteger都知道,提供了原子性的自增方法getAndIncrement,源代码点进去又发现是这样实现的:
public final int getAndIncrement() {
return unsafe.getAndAddInt(this, valueOffset, 1);
}
unsafe继续点进去就会发现compareAndSwap的身影:
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;
}
这个var1其实就是指向unsafe本身,var2可以简单理解为是相对于var1的偏移地址,方法需要通过这个偏移去找到真实的值所在的内存地址,var4就是要增加的数(自增1)。
getIntVolatile可以获取unsafe对象中offset偏移地址对应的整型field的值,这里就用到了我们刚刚提到的var2偏移了,getIntVolatile通过unsafe和偏移读取到内存中的地址。简单的说getIntVolatile就是从内存中读取目标值赋值给var5。
var5进行compareAndSwap操作,也就是拿着var5的去比对内存中的值,如果相等,那么说明没有其他线程修改过,所以会更新为目标值;如果不等,那么说明有其他线程已经访问并且修改过了,这个时候就重新回到第一步,读取当前内存中的值赋给var5,然后再拿着var5去执行compareAndSwap,一直到修改成功修改。。。
其实这里compareAndSwap也可以猜到并非原子性的,因为比较然后再交换嘛,明显得经历2个步骤啊,也就是compare和swap,为啥说CAS能保证原子性呢。
看下面的分析~
最终实现
网上也能看到很多文章会有compareAndSwapInt的代码跟进,我复制了一份,最终跟进的结果就是这样的:
inline jint Atomic::cmpxchg(jint exchange_value, volatile jint* dest, jint compare_value)
{
int mp = os::is_MP();
__asm__ volatile (LOCK_IF_MP(%4) "cmpxchgl %1,(%3)"
: "=a" (exchange_value)
: "r" (exchange_value), "a" (compare_value), "r" (dest), "r" (mp)
: "cc", "memory");
return exchange_value;
}
需要注意的就是这行:
__asm__ volatile (LOCK_IF_MP(%4) "cmpxchgl %1,(%3)"
其中LOCK_IF_MP是一个宏:
#define LOCK_IF_MP(mp) "cmp $0, " #mp "; je 1f; lock; 1: "
通过百度可以知道__asm__
是C语言内联汇编表达式,也就是说__asm__
执行的是汇编,可以分析一下,先把LOCK_IF_MP宏带入可知:
cmp $0, #%4;
je 1f;
lock;
1:
cmpxchg1 %1,(%3)
通过上下文可知mp指的是Multi Processor,即多核处理,因为单核肯定就是原子操作。
#是立即数寻址,%4是占位符,通过立即数寻址读取当前系统是单核还是多核。
cmp指令会做一个减法,不保存结果,只是根据结果修改相应的标志位。代入就是用0-mp,可以知道如果mp是单核,那么mp=0,此时0-mp结果也为0,cmp后会将寄存器中ZF标志位的置为1(ZF是零标志位)。
je指令会在当前ZF=1时执行跳转,1f就是标号,可以看到最下面有个1:这个就是标号了。
也就是说,如果是单核系统,那么cmp后零标志位会为1,会执行cmpxchg1指令;如果是多核系统,那么会需要使用lock指令来保证cmpxchg的原子性。
所以说cmpxchg也并不是原子性的,也是需要加锁来实现,具体lock的实现后面不展开了。
cmpxchg也就是CAS在硬件层面的实现(Compare And Exchange),这个lock其实也有可深究的地方,和同学讨论过,xchg指令族很多都是一个周期就执行完毕的指令,也就是说应该是原子性的指令,那么这个lock的作用是保证原子性呢?还是保证内联汇编语法不破坏当前程序的上下文?
这个先留个疑惑吧,cmpxchg是否原子性并不重要了,就像一个水果吃起来和苹果一个味道,颜色也和苹果一个颜色,那么是可以把这个水果当做苹果的,而不用去纠结是否是"真"苹果。cmpxchg用lock的方式保证了CAS的原子性,既然系统这样划分,那么我们也可以人为是lock保证了cmpxchg的原子性。最终实现的结果一致就好~
CAS缺点
ABA问题
在多线程场景下CAS会出现ABA问题,关于ABA问题这里简单科普下,例如有2个线程同时对同一个值(初始值为A)进行CAS操作,这三个线程如下
- 线程1,期望值为A,欲更新的值为B
- 线程2,期望值为A,欲更新的值为B
线程1抢先获得CPU时间片,而线程2因为其他原因阻塞了,线程1取值与期望的A值比较,发现相等然后将值更新为B,然后这个时候出现了线程3,期望值为B,欲更新的值为A,线程3取值与期望的值B比较,发现相等则将值更新为A,此时线程2从阻塞中恢复,并且获得了CPU时间片,这时候线程2取值与期望的值A比较,发现相等则将值更新为B,虽然线程2也完成了操作,但是线程2并不知道值已经经过了A->B->A的变化过程。
ABA问题带来的危害:
小明在提款机,提取了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问题带来的成功提交。
解决方法:增加版本号
循环时间长开销大
如果CAS操作失败,就需要循环进行CAS操作(循环同时将期望值更新为最新的),如果长时间都不成功的话,那么会造成CPU极大的开销。
这种情况也称为自旋
解决方法:限制自旋次数防止死循环
只能保证一个共享变量的原子操作
Compare And Swap只针对一个共享变量,也就是只保证一个变量的原子性
解决方法: 如果需要对多个共享变量进行操作,可以使用加锁方式(悲观锁)保证原子性,或者可以把多个共享变量合并成一个共享变量进行CAS操作。