CAS 与 volatile
- CAS
- volatile
为什么无锁效率高
CAS特点
CAS的应用
- 原子整数
- 原子引用
  - AtomicStampedReference
  - AtomicMarkableReference

案例

使用CAS无锁方式保证银行转账业务线程安全，CAS的核心就是自旋重试，直到结果正确。


public class TestCAS {
    public static void main(String[] args) {
        Account account = new AccountCas(10000);
        Account.demo(account);
    }
}
class AccountCas implements Account {
    private AtomicInteger balance;
    public AccountCas(int balance) {
        this.balance = new AtomicInteger(balance);
    }
    @Override
    public Integer getBalance() {
        return balance.get();
    }
    @Override
    public void withdraw(Integer amount) {
        while (true) {
            // 获取余额的最新值
            int prev = balance.get();
            // 要修改的余额
            int next = prev - amount;
            // 真正修改
            if (balance.compareAndSet(prev, next)) {
                break;
            }
        }
        //        balance.getAndAdd(-1 * amount);
    }
}
interface Account {
    // 获取余额
    Integer getBalance();
    // 取款
    void withdraw(Integer amount);
    /**
     * 方法内会启动 1000 个线程，每个线程做 -10 元 的操作
     * 如果初始余额为 10000 那么正确的结果应当是 0
     */
    static void demo(Account account) {
        List<Thread> ts = new ArrayList<>();
        for (int i = 0; i < 1000; i++) {
            ts.add(new Thread(() -> {
                account.withdraw(10);
            }));
        }
        long start = System.nanoTime();
        ts.forEach(Thread::start);
        ts.forEach(t -> {
            try {
                t.join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        });
        long end = System.nanoTime();
        System.out.println(account.getBalance() + " cost: " + (end - start) / 1000_000 + " ms");
    }
}

CAS 与 volatile

CAS

CAS无锁保证线程安全，其中的关键是 compareAndSet，它的简称就是 CAS （也有 Compare And Swap 的说法），它必须是原子操作（硬件层面实现）。


public void withdraw(Integer amount) {
    while (true) {
        // 需要不断尝试，直到成功为止
        while (true) {
            // 比如拿到了旧值 1000
            int prev = balance.get();
            // 在这个基础上 1000-10 = 990
            int next = prev - amount;
         /*
        compareAndSet 正是做这个检查，在 set 前，先比较 prev 与当前值
        - 不一致了，next 作废，返回 false 表示失败
        比如，别的线程已经做了减法，当前值已经被减成了 990
        那么本线程的这次 990 就作废了，进入 while 下次循环重试
        - 一致，以 next 设置为新值，返回 true 表示成功
        */
            if (balance.compareAndSet(prev, next)) {
                break;
            }
        }
    }
}

线程1在修改余额从100->90时，线程2已经将余额改为90了
线程1在进行cas操作时发现，期望值是100实际值是90，则本次cas操作失败，重新重主存中获取值90，再次进行cas操作
线程1根据主存中的90自旋一次为80后，线程2又改变了主存中的值为80，线程1本次cas操作又失败，继续自旋
线程1获取主存值80，进行计算，此时没有其他线程在操作，线程1本次cas操作成功

volatile

获取共享变量时，为了保证该变量的可见性，需要使用 volatile修饰。它可以用来修饰成员变量和静态成员变量，他可以避免线程从自己的工作缓存中查找变量的值，必须到主存中获取它的值，线程操作 volatile变量都是直接操作主存。即一个线程对 volatile变量的修改，对另一个线程可见。
CAS 必须借助 volatile 才能读取到共享变量的最新值来实现【比较并交换】的效果

为什么无锁效率高

无锁情况下，即使重试失败，线程始终在高速运行，没有停歇，而 synchronized 会让线程在没有获得锁的时候，发生上下文切换，进入阻塞。

CAS特点

结合 CAS和 volatile可以实现无锁并发，适用于线程数少、多核 CPU 的场景下。CAS是基于乐观锁的思想：最乐观的估计，不怕别的线程来修改共享变量，就算改了也没关系，可以再重试。
synchronized是基于悲观锁的思想：最悲观的估计，得防着其它线程来修改共享变量，我上了锁你们都别想改，我改完了解开锁，你们才有机会。
CAS体现的是无锁并发、无阻塞并发。

CAS的应用

原子整数

J.U.C并发包提供了：

AtomicBoolean
AtomicInteger

AtomicLong
以 AtomicInteger为例

AtomicInteger i = new AtomicInteger(0);
// 获取并自增（i = 0, 结果 i = 1, 返回 0），类似于 i++
System.out.println(i.getAndIncrement());
// 自增并获取（i = 1, 结果 i = 2, 返回 2），类似于 ++i
System.out.println(i.incrementAndGet());
// 自减并获取（i = 2, 结果 i = 1, 返回 1），类似于 --i
System.out.println(i.decrementAndGet());
// 获取并自减（i = 1, 结果 i = 0, 返回 1），类似于 i--
System.out.println(i.getAndDecrement());
// 获取并加值（i = 0, 结果 i = 5, 返回 0）
System.out.println(i.getAndAdd(5));
// 加值并获取（i = 5, 结果 i = 0, 返回 0）
System.out.println(i.addAndGet(-5));
// 获取并更新（i = 0, p 为 i 的当前值, 结果 i = -2, 返回 0）
// 其中函数中的操作能保证原子，但函数需要无副作用
System.out.println(i.getAndUpdate(p -> p - 2));
// 更新并获取（i = -2, p 为 i 的当前值, 结果 i = 0, 返回 0）
// 其中函数中的操作能保证原子，但函数需要无副作用
System.out.println(i.updateAndGet(p -> p + 2));
// 获取并计算（i = 0, p 为 i 的当前值, x 为参数1, 结果 i = 10, 返回 0）
// 其中函数中的操作能保证原子，但函数需要无副作用
// getAndUpdate 如果在 lambda 中引用了外部的局部变量，要保证该局部变量是 final 的
// getAndAccumulate 可以通过 参数1 来引用外部的局部变量，但因为其不在 lambda 中因此不必是 final
System.out.println(i.getAndAccumulate(10, (p, x) -> p + x));
// 计算并获取（i = 10, p 为 i 的当前值, x 为参数1, 结果 i = 0, 返回 0）
// 其中函数中的操作能保证原子，但函数需要无副作用
System.out.println(i.accumulateAndGet(-10, (p, x) -> p + x));

原子引用

基本类型原子类只能更新一个变量，如果需要原子更新多个变量，需要使用引用类型原子类。

AtomicReference：引用类型原子类
AtomicStampedReference：原子更新引用类型里的字段原子类
AtomicMarkableReference：原子更新带有标记位的引用类型
案例 ```java public class Test35 { public static void main(String[] args) {
```
  DecimalAccount.demo(new DecimalAccountCas(new BigDecimal("10000")));
```
} }

class DecimalAccountCas implements DecimalAccount { //保护BigDecimal对象的原子操作 private AtomicReference balance;

public DecimalAccountCas(BigDecimal balance) {
    this.balance = new AtomicReference<>(balance);
}
@Override
public BigDecimal getBalance() {
    return balance.get();
}
@Override
public void withdraw(BigDecimal amount) {
    while(true) {
        //对BigDecimal对象里的值进行原子保护
        BigDecimal prev = balance.get();
        BigDecimal next = prev.subtract(amount);
        if (balance.compareAndSet(prev, next)) {
            break;
        }
    }
}

}

interface DecimalAccount { // 获取余额 BigDecimal getBalance();

// 取款
void withdraw(BigDecimal amount);
/**
 * 方法内会启动 1000 个线程，每个线程做 -10 元 的操作
 * 如果初始余额为 10000 那么正确的结果应当是 0
 */
static void demo(DecimalAccount account) {
    List<Thread> ts = new ArrayList<>();
    for (int i = 0; i < 1000; i++) {
        ts.add(new Thread(() -> {
            account.withdraw(BigDecimal.TEN);
        }));
    }
    ts.forEach(Thread::start);
    ts.forEach(t -> {
        try {
            t.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    });
    System.out.println(account.getBalance());
}

}

<a name="HEGB3"></a>
### ABA 问题及解决
- **ABA问题复现**
```java
/**
 * @author SongHongWei
 * 模拟ABA问题,CAS中的
 * @date 2021/10/3
 */
@Slf4j
public class ABAProblem {
    static AtomicReference<String> ref = new AtomicReference<>("A");
    public static void main(String[] args) {
        log.info("main start...");
        String prev = ref.get();
        aba();
        sleep(1);
        log.info("change A->C...{}", ref.compareAndSet("A", "C"));
    }
    /**
     * @description 线程1 先将共享变量从A->B,线程B再将共享变量B->A
     * @author SongHongWei
     */
    private static void aba() {
        new Thread(() -> {
            boolean flag = ref.compareAndSet("A", "B");
            log.info("change A->B...{}", flag);
        }, "t1").start();
        sleep(0.5);
        new Thread(() -> {
            boolean flag = ref.compareAndSet("B", "A");
            log.info("change B->A...{}", flag);
        }, "t2").start();
    }
}

分析

主线程仅能判断出共享变量的值与最初值 A是否相同，不能感知到这种从 A改为 B又改回 A的情况，如果主线程希望：只要有其它线程【动过了】共享变量，那么自己的 cas就算失败，这时，仅比较值是不够的，需要再加一个版本号

AtomicStampedReference

AtomicStampedReference可以给原子引用加上版本号，追踪原子引用整个的变化过程，如：A ``-``> B ``-``> A ``-``>C ，通过AtomicStampedReference，可以知道，引用变量中途被更改了几次。

static AtomicStampedReference<String> sref = new AtomicStampedReference<>("A", 0);
    public static void main(String[] args) {
        log.info("main start...");
        atomicSref();
    }
    private static void atomicSref() {
        //获取值
        String s = sref.getReference();
        //获取版本号
        int stamp = sref.getStamp();
        saba();
        sleep(1);
        //执行失败,因为版本号被其他线程修改了
        log.info("change A->C...{},现在的版本号{}", sref.compareAndSet(s, "C", stamp, stamp + 1), sref.getStamp());
    }
    private static void saba() {
        new Thread(() -> {
            int stamp = sref.getStamp();
            boolean flag = sref.compareAndSet(sref.getReference(), "B", stamp, stamp + 1);
            log.info("change A->B...{}", flag);
        }, "t1").start();
        sleep(0.5);
        new Thread(() -> {
            int stamp = sref.getStamp();
            boolean flag = sref.compareAndSet(sref.getReference(), "A", stamp, stamp + 1);
            log.info("change B->A...{}", flag);
        }, "t2").start();
    }

AtomicMarkableReference

AtomicStampedReference可以记录变量被修改过多少次，但是有时候，程序并不关心引用变量更改了几次，只是单纯的关心是否更改过，所以就有了AtomicMarkableReference

案例

保洁阿姨与主人共用一个垃圾袋，垃圾袋满了可以换个垃圾袋，也可以倒掉垃圾继续使用垃圾打，只要垃圾袋是空的就不需要更换垃圾袋。


public class ABAProblem {
    public static void main(String[] args) throws InterruptedException {
        GarbageBag bag = new GarbageBag("装满了垃圾");
        // 参数2 mark 可以看作一个标记，表示垃圾袋满了
        AtomicMarkableReference<GarbageBag> ref = new AtomicMarkableReference<>(bag, true);
        log.debug("start...");
        GarbageBag prev = ref.getReference();
        log.debug(prev.toString());
        //保洁线程倒掉垃圾
        new Thread(() -> {
            log.debug("start...");
            bag.setDesc("空垃圾袋");
            ref.compareAndSet(bag, bag, true, false);
            log.debug(bag.toString());
        }, "保洁阿姨").start();
        sleep(1);
        log.debug("想换一只新垃圾袋？");
        boolean success = ref.compareAndSet(prev, new GarbageBag("新垃圾袋"), true, false);
        log.debug("换了么？" + success);
        log.debug(ref.getReference().toString());
    }
}
class GarbageBag {
    String desc;
    public GarbageBag(String desc) {
        this.desc = desc;
    }
    public void setDesc(String desc) {
        this.desc = desc;
    }
    @Override
    public String toString() {
        return super.toString() + " " + desc;
    }
}

并发编程学习笔记

CAS原理及应用