关于java:Java并发编程CAS

CAS

CAS 的概念

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

以上内容取自于维基百科，从形容的最初一句话咱们就能够看出 CAS 的思路。既然要做比拟，那符号两边是不是别离要两个值，那比拟完之后如果须要替换是不是要须要一个值。所以 CAS 存在三个参数，别离是 V, Expected 和 NewValue。V 就是原来内存中的值（要改的那个值），Expected 就是指定数据（冀望的值），NewValue 就是新的值（最初后果的值）。用代码示意如下所示：

cas(V,Expected,NewValue){if(V == Expected){V == NewValue;}
  //retry or stop
}

为什么须要 CAS

synchronized 采纳独占的形式来获取共享变量，当有其余线程心愿获取共享变量时只能挂起期待，所以synchronized 属于乐观锁，而乐观锁所带来的的线程获取锁或开释锁都会引起性能问题；而 CAS 操作则是当多个线程尝试应用 CAS 操作共享变量时，每一个线程并不会因为有其余线程正在操作该共享变量而挂起，因而 CAS 操作属于乐观锁，但最初只有其中一个线程可能操作胜利，其余线程都会失败，具体后续是重试还是进行就由各自决定。简略点说，就是晋升了效率。

乐观锁和乐观锁都是一种思维形式，而 Synchronized 和 CAS 则是其对应的体现。

CAS 毛病

那 CAS 有没有什么毛病呢？凡是任何事物都存在两面性，CAS 也不例外。接下来看看 CAS 的不足之处。

ABA 问题

CAS 最驰名的问题就是 ABA，那什么是 ABA 呢，咱们假如 内存中的值是 A，这个值的变动经验过A–>B–>A，最初在比拟查看的时候是还是可能通过，但本质上内存中的值曾经经验过变动了，这就是 ABA 问题。咱们来举个栗子。

• 线程 A 和线程 B 同时获取到要批改的值 Z，线程 A 和线程 B 应用 CAS 操作时参数内存中的值和预期的值都是 Z；
• CPU 调度，线程 A 胜利批改值 Z 为 X；
• 此时又进来个线程 C，他获取到线程 A 批改完的值 X，线程 C 应用 CAS 操作时参数内存中的值和预期的值都是 X；
• CPU 调度，可能线程 C 的操作优于线程 B，线程 C 先进行操作把值从 X 又批改为了 Z；
• 终于轮到线程 B 了，线程 B 操作把 Z 批改为了 Y，也操作胜利；

但这两头值 Z 曾经被批改过了，线程 B 是不晓得的，还是傻傻的进行了批改。所以 ABA 问题是存在肯定危险的。那 ABA 问题怎么解决呢，能够减少一个版本号（Version）作为比拟查看的根据，也就是说不光要比照内存中的值和预期的值，还须要比拟版本号，每次 CAS 操作胜利之后将版本号（Version + 1）。还是同样的栗子。

• 线程 A 和线程 B 同时获取到要批改的值 Z，线程 A 和线程 B 应用 CAS 操作时参数内存中的值和预期的值都是 Z，版本号也同为 D；
• CPU 调度，线程 A 胜利批改值 Z 为 X，并把版本号 D +1，变为 D1；
• 此时又进来个线程 C，他获取到线程 A 批改完的值 X，线程 C 应用 CAS 操作时参数内存中的值和预期的值都是 X，版本号为 D1；
• CPU 调度，可能线程 C 的操作优于线程 B，线程 C 先进行操作把值从 X 又批改为了 Z，并把版本号 D1+1，变为 D2；

• 终于轮到线程 B 了，线程 B 操作把 Z 批改为 Y，但此时因为过后获取的版本号 D 不等于当初的版本号 D2，所以操作失败。

  循环次数过长

  如果存在大量线程线程 A,B,C,D… 到线程 Z，都对同一个共享变量进行操作，同一时刻只有一个线程可能实现操作，那其余线程如果失败之后持续尝试，长时间的 CAS 重试操作，则会给 CPU 带来比拟大的开销。所以就会对自旋的次数进行限度。比方 synchronized 锁降级的时候，屡次尝试 CAS（自旋）始终未拿到锁，就会降级为重量级锁。

  Java 中 CAS 的体现(1.8)

  AtomicXXX

  Java 中 CAS 体现最闻名的便是 java.util.concurrent.atomic 包下的 Atomic 为结尾的类了，咱们这里以 AtomicLong 为栗子🌰。
  以最常应用的incrementAndGet() 为切入点，咱们来看看具体是怎么实现的。

  public class AtomicLong extends Number implements java.io.Serializable {private static final Unsafe unsafe = Unsafe.getUnsafe();
    private static final long valueOffset;
   
    static {
        try {
            valueOffset = unsafe.objectFieldOffset
                (AtomicLong.class.getDeclaredField("value"));
        } catch (Exception ex) {throw new Error(ex); }
    }
    
    private volatile long value;
  
    public final long incrementAndGet() {return unsafe.getAndAddLong(this, valueOffset, 1L) + 1L;
    }
  }

  从源代码能够看出，incrementAndGet是调用了 Unsafe 类的getAndAddLong 办法，并传入了三个参数，this（以后对象），valueOffset，1L。

• 这个 valueOffset 是变量值在内存中的偏移地址，在动态代码块中实现该值的获取，Unsafe就是通过偏移地址来失去数据的原值的；
• value 是 volatile 的，这样是为了保障 value 在多个线程之间读取到的是一样；
• 这里最初要加 1L 是因为Unsafe 的getAndAddLong办法返回的是旧值 语义是i++；而incrementAndGet 的语义是++i。

看来问题的要害还是在Unsafe 类，先简略介绍下Unsafe 类。

Java 是无奈间接拜访操作系统的，而是通过 native 办法来进行拜访。Unsafe 类就是在 Java 层面提供了这样的一个反对。native 办法多是调用 C 或着 C ++ 的代码，而后 C 或者 C ++ 代码再调用汇编语言生成一些 CPU 的指令来操作。

public final class Unsafe {public final long getAndAddLong(Object var1, long var2, long var4) {
        long var6;
        do {var6 = this.getLongVolatile(var1, var2);
        } while(!this.compareAndSwapLong(var1, var2, var6, var6 + var4));

        return var6;
    }

    public final native boolean compareAndSwapLong(Object var1, long var2, long var4, long var6);
}

getAndAddLong办法先依据传进来的以后对象和值在内存中的偏移地址失去旧值（期望值）。而后调用 native 办法 compareAndSwapLong（cas 操作），其中传入了四个参数：别离是以后对象，值在内存中偏移地址，期望值，新值。当胜利时退出循环，并返回该旧值。这里的native 办法 compareAndSwapLong，就是调用了 C 或者 C ++ 的代码，最初生成了一条 CPU 指令cmpxchg 保障了其操作的原子性。
咱们方才提到了 CAS 会遇到 ABA 问题，Java 中也提供了相应的类 AtomicStampedReference 和 AtomicMarkableReference 作为解决方案。实质上也是通过版本号，有趣味的小伙伴能够从参考链接 死磕 Java 并发 和 小家 Java 中仔细阅读其应用和原理。

LongAdder

LongAdder 在 JDK1.8 中推出，上面的 JavaDoc 是对其的作用形容与AtomicLong 的比拟。

* <p>This class is usually preferable to {@link AtomicLong} when
 * multiple threads update a common sum that is used for purposes such
 * as collecting statistics, not for fine-grained synchronization
 * control.  Under low update contention, the two classes have similar
 * characteristics. But under high contention, expected throughput of
 * this class is significantly higher, at the expense of higher space
 * consumption.

从形容中就能够看出，LongAdder更多地用于收集统计数据，而不是细粒度的同步控制。LongAdder 和 AtomicLong 在低并发时不会有较大区别，但在高并发时，LongAdder 通过就义空间了来进步了吞吐量。
简略介绍下LongAdder 的设计思路，LongAdder 会把值放到一个数组里作为数组元素的值，而后将并发线程扩散到其中的一个值去进行计算，最初将这些值累加起来就是最初的值。

该图取自【小家 java】AtomicLong 能够摈弃了，请应用 LongAdder 代替（或应用 LongAccumulator）
接下来看看源代码，咱们以increment 为切入点来看看。

public class LongAdder extends Striped64 implements Serializable {
    ...
    public void increment() {add(1L);
    }
    
     public void add(long x) {Cell[] as; long b, v; int m; Cell a;
        if ((as = cells) != null || !casBase(b = base, b + x)) {
            boolean uncontended = true;
            if (as == null || (m = as.length - 1) < 0 ||
                (a = as[getProbe() & m]) == null ||
                !(uncontended = a.cas(v = a.value, v + x)))
                longAccumulate(x, null, uncontended);
        }
    }   
}

abstract class Striped64 extends Number {
     /**
     * Base value, used mainly when there is no contention, but also as
     * a fallback during table initialization races. Updated via CAS.
     */
    transient volatile long base;
    
    @sun.misc.Contended static final class Cell {
        volatile long value;
        Cell(long x) {value = x;}
        final boolean cas(long cmp, long val) {return UNSAFE.compareAndSwapLong(this, valueOffset, cmp, val);
        }

        // Unsafe mechanics
        private static final sun.misc.Unsafe UNSAFE;
        private static final long valueOffset;
        static {
            try {UNSAFE = sun.misc.Unsafe.getUnsafe();
                Class<?> ak = Cell.class;
                valueOffset = UNSAFE.objectFieldOffset
                    (ak.getDeclaredField("value"));
            } catch (Exception e) {throw new Error(e);
            }
        }
    }
}

从代码第 9 行能够看出，Cell 数组是进行了判空操作，阐明这个数组不是一开始就初始化好的，那前面 casBase(b = base, b + x) 就是在进行 cas 操作，这个 base 的值是 LongAdder 父类Striped64 中定义的，从正文信息上来看是基值，当线程无争用时应用，看到这里就能够得出一个论断：LongAdder 一开始线程竞争无竞争时并不会间接应用 Cell 数组，而是应用 volatile 的 base 变量来存储。uncontended 示意竞争是否强烈，接下来的代码就是当上一个条件 casBase 失败示意呈现竞争了，上面的判断条件就是竞争刚呈现还没创立 Cell 数组或线程所在 Cell 的 cas 操作失败示意竞争很强烈，这时候就须要调用longAccumulate 办法进行 Cell 数组的创立和扩容。
最初当你须要取得值时须要调用 sum 办法，就是把 Cell 数组的值加起来失去最初后果。

public class LongAdder extends Striped64 implements Serializable {public long sum() {Cell[] as = cells; Cell a;
        long sum = base;
        if (as != null) {for (int i = 0; i < as.length; ++i) {if ((a = as[i]) != null)
                    sum += a.value;
            }
        }
        return sum;
    }
}

参考链接

乐观锁的一种实现形式——CAS
【死磕 Java 并发】—- 深入分析 CAS
【小家 java】原子操作你还在用 Synchronized？Atomic、LongAdder 你真有必要理解一下了
【小家 java】AtomicLong 能够摈弃了，请应用 LongAdder 代替（或应用 LongAccumulator）