CAS – 汪明鑫的个人博客

【CAS Compare and Swap】

CAS 的关键点在于，系统在硬件层面保证了比较并交换操作的原子性，处理器使用基于对缓存加锁或总线加锁的方式来实现多处理器之间的原子操作。

CAS 是非阻塞同步的一种常见实现。

CAS不会把线程挂起，性能要好的多，通常是基于CAS原子指令来实现的。

无锁的原子算法乐观锁是一条CPU的原子指令，其作用是让CPU先进行比较两个值是否相等，然后原子地更新某个位置的值，其实现方式是基于硬件平台的汇编指令，

在intel的CPU中，使用的是cmpxchg指令，就是说CAS是靠硬件实现的，从而在硬件层面提升效率。

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

预期值 可以理解城线程保留的副本。

当你要用 CAS 刷新该值的时候，如果发现线程工作内存和主存中不一致了（说明已经被修改），就会失败，如果一致，就可以更新成功。

public int next(){
  while(true){
     int A=读取内存中的值；
     int B=A+1;
     if（compareAndSwap(内存中的值，A，B)）{
       return B;
      }
  }
}

【CAS的优缺点】
优点：

CAS是在硬件层面保证的原子性，不会锁住当前线程，它的效率很高。

缺点：

1）ABA问题

2）循环时间长开销大。自旋 CAS 如果长时间不成功，会给 CPU 带来非常大的执行开销。因此 CAS 不适合竞争十分频繁的场景。

3）只能保证一个共享变量的原子操作。当对一个共享变量执行操作时，我们可以使用循环 CAS 的方式来保证原子操作，但是对多个共享变量操作时，循环 CAS 就无法保证操作的原子性，这个时候就可以用锁。

【虚拟机限制了自旋次数（几十次至100次），这之后虚拟机会将线程挂起，让出cpu资源。】

【ABA问题】

线程1读到内存的数值为A，然后时间片到期，撤出CPU。

线程2也读到A，把他改为B，又把B改为A。A—->B—->A

接着线程1开始运行，发现内存的值还是A，完全不知道内存被操作过

加一个版本号，就类似mysql 用version

public class AtomicStampedReference<V> {

    private static class Pair<T> {
        final T reference;
        final int stamp;
        private Pair(T reference, int stamp) {
            this.reference = reference;
            this.stamp = stamp;
        }
        static <T> Pair<T> of(T reference, int stamp) {
            return new Pair<T>(reference, stamp);
        }
    }

stamp 就是数据的版本

ABA问题可参考下文

https://www.cnblogs.com/exceptioneye/p/5373498.html

Java 5中引入了注入AutomicInteger、AutomicLong、AutomicReference等特殊的原子性变量类，它们提供的如：compareAndSet（）、incrementAndSet（）和getAndIncrement（）等方法都使用了CAS操作。因此，它们都是由硬件指令来保证的原子方法。

我们都知道 i++ 不是一个原子性操作，存在线程安全问题，如何解决

可以使用 AutomicInteger 底层其实就是CAS

我们怎么操做CAS 呢？

Unsafe是CAS的核心类，Java无法直接访问底层操作系统，而是通过本地（native）方法来访问。

JVM还是开了一个后门：Unsafe 提供了硬件级别的原子操作。

java.util.concurrent.atomic.AtomicInteger

 @CallerSensitive
    public static Unsafe getUnsafe() {
        Class var0 = Reflection.getCallerClass();
        if (!VM.isSystemDomainLoader(var0.getClassLoader())) {
            throw new SecurityException("Unsafe");
        } else {
            return theUnsafe;
        }
    }

看其中的一个方法 incrementAndGet 实现原子性的加加底层就是CAS

/**
     * Atomically increments by one the current value.
     *
     * @return the updated value
     */
    public final int incrementAndGet() {
        return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
    }

//var1 是this指针
 //var2 是地址偏移量
 //var4 是自增的数值，是自增1还是自增N
public final int getAndAddInt(Object var1, long var2, int var4) {

        //获取内存值，这是内存值已经是旧的，称为期望值E
        int var5;
        do {
            var5 = this.getIntVolatile(var1, var2);
            
             //compareAndSwapInt方法是重点，
            //var5是期望值，var5 + var4是要更新的值
            //这个操作就是调用CAS的JNI,每个线程将自己内存里的内存值M
            //与var5期望值E作比较，如果相同将内存值M更新为var5 + var4,否则做自旋操作
        } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));

        return var5;
    }

    public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);

本地方法

返回一个布尔值

更新成功返回true,失败返回false

CAS的自旋就体现在这里

while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4))

更新失败，说明期望值和内存值不同，说明已经有其他线程修改了值，需要重新读取内存值，再比较更新即 compareAndSwapInt

AutomicInteger -> Unsafe -> 本地方法 -> c++ -> 汇编指令 cmpxchg -> 二进制

【同步锁的分类】

Synchronized和Lock是悲观锁，CAS是乐观锁。

代码层次上的锁：同步锁，可重入锁，公平锁，读写锁

数据库层次上的锁：悲观锁，乐观锁，表锁，行锁，页锁，间隙锁

转载请注明：汪明鑫的个人博客 » CAS

说点什么