比较并交换

CAS 把乐观并发的哲学压缩进一条指令：线程不加锁地读取共享状态、在私有空间算出新状态，提交时声明"仅当世界仍是我看到的样子才生效"。若其他线程已抢先修改，提交失败，线程重读重算再试。与悲观的锁相比，它在提交时检查当前值是否仍与预期相等，而不是阻止其他人更新；没有冲突时一次尝试即可成功，遇到不匹配时算法可以重读再试。相等性检查并不检测全部修改历史，后面的 ABA 例子正说明这一边界。这个原语为非阻塞进展提供了工具，但进展性属于整个算法，而不属于 CAS 本身；在所有更新都经 CAS 提交的 lock-free 算法里，一次失败可作为其他线程已改变共享状态的证据，而用 CAS 实现的自旋锁仍可能在持锁线程停顿时卡住所有等待者。

正例是无锁计数器：线程读出 $v$，执行 $\mathrm{CAS}(x,v,v+1)$，失败则重试。两个线程同时从 $v=5$ 出发，只有一个 CAS 成功把 $x$ 变为 6，另一个发现 $x\ne 5$ 而失败、重读到 6、再 CAS 到 7——两次自增都不丢失。对照组是普通的"读、加一、写回"：两个线程都读到 5、都写回 6，一次更新凭空蒸发，这正是 CAS 的条件检查所堵住的漏洞。

无锁栈的压入更能看出 CAS 如何保护复合结构：线程先读取旧栈顶，把新节点的 next 指向旧顶，再尝试把栈顶从旧值换成新节点；失败说明这段时间里栈已经变化，必须重读后重做。成功的 CAS 通常就是线性化一致性公理库线性一致性Linearizability每次操作可放置在调用与返回之间的单点，使历史等价于满足实时顺序的顺序规范。证明中的线性化点，整个压入操作可视为在这一瞬间生效。

实际语言接口还可能提供 weak CAS，允许当前值与预期相等却返回失败；此时一次失败不能证明其他线程已经成功修改状态。弱 CAS 的循环与进展分析应采用其完整接口合同，不能直接套用本页强 CAS 的失败见证。

边界之一是 ABA 问题：CAS 判断的是"值相等"而非"未被动过"。若 $x$ 从 $A$ 改为 $B$ 又改回 $A$，中间的变化对 CAS 完全隐形；在无锁栈中，这可能让指针指向已被弹出又重用的节点，造成结构损坏。版本标签可让相同指针的两代取值不同；hazard pointer、epoch 等安全内存回收机制能防止节点过早释放和地址重用，却不会自动消除所有逻辑上的 ABA，仍需结合数据结构语义分析。边界之二是进展性等级：正确设计的 CAS 重试环常能达到 lock-free 而非 wait-free——系统整体持续完成操作，但个别倒霉线程可能次次落败、无限重试，需要额外的帮扶机制才能升级到 wait-free。

CAS 是现代同步设施的枢纽原语：无锁栈与队列、原子引用、一次性初始化、自旋锁公理库自旋锁Spinlock · Spin lock获取失败时以原子操作持续轮询、等待锁在短时间内释放的互斥锁实现族。与其他互斥实现都以它为骨架，主流指令集与并发库均直接提供。CAS 在标准原子语义下具有无限共识数；这项分类、通用构造与低层对象不可能性统一由共识数与 Wait-free 层级公理库共识数与 Wait-free 层级Consensus number · Consensus hierarchy · Wait-free hierarchy以共识数分类同步原语，并完整证明二进程原子读写共识的双价、临界配置和覆盖写入下界。说明，本页只保留 CAS 的操作规格、算法用法与 ABA 边界。

lock-free 进展公理库无锁进展Lock-free progress · Lock-freedom系统整体保证在有限步内有某个操作完成，而不保证指定线程。的大量正面结果依赖 CAS 或同等强度原语，但一条 CAS 指令本身不赋予整个调用路径任何进展等级。重试策略、帮助机制和内存回收都必须一并分析。

若更新还要受另一个控制字约束，RDCSS公理库RDCSS 条件双比较单更新RDCSS · Restricted double-compare single-swap以可帮助的描述符把控制字比较与单数据字更新合成一个线性一致动作。用可帮助描述符完成“控制仍匹配时修改一个数据字”。多字CAS公理库多字比较并交换Multi-word compare-and-swap · CASN · MCAS以排序占位、单次状态决断和可帮助清理，将多个数据字的逻辑更新线性化为一个原子操作。再让多个占位共享一次状态决断；逐字依次执行普通CAS没有这种原子效果，而连续两次单字读取也不会自动成为多字快照。