CAS（Compare and Swap）

CAS 即 compare and swap（比较与交换），是一种乐观锁机制，也叫无锁机制。即不使用锁的情况下实现多线程之间的变量同步，也就是在没有线程被阻塞的情况下实现变量的同步，所以也叫非阻塞同步（Non-blocking Synchronization)

CAS 中涉及三个要素：

需要读写的内存值 V
进行比较的值 A
拟写入的新值 B

当且仅当预期值A和内存值V相同时，将内存值V修改为B，否则什么都不做

CAS的原子性

CAS操作是原子的，这意味着它要么完全执行成功，要么完全不执行。即使在多线程环境中，也不会有其他线程能够干扰CAS操作的执行

使用volatile关键字修改变量x的过程，但修改和写回操作不是原子性，还是会有数据不一致性的问题，CAS就可以解决这个问题，那使用CAS操作来修改共享变量x，流程又会是如何呢？

步骤：

1.初始化：x=1，存储在主内存

2.线程A读取：A从主内存读取，复制x=1到A的工作内存

3.线程B读取：B从主内存读取x，复制x=1到B的工作内存

4.线程A修改：A在工作内存中修改x=2

5.线程A尝试CAS写回：A将工作内存中的x=2与主内存中的x=1进行比较

 - 如果主内存中仍然是x=1(预期值)，则CAS操作成功，x=1更新至x=2
 - 如果主内存中x≠1（被其他线程修改），则CAS操作失败，线程A需要重新读取更新的值并再次尝试重新读取最新的值

6.线程B修改：B在工作内存中修改x=3 7.线程B尝试CAS写回

如果主内存中x=1（这是B读取时的值，但此时可能已经被A修改x=2），也就是线程B以为主内存中是x=1（预期值），但实际上主内存是x=2（实际值），预期值与实际值不符，则 CAS操作失败
 B需要重新读取最新的值x=2,并尝试CAS操作

8.线程B重新读取：x=2

9.线程B再次尝试CAS写回：B再次尝试将x=2更新至x=3，如果此时没有其他线程修改x，则CAS操作成功

由上述流程可以看出当使用CAS操作来修改共享变量x时，与volatile修改共享变量x流程会有所不同

CAS的应用场景

并发容器：在Java中，并发容器如ConcurrentHashMap、ConcurrentLinkedQueue等，利用CAS操作来实现高效的并发访问。例如，ConcurrentHashMap在更新内部数据结构时，会使用CAS操作来尝试更新某个桶（bucket）中的链表或红黑树，只有当更新成功时，操作才算完成。这种方式避免了全局锁的使用，提高了容器的并发性能。
原子类： Java中的原子类（如AtomicInteger、AtomicLong、AtomicReference等）提供了一系列基于CAS操作的方法，如compareAndSet、getAndIncrement、getAndSet等。这些方法可以确保对基本类型或对象引用的操作是原子的，即在多线程环境中，这些操作不会被其他线程中断。原子类广泛应用于计数器、标志位、序列号生成等场景，它们可以有效地减少锁的使用，提高程序的并发性能。
数据库事务：在数据库事务中，CAS操作可以用来实现乐观锁。乐观锁是一种假设在大多数情况下不会有冲突的锁策略，它允许事务在没有显式锁的情况下读取和修改数据，但在提交时检查是否有冲突发生。如果检测到冲突（即其他事务已经修改了数据），则当前事务可以回滚并重试。这种机制通常通过在数据记录中添加一个版本号或时间戳字段来实现，当事务尝试更新记录时，它会使用CAS操作来比较版本号或时间戳，只有当它们与事务开始时读取的值相同时，更新才会成功。乐观锁适用于读多写少的场景，它可以减少锁竞争，提高并发性能。
无锁数据结构： CAS操作是实现无锁数据结构的基础，如无锁栈、无锁队列、无锁链表等。这些数据结构通过CAS操作来确保在多线程环境中的操作是线程安全的，同时避免了锁带来的性能开销和复杂性。无锁数据结构在需要高并发和高吞吐量的系统中非常有用。
并发算法：在并发编程中，CAS操作可以用来实现各种并发算法，如无锁的内存分配器、并发计数器、并发标志位等。这些算法利用CAS操作来确保操作的原子性，从而避免了锁的使用，提高了算法的并发性能。

CAS操作的优点在于它提供了一种无阻塞的同步机制，可以减少线程等待和上下文切换的开销，从而提高程序的响应性和吞吐量。然而，CAS操作也有其局限性，如ABA问题和自旋开销，因此在设计并发算法时需要仔细考虑这些因素。

CAS的应用场景主要包括：

实现无锁数据结构：无锁数据结构通过CAS操作来确保数据的一致性和线程安全，避免了使用锁可能带来的性能开销和死锁问题。例如，Java并发包中的ConcurrentHashMap就使用了CAS操作来实现无锁化。
实现自旋锁：自旋锁是一种非阻塞锁，当一个线程尝试获取锁失败时，它会进入忙等待状态（自旋），不断重试获取锁，直到成功为止。在这个过程中，CAS操作可以用于检查锁的状态并尝试获取锁。
实现计数器：在需要频繁更新计数的场景下，可以使用CAS操作来实现无锁计数计数器。多个线程可以并发地更新计数器的值，而无需担心数据不一致的问题。

虽然CAS操作在很多场景下都非常有用，但它也存在一些缺点和限制：

ABA问题：如果一个变量初次读取的值是A，并且在准备写入的时候检查到它仍然是A，那么我们就可以认为它没有被其他线程修改过，因此可以放心地写入新值B。但是，在这段时间内，这个变量的值可能被其他线程修改成了B，然后又改回A，此时CAS操作仍然会成功，但实际上这个变量已经被其他线程修改过了，这就是所谓的ABA问题。解决这个问题的一个常见方法是引入版本号，每次变量更新时版本号都加一。
只能保证单个共享变量的原子操作：当涉及多个共享变量时，CAS操作可能无法正确工作。例如，你可能需要同时更新两个值，但CAS只能保证单个值的原子性。当涉及多个共享变量时，CAS操作可能无法正确工作。
可能导致忙等待：在高并发场景下，如果CAS操作操作一直失败，那么线程可能会一直自旋，造成CPU资源的浪费。