cas是一种无锁算法



在多线程编程中，保证数据的安全性和一致性是至关重要的。CAS（Compare and Swap）作为一种无锁并发技术，为我们提供了一个高效的解决方案。本文将深入探讨CAS的实现原理及其在并发编程中的应用。

synchronized 时代：在多线程中为了保持数据的准确性，避免多个线程同时操作某个变量，很多情况下利用关键字 synchronized 实现同步锁。

使用 synchronized 关键字可以使操作的线程排队等待运行，可以说是一种悲观策略，认为线程会修改数据，所以开始就把持有锁的线程锁住，其他线程只能是挂起状态，等待锁的释放，所以同步锁带来了效率问题。

synchronized 时代效率问题：在线程执行的时候，获得锁的线程在运行，其他被挂起的线程只能等待着持有锁的线程释放锁才有机会运行，在效率上都浪费在等待上。
更多请移步深入解析 Java 中的 Synchronized

在很多的线程切换的时候，由于有同步锁，就要涉及到锁的释放，加锁，这又是一个很大的时间开销。

volatile 时代：与锁（阻塞机制）的方式相比有一种更有效地方法，非阻塞机制，同步锁带来了线程执行时候之间的阻塞，而这种非阻塞机制在多个线程竞争同一个数据的时候不会发生阻塞的情况，这样在时间上就可以节省出很多的时间。

我们会想到用 volatile，使用 volatile 不会造成阻塞，volatile 保证了线程之间的内存可见性和程序执行的有序性可以说已经很好的解决了上面的问题。

volatile 时代原子操作问题：一个很重要的问题就是，volatile 不能保证原子性，对于复合操作，例如 i++ 这样的程序包含三个原子操作：取值，增加，赋值。更多请移步深入理解java中的volatile关键字

CAS 操作依赖于底层硬件指令和系统内核的支持。以下是一些关键点：

• 硬件支持：
  • 现代 CPU 提供了专门的指令（如 CMPXCHG、LL/SC）来支持 CAS 操作。
  • 这些指令在硬件层面上保证了操作的原子性。
• 内核原子操作：
  • 操作系统内核提供了对这些硬件指令的封装，以便应用程序能够方便地使用。
  • 在 Linux 内核中，CAS 操作通过 atomic_compare_and_exchange 等内核函数实现。
• 内存模型：
  • CAS 操作需要与内存模型相结合，以确保操作的可见性和有序性。
  • Java 内存模型（JMM）确保了使用 CAS 操作的变量在多线程环境下的正确性。

CAS 操作包含三个操作数：

• V：需要读写的内存位置。
• E：预期值（Expected value）。
• N：新值（New value）。

CAS 操作的步骤如下：

• 比较：将内存位置 V 当前的值与预期值 E 进行比较。
• 交换：如果 V 的当前值等于 E，则将新值 N 写入 V 中。
• 返回结果：返回 V 的旧值，如果 V 的旧值等于 E，则说明交换成功。

这种操作通过硬件指令（如 x86 架构的 CMPXCHG 指令）实现，保证了比较和交换操作的原子性。

在 Java 中，CAS 操作主要通过 sun.misc.Unsafe 类提供的方法来实现，如 compareAndSwapInt、compareAndSwapLong 和 compareAndSwapObject。这些方法直接调用底层硬件的 CAS 指令。

Unsafe类详细使用，请参考：深入理解 Unsafe 类及其实现原理

优点：

• 无锁并发：避免了传统锁带来的开销和线程上下文切换问题，提高了并发性能。
• 高效：在低竞争情况下，CAS操作比锁机制更高效。

缺点：

• ABA问题：如果变量在检查和更新之间发生了变化，且最终值和初始值相同，则CAS无法检测到。可以通过增加版本号解决。
• 自旋等待：在高竞争情况下，CAS操作可能会导致自旋等待（不断重试），造成CPU资源浪费。

版本号机制：一般是在数据中加上一个数据版本号 version 字段，表示数据被修改的次数，当数据被修改时，version 值会加 1。当线程 A 要更新数据值时，在读取数据的同时也会读取 version 值，在提交更新时，若刚才读取到的 version 值为当前数据中的 version 值相等时才更新，否则重试更新操作，直到更新成功。

场景示例：假设商店类 Shop 中有一个 version 字段，当前值为 1 ；而当前商品数量为 50。

• 店员 A 此时将其读出（ version=1 ），并将商品数量扣除 10，更新为 50 - 10 = 40；
• 在店员 A 操作的过程中，店员 B 也读入此信息（ version=1 ），并将商品数量扣除 20，更新为 50 - 20 = 30；
• 店员 A 完成了修改工作，将数据版本号加 1（ version=2 ），商品数量为 40，提交更新，此时由于提交数据版本大于记录当前版本，数据被更新，数据记录 version 更新为 2 ；
• 店员 B 完成了操作，也将版本号加 1（ version=2 ），试图更新商品数量为 30。但此时比对数据记录版本时发现，店员 B 提交的数据版本号为 2 ，数据记录当前版本也为 2 ，不满足 “ 提交版本必须大于记录当前版本才能执行更新 “ 的乐观锁策略，因此，店员 B 的提交被驳回；
• 店员 B 再次重新获取数据，version = 2，商品数量 40。在这个基础上继续执行自己扣除 20 的操作，商品数量更新为 40 - 20 = 20；
• 店员 B 将版本号加 1 ，version = 3，将之前的记录 version 2 更新为 3 ，将之前的数量 40 更新 为 20。

从如上描述来看，所有的操作都不会出现脏数据，关键在于版本号的控制。

CAS 是一种高效的原子操作，通过比较和交换来实现无锁并发。它利用底层硬件指令实现了高性能的同步机制，广泛应用于 Java 并发包中。尽管 CAS 操作存在一些问题，如 ABA 问题和自旋等待，但通过版本号机制等方法，可以有效地解决这些问题。CAS 的应用极大地提高了多线程编程的性能，是实现高效并发的关键技术之一。

版权声明：

本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。

本文网址：https://www.mushiming.com/mjsbk/8003.html