CAS无锁算法

发表于 | 分类于

CAS：Compare and Swap 比较并交换

java.util.concurrent包完全建立在CAS之上的，没有CAS就没有并发包。并发包借助了CAS无锁算法实现了区别于synchronized同步锁的乐观锁。因为对于CAS算法来说，就是在不加锁的前提下而假设没有冲突去完成某个操作，如果因为冲突而导致操作失败，那么就进行重试，直到成功为止。

CAS有三个操作数：真实的内存值V、预期的内存值A、要修改的新值B。当且仅当预期值A和内存值V相同时，将内存值V修改为新值B，否则什么都不做。

我们通过原子操作类AtomicInteger来研究下在没有加锁的前提下是如何做到数据正确性的：

1
private volatile int value;

通过关键字volatile保证value值在线程间是可见的，这样在获取value值的时候可以直接获取：

1
2
3
public final int get() {
        return value;
    }

我们来看看++i是怎么做到的：

1
2
3
4
5
6
7
8
public final int incrementAndGet() {
        for (;;) {
            int current = get();
            int next = current + 1;
            if (compareAndSet(current, next))
                return next;
        }
    }

1
2
3
public final boolean compareAndSet(int expect, int update) {
    return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
    }

1、其中expect是预期的内存值A，而update是要修改的值B，this就是真实的内存值V

2、这里采用了CAS操作，每次从内存中读取数据然后将此数据+1后的结果进行CAS操作，如果成功就返回结果，否则重试，直到成功。

3、compareAndSet利用JNI来完成CPU指令的操作，该方法的过程类似如下

1
2
3
4
5
6
7
8
9
if(this==expect)
    {
        this=update;
        return true;
    }
    else
    {
        return false;
    }

这里成功的过程也不是原子操作，有比较this==expect与this=update这两步操作，这两步的原子性的保证是由底层硬件支持的。
CAS的缺点
虽然CAS有效的解决了原子操作的问题，但是其仍然有三个劣势：

1、ABA问题：因为CAS需要在操作前检查下值有没有发生变化，如果没有则更新。但是如果一个值开始的时候是A，变成了B，又变成了A，那么使用CAS进行检查的时候会发现它的值没有发生变化，但是事实却不是如此。

ABA问题的解决思路是使用版本号，如A-B-A变成1A-2B-3A

2、循环时间长开销大：自旋CAS如果长时间不成功，会给CPU带来非常大的执行开销。

3、只能保证一个共享变量的原子操作：对一个共享变成可以使用CAS进行原子操作，但是多个共享变量的原子操作就无法使用CAS，这个时候只能使用锁。