CAS(Compare and swap)是设计并发算法时用到的一种技术。相比传统的锁和同步技术,资源竞争较少的情况下,CAS可以节约更多的资源。
基本思路
CAS的基本思路其实不算特别复杂,用下面这个伪代码来说明CAS的核心:
CAS(V,E,N)
在上述函数中:
- V: 要被更新的变量内存地址
- E: 旧的值
- N: 更新之后的值
CAS()
函数会返回布尔值,仅有V的值等于E的时候,V的值才会被设置成N。如果V和E的值不一致,说明这个变量已经被别的线程修改,那么CAS()
函数就会返回false
。
可以用以下的思路来实现无锁地正确修改一个值:
do{
备份旧数据;
基于旧数据构造新数据;
}while(!CAS( 内存地址,旧数据,新数据 ))
AtomicInteger的例子
在jdk的atomic
包下,拥有大量使用CAS辅助完成的类。
在此之前,先介绍下Unsafe
这个类,这个类在sun.misc
包下的,这个类里面封装了一些不安全的操作(主要是Oracle不希望大家使用的方法),这些大多数是一些native
的方法,其中跟CAS密切相关的一个方法compareAndSwapInt()
方法:
public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);
以上方法中,第一个参数var1
是给定的要操作对象,var2
是字段到对象头部的偏移量(方便快速定位到字段),var4
表示旧的值,var5
表示希望设置的值。
接下来看到Unsafe
中另外一个方法利用这个CAS函数来无锁地添加值:
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;
}
以上这段代码的思路和伪代码中CAS是一个套路,在当前线程正确修改了值之后,将原值返回。
这个时候回到AtomicInteger
,先看下它的两个参数:
// 这里面存着包装类的值
private volatile int value;
// 这里保存了value属性在AtomicInteger对象的偏移量,方便定位属性的位置
private static final long valueOffset;
接着看它最经典的两个自增方法就非常简单了,它们利用Unsafe
的getAndAddInt()
就可以轻松地完成无锁的正确自增:
/**
* Atomically increments by one the current value.
*
* @return the updated value
*/
public final int incrementAndGet() {
return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
}
/**
* Atomically increments by one the current value.
*
* @return the previous value
*/
public final int getAndIncrement() {
return unsafe.getAndAddInt(this, valueOffset, 1);
}