比较并交换 CAS (Compare-and-Swap)

比较并交换(CAS)是一条由硬件提供的原子指令,它接收内存地址、预期旧值和新值三个参数,只有当内存中的当前值等于预期旧值时才把它替换为新值,并返回是否成功。整个读取、比较、写入过程对其他处理器不可分割。

概述

CAS是构建无锁并发的基石。相比互斥锁的悲观策略,CAS采用乐观策略:线程假设不会发生冲突,直接尝试更新,若发现值已被他人修改则重试。这种方式避免了线程阻塞和上下文切换,在竞争不激烈时性能优异。x86的cmpxchg指令、ARM的加载链接与条件存储都提供类似能力。

核心原理

• 原子性:硬件保证比较与交换作为单条不可中断的操作完成。
• 自旋重试:更新失败时线程循环读取最新值并再次尝试,形成CAS循环。
• 乐观并发:不加锁先操作,冲突时回退重来,减少阻塞。
• ABA问题:值从A变B又变回A时CAS无法察觉变化,常用带版本号的标记或双字CAS解决。

应用场景

原子整数的自增自减、无锁栈与无锁队列、引用计数、乐观锁都建立在CAS之上。Java的AtomicInteger、C++的atomic_compare_exchange、Linux内核的原子操作都以CAS为底层实现。数据库的乐观并发控制也借鉴了先操作后校验版本的思想。

常见问题

问:CAS一定比锁快吗?答:不一定。在低竞争下CAS避免阻塞很高效;但在高竞争下大量线程反复自旋重试会浪费CPU,此时锁反而可能更好,需按场景权衡。

问:什么是ABA问题?答:当某位置的值先被改成B又改回A,CAS只比较值会误以为没被动过。解决办法是附加单调递增的版本号或使用带标记指针,使每次修改都可被识别。