乐趣区

关于java:Java并发编程CAS

作者：

jiezi

在

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）

评论

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理。

更多文章