比较并交换

CAS 把乐观并发的哲学压缩进一条指令：线程不加锁地读取共享状态、在私有空间算出新状态，提交时声明"仅当世界仍是我看到的样子才生效"。若其他线程已抢先修改，提交失败，线程重读重算再试。与悲观的锁相比，它把"防止别人插手"换成了"检测别人是否插过手"：无竞争时零等待，有竞争时以重试为代价。这个原语为非阻塞进展提供了工具，但进展性属于整个算法，而不属于 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每次操作可放置在调用与返回之间的单点，使历史等价于满足实时顺序的顺序规范。证明中的线性化点，整个压入操作可视为在这一瞬间生效。

边界之一是 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以对象类型可为多少参与者 Wait-free 地解决共识来分类同步原语的表达能力。说明，本页只保留 CAS 的操作规格、算法用法与 ABA 边界。

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