Java多线程-CAS

1.乐观锁/悲观锁

他们不是指具体的什么类型的锁，而是指看待并发同步的角度。

悲观锁：总是假设最坏的情况，每次拿数据都认为别人会修改数据，所以当自己进入临界区的时候要加锁，别人只能等待，直到我释放锁才能拿到锁；悲观的认为，不加锁的并发操作一定会出问题。synchronized和ReentrantLock是悲观锁的思想。

乐观锁：总是假设最好的情况，每次拿数据都认为别人不会修改数据，所以不会加锁，乐观的认为，不加锁的并发操作是没有事情的。但是更新的时候，会判断在此期间有没有人修改过；一般基于版本号机制实现。乐观锁是无锁的，乐观锁用到的机制是CAS

2.CAS

CAS：compare and set 或者是compare and swap 的缩写，即比较并交换。

CAS 体现的是无锁并发、无阻塞并发

• 因为没有使用 synchronized，所以线程不会陷入阻塞，这是效率提升的因素之一
• 但如果竞争激烈，可以想到重试必然频繁发生，反而效率会受影响

CAS需要借助volatile才能得到共享变量的最新值，试下无锁并发。适用于线程数少，多核CPU的场景下。

无锁并发

public class compareAndSet {
    private AtomicInteger count = new AtomicInteger(count);

    //减去acount
    public void update(Integer acount){
        while(true){
            //获取最新值
            int prev = count.get();
            //修改后的值
            int newNum = prev - acount;
            //compareAndSet：比较prev和主存中的值是否一样，如果一样，就设置newNum为现在的值，否则不修改（因为已经有其他线程修改了这个共享变量的值）
            if(count.compareAndSet(prev,newNum)){
                break;
            }
        }
    }
}

---

CAS是一种无锁算法，该算法的关键依赖两个值，期望的旧值和新值，底层CPU利用原子操作判断内存原值与期望值是否相等**(正因为该指令具备原子性，所以使用CAS操作数据时不会造成数据不一致的问题)**，如果相等就给内存地址赋新值，否则不做任何处理。

下面这些使用CAS机制实现的操作的原子性的工具类的实现原理是：底层调用Unsafe提供的相关CAS方法，这些方法封装了底层CPU的CAS操作。

/**
* Object var1：需要操作的字段所在的对象
* long var2：需要操作的字段的偏移量，相对于对象头
* int var4：期望的旧值
* int var5：目标的新值
*/
public final native boolean compareAndSetInt(Object var1, long var2, int var4, int var5);
/**
* 用于获取静态属性Field在Class对象中的偏移量，还有一个方法objectFieldOffset0是获取非静态属性的偏移量(非静态属性在对象体中)
*/
private native long staticFieldOffset0(Field var1);

可以通过反射调用Unsafe中的CAS方法

public class GetUnsafe {
	public static void main(String[] args) throws NoSuchMethodException, IllegalAccessException, InvocationTargetException, InstantiationException, NoSuchFieldException {
		// 通过反射获得Unsafe对象
		Class unsafeClass = Unsafe.class;
		// 获得构造函数，Unsafe的构造函数为私有的
		Constructor constructor = unsafeClass.getDeclaredConstructor();
		// 设置为允许访问私有内容
		constructor.setAccessible(true);
		// 创建Unsafe对象
		Unsafe unsafe = (Unsafe) constructor.newInstance();
		
		// 创建Person对象
		Person person = new Person();
		// 获得其属性 name 的偏移量
		Field field = Person.class.getDeclaredField("name");
		long offset = unsafe.objectFieldOffset(field);

		// 通过unsafe的CAS操作改变值
		unsafe.compareAndSwapObject(person, offset, null, "Nyima");
		System.out.println(person);
	}
}

class Person {
    // 配合CAS操作，必须用volatile修饰
 	volatile String name;


	@Override
	public String toString() {
		return "Person{" +
				"name='" + name + '\'' +
				'}';
	}
}

3.使用CAS机制实现的工具类

3.1 原子整数

1. AtomicBoolean
2. AtomicInteger
3. AtomicLong

只能保证一个共享变量的原子操作

循环时间长开销大。自旋CAS如果长时间不成功，会给CPU带来非常大的执行开销。

CAS自旋+volatile实现了线程安全

private volatile int value;
private static final Unsafe U = Unsafe.getUnsafe();
/**
* 最终调用的是Unsafe类中的CAS方法
*/
public final boolean compareAndSet(int expectedValue, int newValue) {
    return U.compareAndSetInt(this, VALUE, expectedValue, newValue);
}

3.2 原子引用

1. AtomicReference

   传入泛型，指定要保护的对象，AtomicReference str;

2. AtomicMarkableReference

3. AtomicStampedReference

---

ABA问题：现在有一个共享变量AtomicReference<String> str = new AtomicReference("aaa");

首先线程C获取到str的值为”aaa”，线程A将str的值改为”bbb”，线程B将str的值改为”aaa”，当线程C去改时，比较并设置，以为str没有被更改过，所以将值设置为”ccc”，但是实际上它已经被修改了，只是值一样而已。

如果想达到只要线程修改，本次就不能再修改的原则，则不仅要比较值，还需要比较版本号，每次修改共享变量时版本号就加1。使用AtomicStampedReference，追踪原子引用的整个变化过程。

AtomicMarkableReference使用布尔值来标志共享变量是否被更改过，只使用于知道对象是否被修改过，不使用对象被修改

3.3 原子数组

如果我们向修改引用对象内部的内容，而不是对象本身的地址。

1. AtomicIntegerArray
2. AtomicLongArray
3. AtomicReferenceArray

---

但是在竞争激烈的场景下，会导致大量的CAS空自旋，由于线程在自旋的过程中并没有阻塞而放弃CPU，因此大量的空自旋会浪费大量的CPU资源，大大降低了程序的性能。

对于AtomicInteger来说，可以使用LongAdder来代替。

3.4 LongAdder

以空间换时间，核心思想是热点分离，将value值分成一个数组，当多线程访问时，通过Hash算法将不同的线程映射到数组的不同元素上进行操作，通过将数组的元素求和来获取最终的value

LongAdder继承Striped64

//Striped64内的成员变量
transient volatile Striped64.Cell[] cells;
transient volatile long base;
transient volatile int cellsBusy;

内部成员包含一个base变量和一个cells数组，当没有竞争的时候，只操作base，当线程执行CAS失败，说明有竞争，开始初始化cells数组，每个cell的值为0，每个线程被映射到cells[threadLocalRandomProbe & cells.length]，线程对这个cell进行操作，最终所有cell的和加上base的值就是最终的value

cells数组第一次初始化容量为2，以后每次扩容变为二倍，最终不能超过CPU核心数。

cellsBusy是标志cells数组正在初始化或者扩容，为1表示正在创建或者扩容，不能进行新cell元素的设置，其他线程需要阻塞，为0表示没有