C++ 中的比较和交换 (CAS)

在当前的并发编程研究中，同步共享数据以便由多个线程读取和修改至关重要。这可以通过传统的锁定技术（如互斥锁）来实现，在执行特定操作时暂时阻止其他线程。然而，锁存在不利之处，因为它们的使用会在存在争用时导致性能下降。因此，大多数开发人员都希望实现“无锁”解决方案，以使多个线程能够并行运行，而不会受到太多结构性的影响。然而，普通计算机用户仍在等待这一天的到来，这要归功于一种相对而言基于指令的操作，称为比较和交换 (CAS)。

• 像大多数无锁算法一样，比较和交换 (CAS) 是一种用于同步的原子操作。CAS 意味着在 CAS 中，数据可以被多个线程访问和操作，而无需使用锁，但需要原子性——这一特性确保特定操作在开始之前已经完成或将要完成。简单来说，CAS 的实际执行方式是：首先将内存位置中的当前值与期望值进行比较。如果两者相等，则表示没有其他线程会更改该值，然后将此值更新为最新的值。如果不相等，则表示另一个线程已经修改了数据，并且我们的操作不成功，没有任何更改。
• CAS 的一个诗意之处在于，当它停止工作时，它会一直重试，直到数据稳定到 NC 关键，同时获得所需结果。好消息是 CAS 不包含阻塞或等待，因此它比锁定性能要好得多，尤其适用于高性能应用程序。
• 假设在多线程程序中使用一个通用的计数器变量，并且有两个或多个线程试图同时递增计数器。使用 CAS，每个线程都可以尝试递增计数器，而无需担心其他线程。这一点很重要，因为如果一个线程发现另一个线程改变了计数器的值，它会等待计数器被递增。这使得线程能够“竞争”特定的工具和进程，而不会相互抢占，因此，处理此类共享资源要快得多，效率也更高。

CAS 经常用于系统编程，在设计高级咨询时较少使用。它对于大多数无锁数据类型实现（如堆栈和队列）以及垃圾收集器算法至关重要。虽然 C++ 等语言对嵌入式系统中的原子性有原生支持，但 CAS 成为变量和有效并发的关键。

CAS 如何工作？

CAS 操作涉及三个主要元素：要执行操作的内存、期望值以及要存储在内存位置的新值。让我们逐步分解这个过程：

• 识别内存位置： CAS 操作的目标是用于存储共享数据的特定内存位置。例如，它可以是一个计数器、一个指针或另一个在线程之间共享的变量。在 C++ 中，通常使用 < < a href="http://www.cplusplus.com/reference/atomic/">atomic > 库中的原子变量进行 CAS 操作。例如，std::atomic<int> 变量可以存储一个多个线程同时更新的计数。
• 比较当前值和期望值： CAS 读取内存位置的值，并将其与用户要输入的值进行比较。这个期望值将是程序员在采样时期望数据处于的状态。在当前传统的或主内存模型中，如果此内存位置当前存储的值等于期望的值，则操作继续；否则，它被取消，内存位置没有更改。
• 如果比较成功，则更新内存位置： 如果 CAS 等于 SE，CAS 则将新值写入 SR 位置，替换当前提供的值。此交换操作以原子方式发生，这使得在比较和更新之间没有其他线程可以更改内存地址中的值。如果比较测试结果为否（当前值等于期望值），则退出循环，内存位置不会有任何更改。

CAS 的好处

让我们讨论一下 CAS 相对于经典锁同步的一些好处。这些优点在应用于 FHP 应用程序或在处理与并发数据访问相关的高精度设置时尤其有用。以下是使用 CAS 的一些主要优点：

• 非阻塞同步： CAS 实际上是一种无锁结构，因此，即使存在争用，它也不会阻止其他线程处于活动状态。这在多个线程并发访问任何共享对象的情况下特别有用。原始锁会使当前线程在队列中等待，这在时间复杂度方面是有害的。另一方面，CAS 使任何特定线程能够以不间断的方式进行尝试，因为它不需要等待。当 CAS 操作（交换原子片段）因竞争条件而失败时，线程可以重试而不会影响其他线程。
• 高性能和可扩展性： CAS 操作不涉及锁定，因此在多核系统中具有高度可扩展性，如下面的优点所述。在许多线程读取或写入共享数据的系统中，锁会通过串行化访问来产生负面影响。然而，CAS 允许更多线程并行运行，从而提高整体操作吞吐量，尤其对于短操作。大多数具有高并发要求的新一代应用程序，包括 Web 服务器和实时应用程序，都因其效率和低延迟而使用 CAS。
• 提高实时系统的响应能力： 正如我们将看到的，在实时应用程序中，必须采取一切措施来减少延迟，因为线程是在时间约束下使用的。CAS 方法最大限度地减少了被锁定的机会，从而避免了可能扭曲实际时间调度的干扰。通过这种方式，CAS 提高了效率以及被挂起或失败的 CAS 操作的线程继续或立即重试的能力，而不是因优先级反转而受到处罚，优先级反转是低优先级线程阻止高优先级线程在系统中运行的状态。
• 降低死锁和活锁的风险： 死锁发生在所有线程都处于等待状态，互相持有对方的资源，导致无法继续执行。而活锁是指进程不断地改变其状态，但无法取得任何进展。由于 CAS 是无锁的，它根本不会导致死锁，并且活锁的发生也大大减少。在基于 CAS 的算法中，线程根据条件继续执行，而不是等待锁；它们可以快速失败并重新开始，而不会拖慢系统。
• 无锁数据结构的基础： CAS 允许开发高性能的线程安全对象，如堆栈、队列和链表，而无需使用锁。在无锁数据结构中，CAS 操作用于以更安全的方式处理多个并发访问和修改。例如，CAS 可以用于无锁堆栈，其中对每个推送或弹出操作不应用锁定机制，因此，两个或多个线程可以推送或弹出堆栈中的元素，它们不会相互阻塞。
• 与硬件原子操作兼容： CAS 机制由许多现代处理器在硬件级别实现，这就是为什么它成为并发编程中独立线程的自然形式。硬件级别的 CAS 操作在大多数情况下都很快，因为它们依赖于 CPU 的原子函数。这种兼容性确保了基于 CAS 的程序在具有这些原子指令的任何系统上都可以非常高效且可移植。

C++ 中的用例

在实践中，它在 C++ 中的应用领域多种多样，但 CAS 最适合需要高并发和低延迟，并且无法使用标准锁的场景。以下是一些 CAS 发挥宝贵作用的最常见用例的概述：

• 原子变量： CAS 是建立原子变量结构的基础。C++ 通过 std::atomic 库提供原子类型，如整数和指针。CAS 操作确保了对这些原子变量的修改在多个线程上是安全的，而无需锁定。它还意味着这些值内的更改可以在不同线程之间安全地同时执行，这在具有许多小型更新的现代应用程序中很常见，例如多线程系统中的计数器、标志和共享计数器。
• 无锁数据结构： CAS 的一个典型用途是生成无锁数据结构。所有传统的数据结构，包括堆栈、队列和链表，都使用锁来控制并发访问。然而，使用 CAS 可以实现这些结构的无锁变体，其中线程可以插入或删除元素并访问它们，而不会被另一个线程阻塞。例如，在无锁堆栈的应用中，CAS 用于修改顶部指针，因为即使许多线程尝试将值推入堆栈或尝试弹出值，也只有一个线程可以更改其值。无锁数据结构应用于许多高性能的实时系统，在这些系统中，低延迟是以牺牲锁为代价实现的，例如操作系统。
• 引用计数和垃圾回收： CAS 在内存管理中至关重要，可以通过引用计数等技术来实现。在并发系统中，对象通常被引用计数，以了解当前有多少线程正在使用某个资源。当此计数返回到零时，即表明该资源可以被删除。CAS 可以在跨线程的这些增量和减量操作中实现，而无需使用锁，从而减少争用并改善内存管理。垃圾回收机制也由 CAS 管理，为具有极低开销的系统提供安全高效的内存管理。
• 乐观并发控制： 线程在乐观并发的假设下进行操作，即冲突是罕见的，在没有锁的情况下执行操作，并在完成后检查冲突。CAS 非常适合这种方法，因为它允许线程在没有其他更新同时发生时继续进行更新。当 CAS 操作启动后数据已被修改时，CAS 操作将被中止，并且该线程将尝试重试或处理失败。这种方法通常用于数据库和高吞吐量系统，在这些系统中，锁定成本太高且涉及低级别的争用。此技术主要用于数据库系统和高吞吐量计算中的并发控制。
• 危险指针和内存管理： CAS 的持续工作对于内存保护技术至关重要，这些技术包括诸如危险指针之类的回收辅助策略。为了提高多线程程序中内存回收的效率，危险指针会在收集迭代序列的过程中隔离数据元素，以防止它们在其他元素被其他线程使用时被回收。CAS 有用，因为如果一个元素被标记为危险并由危险指针指向，其他线程就无法过早删除它。这种机制尤其用于使用并发垃圾回收的实时系统中，因为必须在不中断整个系统的情况下保证安全的内存访问。
• 算法中的重试循环： 许多基于 CAS 的算法中常见的是使用重试循环，它允许线程在与其他线程发生冲突时反复操作。在给定的重试循环中，每个线程都在进行更新，如果 CAS 操作不成功，它会重新开始，直到操作完成。这种模式通常应用于对共享值（例如计数器或累加器）进行大量多线程计算的场景。CAS 配合重试循环可以无锁地工作，但可以确保正确的更新；它适用于允许偶尔重试而不会影响性能的算法。
• 无锁算法和同步原语： 它还提高了更复杂算法的效率，包括实时应用程序、模拟引擎以及更复杂的并发数据结构，如哈希表和树。这些算法使用 CAS 来同步线程之间的访问，而无需实际阻塞，从而使其处理高度并行化。此外，在原子标志、信号量、倒计时锁存器和同步元素中，CAS 通常在管理基本操作的原子级别上起作用。这在应用程序的高吞吐量场景（如模拟引擎和大规模计算）中特别有用，以减少锁争用。

C++ 中比较和交换 (CAS) 的代码示例

1. 使用 CAS 和原子变量

输出

 
Final counter value: 4000   

2. 使用 CAS 实现无锁堆栈

输出

 
Stack elements: 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0   

3. 在重试循环中使用 CAS

输出

 
Final counter value: 4000   

4. 使用 CAS 进行引用计数

输出

 
Resource can be safely deallocated.
Final reference count: 0   

结论

总之，在 C++ 中，CAS 是一个强大的原子调用，非常适合用于创建并发程序。通过使用 CAS，开发人员能够协调对共享对象的访问，并避免使用早期语言所特有的锁。因此，CAS 可以提高并发处理的效率。可以利用 CAS 来设计复杂的线程安全数据结构，如无锁堆栈和计数器，从而提高应用程序的理想性能，尤其是在需要低延迟/高吞吐量的场景中。

CAS 的工作原理是访问一个包含要更改的值的内存位置，并将其与指定值进行比较，然后在一个操作中，将内存位置中存储的值更改为新值。

事实上，CAS 主要应用于低争用和快速响应时间至关重要的实时系统和多线程并发应用程序领域。CAS 及其在 C++ 中的应用，以及开发人员如何利用它来构建高度可扩展的并发系统，可以提高效率，实现出色的资源管理，并能够应对和解决现代工作负载中日益复杂的并发需求。