原子操作-CAS

仅供学习交流,如有错误请指出,如要转载请加上出处,谢谢

概念

CAS(compare and swap),比较和交换,是原子操作的一种,可用于在多线程编程中实现不被打断的数据交换操作,从而避免多线程同时改写某一数据时由于执行顺序不确定性以及中断的不可预知性产生的数据不一致问题。 该操作通过将内存中的值与指定数据进行比较,当数值一样时将内存中的数据替换为新的值—来自wikipedia

现代的大多数CPU都实现了CAS,它是一种无锁(lock-free),且非阻塞的一种算法,保持数据的一致性,原理并不难理解,下面是一段CAS的简单实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean cas(int old_v){
for(;;){
int new_v = old_v+1;
int except_v = getMemoryValue();
if(expect_v == old_v){
setMemoryValue(new_v);
break;
}else{
old_v = except_v;
}
}
return true;
}

其中getMemoryValue()方法指在内存中取出最新的值,setMemoryValue(new_v)方法指在讲新的值放入内存中,整个if-else就是CAS的操作(expect_v==old_v是compare,而setMemoryValue(new_v)是swap),假设有两个线程访问以上代码,用分段图表示如下:

以上图就是CAS的操作表现,由此可知,在CAS中,有三个核心的属性:old_i(旧值),new_i(新值),expect_i(期望值),它每次通过旧值通过计算得到新值,然后利用旧值与期望值(从内存读取的最新的值)相比较,如果相同,就将新值写入内存中替换期望值,如果不相同,则表示操作失败,重新执行。

ABA问题

CAS并不是一个完美的无锁算法,在以上的CAS操作中,getMemoryValue()方法只是在内存中取出最新的值,它不会在乎它的变化,如下图所示

如上图所示,如果线程2期间发生了两次变化,线程1是察觉不到的,经典的例子就是堆的pop和push,线程1入栈时,top的值是A,然后线程2进行了两次入堆,第二次入栈的值也是A,线程1对top进行compare,发现和旧值是一样的,就执行入堆操作,其实这时堆已经发生了改变
当然如果想要解决这个问题,只有加上一个标志或者版本号来监视它的变化,这样由两个值来最为compare的根据,如还是堆的pop和push问题,只要加上一个操作标志,当每次对进行pop或者push就加1,那compare的时候再加上对原来的改变次数和现在的改变次数进行比较,这样就可以避免ABA问题了

应用

乐观锁

乐观锁是在最理想的情况下去执行,只有在发生冲突的时候再进行处理,其实这跟CAS的理念是很符合的,也可以这么讲,CAS也是一种乐观锁技术

JAVA

java中实现了大量的CAS操作,在JDK1.5发布的java.util.concurrent包就是建立在CAS之上的,相对比与synchronized这种锁机制且阻塞的算法,无锁且非阻塞的CAS无疑在性能上有质的提升,来看看java对CAS的实现,以AtomicInteger的增量方法为例(基于JDK1.8)

1
2
3
public final int incrementAndGet() {
return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
}

这里会调用sun.misc包下的Unsafe类,这是一个调用底层指令集的final类,下面看一下getAndAddInt方法

1
2
3
4
5
6
7
8
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;
}

在这里你会看见compareAndSwapInt方法,这是一个native的方法,用来调用CPU的CAS指令实现无锁且非阻塞的增量操作,这在concurrent包下有很多这样的操作,JDK1.8的concurrentHashMap放弃了分段锁的概念,采用了CAS操作,这大大的增加了多线程下的性能

总结

很多时候在线程安全和性能方面很难得到权衡,线程安全的三大特性:可见性,原子性和顺序性,原子性往往就要加上锁去实现,现在用CAS去替代原子性,volatile保证可见性和顺序性,大大增加了多线程在操作上的性能

参考

https://zh.wikipedia.org/wiki/%E6%AF%94%E8%BE%83%E5%B9%B6%E4%BA%A4%E6%8D%A2
http://zl198751.iteye.com/blog/1848575