入坑JAVA多线程并发(九）CAS和ABA

ゞ浴缸里的玫瑰 2022-05-19 00:07 158阅读 0赞

如果了解数据库的悲观锁和乐观锁的话，对于理解CAS就很简单了，因为CAS就是乐观锁的具体实现。  
　　悲观锁：在操作数据库时本能的觉得一定会有竞争，所以把数据锁住，不让其他事物对对应的数据进行操作，在本次操作之后把锁释放，其它事物才可以进行操作。这个在java里面就类似于synchronized。  
　　乐观锁：在操作数据库时都觉得不会有其它事物和自己进行竞争，事物开始的时候就把对应的数据取出，在对数据进行更新的时候把数据和之前取出的数据进行对比，如果一样说明没有其他事物进行操作，可以进行操作，如果不一致，说明期间有其它事物对数据进行了操作，那么这次操作失败，进行重试。

### 1、CAS的三个值 ###

Ｖ：要更新的变量
    Ｅ：变量期望的值
    Ｎ：变量要更新的值

![这里写图片描述][70]  
如上图所示，如果Ｖ和Ｅ的值不符合，就重新取值进行操作，一直到相等执行更新或者符合退出条件为止。

### 2、原子操作类 ###

有AtomicBoolean，AtomicInteger，AtomicLong，这里以AtomicInteger的代码为例  
如下代码：

public class Main { 
        static volatile int cas = 0;
        public static void main(String[] args) {
            new Thread(() -> {
                for (int i = 0 ;i < 100; i++){
                    try {
                        Thread.sleep(100);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                    cas++;
                }
                System.out.println(cas);
            }).start();
            new Thread(() -> {
                for (int i = 0 ;i < 100; i++){
                    try {
                        Thread.sleep(100);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                    cas++;
                }
                System.out.println(cas);
            }).start();
    
        }
    }

输出为

> 173  
> 173

测试多次结果都是小于200，这里volatile只能保证可见性和指令重排。无法确保原子性，这里cas++有三个操作，取出cas的值，加1，同步到主存。所以存在线程安全问题。  
如果用AtomicInteger类型

public class Main { 
        static AtomicInteger cas = new AtomicInteger(0);
        public static void main(String[] args) {
            new Thread(() -> {
                for (int i = 0 ;i < 100; i++){
                    try {
                        Thread.sleep(1);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                    cas.incrementAndGet();
                }
                System.out.println(cas);
            }).start();
            new Thread(() -> {
                for (int i = 0 ;i < 100; i++){
                    try {
                        Thread.sleep(1);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                    cas.incrementAndGet();
                }
                System.out.println(cas);
            }).start();
    
        }
    }

输出为

> 200  
> 200

这里是因为数太小，数据改大一点，第一个数就是小于200的，第二个数会一直等于预期的和，这里就是用了CAS。

###### incrementAndGetf方法 （1.7和1.8版本） ######

//1.7版本
    public final int incrementAndGet() {
        for (;;) {
            int current = get();
            int next = current + 1;
            if (compareAndSet(current, next))
                return next;
        }
    }
    //CAS操作
    public final boolean compareAndSet(int expect, int update) {
        return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
    }
    
    //unsafe类的本地操作方法
    public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);
    
    //1.8版本
    //AtomicInteger的incrementAndGet方法
    public final int incrementAndGet() {
        return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
    }
    
    //CAS操作
    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;
    }
    
    //获取实时的value的值
    public native int getIntVolatile(Object var1, long var2);

compareAndSwapInt这个方法有四个参数，其中第一个参数为需要改变的对象，第二个为偏移量(即之前求出来的valueOffset的值)，第三个参数为期待的值，第四个为更新后的值。整个方法的作用即为若调用该方法时，value的值与expect这个值相等，那么则将value修改为update这个值，并返回一个true，如果调用该方法时，value的值与expect这个值不相等，那么不做任何操作，并范围一个false；  
　　1.7和1.8的不同在于CAS的操作返回值不一样。1.7是直接返回加1后的值，1.8的CAS返回的是原始的值，只是在incrementAndGetf方法内把返回值进行加1再返回。  
　　CAS就是循环获取value值，执行compareAndSwapInt方法。返回true就代表执行成功。退出循环。concurrent包很多类都是基于CAS实现的。  
　　其它方法包括getAndIncrement、getAndDecrement、getAndAdd、decrementAndGet等就是对int值进行加减运输，内部实现原理和incrementAndGet是一样的

### 3、ABA问题和AtomicStampedReference类 ###

ABA问题：CAS算法实现一个重要前提需要取出内存中某时刻的数据，而在下时刻比较并替换，那么在这个时间差类会导致数据的变化。  
　　**举个栗子**：一个用单向链表实现的堆栈，栈顶为A，这时线程T1已经知道A.next为B，然后希望用CAS将栈顶替换为B，在T1执行之前，线程T2介入，将A、B出栈，再pushD、C、A。此时轮到线程T1执行CAS操作，检测发现栈顶仍为A，所以CAS成功，栈顶变为B，但实际上B.next为null。具体如下图  
　　![这里写图片描述][70 1]  
解决方法就是添加一个版本号。乐观锁的一种实现也是通过版本号实现，每一次操作都改变版本号，对比版本号确定是否执行操作。  
JAVA中AtomicStampedReference就实现了这种版本标记的功能。

public class Main { 
    
        static AtomicStampedReference<Integer> stampedReference = new AtomicStampedReference<>(0,1);
        public static void main(String[] args) {
            new Thread(() -> {
                for (int i = 0 ;i < 1000; i++){
                    try {
                        Thread.sleep(1);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                    stampedReference.compareAndSet(stampedReference.getReference(),stampedReference.getReference()+1,stampedReference.getStamp(),stampedReference.getStamp()+1);
                }
                System.out.println(stampedReference.getReference());
            }).start();
            new Thread(() -> {
                for (int i = 0 ;i < 1000; i++){
                    try {
                        Thread.sleep(1);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                    stampedReference.compareAndSet(stampedReference.getReference(),stampedReference.getReference()+1,stampedReference.getStamp(),stampedReference.getStamp()+1);
                }
                System.out.println(stampedReference.getReference());
            }).start();
    
        }
    }

输出为：

> 1970  
> 1971

重复测试多次输出一直是两个小于2000的数字，因为两个线程一起操作。会存在线程2在操作期间线程1已经把数字更新了，线程2就会操作失败。所以最终的结果一定会和预期不符。

[70]: /images/20220519/c2e04614be0842adaa591f705f8c3ac5.png
[70 1]: /images/20220519/e3f9c07c57a744cea862abe1c749675b.png