1. CAS基础

1.1 CAS操作原理 

CAS: compare and swap

CAS操作包含三个操作数：内存位置（V)、预期原值（A）、更新值（B）；

2 Atomic原子类

JDK5之后新增并发包java.util.concurrent.*,其下的类使用CAS算法实现了区别synchronized悲观锁之外的一种乐观锁。compareAndeSet()是调用native方法来完成cpu指令的操作

concurrent包下原子类如下

 2.1 AtomicInteger常用方法

public final int get() 获取当前的值
public final int getAndSet(int newValue) 获取当前的值，然后设置新的值
public final int getAndIncrement() 获取当前的值，然后自增
public final int getAndDecrement() 获取当前的值，然后自减

public final int incrementAndGet() 获取当前值+1

public final int decrementAndGet() 获取当前值-1
public final int getAndAdd(int delta) 获取当前的值，并加上预期的值
boolean compareAndSet(int expect, int update) 通过 CAS 方式设置整数值

2.2 incrementAndGet()如何实现原子性源码分析

源码：

private volatile int value;

/* * AtomicInteger内部声明了一个volatile修饰的变量value用来保存实际值 * 使用带参的构造函数会将入参赋值给value，无参构造器value默认值为0 */

public AtomicInteger(int initialValue) {
    value = initialValue;
}

public final int incrementAndGet() {
    return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
}

//getIntVolatile和compareAndSwap都是native方法

public final int getAndAddInt(Object var1, long var2, int var4) {
    int var5;
    do { //自旋
        var5 = this.getIntVolatile(var1, var2); //获取当前期望值A
    } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4)); //cas操作，通过比较内存区v相应值和期望值A判断内存区V对应值是否被其他线程修改，如果v值等于A则将新值var5+var4直接赋给V

    return var5;
}

2.3 compareAndSet

atomicInteger中compareAndSet源码如下

public class AtomicTest {
    public static void main(String[] args) {
        AtomicInteger atomicInteger=new AtomicInteger(0);
        atomicInteger.compareAndSet(0,11); //此时输出atomicInteger为11；如果这里改为compareAndSet(10,11)则输出atomicInteger为0
        System.out.println("output:"+atomicInteger);
    }
}

public final boolean compareAndSet(int expect, int update) {
    return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}

atomicInteger中compareAndSet函数中只有V A B，所以没法解决ABA问题，如果想解决参考part3内容

3. CAS ABA问题

CAS也并非完美的，它会导致ABA问题，就是说，当前内存的值一开始是A，被另外一个线程先改为B然后再改为A，那么当前线程访问的时候发现是A，则认为它没有被其他线程访问过。在某些场景下这样是存在错误风险的。比如在链表中。

那么如何解决这个ABA问题呢，大多数情况下乐观锁的实现都会通过引入一个版本号标记这个对象，每次修改版本号都会变话，比如使用时间戳作为版本号，这样就可以很好的解决ABA问题。

在JDK中提供了AtomicStampedReference类来解决这个问题，思路是一样的。这个类也维护了一个int类型的标记stamp，每次更新数据的时候顺带更新一下stamp。

3.1 atomicStampedReference compareAndSet源码

atomicStampedReference这个类也维护了一个int类型的标记stamp，每次更新数据的时候顺带更新一下stamp。

    public boolean compareAndSet(V   expectedReference,
                                 V   newReference,
                                 int expectedStamp,
                                 int newStamp) {
        Pair<V> current = pair;
        return
            expectedReference == current.reference &&
            expectedStamp == current.stamp &&
            ((newReference == current.reference &&
              newStamp == current.stamp) ||
             casPair(current, Pair.of(newReference, newStamp)));
    }

3.2 atomicStampedReference使用

package com.wangjun.thread;

import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicStampedReference;

public class ABA {
    
    // 普通的原子类，存在ABA问题
    AtomicInteger a1 = new AtomicInteger(10);
    // 带有时间戳的原子类，不存在ABA问题，第二个参数就是默认时间戳，这里指定为0
    AtomicStampedReference<Integer> a2 = new AtomicStampedReference<Integer>(10, 0);
    
    public static void main(String[] args) {
        ABA a = new ABA();
        a.test();
    }
    
    public void test() {
        new Thread1().start();
        new Thread2().start();
        new Thread3().start();
        new Thread4().start();
    }
    
    class Thread1 extends Thread {
        @Override
        public void run() {
            a1.compareAndSet(10, 11);
            a1.compareAndSet(11, 10);
        }
    }
    class Thread2 extends Thread {
        @Override
        public void run() {
            try {
                Thread.sleep(200);  // 睡0.2秒，给线程1时间做ABA操作
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            System.out.println("AtomicInteger原子操作：" + a1.compareAndSet(10, 11));
        }
    }
    class Thread3 extends Thread {
        @Override
        public void run() {
            try {
                Thread.sleep(500);  // 睡0.5秒，保证线程4先执行
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            int stamp = a2.getStamp();
            a2.compareAndSet(10, 11, stamp, stamp + 1);
            stamp = a2.getStamp();
            a2.compareAndSet(11, 10, stamp, stamp + 1);
        }
    }
    class Thread4 extends Thread {
        @Override
        public void run() {
            int stamp = a2.getStamp();
            try {
                Thread.sleep(1000);  // 睡一秒，给线程3时间做ABA操作
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            System.out.println("AtomicStampedReference原子操作:" + a2.compareAndSet(10, 11, stamp, stamp + 1));
        }
    }
}

 可以看到使用AtomicStampedReference进行compareAndSet的时候，除了要验证数据，还要验证时间戳。

如果数据一样，但是时间戳不一样，那么这个数据其实也被修改过了。

参考文献

https://www.cnblogs.com/danielzzz/p/15555693.html

https://www.cnblogs.com/scuwangjun/p/9098057.html

atomicInteger