CAS与FAA：原子操作在多线程应用程序中的重要性 -- 知识铺

 介绍

1. CAS 和 FAA 的定义 CAS（比较和交换）和 FAA（获取和添加）是原子操作，旨在确保多线程应用程序中的线程安全和同步。

   CAS 允许将变量的值与预期值进行比较，并在比较成功时对其进行原子更新。FAA 提供变量的原子增量或递减，使其成为计数器和聚合器的理想选择。

2. 原子操作重要性的证明 原子操作在多线程编程中起着重要作用，因为它们可以在不使用锁的情况下确保线程安全和同步。

   锁通常会导致性能问题，例如吞吐量和可伸缩性问题，以及调试和分析代码的困难。

   原子操作提供了高效、无阻塞的替代方案，可以显著提高多线程应用程序的性能和稳定性。

3. CAS和FAA在多线程应用中的应用概述 CAS和FAA被广泛用于实现各种多线程数据结构和算法。例如，在 Java 中，CAS 用于 AtomicInteger、AtomicLong 和 AtomicReference 等类，以提供对基本数据类型的线程安全原子操作。

   FAA 用于 LongAdder 和 DoubleAdder 等类，以实现高效的变量增量，同时考虑可扩展性。

在本文中，我们将详细研究 CAS 和 FAA 的机制，它们在 Java 中的应用，并比较它们在不同使用场景下的性能、优缺点。

 CAS（比较和交换）

1. CAS机制说明 CAS（Compare-and-Swap）是一种原子操作，它将变量的值与期望值进行比较，如果它们匹配，则使用新值更新变量。

执行 CAS 的整个过程是原子的，这意味着它不能被其他线程或操作中断。

CAS 操作包括三个操作数：存储单元地址 （V）、预期的旧值 （A） 和新值 （B）。

如果存储单元中的值与预期的旧值 （A） 匹配，则处理器会以原子方式更新存储单元地址 （V）;否则，不会记录修改。无论哪种情况，都将返回请求之前存在的值。

CAS 方法的某些变体返回有关操作成功的信息，而不是当前值。从本质上讲，CAS 说：

地址 V 处的值可能等于 A;如果是这样，请将其替换为 B，否则不要更改它，但请务必告诉我当前值。

在 Java 中使用 CAS 的示例

AtomicInteger、AtomicLong 和其他原子类 Java 提供了诸如 AtomicInteger、AtomicLong 等类，这些类实现了用于处理基元数据类型的 CAS 机制。下面是使用 AtomicInteger 类实现线程安全计数器的示例。

1

import java.util.concurrent.atomic.AtomicInteger; public class Counter { private final AtomicInteger counter = new AtomicInteger(0); public void increment() { counter.incrementAndGet(); } public int getCounter() { return counter.get(); } }

使用 CAS 进行变量操作的流程图：

使用 AtomicReferenceFieldUpdater 类对对象字段进行原子操作。

AtomicReferenceFieldUpdater 类允许使用 CAS 机制对对象字段执行原子操作。下面是使用 AtomicReferenceFieldUpdater 实现对象状态的线程安全修改的示例。

1

import java.util.concurrent.atomic.AtomicReferenceFieldUpdater; public class BankAccount { private static final AtomicReferenceFieldUpdater<BankAccount, Double> balanceUpdater = AtomicReferenceFieldUpdater.newUpdater(BankAccount.class, Double.TYPE, "balance"); private volatile double balance; public BankAccount(double initialBalance) { this.balance = initialBalance; } public boolean withdraw(double amount) { double currentBalance; double newBalance; do { currentBalance = balance; newBalance = currentBalance - amount; if (newBalance < 0) { return false; } } while (!balanceUpdater.compareAndSet(this, currentBalance, newBalance)); return true; } }

CAS 在硬件级别的操作

CAS 使用特殊的处理器指令在硬件中实现，这些指令保证了比较和更新操作的原子性。因此，CAS 在更新共享数据时提供高性能和低延迟。

在硬件层面使用 CAS 的过程中，有几个关键点：

1. 原子性：CAS指令必须是原子的，也就是说，它必须完全执行或根本不执行。这可确保其他线程不能同时更改变量的值。
2. 寻址：CAS 指令必须是可寻址的，即必须指定变量在内存中的位置。
3. 比较：CAS 指令必须将变量的值与预期值进行比较。如果值匹配，则指令将新值写入内存。
4. 原子写入：CAS 指令必须以原子方式将变量的新值写入内存。

每个处理器可以以不同的方式实现 CAS 机制。例如，某些处理器可能使用特殊的寄存器来存储变量的当前值和预期值。

在这种情况下，在寄存器中比较这些值，如果它们匹配，则将新值写入内存。

其他处理器可能使用更复杂的机制，即使用缓存内存和多线程。在这种情况下，将在缓存中比较这些值，如果值匹配，则将新值写入内存。

因此，CAS在硬件级别的操作取决于处理器微架构中的具体实现。

但是，无论具体实现如何，CAS 指令都确保了读取、检查和更改变量值的操作的原子性。

CAS 机制在硬件级别的具体实现取决于处理器的制造商和型号。以下是一些示例：

1. 英特尔 x86：英特尔 x86 处理器支持 CAS 指令，该指令将变量的值与预期值进行比较，如果匹配，则写入新值。此指令在实际模式和受保护模式下可用。
2. ARM：ARM 处理器支持读取变量值的 LDREX（负载独占）指令，以及 STREX（存储独占）指令，如果变量自读取以来未更改，则将新值写入变量。两条指令必须在单个事务中执行。
3. PowerPC：PowerPC 处理器支持 LWARX（加载字和保留）指令来读取变量的值并保留相应的内存，以及 STWCX（存储字条件）指令，如果变量没有被其他处理器修改，则将新值写入变量。
4. SPARC：SPARC 处理器支持 CASA（比较和交换原子）指令，将变量的值与预期值进行比较，如果匹配，则写入新值。此指令可用于对 32 位和 64 位值进行原子操作。
5. IBM z/Architecture：IBM z/Architecture 处理器支持 CS（比较和交换）指令，用于将变量的值与预期值进行比较，如果匹配，则写入新值。此指令可用于对 32 位和 64 位值进行原子操作。

从这些示例中可以看出，每个处理器架构都以不同的方式实现 CAS 机制，但总的来说，它们的工作原理相同——将变量的值与预期值进行比较，如果它们匹配，则写入一个新值。

CAS的优缺点

 CAS的优点：

• 与传统锁定机构相比，操作速度快，成本低。
• 一种非阻塞方法，可降低死锁的可能性并提高应用程序性能。
• 启用乐观的同步策略，这些策略可以在低争用（线程之间的竞争）下有效工作。

 CAS的缺点：

• CAS 可能会导致“饥饿”问题，即一个线程不断尝试执行 CAS 操作，但由于与其他线程竞争而无法执行。
• CAS 操作可能导致“ABA 问题”，即变量的值从 A 变为 B，然后再变回 A，这可能会导致某些算法出现错误。
• 需要知识和经验才能实现正确的算法，尤其是在解决 ABA 问题时。

CAS 的进展保证

CAS 提供了称为“无障碍”的进度保证，这意味着如果线程在没有与其他线程竞争的情况下执行 CAS 操作（即其他线程不干扰），它将始终能够成功完成该操作。

但是，在线程之间主动竞争的情况下，无法保证进度，这可能会导致饥饿问题和 ABA 问题等问题。

为了提供严格的进度保证（例如“无锁”或“无等待”），可能需要其他机制和算法，例如使用双字 CAS、版本控制或其他数据结构（如描述符）。

 FAA（获取和添加）

FAA机制说明

Fetch-and-Add （FAA） 是一种原子操作，它读取变量的当前值，向其添加指定的数字，然后返回变量的旧值。FAA 是在多线程应用程序中实现原子操作的关键原语之一。

FAA 涉及两个操作数：内存位置的地址 （V） 和要添加到存储在内存位置 （V） 的旧值的值 （S）。因此，FAA可以表示如下：提取指定地址（V）处的值并临时存储。

然后，将先前存储的值（按第二个操作数 （S） 的值递增）写入指定的地址 （V）。需要注意的是，上述所有操作都是以原子方式执行的，并在硬件级别实现。

在 Java 中使用类似 FAA 功能的示例

AtomicInteger 和 AtomicLong

在 Java 中，AtomicInteger 和 AtomicLong 类提供了 getAndAdd（） 和 addAndGet（） 方法，它们实现了类似的 FAA 功能。下面是使用 AtomicInteger 实现线程安全计数器的示例：

1

import java.util.concurrent.atomic.AtomicInteger; public class Counter { private final AtomicInteger counter = new AtomicInteger(0); public void increment() { counter.getAndAdd(1); } public int getCounter() { return counter.get(); } }

LongAdder 和 DoubleAdder

Java 还提供了 LongAdder 和 DoubleAdder 类，这些类专为高性能和可伸缩的计数器实现而设计。下面是使用 LongAdder 实现线程安全计数器的示例。

FAA在硬件上的操作

级别 与 CAS 一样，FAA 使用特殊的处理器指令在硬件级别实现，这些指令保证了读取、添加和更新操作的原子性。这在更新共享数据时提供高性能和低延迟。

当线程想要执行 FAA 操作时，处理器首先将变量的值加载到寄存器中并返回它。

然后，处理器在此值和传递的操作数之间执行加法操作，将结果存储在寄存器中，并将新值写回内存。

因此，FAA 操作包括三个步骤：读取变量的值、执行加法操作和写入新值。

例如，如果我们想在包含值 10 的变量计数器上执行 FAA 操作并传递操作数 2，处理器将执行以下步骤：

1. 将计数器变量 （10） 的值加载到寄存器中。
2. 在此值 （10） 和传递的操作数 （2） 之间执行加法运算，得到 （12）。
3. 将结果 （12） 存储在寄存器中。
4. 将变量 （12） 的新值写回内存。

由于 FAA 操作，计数器变量的值将增加 2。

与 CAS 一样，处理器必须确保 FAA 操作的原子执行，以确保多线程应用程序的正确运行。

FAA 机制在硬件级别的确切实现取决于特定的处理器架构，但总的来说，它的工作原理是上述的。

FAA机制在硬件层面的实施取决于处理器的制造商和型号。一些现代处理器（如 Intel x86 和 ARM）在硬件级别支持原子 FAA 操作。

例如，从 1990 年代后期开始的 Intel Pentium 架构的 Intel 处理器支持“xadd”指令，该指令对 32 位和 64 位整数值执行 FAA 操作。

此指令从操作数中读取值，在操作数之间执行加法操作，将结果存储在寄存器中，并将新值写入内存。因此，可以使用此指令在硬件级别以原子方式执行 FAA 操作。

同样，从 ARMv6K 架构开始的 ARM 处理器也支持用于从内存中读取值的“LDREX”指令和用于将新值写回内存的“STREX”指令。

这些指令可用于在硬件级别执行原子 FAA 操作。

FAA机制在其他处理器架构上的实现可能有所不同，但总的来说，工作原理是相似的。

FAA的优缺点

 FAA的优势：

• 与传统锁定机构相比，操作速度快，成本低。
• 非阻塞方法可降低死锁的可能性，并提高应用程序性能。
• 简化原子计数器和聚合器（如 LongAdder 和 DoubleAdder）的实现。

 FAA的缺点：

• 可能并不适合所有用例，因为它假设原子增量为固定量，这可能不是所有任务的通用解决方案。
• 与 CAS 一样，FAA 需要一定程度的专业知识和知识才能正确实现算法，尤其是在高线程争用的情况下。

美国联邦航空局（FAA）的进展保证

FAA 还提供称为“无障碍”的进度保证，这意味着如果线程执行 FAA 操作而没有与其他线程争用（即无干扰），它将始终能够成功完成操作。

但是，在主动线程争用的情况下，无法保证进度，可能需要更复杂的算法和机制来确保严格的进度保证，例如“无锁”或“无等待”。

在某些情况下，可以使用组合方法来确保严格的进度保证，例如结合 CAS 和 FAA 机制或使用其他数据结构（如描述符）来减少线程之间的争用并提高性能。

CAS 和 FAA 的比较

CAS 和 FAA 的异同

CAS 和 FAA 之间的相似之处：

• 两者都是原子操作，可确保多线程应用程序中的线程安全。
• 这两种机制都是使用特殊的处理器指令在硬件级别实现的。
• 两者都提供“无障碍”进度保证。

CAS 和 FAA 之间的区别：

• CAS 将变量的当前值与预期值进行比较，仅当变量与预期值匹配时，才将其替换为新值。FAA 读取变量的当前值，将其增加一个指定的数字，然后返回变量的旧值。
• CAS 可用于实现更复杂的算法和数据结构，例如非阻塞堆栈和队列。FAA主要用于原子计数器和聚合器。
• CAS 可能会遇到 ABA 问题，而 FAA 通常不会遇到此类问题。

带宽和可扩展性

与传统的锁定机制相比，CAS 和 FAA 提供了高带宽和可扩展性。但是，由于使用场景和操作特性的差异，带宽和可扩展性可能会有所不同。

在 CAS 的情况下，由于频繁的更新尝试失败，线程之间的高度竞争可能会降低带宽。

FAA 通常具有更好的带宽和可伸缩性，尤其是在使用 LongAdder 和 DoubleAdder 等类时，这些类是为了减少线程之间的争用而开发的。

CAS 和 FAA 的用例

 中国科学院：

• 实现非阻塞数据结构，例如堆栈、队列和列表。
• 在线程之间的争用为低或中等的情况下实现乐观的同步策略。
• 解决多线程应用程序中与锁和死锁相关的问题。

 联邦 航空 局：

• 实现线程安全计数器和聚合器，其中高性能和可伸缩性至关重要。
• 解决需要变量的原子递增或递减的问题。
• 在监测和统计系统中实施累积计数器。

 代码示例：

 AtomicInteger 中的 CAS：

1

AtomicInteger atomicInt = new AtomicInteger(0); boolean success = atomicInt.compareAndSet(0, 1); System.out.println("CAS success: " + success + ", new value: " + atomicInt.get());

 AtomicInteger 中的 FAA：

1

AtomicInteger atomicInt = new AtomicInteger(0); int oldValue = atomicInt.getAndAdd(1); System.out.println("Old value: " + oldValue + ", new value: " + atomicInt.get());

总之，CAS 和 FAA 为在多线程应用程序中实现线程安全操作提供了强大而灵活的机制。

与传统的锁定机制相比，它们具有高性能和可扩展性，但需要仔细理解和分析才能在不同的场景和任务中正确使用。

 结论

文章主要思想摘要

在本文中，我们研究了确保多线程应用程序中线程安全的两种重要机制 — CAS（比较和交换）和 FAA（获取和添加）。

我们讨论了这些机制如何工作的基本原理，它们在 Java 中的使用示例，并比较了它们的特点、优点和缺点。

CAS 允许将变量的值与预期值进行原子比较，并在比较成功时对其进行更新。这对于实现非阻塞数据结构和乐观同步策略特别有用。

FAA 提供变量的原子增量或递减，使其成为计数器和聚合器的理想选择。在 Java 中，LongAdder 和 DoubleAdder 类是专门为在递增变量时提供高性能和可伸缩性而开发的。

为多线程应用程序选择正确机制的重要性。

选择适当的同步机制对于确保多线程应用程序的性能和可靠性至关重要。不正确的选择可能会导致性能问题、阻塞，甚至竞争条件。

因此，开发人员需要仔细研究可用的机制，并根据具体任务和使用场景选择最合适的机制。

进一步研究和发展该主题的方向

多线程编程是一个复杂且不断发展的领域，有许多方向需要进一步研究和发展。其中一些包括：

• 研究更高级的同步机制，如无锁和无等待算法，提供严格的进度保证，可以确保更高的性能和可扩展性。
• 开发和分析新的数据结构和算法，为多线程应用程序提供更高的线程安全性和性能。
• 研究不同的内存模型及其对多线程应用程序的行为和性能的影响。
• 考虑其他同步方法，例如参与者模型和基于消息的并行编程，可以为开发多线程系统提供其他原则和策略。
• 在开发过程中应用形式化方法和静态分析来检测和防止同步问题和竞争条件。

总之，CAS 和 FAA 为在多线程应用程序中实现线程安全操作提供了强大的工具，开发人员需要仔细研究和应用它们，以在系统的性能、可靠性和可扩展性方面取得最佳结果。

 书目

文章中使用的信息来源：

1. Herlihy，M.和Shavit，N.（2008）。多处理器编程的艺术。爱思唯尔。
2. Goetz，B.，Peierls，T.，Bloch，J.，Bowbeer，J.，Lea，D.和Holmes，D.（2006）。Java 并发在实践中。艾迪生-卫斯理。
3. 兰波特，L.（1984 年）。Dijkstra 并发编程问题的新解决方案。ACM通讯，27（8），770-781。
4. 甲骨文公司。（2021）. Java® 语言规范，Java SE 17 版。取自 https://docs.oracle.com/javase/specs/jls/se17/html/index.html
5. 麦肯尼，PE（2013 年）。并行编程难吗，如果是这样，你能做些什么？取自 https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook-1c.2013.12.22a.pdf

以下是一些推荐的读物，以供进一步探索：

1. Sutter，H.和Alexandrescu，A.（2004）。C++ 并发在行动：实用的多线程。曼宁出版社。
2. Lea，D.（2000 年）。Java 中的并发编程：设计原则和模式。艾迪生-卫斯理。
3. 雷纳尔，M.（2012 年）。并发编程：算法、原理和基础。斯普林格。
4. Shun，J.和Blelloch，GE（2013）。Ligra：用于共享内存的轻量级图形处理框架。ACM SIGPLAN 通知，48（8），135–146。

本参考书目代表了撰写本文时使用的来源，以及为那些想要深入研究 CAS、FAA 和多线程编程其他方面的人提供进一步阅读的建议。