What

悲观锁 vs 乐观锁

悲观锁：
加锁是一种悲观的策略，它总是认为每次访问共享资源的时候，总会发生冲突，所以宁愿牺牲性能（时间）来保证数据安全。
乐观锁：
无锁是一种乐观的策略，它假设线程访问共享资源不会发生冲突，所以不需要加锁，因此线程将不断执行，不需要停止。一旦碰到冲突，就重试当前操作直到没有冲突为止。

CAS 概述

CAS的全称为Compare-And-Swap，它是一条CPU并发原语，所以不会有线程安全问题。
因此，CAS常作为乐观锁常用的解决方案。

  • CAS的具体操作：

在修改某个主物理内存中的数据前，将该主物理内存中的数据值拷贝一份到工作内存中A1，当该值修改完毕写回物理内存时，先比较A1的值和此时主物理内存中的值是否一致，如果不一致（说明我操作的时候被其他线程修改过），就重试当前操作直到A1（每次A1值都会更新为最新值）的值与当前主物理内存中对应的值一致为止。

jdk5增加了并发包java.util.concurrent.*,其下面的类使用CAS算法实现了区别于synchronouse同步锁的一种乐观锁。JDK 5之前Java语言是靠synchronized关键字保证同步的，这是一种独占锁，也是悲观锁。

CAS 实现原理

CAS并发原语体现在JAVA语言中就是sun.misc.Unsafe类中的各种方法。调用UnSafe类中的CAS方法，JVM会实现CAS汇编指令。这是一种完全依赖于硬件的功能，通过它实现了原子操作。

再次强调，由于CAS是一种系统原语，原语属于操作系统用语范畴，是由若干条指令组成的，用于完成某个功能的程序段，并且原语的执行必须是连续的，在执行过程中不允许被中断，也就是说CAS是一条CPU的原子指令，不会造成数据不一致的问题。

核心算法_自旋锁

执行函数：CAS(V，E，N)
CAS - 图1

  • 手写自旋锁

    1. public class MySpinLock {
    3.   //原子引用线程
    4.   AtomicReference<Thread> atomicReference = new AtomicReference<>();
    6.   public void myLock() {
    7.       Thread thread = Thread.currentThread();
    8.       while (!atomicReference.compareAndSet(null, thread)) {
    9.           System.out.println(thread.getName() + "线程获得锁失败！");
    10.       }
    11.       System.out.println(thread.getName() + "线程成功获得锁！");
    12.   }
    14.   public void myUnlock() {
    15.       Thread thread = Thread.currentThread();
    16.       atomicReference.compareAndSet(thread, null);
    17.       System.out.println(thread.getName() + "线程释放锁！");
    18.   }
    19. }

  • 保证原子性_Unsafe

Java提供了一个Unsafe类，其内部方法操作可以像C的指针一样直接操作内存，方法都是native（原语）的。

CAS优缺点

  • 优点

无须加锁，也就没有类似wait的阻塞，在并发量不大的时候，可以大大提高并发效率。

  • 缺点
  1. 并发量过大且单次需操作的主物理内存中的数据的时间过长，会导致自旋过多，时间过长，这样对CPU的开销会变得非常大，尤其在对该共享数据写十分频繁的场景下尤为明显；
  2. 只能保证一个共享变量的原子操作；
  3. 引出来ABA问题。

    How

    Java提供的CAS操作

    为了让Java程序员能够受益于CAS等CPU指令，JDK并发包中有一个atomic包，它们是原子操作类，它们使用的是无锁的CAS操作，并且统统线程安全。atomic包下的几乎所有的类都使用了这个Unsafe类。
    CAS - 图2
    分类如下：
原子基本类型 原子引用类型 原子数组类型 原子字段类型
AtomicInteger AtomicMarkableReference AtomicIntegerArray AtomicIntegerFieldUpdater
AtomicLong AtomicStampedReference AtomicLongArray AtomicLongFieldUpdater
AtomicBoolean AtomicReference AtomicReferenceArray AtomicReferenceFieldUpdater

⚠️ 原子引用类型，是带范型的，使其引用类型的对象 的所有操作具有原子性。如果引用类型为Integer等基础数值类型时，当范围在[-127～128]时会从常量池中获取对象，但超过这个范围则会创建新的对象（这点需要注意，否则CAS每次判断的数值看似一样，实际并非同一个对象而导致失败！）。

这些类中，最有代表性的就是AtomicInteger类，源码如下：

  1. public class AtomicInteger extends Number implements java.io.Serializable {
  3.     private static final long serialVersionUID = 6214790243416807050L;
  5.     // 这个就是封装CAS操作的指针
  6.     private static final Unsafe unsafe = Unsafe.getUnsafe();
  8.     //原来内部的共享变量，就是这个value，并且使用volatile让其在多个线程之间可见
  9.     private volatile int value;
  11.     //初始化的构造函数
  12.     public AtomicInteger(int initialValue) {
  13.         value = initialValue;
  14.     }
  15.     //获取当前值
  16.     public final int get() {
  17.         return value;
  18.     }
  19.     //设置当前的共享变量的值
  20.     public final void set(int newValue) {
  21.         value = newValue;
  22.     }
  23.     //使用CAS操作设置新的值，并且返回旧的值
  24.     public final int getAndSet(int newValue) {
  25.         //使用指针unsafe类的三大原子操作方法之一
  26.         return unsafe.getAndSetInt(this, valueOffset, newValue);
  27.     }
  28.     //把expect与内部的value进行比较，如果相等，那么把value的值设置为update的值
  29.     public final boolean compareAndSet(int expect, int update) {
  30.         return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
  31.     }
  32.     //返回value，并把value + 1 
  33.     public final int getAndIncrement() {
  34.         return unsafe.getAndAddInt(this, valueOffset, 1);
  35.     }
  36.     //自增，并且返回自增后的值
  37.     public final int incrementAndGet() {
  38.         return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
  39.     }
  40. }

Why

ABA问题

  • 问题描述：

在CAS的核心算法中，通过死循环不断获取最新的E。如果在此之间，V被修改了两次，但是最终值还是修改成了旧值V，这个时候，就不好判断这个共享变量是否已经被修改过。

  • 解决方案：

为了防止这种不当写入导致的不确定问题，原子操作类提供了一个带有时间戳的原子操作类 AtomicStampedReference。

带有时间戳的原子操作类AtomicStampedReference，当其对应的数值被修改时，除了更新数据本身外，还必须要更新时间戳。当AtomicStampedReference设置对象值时，对象值以及时间戳都必须满足期望值，写入才会成功。因此，即使对象值被反复读写，写回原值，只要时间戳发生变化，就能防止不恰当的写入。

  • AtomicStampedReference底层实现：

    通过Pair私有内部类存储数据和时间戳, 并构造volatile修饰的私有实例接着看AtomicStampedReference类的compareAndSet（）方法的实现：
    同时对当前数据和当前时间进行比较，只有两者都相等是才会执行casPair()方法，单从该方法的名称就可知是一个CAS方法，最终调用的还是Unsafe类中的compareAndSwapObject方法到这我们就很清晰AtomicStampedReference的内部实现思想了，通过一个键值对Pair存储数据和时间戳，在更新时对数据和时间戳进行比较，只有两者都符合预期才会调用Unsafe的compareAndSwapObject方法执行数值和时间戳替换，也就避免了ABA的问题。

  1. public class AtomicStampedReference<V> {
  2.      //通过一个volatile修饰的Pair对象
  3.      private volatile Pair<V> pair;
  4.      //嵌套类Pair技能存储对象引用，也存储了时间戳
  5.      private static class Pair<T> {
  6.           final T reference;
  7.           final int stamp;
  8.           private Pair(T reference, int stamp) {
  9.             this.reference = reference;
  10.             this.stamp = stamp;
  11.     }
  12.     public boolean compareAndSet(V expectedReference,V newReference,int expectedStamp,int newStamp) {
  13.         Pair<V> current = pair;
  14.         return expectedReference == current.reference &&
  15.                expectedStamp == current.stamp &&
  16.                ((newReference == current.reference &&
  17.                newStamp == current.stamp) ||
  18.                casPair(current, Pair.of(newReference, newStamp)));
  19.     }
  20. }

Unsafe类

详见：https://www.bilibili.com/video/BV1zb411M7NQ?p=12
https://www.bilibili.com/video/BV1zb411M7NQ?p=29