Java 并发包的基石（一）：原子变量和 CAS

1. 什么是原子变量，为什么需要它们

• 对于 count++ 这种操作，使用 synchronized 关键字可以保证原子更新操作。但使用 synchronized 的成本太高了：需要先获取锁，最后需要释放锁，获取不到锁的情况下需要等待，还会有线程的上下文切换，这些都是成本

• 对于这种情况，完全可以使用原子变量代替，Java 并发包中的基本原子变量类型有以下几种

  • AtomicBoolean：原子 Boolean 类型，常用来在程序中表示一个标志位
  • AtomicInteger：原子 Integer 类型
  • AtomicLong：原子 Long 类型，常用来在程序中生成唯一序列号
  • AtomicReference：原子引用类型，用来以原子方式更新复杂类型
  • 针对数组类型的类：AtomicLongArray、AtomicReferenceArray
  • 用于以原子方式更新对象中的字段的类，如 AtomicIntegerFieldUpdater、AtomicReferenceFieldUpdater 等
  • Java 8 增加了几个类，在高并发统计汇总的场景中更为合适，包括 LongAdder、LongAccumulator、DoubleAdder、DoubleAccumulator

• 之所以称为原子变量，是因为它包含一些以原子方式实现组合操作的方法，部分方法如下（针对 AtomicInteger）

  • public final int getAndSet(int newValue) //以原子方式获取旧值并设置新值
  • public final int getAndIncrement() /以原子方式获取旧值并给当前值加 1
  • public final int getAndrDecrement() //以原子方式获取旧值并给当前值减 1
  • public final int getAndAdd(int delta) //以原子方式获取旧值并给当前值加 delta
  • public final int incrementAndGet() //以原子方式给当前值加 1 并获取新值
  • public final int decrementAndGet() //以原子方式给当前值减 1 并获取新值
  • public final int addAndGet(int delta) //以原子方式给当前值加 delta 并获取新值

• 这些方法的实现都依赖另一个 public 方法：public final boolean compareAndSet(int expect, int update)

  • compareAndSet() 是一个非常重要的方法，比较并设置，简称为 CAS
  • 该方法有两个参数 expect 和 update，以原子方式实现了如下功能：如果当前值等于 expect，则更新为 update，否则不更新；如果更新成功，返回 true，否则返回 false

2. 写一个 AtomicInteger 的应用实例

• AtomicInteger 可以在程序中用作一个计数器，多个线程并发更新，也总能实现正确性

  public class AtomicIntegerDemo {
      private static AtomicInteger counter = new AtomicInteger(0);
      static class Visitor extends Thread {
          @Override
          public void run() {
              for(int i=0; i<1000; i++) {
                  counter.incrementAndGet();
              }
          }
      }
      public static void main(String[] args) throws InterruptedException {
          int num = 1000;
          Thread[] threads = new Thread[num];
          for(int i=0; i<num; i++) {
              threads[i] = new Visitor();
              threads[i].start();
          }
          for(int i=0; i<num; i++) {
              threads[i].join();
          }
          System.out.println(counter.get());
      }
  }

  • 输出: 程序的输出总是正确的，为 1000000

3. AtomicInteger 内部是怎样实现的

• AtomicInteger 的主要内部成员是 private volatile int value，使用 volatile 保证内存可见性

• 它的大部分更新方法都类似，以 incrementAndGet() 为例，代码为

  public final int incrementAndGet() {
      for(;;) {
          int current = get();
          int next = current + 1;
          if(compareAndSet(current, next)) {
              return next;
          }
      }
  }

• 代码主体是个死循环，先获取当前值 current，计算期望的值 next，然后调用 CAS 方法进行更新，如果更新没有成功，说明 value 被别的线程改了，则再去取最新值并尝试更新直到成功为止（一直尝试，没有阻塞）

• 参考：Java 并发编程包中 Atomic 的实现原理

4. synchronized 与原子变量的区别是

• synchronized 和原子变量是两种不同的思维方式

  • synchronized

    • synchronized 是悲观的，它假定更新很可能冲突，所以先获取锁，得到锁后才更新
    • synchronized 代表一种阻塞式算法，得不到锁的时候，进入锁等待队列，等待其他线程唤醒，有上下文切换开销

  • 原子变量

    • 原子变量是乐观的，它假定冲突比较少，但使用 CAS 更新，也就是进行冲突检测，如果确实冲突了，那也没关系，继续尝试就好了
    • 原子变量的更新逻辑是非阻塞式的，更新冲突的时候，它就重试，不会阻塞，不会有上下文开销

• 对于大部分比较简单的操作，无论是在低并发还是在高并发情况下，这种乐观非阻塞方式的性能都远高于悲观阻塞式方式

• 原子变量相对比较简单，但对于复杂一些的数据结构和算法，非阻塞方式往往难于实现和理解。幸运的是，Java 并发包中已经提供了一些非阻塞容器，我们只需要会使用就可以了，比如

  • ConcurrentLinkedQueue 和 ConcurrentLinkedDeque：非阻塞并发队列
  • ConcurrentSkipListMap 和 ConcurrentSkipListSet：非阻塞并发 Map 和 Set

• 对于并发环境中的计数、产生序列号等需求，应该使用原子变量而非锁

5. compareAndSet() 方法是怎么实现的

• 代码

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

• 它调用了 unsafe 的 comareAndSwapInt() 方法。unsafe 的类型是 sun.misc.Unsafe，定义为：private static final Unsafe unsafe = Unsafe.getUnsafe();，它是 Sun 的私有实现，表示的是“不安全”，一般应用程序不应该直接使用

  • 原理上，一般的计算机系统都在硬件层面上直接支持 CAS 指令，而 Java 的实现都会利用这些特殊指令
  • 从程序的角度看，可以将 compareAndSet() 视为计算机的基本操作，直接接纳就好
  • CAS 是 Java 并发包的基础，基于它可以实现高效的、乐观的、非阻塞式的数据结构和算法

• CAS 也是并发包中锁、同步工具和各种容器的基础

• 参考：乐观锁的一种实现方式：CAS

6. 怎样实现一个锁，使用 AtomicInteger 实现一个锁

• 基于 CAS，除了可以实现乐观非阻塞算法之外，还可以实现悲观阻塞算法，比如锁

• 实际上，Java 并发包中的所有阻塞式工具、容器、算法也都是基于 CAS 的（不过，也需要一些别的支持）

• 使用 AtomicInteger 实现一个锁

  public class MyLock {
      private AtomicInteger status = new AtomicInteger(0); //status 表示锁的状态，0 表示未锁定，1 表示锁定
      
      //使用 CAS 方法更新，只有在更新成功后才退出，实现了阻塞的效果。但这种阻塞方式过于消耗 CPU，实际开发中应该使用 Java 并发包中的更为高效的 ReentrantLock 类
      public void lock() { 
          while(!status.compareAndSet(0, 1)) {
              Thread.yield();
          }
      }
      
      //使用 CAS 方法更新
      public void unlock() {
          status.compareAndSet(1, 0);
      }
  }

7. 使用 CAS 方式更新会有一个 ABA 问题，那什么是 ABA 问题

• 概念：假设当前值为 A，如果另外一个线程先将 A 修改成 B，再修改回成 A，那么当前线程的 CAS 操作无法分辨当前值发生过变化
• ABA 是不是一个问题与程序的逻辑有关，一般不是问题。而如果确实有问题，解决方法是使用 AtomicStampedReference，在修改值的同时附加一个时间戳，只有值和时间戳都相同才进行修改
• 其 CAS 方法声明为：public boolean compareAndSet(V expectedReference, V newReference, int expectedStamp, int newStamp)。AtomicStampedReference 内部会将引用值和时间戳组合为一个内部类对象，比较修改的是一个值

8. 使用 CAS 实现一个线程安全的单例模式

• 参考：不使用 synchronized 和 lock，如何实现一个线程安全的单例