Java 并发包的基石(一):原子变量和 CAS

  1. 什么是原子变量?为什么需要它们
    答:

    • 对于 count++ 这种操作,使用 synchronized 关键字可以保证原子更新操作。但使用 synchronized 的成本太高了,需要先获取锁,最后需要释放锁,获取不到锁的情况下需要等待,还会有线程的上下文切换,这些都是成本。
    • 对于这种情况,完全可以使用原子变量代替Java 并发包中的基本原子变量类型有以下几种:

      • AtomicBoolean:原子 Boolean 类型,常用来在程序中表示一个标志位
      • AtomicInteger:原子 Integer 类型。
      • AtomicLong:原子 Long 类型,常用来在程序中生成唯一序列号
      • AtomicReference:原子引用类型,用来以原子方式更新复杂类型。
      • 针对数组类型的类:AtomicLongArrayAtomicReferenceArray
      • 用于以原子方式更新对象中的字段的类,如 AtomicIntegerFieldUpdaterAtomicReferenceFieldUpdater 等。
      • Java 8 增加了几个类,在高并发统计汇总的场景中更为合适,包括 LongAdderLongAccumulatorDoubleAdderDoubleAccumulator
    • 之所以称为原子变量,是因为它包含一些以原子方式实现组合操作的方法,部分方法如下(针对 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
    • 该方法有两个参数 expectupdate,以原子方式实现了如下功能:如果当前值等于 expect,则更新为 update,否则不更新;如果更新成功,返回 true,否则返回 false
  2. 【笔试题】手写一个 AtomicInteger 的应用实例?
    答:AtomicInteger 可以在程序中用作一个计数器,多个线程并发更新,也总能实现正确性

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    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());
    }
    }

    Output: 程序的输出总是正确的,为 1000000。
  1. AtomicInteger 内部是怎样实现的?
    答:

    • AtomicInteger 的主要内部成员是 private volatile int value使用 volatile 保证内存可见性
    • 它的大部分更新方法都类似,以 incrementAndGet() 为例,代码为:

      1
      2
      3
      4
      5
      6
      7
      8
      9
      public final int incrementAndGet() {
      for(;;) {
      int current = get();
      int next = current + 1;
      if(compareAndSet(current, next)) {
      return next;
      }
      }
      }
* 代码主体是个死循环,先获取当前值 `current`,计算期望的值 `next`,然后调用 `CAS` 方法进行更新,如果更新没有成功,说明 `value` 被别的线程改了,则**再去取最新值并尝试更新直到成功为止(一直尝试,没有阻塞)**。
  1. synchronized 与原子变量的区别是
    答:

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

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

      • 原子变量是乐观的,它假定冲突比较少,但使用 CAS 更新,也就是进行冲突检测,如果确实冲突了,那也没关系,继续尝试就好了。
      • 原子变量的更新逻辑是非阻塞式的,更新冲突的时候,它就重试,不会阻塞,不会有上下文开销
    • 对于大部分比较简单的操作,无论是在低并发还是在高并发情况下,这种乐观非阻塞方式的性能都远高于悲观阻塞式方式。

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

      • ConcurrentLinkedQueueConcurrentLinkedDeque:非阻塞并发队列
      • ConcurrentSkipListMapConcurrentSkipListSet:非阻塞并发 MapSet
    • 对于并发环境中的计数、产生序列号等需求,应该使用原子变量而非锁

  2. compareAndSet() 方法是怎么实现的
    答:

    • 代码:

      1
      2
      3
      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` 也是并发包中锁、同步工具和各种容器的基础**。
  1. 【笔试题】怎样实现一个锁?使用 AtomicInteger 实现一个锁?
    答:

    • 基于 CAS,除了可以实现乐观非阻塞算法之外,还可以实现悲观阻塞式算法,比如锁
    • 实际上,Java 并发包中的所有阻塞式工具、容器、算法也都是基于 CAS(不过,也需要一些别的支持)。
    • 使用 AtomicInteger 实现一个锁

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      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);
      }
      }
  1. 使用 CAS 方式更新有一个 ABA 问题,那什么是 ABA 问题
    答:
    • 概念:假设当前值为 A,如果另外一个线程先将 A 修改成 B,再修改回成 A,那么当前线程的 CAS 操作无法分辨当前值发生过变化
    • ABA 是不是一个问题与程序的逻辑有关,一般不是问题。而如果确实有问题,解决方法是使用 AtomicStampedReference,在修改值的同时附加一个时间戳,只有值和时间戳都相同才进行修改
    • CAS 方法声明为:public boolean compareAndSet(V expectedReference, V newReference, int expectedStamp, int newStamp)AtomicStampedReference 内部会将引用值和时间戳组合为一个内部类对象,比较修改的是一个值。