CAS(Compare And Swap比较交换)

java

Compare And Swap 即比较交换

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

1
2
3
4
5
6
7
8
 
int cas(long *addr, long old, long new)
{
    /* 原子性操作. */
    if(*addr != old)
        return 0;
    *addr = new;
    return 1;
}

CAS开销

JVM对CAS的支持

在JDK1.5之前，如果不编写明确的代码就无法执行CAS操作
在JDK1.5中引入了底层的支持，在int、long和对象的引用等类型上都公开了CAS的操作

AtomicXXX实现用了乐观锁技术，调用了sun.misc.Unsafe类库里面的 CAS算法，用CPU指令来实现无锁自增。所以，AtomicLong.incrementAndGet的自增比用synchronized的锁效率倍增。

1
2
3
4
5
6
7
 
public final boolean compareAndSet(long expect, long update) {
  // 字段的偏移量
  // Unsafe只有根加载器加载的类才能调用，如果想获得unsafe对象只能通过反射的方式获得
  valueOffset = unsafe.objectFieldOffset(AtomicLong.class.getDeclaredField("value"));
  // 操作对象，偏移量，预期值，修改值
	return unsafe.compareAndSwapLong(this, valueOffset, expect, update);
}

CAS使用时机

在轻度到中度的争用情况下，非阻塞算法的性能会超越阻塞算法，因为 CAS 的多数时间都在第一次尝试时就成功，而发生争用时的开销也不涉及线程挂起和上下文切换，只多了几个循环迭代。没有争用的 CAS 要比没有争用的锁便宜得多，而争用的 CAS 比争用的锁获取涉及更短的延迟。

缺陷

  • ABA问题

    因为CAS需要在操作值的时候，检查值有没有发生变化，如果没有发生变化则更新，但是如果一个值 原来是A，变成了B，又变成了A，那么使用CAS进行检查时会发现它的值没有发生变化，但是实际上却变化了

    解决思路就是使用版本号。在变量前面追加版本号，每次变量更新的时候把版本号+1，那么A->B->A 就会变成1A->2B->3A。从JDK1.5 开始，JDK的Atomic包里提供了一个类Atomic包里提供了一个AtomicStampedReference来解决ABA问题

  • 循环时间长，开销大

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

  • 只能保证一个共享变量的原子操作

    当对一个共享变量执行操作时，我们可以使用循环CAS的方式来保证原子操作，但是对多个共享变量操作时，循环CAS就无法保证操作的原子
    性，这个时候就可以用锁。还有一个取巧的办法，就是把多个共享变量合并成一个共享变量来操作。比如，有两个共享变量i＝2，j=a，合并一下ij=2a，然后用CAS来操作ij。从Java 1.5开始，JDK提供了AtomicReference类来保证引用对之间的原子性，就可以把多个变量放在一个对象里来进行CAS操作。

ABA

实现原理

ConcurrentHashMap的实现原理

ConcurrentLinkedQueue实现方法

参考

 concurrent
 上一篇

concurrent