CAS和ABA

什么是CAS ?

CAS的全称是Compare-And-Swap，它是一条CPU并发原语。
正如它的名字一样，比较并交换，它是一种很重要的同步思想。如果主内存的值跟期望值一样，那么就进行修改，否则一直重试，直到一致为止。
而原语的执行必须是连续的，在执行过程中不允许被中断，也就是说CAS是一条CPU的原子指令，不会造成所谓的数据不一致性问题。
它的功能是判断内存某个位置的值是否为预期值，如果是则更改为新的值，这个过程是原子的。

public class CasDemo {
  public static void main(String[] args) {
    //初始值
    AtomicInteger integer = new AtomicInteger(5);
    //比较并替换
    boolean flag = integer.compareAndSet(5, 10);
    boolean flag2 = integer.compareAndSet(5, 15);
    System.out.println("是否自选并替换 \t"+flag +"\t更改之后的值为："+integer.get());
    System.out.println("是否自选并替换 \t"+flag2 +"\t更改之后的值为："+integer.get());
  }
}

第一次修改，期望值为5，主内存也为5，修改成功，为10。

第二次修改，期望值为5，主内存为10，修改失败。

CAS原理

在翻了源码之后，大致可以总结出三个关键点：

1. volatile关键字：

告诉编译器，该变量随时会发生变量，每次使用该变量直接到内存中去取而不是采用暂存在寄存器中的值

1. 自旋；
2. unsafe类

Unsafe类的大部分方法都是native的，用来像C语言一样从底层操作内存。

compareAndSet方法:

// AtomicInteger类内部
public final boolean compareAndSet(int expect, int update) {
  return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}

//unsafe内部类
public final int getAndAddInt(Object var1, long var2, int var4) {
  int var5;
  do {
      var5 = this.getIntVolatile(var1, var2);
  } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));
  return var5;
}

CAS缺点

1.循环时间长开销大（如果CAS加载失败，会一直尝试，一直不成功，就一直循环，这样会给cpu带来很大负担）

2.只能保证一个共享变量的原子性，多个变量依然要加锁。

3.ABA问题
CAS算法实现一个重要前提需要取出内存中某时刻的数据，而在下时刻比较并替换，那么在这个时间差类会导致数据的变化。
比如说一个线程one从内存位置V中取出A，这时候另一个线程two也从内存中取出A，并且two进行了一些操作变成了B，然后two又将V位置的数据变成A，这时候线程one进行CAS操作发现内存中仍然是A，然后one操作成功。尽管线程one的CAS操作成功，但是不代表这个过程就是没有问题的。如果链表的头在变化了两次后恢复了原值，但是不代表链表就没有变化。

AtomicReference原子引用

使用AtomicReference 对某个类进行原子包装

User user1 = new User("Jack",25);
User user2 = new User("Lucy",21);
AtomicReference<User> atomicReference = new AtomicReference<>();
atomicReference.set(user1);
System.out.println(atomicReference.compareAndSet(user1,user2)); // true 
System.out.println(atomicReference.compareAndSet(user1,user2)); //false

AtomicStampedReference（原子性）

引入时间戳，每次变量改变，时间戳就会加1。如果时间戳不同，即使值相同，也不会成功
这样便可以解决ABA问题

AtomicStampedReference.compareAndSet(expectedReference,newReference,oldStamp,newStamp);

https://www.rongsoft.com/article/2020/09/021501525294/