比较并交换

在计算机科学中，比较和交换 (CAS) 是多线程中用于实现同步的原子指令。 它将内存位置的内容与给定值进行比较，只有当它们相同时，才将该内存位置的内容修改为新的给定值。 这是作为单个原子操作完成的。 原子性保证新值是根据最新信息计算的； 如果该值同时被另一个线程更新，则写入将失败。 操作的结果必须表明它是否执行了替换； 这可以通过简单的布尔响应（这种变体通常称为比较和设置）或通过返回从内存位置读取的值（而不是写入它的值）来完成。

此操作用于实现信号量和互斥量等同步原语，以及更复杂的无锁和无等待算法。 Maurice Herlihy (1991) 证明了 CAS 可以实现比原子读、写或获取和添加更多的算法，并且假设有相当大的内存，它可以实现所有这些算法。 CAS 等同于加载链接/条件存储，在某种意义上，任一原语的恒定调用次数可用于以无等待方式实现另一个原语。

围绕 CAS 构建的算法通常会读取一些关键内存位置并记住旧值。 基于旧值，他们计算出一些新值。 然后他们尝试使用 CAS 交换新值，其中比较检查位置是否仍然等于旧值。 如果 CAS 指示尝试失败，则必须从头开始重复：重新读取位置，重新计算新值并再次尝试 CAS。 研究人员发现，在 CAS 操作失败后不是立即重试，而是可以在多处理器系统中提高总体系统性能——在多处理器系统中，许多线程不断更新一些特定的共享变量——如果发现 CAS 失败的线程使用指数退避——换句话说，等待 在重试 CAS 之前。

作为比较和交换的示例用例，这里是一个用于原子递增或递减整数的算法。 这在使用计数器的各种应用程序中很有用。 函数 add 以原子方式执行操作 *p ← *p + a（再次用 * 表示指针间接，如在 C 中）并返回存储在计数器中的最终值。 与上面的 cas 伪代码不同，除了 cas 之外，不要求任何操作序列都是原子的。

在此算法中，如果 *p 的值在获取之后（或同时！）在 CAS 执行存储之前发生变化，CAS 将注意到并报告这一事实，从而导致算法重试。

一些基于 CAS 的算法受到误报匹配问题或 ABA 问题的影响并且必须处理这些问题。 有可能在读取旧值和尝试 CAS 之间，某些其他处理器或线程两次或多次更改内存位置，以便它获取与旧值匹配的位模式。 如果这个看起来与旧值一模一样的新位模式具有不同的含义，就会出现问题：例如，它可能是回收地址或包装版本计数器。

对此的一般解决方案是使用双倍长度的 CAS (DCAS)。 例如，在 32 位系统上，可以使用 64 位 CAS。 下半场用于举行柜台。 操作的比较部分将指针和计数器的先前读取值与当前指针和计数器进行比较。 如果它们匹配，则交换发生——新值被写入——但新值有一个递增的计数器。

这意味着如果发生 ABA，虽然指针值相同，但计数器极不可能相同（对于 32 位值，必须发生 232 次操作的倍数，导致计数器回绕 在那一刻，指针值也必须偶然相同）。

另一种形式（在缺少 DCAS 的 CPU 上有用）是使用空闲列表的索引，而不是完整的指针，例如 对于 32 位 CAS，使用 16 位索引和 16 位计数器。 然而，减少的计数器长度开始使 ABA 在现代 CPU 速度下成为可能。

一种有助于缓解此问题的简单技术是在每个数据结构元素中存储一个 ABA 计数器，而不是对整个数据结构使用单个 ABA 计数器。