CAS(compare and swap)

文章目录

CAS 的应用
- 标准库的原子类
- 自旋锁
CAS的ABA问题
- 什么是 ABA 问题
- ABA 问题引来的 BUG
- 相关面试题

CAS是一条CPU指令,就可以完成比较和交换这样的操作
我们假设内存中的原数据V，旧的预期值A，需要修改的新值B。
1.比较 A 与 V 是否相等。（比较）
2. 如果比较相等，将 B 写入 V。（交换）
3. 返回操作是否成功。

这里说的交换,实际上更多用来赋值(把寄存器的值交换到内存中)

当多个线程同时对某个资源进行CAS操作，只能有⼀个线程操作成功，但是并不会阻塞其他线程,其他线程只会收到操作失败的信号。

CAS 可以视为是⼀种乐观锁.(或者可以理解成 CAS 是乐观锁的⼀种实现方式)

CAS 的应用

由于CPU提供了上述指令,操作系统内核也就能够完成上述操作,就会提供这样的CAS的API
JVM又对系统的CAS的API进一步封装在了"unsafe"包里,这样在Java代码中就可以使用CAS操作了

标准库的原子类

标准库提供了 java.util.concurrent.atomic 包, 里面的类都是基于CAS的方式来实现的.
典型的就是 AtomicInteger 类. 其中的 getAndIncrement 相当于 i++ 操作

import java.util.concurrent.atomic.AtomicInteger;

public class Test {
    private static AtomicInteger count = new AtomicInteger(0);

    public static void main(String[] args) throws InterruptedException {
        Thread t1 = new Thread(()-> {
            for (int i = 0; i < 50000; i++) {
                //count++
                count.getAndIncrement();
                //++count
                //count.incrementAndGet();
                //count--
                //count.getAndDecrement();
                //--count
                //count.decrementAndGet();
                //count += 10
                //count.getAndAdd(10);
            }
        });
        Thread t2 = new Thread(()-> {
            for (int i = 0; i < 50000; i++) {
                //count++
                count.getAndIncrement();
            }
        });
        t1.start();
        t2.start();
        t1.join();
        t2.join();
        System.out.println("count = " + count);
    }
}

在这里插入图片描述
此处我们代码中没有用到任何的加锁操作,这样的方式使代码以更高的效率来执行程序
这一套基于CAS不加锁来实现线程安全代码的方式,也称为"无锁编程"

虽然挺好用的但是适用范围没有锁更广泛,只能针对一些特殊场景

getAndIncrement其实是调用unsafe包里的方法

在这里插入图片描述

getAndIncrement的伪代码实现:

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

假设两个线程同时调用 getAndIncrement

两个线程都读取 value 的值到 oldValue 中(oldValue 是⼀个局部变量, 在栈上。每个线程有自己的栈)
假设线程1 先执行 CAS 操作. 由于 oldValue 和 value 的值相同, 直接进行对 value 赋值.

注意:
• CAS 是直接读写内存的, 而不是操作寄存器.
• CAS 的读内存, 比较, 写内存操作是⼀条硬件指令, 是原子的.

线程2 再执行 CAS 操作, 第⼀次 CAS 的时候发现 oldValue 和 value 不相等, 不能进行赋值. 因此需要进入循环.在循环里重新读取 value 的值赋给 oldValue
线程2 接下来第二次执行 CAS, 此时 oldValue 和 value 相同, 于是直接执行赋值操作.
线程1 和线程2 返回各自的 oldValue 的值即可.

通过形如上述代码就可以实现⼀个原子类. 不需要使用重量级锁, 就可以高效的完成多线程的自增操作.
本来比较和交换这样的操作在代码角度不是原子的. 但是在硬件层面上可以让⼀条指令完成这个操作, 也就变成原子的了.

自旋锁

自旋锁伪代码:

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

CAS的ABA问题

什么是 ABA 问题

CAS的机制是"比较-发现相等-交换"

假设存在两个线程 t1 和 t2. 有⼀个共享变量 num, 初始值为 A.
接下来, 线程 t1 想使用 CAS 把 num 值改成 Z, 那么就需要

先读取 num 的值, 记录到 oldNum 变量中.
使用 CAS 判定当前 num 的值是否为 A, 如果为 A, 就修改成 Z.

但是, 在 t1 执行这两个操作之间, t2 线程可能把 num 的值从 A 改成了 B, 又从 B 改成了 A (A->B->A)
线程 t1 的 CAS 期望 num 不变. 但是 num 的值已经被 t2 给改了. 只不过又改成 A 了. 这个时候 t1 究竟是否要更新 num 的值为 Z 呢?

t1 线程无法区分当前这个变量始终是 A, 还是经历了一个变化过程.

ABA 问题引来的 BUG

大部分的情况下, t2 线程这样的⼀个反复横跳改动, 对于 t1 是否修改 num 是没有影响的. 但是不排除⼀些特殊情况.

比如说余额有1000元,去ATM取500元,假设此处取款的操作是按照CAS的方式执行的。

	//伪代码,balance是账户余额
	void 取款() {
        int oldBalance = balance;
        
        if (!CAS(balance, oldBalance, oldBalance-500)) {
            
        }
    }

机器出bug了,按了一下没反应,又按了一下,这样就有两个线程去取款,按照正常情况,第一个取款成功,第二个因为余额(balance)变成500条件判定不是true就不会执行

但是如果这两个取款操作之间有人汇款了500元,这样第二个取款操作中余额还是1000元,就会进入if语句执行扣款操作,相当于取了两次500元

解决ABA问题的核心思路是引入"版本号"
使用账户余额判定就不太科学,账户余额"能加也能减",就容易出现ABA问题
我们约定版本号只能加不能减,每操作一次余额,版本号都要+1,如果版本号没有发生改变,数据就一定没有变过

	//伪代码
	void 取款() {
        int oldVersion = version;

        if(CAS(version, oldVersion, oldVersion+1)) {
            balance -= 500;
        }
    }