《Java-SE-第二十八章》之CAS

用户10517932

发布于 2023-10-07 14:46:02

1350

发布于 2023-10-07 14:46:02

文章被收录于专栏：929KC929KC

前言

在你立足处深挖下去,就会有泉水涌出!别管蒙昧者们叫嚷:“下边永远是地狱!”
博客主页：KC老衲爱尼姑的博客主页博主的github，平常所写代码皆在于此共勉：talk is cheap, show me the code 作者是爪哇岛的新手，水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

CAS

什么是CAS?

CAS: 全称Compare and swap，字面意思:”比较并交换“，一个 CAS 涉及到以下操作:把内存中的某个值和CPU寄存器A中的值,进行比较,如果两个值相同,就把另一个寄存器B中的值个内存的值进行交换,也就是把内存的值放到寄存器B,同时把寄存器B的值写给内存。

CAS 伪代码如下:

boolean CAS(address, expectValue, swapValue) {
 if (&address == expectedValue) {
   &address = swapValue;
        return true;
   }
    return false;
}

上述伪代码看起来是线程不安全的,实际上是安全的,因为上述操作都是硬件上提供的原子性的指令完成的。当多个线程同时对某个资源进行CAS操作,只能有一个线程操作成功,但是并不会阻塞其他线程,其他线程只会收到操作失败的信号。

CAS是怎么实现的

针对不同的操作系统，JVM 用到了不同的 CAS 实现原理，简单来讲：java 的 CAS 利用的的是 unsafe 这个类提供的 CAS 操作；unsafe 的 CAS 依赖了的是 jvm 针对不同的操作系统实现的 Atomic::cmpxchg；Atomic::cmpxchg 的实现使用了汇编的 CAS 操作，并使用 cpu 硬件提供的 lock 机制保证其原子性。简而言之，是因为硬件予以了支持，软件层面才能做到。

CAS的应用

1. 原子类

Java标准库中提供了 java.util.concurrent.atomic 包, 里面的类都是基于这种方式来实现的,这些类名都以Atomic开头,针对基础的数据类型进行封装,由于是基于CAS实现的,所以都是线程安全的。

以 AtomicInteger 举例，常见方法有

addAndGet(int delta); i += delta; decrementAndGet(); --i; getAndDecrement(); i–; incrementAndGet(); ++i; getAndIncrement(); i++;

使用演示

两个线程对同一个变量,各自自增5000,使其达到一万,这次不加锁,使用AtomicInteger 来实现

代码如下:

import java.util.concurrent.atomic.AtomicInteger;

public class AtomicDemo {
    private static AtomicInteger counter = new AtomicInteger();
    public static void main(String[] args) throws InterruptedException {
        Thread t1 = new Thread(() -> {
            for (int i = 0; i <5000;i++) {
                counter.getAndIncrement();
            }
        });
        Thread t2 = new Thread(() -> {
            for (int i = 0; i <5000;i++) {
                counter.getAndIncrement();
            }
        });
        t1.start();
        t2.start();
        t1.join();
        t2.join();
        System.out.println(counter);
    }
}

运行结果:

getAndIncrement ()的伪代码实现

class AtomicInteger {
    private int value;
    public int getAndIncrement() {
        int oldValue = value;
        while ( CAS(value, oldValue, oldValue+1) != true) {
            oldValue = value;
       }
        return oldValue;
   }
}

CAS中的i++

假设两个线程同时调用 getAndIncrement

(1) 两个线程都读取 value 的值到 oldValue 中

(2)线程1 先执行 CAS 操作. 由于 oldValue 和 value 的值相同, 直接进行对 value 赋值(value=value+1)

(3)线程2 再执行 CAS 操作, 第一次 CAS 的时候发现 oldValue 和 value 不相等, 不能进行赋值. 因此需要进入循环. 在循环里重新读取 value 的值赋给 oldValue

(4)线程2 接下来第二次执行 CAS, 此时 oldValue 和 value 相同, 于是直接执行赋值操作.

(线程1 和线程2 返回各自的 oldValue 的值即可.

2. 实现自旋锁

此外基于CSA还可以实现自旋锁

伪代码如下:

public class SpinLock {
    private Thread owner = null;
    public void lock(){
        // 通过 CAS 看当前锁是否被某个线程持有. 
        // 如果这个锁已经被别的线程持有, 那么就自旋等待. 
        // 如果这个锁没有被别的线程持有, 那么就把 owner 设为当前尝试加锁的线程. 
        while(!CAS(this.owner, null, Thread.currentThread())){
       }
   }
    public void unlock (){
        this.owner = null;
   }
}

上述代码逻辑,如果当前锁对象被线程占用,则lock()方法会不断的获取锁是否释放,一旦释放了就将owner置为null,然后根据CAS操作将占用该锁的线程设置为当前的线程,并日退出lock()方法,如果是要解锁,就将占用锁对象的线程设置为null。

CAS的ABA问题

什么是ABA问题

通过上述介绍了CAS的操作，该操作最主要的就是先比较，满足条件后交换。但是这存在一个非常极端的情况,假设有2个线程t1和t2,有一个共享变量num,初始值为A,接下里,线程t1想使用CAS把num值修改为Z,由于需要进行CAS操作,就需要先读取num的值,保存到oldNum中m,然后CAS判断当前的num的值是否为A,如果是A,就修改成Z。但是t1执行这两个操作之间,t2线程可能把num的值从A修改成B,又从B修改成A。而线程t1中的CAS的期望啥num的值不变就修改,但是num被t2线程修改了,只不过又改回来了,此时t1是无法判断当前的这个变量始终是A,还是经历了一个变化的过程,那么是否要更新num的值为Z呢。这就是ABA问题,举个栗子,来记忆一下,张三和李四是一对情侣，某一天闹掰了,就分手了,张三在分手期间又找了个女朋友,过了半年又和新的女朋友分手了和李四又在一起了,这个过程中,李四是不知道张三已经移情别恋了。

ABA问题引来的BUG

假设张三有100存款,张三想去ATM取50块钱,取款机创建了2个线程来并发执行这个操作。我们期望一个线程执行成功,另一个线程执行失败,如果使用CAS的方式来来完成这个扣款的过程就会出bug。

正常的过程

存款 100. 线程1 获取到当前存款值为 100, 期望更新为 50; 线程2 获取到当前存款值为 100, 期望更新为 50
线程1 执行扣款成功, 存款被改成 50. 线程2 阻塞等待中.
轮到线程2 执行了, 发现当前存款为 50, 和之前读到的 100 不相同, 执行失败.

异常的过程

存款 100. 线程1 获取到当前存款值为 100, 期望更新为 50; 线程2 获取到当前存款值为 100, 期望更新为 50.
线程1 执行扣款成功, 存款被改成 50. 线程2 阻塞等待中.
在线程2 执行之前, 滑稽的朋友正好给滑稽转账 50, 账户余额变成 100 !!
轮到线程2 执行了, 发现当前存款为 100, 和之前读到的 100 相同, 再次执行扣款操作

此时ATM就会扣款2次,预期结果是扣一次50,结果扣了2次。

ABA问题复现

public class AtomicReferenceDemo {
    public static AtomicReference<String> ref = new AtomicReference<String>("A");

    public static void main(String[] args) throws InterruptedException {
        System.out.println("main start ...");
        String prev = ref.get();
        update();
        Thread.sleep(1000);
        System.out.println("change A->Z "+ref.compareAndSet(prev, "Z"));
    }

    private static void update() throws InterruptedException {
        new Thread(() -> {
            System.out.println("change A-B");
            ref.compareAndSet(ref.get(), "B");
        },"t1").start();
        new Thread(() -> {
            System.out.println("change B-A");
            ref.compareAndSet(ref.get(), "A");
        },"t2").start();
    }
}

运行结果:

解决方案

给要修改的值, 引入版本号. 在 CAS 比较数据当前值和旧值的同时, 也要比较版本号是否符合预期,CAS 操作在读取旧值的同时, 也要读取版本号,真正修改的时候, 如果当前版本号和读到的版本号相同, 则修改数据, 并把版本号 + 1.如果当前版本号高于读到的版本号. 就操作失败(认为数据已经被修改过了).。

在 Java 标准库中提供了 AtomicStampedReference 类. 这个类可以对某个类进行包装, 在内部就提供了上面描述的版本管理功能.

AtomicStampedReference使用演示

代码如下

import java.util.concurrent.atomic.AtomicStampedReference;

public class AtomicStampedReferencedDemo {
    static AtomicStampedReference<String> ref = new AtomicStampedReference<>("A", 0);

    public static void main(String[] args) throws InterruptedException {
        System.out.println("main start ...");
        //获取A的值
        String prev = ref.getReference();
        //获取版本号
        int stamp = ref.getStamp();
        System.out.println(stamp);
        update();
        Thread.sleep(1000);
        System.out.println("change A->Z "+ref.compareAndSet(prev, "Z",stamp,stamp+1));
    }

    private static void update() throws InterruptedException {
        new Thread(() -> {
            System.out.println("change A-B");
            ref.compareAndSet(ref.getReference(), "B",ref.getStamp(), ref.getStamp()+1);
            System.out.println("t1的版本号:"+ref.getStamp());
            },"t1").start();
        new Thread(() -> {
            System.out.println("change B-A");
            ref.compareAndSet(ref.getReference(), "A",ref.getStamp(), ref.getStamp()+1);
            System.out.println("t2的版本号:"+ref.getStamp());
        },"t2").start();
    }

}

运行结果: