CAS（Compare and swap）

CAS（比较与交换，Compare and swap） 算法是一种有名的非阻塞算法（non-blocking algorithm），同时也是一种无锁算法（lock-free algorithm），即在没有锁的情况下实现同步（并发控制），基于**乐观并发控制（optimistic concurrent control）**的思想。

2021.5 update：

这里避免使用“乐观并发控制（optimistic lock）”这个词，原因是这可能会带来confusion

因为“乐观并发控制”本身 imply使用到了锁（lock），而锁本来就是悲观的（pessimistic），这与乐观（optimistic）相互矛盾

另外，乐观并发控制其实描述的是一种进行并发控制（concurrent control）的思想，在这种思想中并不存在锁

因而，就可能导致 confusion

如果称为乐观并发控制（optimistic concurrent control），就会更准确。因而在本文中，不会使用“乐观锁”这个词，而是使用乐观并发控制。

也可能称为无锁并发控制（lock-free concurrent control）

java.util.concurrent包中的原子类（比如 AtomicInteger）就是通过CAS来实现乐观并发控制的。

当多个线程尝试使用 CAS 同时更新同一个变量时，只有其中一个线程能成功地更新变量的值，而其它线程都失败，失败的线程并不会被挂起，而是被告知这次竞争中失败，并可以再次尝试。

CAS 无锁算法的 C 实现如下：

int compare_and_swap (int* reg, int oldval, int newval) 
{
  ATOMIC();
  int old_reg_val = *reg;
  if (old_reg_val == oldval) 
     *reg = newval;
  END_ATOMIC();
  return old_reg_val;
}

*由于 CAS 需要以原子操作的方式更新 reg 的值，因此 CAS 需要硬件指令的支持。

总结来说：

CAS 算法：会执行一个原子操作
在这个原子操作中，先检查当前value是否等于current，如果相等，则意味着value没被其他线程修改过，更新并返回true。如果不相等，compareAndSet则会返回false，然后循环继续尝试更新。

就是指当两者进行比较时，如果相等，则证明共享数据没有被修改，因此可以替换成新值，然后继续往下运行；如果不相等，说明共享数据已经被修改，放弃已经所做的操作，然后重新执行刚才的操作。容易看出 CAS 操作是基于共享数据不会被修改的假设（即乐观并发控制思想），采用了类似于数据库的 commit-retry 的模式。当同步冲突出现的机会很少时，这种假设能带来较大的性能提升。

ABA问题

ABA问题是无锁结构实现中常见的一种问题，可基本表述为：

进程P1读取了一个数值A
P1被挂起(时间片耗尽、中断等)，进程P2开始执行
P2修改数值A为数值B，然后又修改回A
P1被唤醒，比较后发现数值A没有变化，程序继续执行。

对于P1来说，数值A未发生过改变，但实际上A已经被变化过了，继续使用可能会出现问题。在CAS操作中，由于比较的多是指针，这个问题将会变得更加严重。试

一个通常的解决 ABA 问题的思路是增加时间戳，即在进行数据更新时，不仅仅对比当前值与开始操作之前的值是不是一致，还对比最后修改数据的时间戳是否一致。

CAS 的权衡

在轻度到中度的争用情况下，非阻塞算法的性能会超越阻塞算法，因为 CAS 的多数时间都在第一次尝试时就成功，而发生争用时的开销也不涉及线程挂起和上下文切换，只多了几个循环迭代。没有争用的 CAS 要比没有争用的锁便宜得多（这句话肯定是真的，因为没有争用的锁涉及 CAS 加上额外的处理），而争用的 CAS 比争用的锁获取涉及更短的延迟。

在高度争用的情况下（即有多个线程不断争用一个内存位置的时候），基于锁的算法开始提供比非阻塞算法更好的吞吐率，因为当线程阻塞时，它就会停止争用，耐心地等候轮到自己，从而避免了进一步争用。但是，这么高的争用程度并不常见，因为多数时候，线程会把线程本地的计算与争用共享数据的操作分开，从而给其他线程使用共享数据的机会。

【Concurrent Control】CAS（Compare-and-swap）

CAS（Compare and swap）

ABA问题

CAS 的权衡

Reference

FEATURED TAGS

FRIENDS

TOC