并发编程：CAS

CAS，全称为 Compare and Swap，即比较-替换。这是一个由 CPU 硬件提供并实现的原子操作。

CAS 是一种有名的无锁（lock-free）算法。也是一种现代 CPU 广泛支持的 CPU 指令级的操作，只有一步原子操作，所以非常快。而且 CAS 避免了请求操作系统来裁定锁的问题，不用麻烦操作系统，直接在 CPU 内部就搞定了。CAS 的引入是为了解决 java 锁机制带来的性能问题。

Jdk5 增加了并发包 java.util.concurrent.*,其下面的类使用 CAS 算法实现了区别于 synchronouse 同步锁的一种乐观锁。JDK5 之前 Java 语言是靠synchronized 关键字保证同步的，这是一种独占锁，也是是悲观锁。

以 AtomicInteger 为例:

import java.util.concurrent.atomic.AtomicInteger;


public class CasLearn {
  public static void main(String[] args) {
    
    AtomicInteger atomicInteger = new AtomicInteger(1);
    System.out.println(atomicInteger.compareAndSet(1, 8));
    System.out.println(atomicInteger.compareAndSet(1, 10));
  }
}

假设有三个操作数：内存值V、旧的预期值E、要修改的值U。当且仅当预期值 E 和内存值 V 相同时，才会将内存值修改为 U 并返回 true，否则什么都不做并返回 false。当然 CAS 一定要 volatile 变量配合，这样才能保证每次拿到的变量是主内存中最新的那个值，否则旧的预期值 E 对某条线程来说，永远是一个不会变的值 E，只要某次 CAS 操作失败，永远都不可能成功。

CAS 虽然很高效的解决原子操作，但是 CAS 仍然存在三大问题。ABA问题，循环时间长开销大和只能保证一个共享变量的原子操作。

并发环境下，假设初始条件是 A，去修改数据时，发现是 A 就会执行修改。但是看到的虽然是 A，中间可能发生了 A 变 B，B 又变回 A 的情况。此时 A 已经非彼 A，数据即使成功修改，也可能有问题。

解决方案：

ABA问题的解决思路就是使用版本号。可以通过 AtomicStampedReference**「解决ABA问题」**，它是一个带有标记的原子引用类，通过控制变量值的版本来保证CAS的正确性。

自旋CAS，如果一直循环执行，一直不成功，会给CPU带来非常大的执行开销。

解决方案：

破坏掉 for 死循环，当超过一定时间或者一定次数时，return退出。JDK8新增的 LongAddr,和 ConcurrentHashMap 类似的方法。当多个线程竞争时，将粒度变小，将一个变量拆分为多个变量，达到多个线程访问多个资源的效果，最后再调用sum把它合起来。

CAS 保证的是对一个变量执行操作的原子性，如果对多个变量操作时，CAS 目前无法直接保证操作的原子性的。

解决方案：

• 使用互斥锁来保证原子性；
• 将多个变量封装成对象，通过 AtomicReference 来保证原子性。

AQS 全称为 AbstractQueuedSychronizer，翻译过来应该是抽象队列同步器。

如果说 java.util.concurrent 的基础是 CAS 的话，那么 AQS 就是整个 Java 并发包的核心了，ReentrantLock、CountDownLatch、Semaphore等等都用到了它。

AQS 实际上以双向队列的形式连接所有的 Entry，比方说 ReentrantLock，所有等待的线程都被放在一个 Entry 中并连成双向队列，前面一个线程使用ReentrantLock 好了，则双向队列实际上的第一个 Entry 开始运行。

AQS 定义了对双向队列所有的操作，而只开放了 tryLock 和 tryRelease 方法给开发者使用，开发者可以根据自己的实现重写 tryLock 和 tryRelease 方法，以实现自己的并发功能。