3.原子变量 CAS算法

前言

在上一篇中我们讲述了关于多线程并发，导致共享属性在内存不可见的问题。以及使用 volatile 关键字设置共享属性，使其在多线程并发中内存可见。

但是我们只讲述了多线程中单一步骤的操作，我们一般在多线程并发的情况下，还会有对一个共享值存在多个步骤的执行情况。

例如：多线程并发执行i++，那么就可能存在两个线程或者以上同时给一个 i 值相加，导致相加错误的情况。

那么该类问题该怎么解决呢？

在这里我们可以引入 CAS算法以及原子变量来解决。

知识点说明

CAS 算法

- CAS (Compare-And-Swap) 是一种硬件对并发的支持，针对多处理器操作而设计的处理器中的一种特殊指令，用于管理对共享数据的并发访问。
- CAS 是一种无锁的非阻塞算法的实现。 
- CAS 包含了 3 个操作数：
  - 需要读写的内存值 V 
  - 进行比较的值 A 
  - 拟写入的新值 B 
- 当且仅当 V 的值等于 A 时，CAS 通过原子方式用新值 B 来更新 V 的值，否则不会执行任何操作。

原子变量

- 类的小工具包，支持在单个变量上解除锁的线程安全编程。事实上，此包中的类可将 volatile 值、字段和数组元素的概念扩展到那些也提供原子条件更新操作的类。

- 类 AtomicBoolean、AtomicInteger、AtomicLong 和 AtomicReference 的实例各自提供对相应类型单个变量的访问和更新。每个类也为该类型提供适当的实用工具方法。

- AtomicIntegerArray、AtomicLongArray 和 AtomicReferenceArray 类进一步扩展了原子操作，对这些类型的数组提供了支持。这些类在为其数组元素提供 volatile 访问语义方面也引人注目，这对于普通数组来说是不受支持的。 

- 核心方法：boolean compareAndSet(expectedValue, updateValue) 
  
- java.util.concurrent.atomic 包下提供了一些原子操作的常用类: 
  - AtomicBoolean 、AtomicInteger 、AtomicLong 、 AtomicReference
  - AtomicIntegerArray 、AtomicLongArray 
  - AtomicMarkableReference 
  - AtomicReferenceArray 
  - AtomicStampedReference

原子性问题的演示

1.首先编写一个实现自增序列号的线程类

/**
 * 创建一个线程类
 */
class AtomicDemo implements Runnable{

    //成员属性：线程共享属性，使用 volatile 设置内存可见性
    private volatile int serialNumber = 0;

    //线程run方法
    @Override
    public void run() {

        //休眠500毫秒, 提高并发时候的重复操作概率
        try {
            Thread.sleep(500);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        //打印本线程以及当前的serialNumber值
        //注意：在getSerialNumber将会自增 +1
        System.out.println("当前的线程: " + Thread.currentThread().getName() + ", serialNumber: " + this.getSerialNumber());

    }

    // getter: 在获取序列号的同时，对序列号进行 自增 ++
    public int getSerialNumber() {
        return serialNumber++; // 自增 +1
    }
    
}

2.创建以及启动 10个线程，查看并发打印出来的序列号 serialNumber 有没有出现相同值的情况

public class TestAtomicDemo {

    public static void main(String[] args) {

        //创建线程类对象
        AtomicDemo atomicDemo = new AtomicDemo();

        //创建10个线程
        for (int i = 0; i < 10; i++) {
            new Thread(atomicDemo).start(); // 创建以及启动线程
        }

    }

}

测试执行如下：

3.多线程并发获取到相同自增序列号的问题原因

从上图的说明中，我们大概已经知道了，由于我在线程中设置了休眠，那么就提供了多个线程同时读取 serialNumber 相同值的情况。

例如：

线程 thread-1 读取 serialNumber = 0 , 同时 thread-n 也读取 serialNumber = 0，那么这两个线程执行自增后的值就是相同的。

当时，这并不是我们希望的效果，我们更加希望每个线程就算是并发，也应该对 serialNumber 进行逐步自增(0，1，2，3，4....)，而不是存在获取相同值的情况(0, 0, 1, 1 ....)。

那么如果要解决这个问题，我们就需要给 serialNumber 自增的这个步骤设置原子性：在多线程并发的情况下，同一时刻只允许一个线程变更 serialNumber 的值。

使用CAS算法解决原子性问题

/* 
 * 二、原子变量：在 java.util.concurrent.atomic 包下提供了一些原子变量。
 *   1. volatile 保证内存可见性
 *   2. CAS（Compare-And-Swap） 算法保证数据变量的原子性
 *    CAS 算法是硬件对于并发操作的支持
 *    CAS 包含了三个操作数：
 *    ①内存值  V
 *    ②预估值  A
 *    ③更新值  B
 *    当且仅当 V == A 时， V = B; 否则，不会执行任何操作。
 */

在这里要理解号 CAS 算法如何保证原子性的话，我们来画图理解一下。

1. 画图理解

1.1 首先假设两个线程同时从内存中读取 `serialNumber = 0` 的值，此时设置 `V = 0`

1.2 在线程1 中，从内存获取 serialNumber 之后，立即将其设置回线程对象的属性中，也就是预估值 A（后续拿来与 V 比较）。并且同时对 A 进行自增，将更新值设置为 B。当 V == A ，也就是说没有其他线程更新内存 serialNumber 的值，此时允许内存 serialNumber 的值改为 B

1.3 由于线程 1 更新了内存 serialNumber 的值为 1，那么后续线程 n 获取的预估值 A 则为 1，此时由于 V 不等于 A，所以判断有其他线程更新了内存数据，本次不更新

2.代码实现原子性变量

2.1 将序列号设置为原子性变量

//使用AtomicInteger设置原子性变量
private AtomicInteger serialNumber = new AtomicInteger(0);

2.2 设置为原子性变量之后，就要调用相应的原子性方法进行数据操作（底层使用CAS算法）

serialNumber.getAndIncrement(); // 调用原子性自增操作

2.3 设置原子性操作之后，就不会有重复的值了，如下

模拟CAS算法示例

在上面我们设置了原子性操作来解决原子性问题。但是并没有写 CAS算法，因为这是底层调用的。

那么为了更好的理解，我们写一个简单的模拟CAS算法示例。

1.首先创建一个模拟CAS算法的类

/**
 * 模拟CAS算法的类
 */
class CompareAndSwap {

    //成员属性
    private int value;

    //1. 获取内存值 V
    public synchronized int get() {
        return value;
    }

    //2.比较： 获取预估值 A = expectedValue， 比较 V 与 A 过后，判断是否
    public synchronized int compareAndSwap(int expectedValue, int newValue) {
        //1.首先读取内存中的值 V，设置为 oldValue
        int oldValue = this.value;

        //2.进行 V 与 A（预估值 expectedValue） 的比较，
        //  如果 V == A，那么内存值 V 设置为 B
        if (oldValue == expectedValue) {
            this.value = newValue;
        }

        //3.不管上面的操作如何，返回原来的内存值 V
        return oldValue;
    }

    //3. 判断设置是否成功
    public synchronized boolean compareAndSet(int expectedValue, int newValue) {
        //1. 根据CAS判断返回的值 oldValue，判断是否 V == A
        //   如果返回的 V（oldValue） == A（expectedValue），则更新成功；反之失败
        return expectedValue == compareAndSwap(expectedValue, newValue);
    }
}

2.基于 CAS 算法类，创建多个线程，查看是否每次 CAS 更新成功

public class TestCompareAndSwap {

    public static void main(String[] args) {
        //1.创建cas算法类对象
        final CompareAndSwap cas = new CompareAndSwap();

        //2.遍历创建10个线程
        for (int i = 0; i < 10; i++) {
            new Thread(new Runnable() {

                @Override
                public void run() {
                    //1.在并发线程中，每个线程首先从内存获取值
                    int expectedValue = cas.get();
                    //2.将内存值设置 cas 算法中 与 随机更新值 比较
                    boolean b = cas.compareAndSet(expectedValue, (int)(Math.random() * 101));
                    //3.打印 cas 更新成功的情况
                    System.out.println(b);
                }
            }).start();
        }

    }

}