Oracle 锁定 Latch 的 CAS 实现：Compare-And-Swap

原创 liaju 2021-03-26

1235

在 Oracle 数据库中，Latch 的实现通常是通过指令级的原子性操作完成的，CAS 就是常见的方法之一。

Compare-And-Swap

Compare-And-Swap(CAS)是一个用在多线程环境中实现同步的原子指令( atomic )。

该指令将在一个给定值(given value)和指定内存位置的内容之间比对
仅在一致的情况下修改该内存位置的内容为一个给定的新值(不是前面那个值)

这些行为都包含在一个单独的原子操作中。原子性保证了该新的值是基于最新的信息计算获得的；

如果该内存位置的内容在同时被其他线程修改过，则本次写入失败
该操作的结果必须说明其到底是否执行了取代动作。
它要么返回一个布尔类型的反馈，要么返回从指定内存地址读取到的值(而不是要写入的值)。

Oracle的 Compare-And-Swap Latch

使用原生态的Compare-And-Swap指令实现。
和TAS Latch类似，空值代表latch是free的，而一个非空值代表latch正忙。
但是一个CAS latch 可以有多种状态：

空闲的
以共享模式被持有
以排他模式被持有。

CAS latch可以在同一时间被多个进程或线程以共享模式持有，但还是仅有一个进程能以排他模式持有CAS latch。

典型的情况下，共享持有CAS latch的进程以只读模式访问相关数据，而一个排他的持有者目的显然是要写入/修改对应CAS latch保护的数据。

举例来说， CAS latch的共享持有者是为了扫描一个链表 linked list ，而相反排他的持有者是为了修改这个列表。共享持有者的总数上线是0x0fffffff即10进制的268435455。

几乎所有平台均支持CAS latch，仅仅只有HP的PA-RISC平台不支持。在PA-RISC上CAS latch实际是采用TAS latch。所以虽然在HP PA-RISC上代码仍会尝试以共享模式获得一个latch，但是抱歉最终会以排他模式获得这个latch。

一段英文描述：

Compare and swap
This is a common atomic instruction that exists on many CPU architectures. (x86: cmpxchg, SPARC: cas). It compares a value in memory with a value in a register, and if they match, overwrites the value in memory with a third value. If successful, the operation sets a status flag that can be used for branching. This can be used to efficiently implement spinlocks.

CAS无锁算法

要实现无锁（lock-free）的非阻塞算法有多种实现方法，其中CAS（比较与交换，Compare and swap）是一种有名的无锁算法。

CAS, CPU指令，在大多数处理器架构，包括IA32、Space中采用的都是CAS指令，CAS的语义是:

“我认为V的值应该为A，如果是，那么将V的值更新为B，否则不修改并告诉V的值实际为多少”

CAS是项乐观锁技术，当多个线程尝试使用CAS同时更新同一个变量时，只有其中一个线程能更新变量的值，而其它线程都失败，失败的线程并不会被挂起，而是被告知这次竞争中失败，并可以再次尝试。CAS有3个操作数，内存值V，旧的预期值A，要修改的新值B。当且仅当预期值A和内存值V相同时，将内存值V修改为B，否则什么都不做。

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（乐观锁算法）的基本假设前提

CAS比较与交换的伪代码可以表示为：

do{  
       备份旧数据； 
       基于旧数据构造新数据； 
}while(!CAS( 内存地址，备份的旧数据，新数据 ))  
复制

（上图的解释：CPU去更新一个值，但如果想改的值不再是原来的值，操作就失败，因为很明显，有其它操作先改变了这个值。）

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

CAS的开销（CPU Cache Miss problem）

前面说过了，CAS（比较并交换）是CPU指令级的操作，只有一步原子操作，所以非常快。而且CAS避免了请求操作系统来裁定锁的问题，不用麻烦操作系统，直接在CPU内部就搞定了。但CAS就没有开销了吗？不！有cache miss的情况。这个问题比较复杂，首先需要了解CPU的硬件体系结构：

上图可以看到一个8核CPU计算机系统，每个CPU有cache（CPU内部的高速缓存，寄存器），管芯内还带有一个互联模块，使管芯内的两个核可以互相通信。在图中央的系统互联模块可以让四个管芯相互通信，并且将管芯与主存连接起来。数据以“缓存线”为单位在系统中传输，“缓存线”对应于内存中一个 2 的幂大小的字节块，大小通常为 32 到 256 字节之间。当 CPU 从内存中读取一个变量到它的寄存器中时，必须首先将包含了该变量的缓存线读取到 CPU 高速缓存。同样地，CPU 将寄存器中的一个值存储到内存时，不仅必须将包含了该值的缓存线读到 CPU 高速缓存，还必须确保没有其他 CPU 拥有该缓存线的拷贝。

比如，如果 CPU0 在对一个变量执行“比较并交换”（CAS）操作，而该变量所在的缓存线在 CPU7 的高速缓存中，就会发生以下经过简化的事件序列：

CPU0 检查本地高速缓存，没有找到缓存线。
请求被转发到 CPU0 和 CPU1 的互联模块，检查 CPU1 的本地高速缓存，没有找到缓存线。
请求被转发到系统互联模块，检查其他三个管芯，得知缓存线被 CPU6和 CPU7 所在的管芯持有。
请求被转发到 CPU6 和 CPU7 的互联模块，检查这两个 CPU 的高速缓存，在 CPU7 的高速缓存中找到缓存线。
CPU7 将缓存线发送给所属的互联模块，并且刷新自己高速缓存中的缓存线。
CPU6 和 CPU7 的互联模块将缓存线发送给系统互联模块。
系统互联模块将缓存线发送给 CPU0 和 CPU1 的互联模块。
CPU0 和 CPU1 的互联模块将缓存线发送给 CPU0 的高速缓存。
CPU0 现在可以对高速缓存中的变量执行 CAS 操作了

以上是刷新不同CPU缓存的开销。最好情况下的 CAS 操作消耗大概 40 纳秒，超过 60 个时钟周期。这里的“最好情况”是指对某一个变量执行 CAS 操作的 CPU 正好是最后一个操作该变量的CPU，所以对应的缓存线已经在 CPU 的高速缓存中了，类似地，最好情况下的锁操作（一个“round trip 对”包括获取锁和随后的释放锁）消耗超过 60 纳秒，超过 100 个时钟周期。这里的“最好情况”意味着用于表示锁的数据结构已经在获取和释放锁的 CPU 所属的高速缓存中了。锁操作比 CAS 操作更加耗时，是因深入理解并行编程
为锁操作的数据结构中需要两个原子操作。缓存未命中消耗大概 140 纳秒，超过 200 个时钟周期。需要在存储新值时查询变量的旧值的 CAS 操作，消耗大概 300 纳秒，超过 500 个时钟周期。想想这个，在执行一次 CAS 操作的时间里，CPU 可以执行 500 条普通指令。这表明了细粒度锁的局限性。