同步与互斥

设计原则

数据库的一个重要能力就是为多个用户提供并发访问服务，并发度是考察数据库性能的重要指标之一。事务隔离级别定义了并发控制算法的正确性，并让用户通过选择隔离级别在正确性和高性能之间进行平衡。事务重点考虑的是数据层面的并发控制，是属于较上层的同步与互斥。实际上，数据库系统是由大量进程、线程、数据结构构成的，进程、线程会并发地访问、修改数据结构，还需要在较底层级解决数据结构的同步与互斥问题。只有通过底层的同步与互斥机制建立起正确的系统，才能进一步获得数据层面的并发控制能力。

同步与互斥涉及硬件、操作系统、数据库软件自身三个层面，越接近硬件构筑互斥能力，效率越好，但跨平台的能力也越差。为此，本章在Oracle、MySQL的基础上增加了Intel CPU和Linux操作系统关于同步与互斥的设计，从而进行全栈地比较。在设计同步与互斥时需要重点考虑如下几个方面：

• 申请的时延；
• 系统的效率，包括系统总线负载、 CPU 负载以及随 CPU 数量的扩展情况；
• 公平性，多个进程或线程竞争互斥对象时，大家获取互斥对象的概率是否是相等的；
• 可分析、可配置能力，同步与互斥是高并发的基础，当并发性达不到预期时，是否有充分的、直观的跟踪数据供分析出关键竞争热点，并具备进一步配置调整的能力；
• 存储空间，为了提升并发性能一般会对被保护的资源进行切分，这会引入大量的同步与互斥对象；

CPU设计原理

CPU基本特性

同步与互斥仅靠软件是无法达成的，必须由底层硬件提供支撑。为了更好地理解同步与互斥背后的逻辑，以及对性能的影响，首先需要了解CPU的基本特性，主要包括流水线、乱序执行、缓存机制和内存应用。

CPU流水线。1980年代早期，CPU处理一条指令需要经过加载、解码、执行三个部分，相应的也就需要三个时钟周期。到1990年代底2000年代初，通过流水线技术，CPU可以同时处理多条指令，极大地提高了硬件性能。

程序的控制流高度可预测，流水线就可以很长，CPU就可以全负荷运行，从而获得极高的性能。紧凑的循环（如矩阵或向量运算），CPU可以准确地预测循环的结束分支，这样流水线可以一直维持饱满状态，CPU全力运行。相反，程序中有大量小而随机的循环，或者程序中有大量的虚对象，每个虚对象有对应着大量的实对象，这些对象又有大量高频使用的成员函数。这时就很难或者不可能预测控制流的走向，CPU要么等待控制流进行到足以知道分支的走向，要么干脆猜测（由于不可预测，常常猜错）。这时流水线就需要刷新，将预测错误的指令从缓存中删除，从而加载正确的指令分支，代价非常高。

图5.2-1 乱序执行示例

乱序执行。CPU在保证逻辑正确的前提下会对指令重新排序，从而最大化地发挥CPU的性能，减少等待时间。但有些重新排序是有害的，会影响正确性。如图5.2-1所示，a的增加和加锁在依赖关系上是不相关的，所以CPU可能在执行时交换顺序。然后a的增加操作依赖于锁的保护，所以执行顺序必须是先执行加锁，然后再执行a的增加。这就需要在这两条指令间加上内存栅栏原语，禁止CPU重新排序，但这样会降低CPU的性能。

图5.2-2 Intel Nehalem CPU微架构

缓存机制。如图5.2-2所示，当代CPU已经发展出三级缓存机制（L1 Cache、L2 Cache、L3 Cache），用于平衡内存访问和CPU执行时钟之间的巨大差距。然而在获得缓存优势的同时，系统复杂度带来了极大的挑战。需要解决缓存与缓存之间、缓存与内存之间同步问题。为了降低访问内存的时延，CPU会配置较大的缓存。然而对于在CPU间共享且频繁访问的变量，缓存反而其了反作用。某CPU准备修改某变量时，该变量刚刚被另外一个CPU修改过，这时缓存在该CPU缓存中的变量是无效的，必须发起缓存丢失以从其它CPU处获取该变量的最新值。

原子指令和流水线的一次一片的装配操作是冲突的，解决方法是将原子指令所涉及的数据归属到一个CacheLine中，并私有化到对应的CPU，由该CPU独享。如果其它CPU也需要操作该CacheLine中的数据，必须等待CPU完成原子指令，从而导致流水线等待或刷新。

图5.2-3 多CPU互联架构

内存引用。上世纪80年代，访问内存的速度快于执行指令，但到了2006年，访问内存的时间里CPU可以执行上千条指令。虽然增大CPU缓存可以降低数据访问时延，但这依赖于缓存对即将访问的数据有很高的预测准确率。然而某些操作，如遍历指针链表，是无法预测对应数据的，从而不得不访问内存，导致CPU性能下降。

随着CPU的增加，通过单一的北桥集中访问内存已经越发不可行。CPU逐渐将内存控制器集成到CPU内部，从而提高内存访问带宽和速度。如图5.2-3所示，各CPU都通过内部集成的内存控制器访问内存，这样极大地提高了内存访问带宽和扩展性，同时系统中不存在单点瓶颈。然而互联架构下各CPU访问内存并不均衡，图中CPU0访问DDR0是非常快速的，但CPU0访问DDR5经过的路径明显变长，即内存访问不是统一的（NUMA）。实际上，CPU之间互联是有数量限制的，当到达一定数量后（如大于8路）就必须借助多节点控制器（node controller）扩展更多的CPU，这时不均衡性就会更加明显。

硬件系统的架构

图5.2-4 4颗CPU互联架构

图5.2-4给出了一个八核系统的概要结构（简化了3级缓存）：

• 4 颗 CPU 芯片组成，芯片与芯片之间的交互都通过中央的互联模块组成；
• 每颗 CPU 芯片包括 2 个核，每个核有自己的缓存，两个核的交互通过芯片内的互联模块完成；

数据在系统内的流动是以CacheLine为单位进行的，对应于2的幂大小字节数的内存块，通常为32到256个字节。Core将某变量从内存加载到寄存器中时，先将含该变量的内存块以CacheLine为单位加载到该Core的Cache中。Core将寄存器中的变量写到内存时，也需要先将含该变量的CacheLine加载到该Core的Cache中，且要确保该CacheLine不会出现在其它Core的Cache中。

下面以示例的方式大致介绍一下数据的流动过程，假设Core0要对某变量执行CAS（Compare And Swap，比较交换）操作，该变量刚好驻留在Core7的Cache中：

• Core0 检查本地 Cache ，发现不存在含该变量的 CacheLine ；
• 请求被发送到同一个 CPU 芯片中的 Core1 ， Core1 检查本地 Cache 也不存在含该变量的 CacheLine ；
• 请求被发送到芯片间的中央互联模块，互联模块发现该 CacheLine 被 CPU3 芯片所拥有；
• 请求被发送到 CPU3 芯片内的互联模块，检查两个 Core 的 Cache ，发现在 Core7 的 Cache 中；
• Core7 将包含该变量的 CacheLine 发送给芯片内的互联模块，并将该 CacheLine 从本地 Cache 中删除；
• CPU3 芯片内的互联模块将 CacheLine 发送给芯片间的中央互联模块；
• 芯片间的中央互联模块将 CacheLine 发送给 CPU0 芯片内的互联模块；
• CPU0 芯片内的互联模块将 CacheLine 发送给 Core0 的 Cache 中；
• Core0 执行 CAS 操作；

上述模型做了大量简化，产品级的缓存一致性机制是非常复杂的，例如：

• 其它 Core 很可能同时对该 CacheLine 中的变量做 CAS 操作；
• 其它几个 Core 的 Cache 中很可能以只读方式保存了该 CacheLine ，这时需要删除；
• 当请求到达 Core7 时， Core7 很可能已经又开始操作该 CacheLine ，请求需要被保持直至操作完成；
• 当请求达到 Core7 时， Core7 很可能开始释放该 CacheLine （腾出 Cache 空间给其它数据使用），即该 CacheLine 不在 Core7 的 Cache 中，已经在流向内存的途中；
• CacheLine 中可能发生了可校正的错误，在使用数据前需要先校正；

缓存一致协议

在上节我们已经知道，在多CPU环境中，需要确保CPU Cache与Cache之间、Cache与内存之间的数据保持一致，缓存一致性协议就为了达成该目的的。缓存一致性协议非常复杂，有几十种状态，出于理解的目的，本节将其简化为4种状态（MESI）。每个CacheLine除了有地址和数据之外，还会维护一个状态：

• Modified ：该状态的 CacheLine 拥有最新的数据，且被本 Core 独占，本 Core 在删除该 CacheLine 前有责任将其传递给其它 Core ，或者写回到内存；
• Exclusive ：该状态的 CacheLine 和 Modified 状态类似，区别只是内存中也有一份最新的数据。 E 状态有排它性，数据只能被本 Core 独占，但删除该 CacheLine 不需要传递给其它 Core ，或者写回到内存；
• Shared ：该状态表示对应的 CacheLine 至少还出现在另外一个 Core 的 Cache 中，所以本 Core 不能修改 CacheLine 中的数据。和 E 状态类似，删除该 CacheLine 不需要传递给其它 Core ，或者写回到内存；
• Invalid ：该状态表示对应的 CacheLine 为空，数据优先写入状态为 I 的 CacheLine 中，覆盖其它状态的 CacheLine 会引起非常高的成本；

Core之间通过大量的消息交互维持上述的状态转换，下面给出CPU共享单个总线时之间的交互消息：

• 读：读消息中包含 CacheLine 的物理地址；
• 读响应：为读的响应消息，包含读请求的数据。响应消息既可能来源于内存，也可能来源于其它 Core 的 Cache 。例如某 Cache 拥有该 CacheLine ，且状态为 Modified ，则必须对该 CacheLine 的读消息做出响应；
• 失效：包含失效 CacheLine 的物理地址，所有包含该 CacheLine 的 Cache 必须移除该 CacheLine ，并回复响应；
• 失效确认： Core Cache 收到失效请求时，在移除该 CacheLine 之后回复失效确认消息；
• 读失效：包含 CacheLine 的物理地址，要求读取该 CacheLine ，并让其它 Cache 删除该 CacheLine ，是读消息和失效消息的组合，接收端必须回复读响应和失效确认两个消息；
• 回写：包含物理地址和数据，用于将数据写回到内存。处于 Modified 状态的 CacheLine 在被移除时，先通过回写消息将数据写回内存；

可见，多核系统在底层也是一个基于消息驱动的系统。回写消息源于什么场景？接收端会时谁？Cache空间不足，需要删除某CacheLine，同时该CacheLine又处于Modified状态。因为只有本Cache拥有该CacheLine的最新数据，所以需要回写，否则直接删除即可。接收端一般是内存或者上级Cache，如一级Cache回写到二级Cache。也有可能是其它Core的Cache，如某Core Cache近期刚刚读过该CacheLine，说明其对该数据有兴趣。

两个Core同时对同一个CacheLine发起失效的过程是怎样的？两个Core首先需要同时争用共享的总线，只能有一个Core获胜。获胜的Core发出失效消息，另一个Core必须删除并回复响应。随后落败的Core再发起失效消息，之前获胜的Core删除数据并回复响应。可见获胜是临时的，最终两个Core中的对应CacheLine都失效了。每个Core都必须对失效请求做出响应会不会引起消息风暴，侵害了系统总线的带宽？在本简化模型中确实有这个问题，但在实际系统中会避免该问题。

原子指令

单行代码或函数在CPU中执行时是由多条指令组成的，在可中断或并发环境中某些情况下需要保证这些指令具备原子性。以Intel CPU为例，从应用的角度来看CPU提供了如下原子操作手段：

• TAS （ Test And Set ）：指令 xchgb 、 xchgw 、 xchgl 分别提供单字节、双字节、 4 字节的 TAS 原子操作；
• CAS （ Compare And Swap ）：指令 cmpxchgb 、 cmpxchgw 、 cmpxchgl 分别提供单字节、双字节、 4 字节的 CAS 原子操作；
• LOCK ：通用的原子操作，加了 LOCK 前缀的指令必须被原子地执行；

不管是TAS、CAS、LOCK，CPU内部实现原子性的原理和机制是一致的。但由于历史原因，TAS指令不需要加LOCK前缀，CAS需要加LOCK前缀。主要原因是TAS是最早的原子指令（也是最简单的），不仅CPU厂商提供TAS能力，很多内存厂商也提供TAS能力。内存厂商实现TAS的方案有：

• 方案 1 ：维护一个独立的区域。当从 CPU1 接收到 TAS 指令之后，将指令所涉内存地址存放到该独立区域中。如果在此期间同时从 CPU2 收到 TAS 指令，检查发现该 TAS 指令所涉地址已经在独立区域中，对 CPU2 发起 BUZY 中断，让其重试；
• 方案 2 ：维护一个独立的区域。当从 CPU1 接收到 TAS 指令之后，并不直接修改内存，而是将新值存放到独立区域中，同时将对应的内存区域打上特殊标签， TAS 指令执行完毕后再将新值从独立区域拷贝到内存区域。如果在此期间同时从 CPU2 接收到 TAS 指令，检查发现该 TAS 指令所涉内存区域的值是特殊标签，对 CPU2 发起 BUZY 中断，让其重试；

随着原子操作要求的功能越来越复杂，原子能力逐渐基本都由CPU来提供。CPU提供原子能力的手段主要有两种：

• 锁总线： CPU 有一条 Lock 引线，当执行原子操作时会拉低 Lock 引线的电位，锁住总线，这样其它 CPU 或者外设暂时无法通过总线访问内存，从而达到原子性目的；
• 锁缓存：当原子操作所涉数据在一个 CacheLine 中，且该 CacheLine 已经在 CPU 的 Cache 中，锁住本 CacheLine 直至原子操作完成并写入内存，在此期间通过缓存一致性协议（ MESI ）确保其它 CPU Cache 无效；

早期CPU仅支持锁总线，这种方法粒度较粗，对系统的性能影响非常大。Intel从P6 CPU开始引入锁缓存机制，从而优化提升原子操作的性能。

原子指令的成本

图5.2-5 原子自增操作的数据流

如图5.2-5给出了高并发下原子自增操作的数据流动。为了使得每个Core都有机会执行自增操作，包含自增变量的CacheLine必须在各个Core之间循环。CacheLine循环在2011年有了重大改进，其原理是将多个Core的原子操作整合成组合树，从而将时延从O（N）减少到O（LogN）量级。

表5.2-1 4Core 1.8GHz AMD CPU同步操作成本

表5.2-1给出了同步机制涉及的常见操作的成本，第二列为操作消耗的时间，第三列为消耗的时钟周期数（一般情况下，一个时钟周期内至少可以执行一条普通指令）：

• 最好情况下的 CAS 是指对应的数据在 core 的本地 cache 中，该原子操作消耗约 60 个时钟周期；
• 最好情况下的 lock 是指对应的数据在 core 的本地 cache 中，该操作消耗约 100 个时钟周期，原因是 lock 需要进行两次原子操作；
• 此处的 cache miss 指数据不在 core 的本地 cache 中，但可以从其它 core 的 cache 中获取，不需要从内存中获取，该操作消耗 230 个时钟周期；
• CAS cache miss ， CAS 涉及旧值读取和新值存储，在 Cache 未命中的情况下需要消耗 510 个时钟周期；
• IO 操作的成本更高：高性能的通信网络（如 InifiBand ）需要 5000 个时钟周期，标准通信网络涉及协议编解码，成本更高。光绕地球一圈需要 130 毫秒，相当于 2.16 亿个时钟周期；

表5.2-2 16Core 2.8GHz Intel X5550(Nehalem)CPU同步操作成本

硬件设计者在最大程度地优化这些操作的成本，但受制于光速和原子大小的限制。前者限制了速度，后者限制了进一步微型化，从而限制了频率。当然一些厂商的优化效果也非常明显，表5.2-2给出了Intel CPU在核心、核间、芯片间的操作成本。

图5.2-6 原子自增操作时延和CPU数量间的关系

在Intel双核CPU上的测试：

• 单线程的原子计数器做自增要比普通计数器做自增慢 6 倍；
• 双线程的原子计数器做自增要比普通计数器做自增慢 10 倍；

图5.2-6给出了原子自增操作消耗的时间和CPU数量之间的关系：

• 和横轴平行的虚线 B 是理想状态下的性能，为非原子操作，随着 CPU 数量的增加操作消耗的时间保持为常量；
• 即使在 CPU 为 1 时，原子自增操作也比普通自增操作所需的时间要长，说明原子操作自身也是有成本的；
• 原子自增操作的成本随着 CPU 数量的增加而增加，量级为 O （ N ）， N 为 CPU 的数量；

Linux设计原理

总体设计

图5.3-1 Linux同步与互斥原语间的关系及成本

如图5.3-1所示，Linux提供了原子函数、spinlock、mutex、semaphore多种同步与互斥机制。不管哪种机制，都是建立在CPU原子指令基础之上的，即没有硬件的支撑，软件是无法独立建立同步与互斥能力的。在同步与互斥成本上，原子函数的逻辑最简单，仅仅提供原子能力，所以成本最低。Spinlock相比原子函数增加了一些逻辑，会进行循环比较与等待，并延伸出排队、区分读写等一系列特性。Semaphore的成本在spinlock之上，因为semaphore一旦发现冲突就会迫使相关进程休眠阻塞，直至冲突资源被其它进程释放。Mutex的成本在spinlock和semaphore之间，mutex发现冲突之后仍然会自旋尝试一段时间，仍然无法获得冲突资源才会进入休眠阻塞态。

Linux的各种同步与互斥原语不是一蹴而就的，而是在不断地演进中发展起来的。例如，spinlock就经历了传统spinlock、排队spinlock、读写spinlock、mcs spinlock、seq spinlock等等。原子函数、spinlock、mutex、semaphore等同步与互斥原语虽然成本不同，但都会调用底层CPU的原子指令，而原子指令的成本远高于普通指令。所以Linux又设计了RCU机制，RCU的读原语不调用底层的原子指令，所以非常轻量。

原子函数

原子函数是在CPU提供的原子指令基础上进行的简单封装，和spinlock、mutex、semaphore相比非常简单，仅实现了基础原子能力，没有实现其它等待、循环等逻辑，所以相对比较轻量。

表5.3-1 Linux POSIX和GCC提供的原子函数

线程、锁、原子函数在专家委员会关注之间，已经被广泛地长时间使用。同时处于历史或性能等原因，通过汇编语言自己实现这些功能也很普遍，所以这些原语的变体非常多，表5.3-1给出了POSIX和GCC提供的原子函数之间的对应关系（Linux内核大量使用了GCC提供的原语）。当然POSIX和GCC提供的原子函数远多于表5.3-1，具体可以查看相关手册。

图5.3-2 基于TAS指令实现的xchg原子函数

#define xchg(ptr,v) ((_typeof_(*(ptr)))_xchg((unsigned long)(v),\

(ptr),sizeof(*(ptr))))

static inline unsigned long _xchg(unsigned long x, volatile void* ptr,int size)

{

switch(size){

case 1:

_asm_ _volatile_(“xchgb %b0,%1”

:”=q”(x)

:”m”(*_xg(ptr)),”0”(x)

:”memory”);

break;

case 2:

_asm_ _volatile_(“xchgw %w0,%1”

:”=r”(x)

:”m”(*_xg(ptr)),”0”(x)

:”memory”);

break;

case 4:

_asm_ _volatile_(“xchgl %b0,%1”

:”=r”(x)

:”m”(*_xg(ptr)),”0”(x)

:”memory”);

break;

}

return x;

}

如图5.3-2所示，Linux内核使用的xchg原子函数就是基于原子指令xchgb、xchgw、xchgl实现的，且没有加LOCK前缀。其实现的功能和TAS一致，即将v值写到ptr指向的内存区域，并返回ptr所指内存区域中的旧值。

图5.3-3 基于CAS指令实现的cmpxchg原子函数

#define cmpxchg(ptr,o,n) ((_typeof_(*(ptr)))_cmpxchg((ptr),(unsigned long)(o),\

(unsigned long)(n),sizeof(*(ptr))))

static inline unsigned long _cmpxchg(volatile void* ptr,unsigned long old, 

unsigned long new,int size)

{

unsigned long prev;

switch(size){

case 1:

_asm_ _volatile_(LOCK_PREFIX “cmpxchgb %b1,%2”

:”=a”(prev)

:”q”(new),”m”(*_xg(ptr)),”0”(old)

:”memory”);

return prev;

case 2:

_asm_ _volatile_(LOCK_PREFIX “cmpxchgw %w1,%2”

:”=a”(prev)

:”r”(new),”m”(*_xg(ptr)),”0”(old)

:”memory”);

return prev;

case 4:

_asm_ _volatile_(LOCK_PREFIX “cmpxchgl %w1,%2”

:”=a”(prev)

:”r”(new),”m”(*_xg(ptr)),”0”(old)

:”memory”);

return prev;

}

return old;

}

如图5.3-3所示，Linux内核使用的cmpxchg原子函数就是基于原子指令cmpxchgb、cmpxchgw、cmpxchgl实现的，但加上了LOCK前缀。其功能和CAS一致，即将old和ptr指向的内存值比较，如果相等将new写入到ptr指向的内存并返回old值，如果不等则返回ptr指向的内存值。

图5.3-4 基于LOCK指令实现的atomic_add原子函数

typedef struct { volatile int counter; } atomic_t;

static _inline_ void atomic_addd(int i,atomic_t *v) 

{

_asm_ _volatile_(LOCK_PREFIX “addl %1,%0”

:”=m”(v->counter)

:”ir”(i),”m”(v->counter));

}

如图5.3-4所示，Linux内核版本的atomic_add是通过LOCK指令来保证原子性的。

Spinlock

Spinlock自旋锁在原子指令的基础上加入了等待和自旋的逻辑。维护一个spinlock_t变量，该变量有open和close两种状态。当申请spinlock是检查状态：

• 如果状态为 open ，将状态改为 close ，表示本次申请已经成功获得 spinlock 锁，检查状态和修改状态必须是一个原子操作；
• 如果状态为 close ，就旋转等待以循环检查状态，直至其它线程释放该 spinlock 锁；

图5.3-5 传统spinlock的实现

typedef struct { volatile unsigned int slock; } spinlock_t;

#define spin_lock_string\

“\n1:\t”\

“LOCK_PREFIX;decb %0\n\t”\

“ins 3f\n”\

“2:\t”\

“rep:nop\n\t”\

“cmpb $0,%0\n\t”\

“jle 2b\n\t”\

“jmp lb\n”\

“3:\n\t”

static _inline_ void _raw_spin_lock(spinlock_t *lock) 

{

_asm_ _volatile_(

Spin_lock_string

:”=m”(lock->slock)::”memory”);

}

图5.3-5是Linux spinlock的实现，采用的仍然是CPU的lock指令。不过上述实现是传统实现（2.6.25版本之前），有如下缺点：

• 每个申请自旋锁的 CPU 均在全局变量 slock 上忙等待，系统总线将因为 CPU 间的 cache 同步而引起非常高的流量，从而降低了系统的总体性能；
• 随着 CPU 数量的增加，自旋锁的竞争也将同步增加，导致更长的等待时间；
• 释放自旋锁的重置操作将无效化所有其它正在忙等待的 CPU cache ，那么在 CPU 拓扑结构中临近当前自旋锁拥有者的 CPU 可能会更快地刷新本地 cache ，因而增大获得自旋锁的几率，导致不公平；

2.6.25版本开始Linux将spinlock发展排队自旋锁，采用FIFO Ticket机制解决不公平问题。其方法是将slock分为next和owner两个部分，申请时next加1，释放时owner加1，申请时获得的next等于owner时才能获得锁，这样就获得锁的顺序就是申请的顺序，从而保证了公平性。

基于FIFO Ticket的spinlock只解决了不公平问题，但并没有解决频繁缓存失效导致的性能下降问题。之后Linux发展出mcs spinlock，让每个申请者都自旋在本地变量上，而不是全局变量上，从而极大地提升了多CPU下的性能。当然，spinlock还在不断地演进：

• 读写锁（ reader-writer spinlock ）：用于区分读写的场景，读与读不冲突，读与写、写与写冲突，从而提高被保护资源的并发访问度；
• 顺序锁（ seq spinlock ）：用于读写也不冲突，只有写写冲突的场景。顺序锁是写优先的锁，不过在读多的场景中，读原语非常轻量（没有原子操作），顺序锁的性能非常好。 Linux 内核的计时校正和文件路径遍历就是利用顺序锁保护的；

Semaphore

Spinlock是循环等待的，发生冲突时进行自旋，仍然会消耗CPU资源。Semaphore则在发生冲突时，让冲突进程阻塞等待，让出CPU，当持有者释放后再唤醒阻塞进程，让其继续工作。Semaphore在提供同步与互斥的同时，还可以区分读和写。当semaphore处于close状态时，任何读操作或者写操作都被插入到semaphore等待队列的末尾。当semaphore处于open状态时，semaphore等待队列中的第一个操作被唤醒。如果第一个操作时写操作，等待队列中的其它操作继续休眠等待。如果第一个操作时读操作，从队列中的第一个操作开始到第一个写操作之间的所有读操作都会唤醒，获得该semaphore。可见，semaphore也是采用FIFO的等待顺序。Semaphore和spinlock的主要区别有：

• spinlock 发现冲突会循环等待， semaphore 发现冲突会立刻休眠；
• spinlock 是针对单个锁进行冲突检查， semaphore 可以通过 num_sems 定义多个信号，当 num_sems=1 时， semaphore 又称为 binary semaphore ；
• spinlock 用于锁持有时间较小的场景， semaphore 用于锁持有时间较长的场景；

图5.3-6 semaphore结构

struct semaphore{ 

raw_spinlock_t lock;

unsigned int count;

struct list_head wait_list;

};

图5.3-6给出了semaphore的结构定义，wait_list存放等待者列表，整个结构通过spinlock进行保护。和spinlock相比，semaphore更加厚重，涉及进程上下文切换，一般用于冲突时间较长、临界区较大的互斥保护场景。

Mutex

当semaphore的信号数等于1时，其功能与mutex是基本一致的。两者的主要区别是semaphore发现冲突会立刻休眠，mutex发现冲突会尝试自旋等待，自旋等待一段时间仍然无法获取则进行休眠。可见，mutex的设计理念是轻量级的semaphore，其用于冲突时间在spinlock和semaphore之间的互斥保护场景。

图5.3-7 mutex结构

struct mutex{ 

atomic_t count;

spinlock_t wait_lock;

struct list_head wait_list;

struct task_struct *owner;

};

图5.3-7给出了mutex的定义，相比semaphore多了owner成员，用于保存mutex的当前拥有者。Mutex相比semaphore有如下优势：

• owner 可以防止同一个线程重复申请相同的锁；
• mutex 一般用于线程间的同步与互斥，进程重启后自然消亡，无需考虑清理问题；

RCU

RCU（Read-Copy Update）同步互斥机制于2002年10月被Linux内核采纳。RCU允许读读兼容、读写兼容、但写写不兼容。RCU会维护对象的多个版本，并确保直到所有线程退出读临界区才会释放对象的旧版本。RCU的读临界区原语非常轻量，甚至在某些不可抢占的内核中，读原语的成本为0。

RCU的读原语不会阻塞和自旋，写原语不会回滚和退出，所以读和写可以并发执行，但这会导致有可能读到过期甚至是不一致的数据。然而真实环境中很多场景是允许读取过期和不一致数据的，例如网络中路由表的更新。

图5.3-8 RCU vs Spinlock(RW)

图5.3-8对比了读写锁和RCU在并发读写下的数据视图。在读写锁场景下，写自旋一致持续到最后一个读完成，然后才能开始写操作。而一旦开始写操作，所有的读操作都需要自旋等待，直至写完成，但写之后的读操作都可以读到最新的值。在RCU场景中，读和写是并发执行的，所以读可以更早地读到新值，然而由于读和写存在重叠期，所以之前的RCU可能读到新值，也可能读到旧值。

Linux内核中使用RCU最多的地方就是在读敏感的地方使用RCU替换读写锁。RCU的优点有高性能、无死锁、低时延，缺点是由于读写可以并发执行，运行在读临界区的低优先级线程执行权被高优先级线程抢占导致synchronize_rcu同步时长变长（可能达到好几毫秒）。

Oracle设计原理

综述

表5.4-1 Oracle内部主要同步与互斥机制

如表5.4-1所示，Oracle内部主要有internal lock、latch、mutex三种同步与互斥机制。Internal lock的层级相对较高，和数据的并发控制比较类似，我们将在“并发控制”章节一并讨论。Latch和mutex的层级较低，用于保护内部共享数据结构、对象、文件的并发访问。Mutex在Oracle10g才引入，设计的更加轻量，并用于替代部分latch场景。Mutex除了具有并发访问的保护功能之外，还可以用于对象的引用计数，防止内存对象的老化移出。

Latch基本特性

系统中每个latch都对应一个KSLLT结构。在Oracle11g版本中，32位KSLLT占用100个字节，64位KSLLT占用160个字节。KSLLT结构中的关键信息有：

• Latch id ：对应于 latch 的 name （ v$views ），系统的 latch 数量，每个 latch 的名称和作用，在 Oracle 发布正式 GA 版本时就已经确定（ child 型 latch 除外），即编译时已经确定；
• Latch value ： latch 的核心变量，通过 spin 和原子操作本变量获得基础互斥能力；
• Level ：每个 latch 都会赋予一个特定的 level 级别，用于解决死锁问题；
• Class ：每个 latch 都会设置一个特定的 class 级别，用于定义发生竞争冲突时 latch 的行为；
• Where ：本 latch 已经被某进程持有， where 描述该进程是在什么地方申请本 latch 的，对应于 x$ksllw.indx ；
• Why ：本 latch 已经被某进程持有， why 描述该进程为什么在 where 处申请本 latch ；
• Wait list ：当多个进程申请同一个 latch 会发生冲突， wait list 存放所有需要等待的进程；
• SHR ：描述本 latch 的模式，支持 exclusive 和 share 两种模式。 exclusive 模式下不区分 e 和 s ，任何两次申请都是冲突的。 share 模式区分 e 和 s ， s 与 s 不冲突， e 与 e 、 e 与 s 冲突；
• Type ：描述本 latch 的类型，支持 solitary 、 parent 和 child 三种类型；
• G2C ：本 latch 是否支持同时以 wait 方式申请 2 个 child latch ；
• Recovery ：恢复区，进程获取 latch 后修改临界区数据，如果进程在修改的过程中异常退出，会造成临界区数据异常。因此，进程在修改临界区时会在 recovery 区中记录日志，如果进程异常退出，后继 PMON 后台进程会根据 recovery 区中的日志恢复临界区中的异常数据；
• Statistics ：本 latch 相关的统计信息，如 GETS 、 MISSES 、 SLEEPS 、 SPIN_GETS 、 WAIT_TIME 、 IMMEDIATE_GETS 、 IMMEDIATE_MISSES 等等；

了解了latch的主要数据结构KSLLT之后，下面来看latch提供的主要访问函数：

• kslgetl(laddr, wait, why, where) ：申请 exclusive 模式的 latch ；
• kslgtesl(laddr, wait, why, where, mode) ：申请 share 模式的 latch ；
• ksl_get_shared_latch(laddr, wait, why, where, mode) ：申请 share 模式的 latch ， 11g 及后继版本提供主要访问函数；
• kslg2cs(laddr1, laddr2, mode, trc, why, where) ：同时申请两个 share 模式的 child latch ；
• kslfree(laddr) ：释放 latch ；

其中laddr用于指定具体申请哪个latch，where用于指定本次是在什么地方申请本latch，why用于指定本次为什么在where处申请本latch。当申请share模式的latch时，通过mode参数指定申请的锁类型，mode等于16表示申请e锁，mode等于8表示申请s锁。

Latch支持no-wait和wait两种申请方式：

• no-wait ：用于存在多个相同类型 latch 的场景，某个 latch 不可用则申请下一个，直至所有 latch 都不可用，例如 redo copy latch 有大量 child latch ；
• wait ：如果空闲则获取，如果冲突则进行 spin 、 sleep 或者 post/wait ，具体行为和策略由 class 定义；

Latch value是latch的核心变量，latch正是通过spin该变量获得互斥能力的。Latch value由flag和pid_ref_count两个部分组成：

• flag ： 0x00 表示空闲或共享占用 (s) ， 0x40 表示有进程正在尝试独占占用 (e) ， 0x20 表示独占占用；
• pid_ref_count ：当 flag 等于 0x00 或者 0x40 时表示以 s 方式持有本 latch 的进程数，当 flag 等于 0x20 时表示以 e 方式持有本 latch 的进程 pid ；

当flag等于0x40时，pid_ref_count可以不等于0，即此时latch仍然被多个进程以s方式持有。然而，flag一旦等于0x40以后，后继进程将无法再以s方式获得本latch，而等到pid_ref_count减到0以后被当前申请者以e方式持有，可见latch是独占优先的。

Latch在类型上又分为solitary、parent和child。系统中有两大类latch，一类是静态的，在发布GA版本时就已经确定下来，另一类是动态，在系统启动时根据系统的资源情况动态决定的。例如，redo copy latch的数量和redo buffer pool的数量是一致的，而redo buffer pool的数量是系统启动后根据CPU的数量动态决定的。每个redo buffer pool都有一个动态创建的redo copy latch，这些latch都是child latch，都属于一个parent latch。然而，不管child latch还是parent latch都和redo buffer pool相关的，所以它们的name是一样的，都是redo copy latch。可见，solitary latch和parent latch是静态latch，而child latch是动态latch。Child latch是为解决单一latch保护的资源过大，需要在运行期间根据资源的实际大小进一步对latch进行切分的场景。被分裂的latch是parent latch，生成的各个子latch就是该parent latch的child latch。Child latch的属性集成于parent latch，包括name、level、class等等。正常情况下，在SGA初始化时，solitary、parent、child latch都会完成初始化。但在oracle 10g及后继版本中，系统资源会在运行过程中动态调整，所以有些child latch也会动态的创建和删除。V$latch_parent展示所有的parent latch情况，v$latch_children展示所有的child latch情况，v$latch则展示所有latch的情况。

图5.4-1 Latch死锁示例

如图5.4-1所示，ProcessB已经持有latch4，并等待latch3释放，而ProcessC已经持有latch3，并等待latch4释放，这样就形成了一个循环。在没有外界干预的情况下，永远等待，进程自身已经无法解决。解决死锁的方案有事前和事后两类方案，事后方案主要通过超时解决，但一般存在误判，成本较高。常见的事前方案有：

• 方案 A ：进程同时只能申请和持有一个 latch ，即申请新的 latch 前必须释放所有已经持有的 latch ；
• 方案 B ：所有进程都以相同的顺序申请 latch ；
• 方案 C ：建立系统全局的 latch 有向图，进程在申请 latch 时，在阻塞等待前判断有向图中是否有循环，如果有则放弃申请；

latch支持wait方式，所以也存在死锁的风险。Oracle综合考虑成本和功能等因素，采用了方案B。其方法是根据各latch的物理含义给每个latch分配一个level，并做如下约定：

• 对于 solitary 、 parent 、 child 之间的场景：当进程持有 latch x 后，且期望申请 latch y ，当且仅当 y.level 大于 x.level ，进程才可以申请 latch y ；
• 对于属于同一个 parent 的 child 与 child 之间的场景： child 都继承于 parent ，所以 level 是相等的。当进程持有 latch x 后，且期望申请 latch y ，当且仅当 y.child_number 小于 x.child_number ，进程才可以申请 latch y ；

上述约定实际上限制了latch的申请顺序，从而从latch的最前端规避了死锁的风险。每个latch的level具体取值取决于latch的物理含义。Oracle在设计latch时，会综合考虑各个latch的物理含义以及在各种场景中可能的运用顺序，最终为每个latch分片一个合理的level值（0~14，共计15个level级别）。

Latch的实现

图5.4-2 Latch运行示意图

图5.4-2给出了latch的运行过程，大致可以分为如下几个步骤：

• 调用 sskgslgf 尝试立刻获得本 latch （ sskgslgf 函数用于获得 Exclusive 模式的 latch ，如果是 Share 模式的 latch 则调用 kslgetsl 函数），如果获得则结束，否则进入下一步；
• 重置 spin_count 和 yield_count ，具体取值取决于该 latch 的 class 属性；
• 调用 spin_count 次 sskglspin ，自旋尝试获得 latch ，一旦获得立刻结束，否则自旋尝试直至达到 spin_count 次；
• 如果 yield_count 大于 0 ，调用一次 sched_yield （ Linux 系统），为优先级相等或更高的进程让出执行权，然后继续进行 spin_count 次 sskglspin ；
• 当达到 spin_count*(yield_count+1) 次 sskglspin 时，进行一次 sleep （ Linux 下通过调用 select 达到 sleep 的目的）；
• Sleep 完成后，重置 spin_count 和 yield_count ，进入下一轮循环，如此循环往复，直至获得本 latch ；

可见，latch循环的过程是spin、sched_yield、sleep的组合，每进行spin_count次spin后进行一次sched_yield，每进行spin_count*(yield_count+1)次spin时进行一次sleep。如此循环，直至某次spin获得本latch。那么spin_count、yield_count、sleep time又是哪里来的呢？这就要看latch的class属性了。

表5.4-2 x$skllclass示例（仅含部分列）

latch的行为是由class定义的。如表5.4-2所示，系统定义了0~7共计8种class。每个latch可以设置是哪个class，每种class中的spin、yield、sleep都是可以设置，从而可以配置出非常丰富的latch行为。class主要包括spin、yield、sleep三个部分：

• Spin ：定义每次自旋的次数，即 spin_count ；
• Yield ：定义 yield 的次数，即 yield_count ；
• Sleep ：定义 sleep 的时间，第一次 sleep 的时间由 sleep0 定义，第八次 sleep 的时间由 sleep7 定义，后继 sleep 的时间都是 sleep7 定义的时间（ Oracle6 及早期版本， sleep 时间按照指数进行回退的）；

用户可以通过_latch_classes设置或更改latch的class属性。例如，语句“alter system set “_latch_classes” = ‘46:3 103:3’ scope=spfile;”将46号latch（second spare latch）和103号latch（gcs pcm hashed value bucket latch）的class设置为3。class中的spin_count、yield_count和sleep参数可以通过_latch_class_n设置或修改。例如，“alter system set “_latch_class_3” = “ 100 2 3 10000 20000 30000 40000 50000 60000 70000 80000” scope=spfile;”将spin_count设置为100，yield_count设置为2，sleep0设置为10000，sleep7设置为80000。

可见，通过class可以设置每个latch属于具体哪个class，也可以为每种class设置各个阶段的详细行为。然而，Oracle在此基础上还设置了两种特殊情况：

• class_0 采用 post/wait 机制，不受 yield_count 、 sleep0~sleep7 影响；
• 对于 share 模式的 latch ，申请 s 时如果有冲突直接进入后继的 sleep 或者 post/wait 机制，不进行 spin 。当然如果申请 x 有冲突，仍然按照正常的流程来走（即有 spin ）。因此，对于 share 模式的 latch ， x 是优先的；

下面来看class_0的post/wait机制。当申请latch（class属性等于0）时，如果有冲突，首先按照class_0定义的spin_count和yield_count调用sskglspin。如果仍然无法获得latch，则进入post/wait机制（而不是sleep机制），post/wait机制因SHR属性有所不同：

• Exclusive 模式：调用 kslwlmod 函数将自己加入到该 latch 的 wait_list 中，然后调用 sskgslgf 再次尝试获取本 latch ，如果仍然无法获取则调用 semop 进入后台等待；
• Share 模式：调用 kslwlmod 函数将自己加入到该 latch 的 wait_list 中，然后再进行一轮 spin ，尝试获取本 latch ，如果仍然无法获取则调用 semop 进入后台等待；

Share模式下的差别仍然是让x优先获得锁。当前进程因为latch冲突调用semop进入后台等待后将一直等待，直至latch持有进程在释放latch时通过semaphore唤醒该进程。在早期版本，因为系统不够健壮，此处是进程夯住的主要原因，可通过_enable_reliable_latch_wait参数系统调用semtimedop以替代semop，前者有0.3秒的超时时间，从而保证阻塞的后台进程可以醒来。可见，class_0的latch综合运用了spinlock、semaphore等多种措施以获得最优的同步与互斥效果。最后讨论一下latch的最核心问题，Oracle版的spinlock是如何实现的。

表5.4-3 关键操作的时间对比

如表5.4-3所示，spin的时间成本低于OS上下文切换的时间成本，再加上wait_list的管理，spin成本是远低于post/wait机制的，所以latch在前期采用spin机制是非常合适的。Oracle Latch的spin机制基本一致，不过底层调用的原子函数略有不同：

• Exclusive 模式：因为不区分 x 和 s ，逻辑简单，所以采用 TAS 原子操作，即调用 xchg 函数；
• Share 模式：需要区分 x 和 s ，所以采用 CAS 原子操作，即调用 cmpxchg 函数；

至于spin的实现则采用TTS和Intel的Pause指令以达到最优的效果（等价于Linux采用的rep;nop）。TTS的核心思路是在TAS或CAS等原子操作前先进行非原子的判断，如果非原子判断发现latch可用，再进行TAS或CAS原子操作，从而解决频繁原子操作导致频繁锁总线和缓存失效问题，降低原子操作带来的高成本。

Latch布局

表5.4-4 Oracle常见Latch

在Oracle 11g版本中有550+个latch，表5.4-4给出了一些常见的latch。系统启动时会在SGA中生成这些latch，其中除“process allocation latch”以外其它latch默认都是class_0。

图5.4-3 进程与SGA中Latch的关系

如图5.4-3所示，Oracle启动后会在SGA中生成所有的latch，进程在执行过程中会在自己的内存区域中记录已经持有或者申请中的latch。Latch是多进程共同使用的，当某些进程异常退出就会导致其持有的latch异常。正常进程在spin latch一定次数仍然无法获得该latch时会发送消息给PMON进程，让PMON进程检查该latch的持有者是否异常。PMON进程会检查该latch，如果发现该latch的持有者进程异常，就会启动修复机制。Latch持有进程异常退出时，很可能该latch保护的临界区是异常（即部分修改），PMON进程根据该latch的recovery区域中记录的日志修改临界区，重置latch状态，并唤醒该latch的阻塞进程。

Mutex

Oracle从10g版本开始引入mutex，作为一个比latch更加轻量的同步与互斥机制，在某些场景下替代latch。Mutex的轻量首先体现在：

• 获取 1 个 mutex 一般需要 30~35 个指令，而获取 1 个 latch 一般需要 150~200 个指令；
• Mutex 结构占用大约 16 个字节，而 latch 结构占用大约 100 个字节；

由于mutex的设计目标是更加轻量，系统启动时不会在SGA中生成所有的mutex对象，mutex一般包含在被保护的数据结构中，和被保护的数据结构一起动态生成。Mutex结构主要包含如下内容：

• Mutex value ： mutex 的核心变量，高位的 2 个字节存放 holding SID ，地位的 2 个字节存放 reference count （ 64 位系统分别为高位 4 个字节和低位 4 个字节）；
• GETS ：请求本 mutex 的次数统计；
• SLEEPS ：请求本 mutex 的 sleep 次数统计；
• OP ：当前的 mutex 操作；

Mutex支持X（eXclusive）和S（Share）两种方式申请。Mutex一旦被以X模式持有，那么本mutex是独占的，其它session必须等待。Mutex如果是以S模式持有，那么本mutex是共享的，其它session可以以S方式申请并持有，但如果以X方式申请则需要等待。实际上，mutex可能有如下四种状态：

• S ：当前以共享方式被某些 session 持有，此时 holding SID 等于 0 ， reference count 等于当前以共享方式持有本 mutex 的 session 数量；
• X ：当前以独占方式被某 session 持有，此时 holding SID 等于持有者 SID ， reference count 等于 0 ；
• E ：检查模式（ Examine ）， mutex value 的调整是通过原子操作进行的，同时只能有一个 session 进入 E 状态进行调整；
• N ：空闲，本 mutex 没有被任何 session 持有；

Mutex和latch同步互斥机制一样，都是基于spin机制，并在此基础上综合运用sched_yield、select（sleep）等机制。不同的是mutex的设计初衷是更加轻量，所以考虑运用post/wait机制（semaphore）。Latch通过class定义spin、sched_yield、select之间的比例，并且每个latch可以设置不同的class。Mutex则通过_mutex_wait_scheme定义spin、sched_yield、select之间的比例，并且是全局的。

_mutex_wait_scheme大于2时，mutex的行为和10g的行为非常类似（Oracle 11g对mutex做了大量调整），采用了激进的获取方式，执行序列为：

64K次spin;sched_yield;64K次spin;sched_yield;64K次spin;sched_yield;......

上述执行模式下，mutex一直尝试获取，中间间或提供机会让出CPU给优先级相等或者更高的繁忙任务。此时可以最快地获取mutex，但会非常消耗CPU（某颗核可能是100%）。但如果系统确实非常繁忙，sched_yield会让出CPU。

_mutex_wait_scheme等于2是Oracle的默认设置，mutex的执行序列如下：

spin;sched_yield;spin;sched_yield;spin;select;spin;select;spin;select;spin;select;......

上述执行模式下，前两个spin周期内会调用sched_yield，后面都调用select进行sleep，sleep的时间以10ms为起点进行指数退避（Exponential Backoff），最大时间由参数_mutex_wait_time定义。当然如果_mutex_wait_time设置得过小，指数增长效果不明显。例如默认情况下_mutex_wait_time等于1ms，指数退避显现不出来。

_mutex_wait_scheme等于1时，mutex的执行序列如下：

spin;sched_yield;spin;select;spin;select;spin;select;spin;select;spin;select;......

上述执行模式下，第一个spin周期会调用sched_yield，后面都调用select进行sleep，且sleep的时间是固定的，就是_mutex_wait_time定义的时间。

当_mutex_wait_scheme等于0时，mutex的行为是灵活的，可以进行非常多样化的定义。定义的参数包括_wait_yield_sleep_time_msecs、_wait_yield_mode、_wait_yield_hp_mode、_wait_yield_sleep_freq、_wait_yield_yield。Mutex的行为实际上就是spin序列，两个spin之间要么调用select，要么调用sched_yield，上述参数就是定义select和sched_yield之间的比例。总的来说，可以通过_wait_yield_mode设置两种模式：

• yield 模式：以 sched_yield 为主，每 _wait_yield_sleep_freq-1 次 sched_yield 就有 1 次 select ， select 时间由 _wait_yield_sleep_time_msecs 定义；
• sleep 模式：以 select 为主，每 _wait_yield_yield_freq-1 次 select 就有 1 次 sched_yield ， select 时间同样由 _wait_yield_sleep_time_msecs 定义；

_wait_yield_hp_mode的取值范围和_wait_yield_mode一样，只是将高优先级session获取的mutex行为单独定义，从而合理地定义高优先级进程和低优先级进程之间的mutex竞争。

表5.4-5 关键操作的时间对比

至于spin内，操作mutex value的次数则由_mutex_spin_count定义，默认为255次。由于mutex是区分读写的，所以spin过程是对mutex value采用CAS原子操作。当然了为了降低锁总线和缓存失效带来的性能影响，mutex和latch一样，也采用了TTS设计思路，即首先采用非原子操作，确认后在采用原子操作。如表5.4-5所示，mutex的持有时间要比latch小，所以采用更加轻量的策略是合适的。

表5.4-6 Oracle常见Mutex

图5.4-4 会话与Mutex的关系

常见的mutex如表5.4-6所示，library cache、bucket等mutex用于保护KGL lock和library cache中的hash结构。Cursor parent、hash table等mutex则保护解析或者重载过程中的parent cursor。Cursor pin用于对library cache中的对象（如child cursor）做pin计数器，从而防止这些对象从share pool中老化移出。

从申请者和内存布局的角度来看mutex和latch也有很大的不同的。如图5.4-4所示，mutex不是在SGA中全局申请的，而是嵌在被保护的对象中，和被保护对象一起申请的。Latch是由进程申请的，而mutex是由session申请的。Latch的recovery区保存在latch的结构中，而mutex的recovery区不在mutex结构中，而是在独立的atomic operation logs区域中。

MySQL设计原理

Mutex

表5.5-1 ib_mutex_t结构

MySQL的mutex是一个互斥型的同步机制，不区分读和写。一个mutex对应于一个ib_mutex_t结构，ib_mutex_t结构的详细情况如表5.5-1所示，其中关键的信息有：

• lock_word ： mutex 的核心变量，通过对该变量进行 TAS 原子操作从而获得互斥能力， 0 表示空闲，非 0 表示已经被持有；
• event ：当进行多次尝试后仍然获取不到本 mutex ，线程将阻塞在 event 中的条件变量上，等待本 mutex 的持有者线程唤醒；
• list ：系统中所有 mutex 都通过全局变量 mutex_list 管理起来，即通过 mutex_list 以及各 mutex 中的 list 变量组建一个 mutex 的双向链表；

Mutex提供的相关函数主要有：

• mutex_create_func ：创建一个 mutex 互斥对象；
• mutex_free_func ：销毁一个 mutex 互斥对象；
• mutex_enter_func ：申请占用某个 mutex 互斥对象；
• mutex_enter_nowait_func ：申请占用某个 mutex 互斥对象，但不会被阻塞，申请不到立刻退出；
• mutex_exit_func ：是否已经持有的某个 mutex 互斥对象；

图5.5-1 mutex_enter_func示例代码

void mutex_enter_func(ib_mutex_t *mutex)

{

if(0==_sync_lock_test_and_set(mutex->lock_word, 1)){

//get mutex successfully

return;

}

Loop:

while(0!=mutex->lock_word && i<srv_n_spin_wait_rounds){

ut_delay(0, srv_spin_wait_delay);

i++;

}

if(i>=srv_n_spin_wait_rounds) sched_yield();

if(0==_sync_lock_test_set(mutex->lock_word, 1)){

//get mutex successfully

return;

}

if(i<srv_n_spin_wait_rounds) goto Loop;

mutex->waiters=1;

for(j=0;j<4;j++){

if(0==_sync_lock_test_set(mutex->lock_word, 1)){

//get mutex successfully

return;

}

}

sync_arrary_wait_event();

}

图5.5-1是mutex_enter_func的伪代码，其实现的过程大致如下（简化了跨平台等不相关问题）：

• step1 ：调用 posix 接口原子函数 _sync_lock_test_and_set ，如果获得 lock_word ，即原来为 0 ，并原子性地将其改为 1 ，表示成功获得本 mutex ，直接退出；
• step2 ：对 lock_word 做 srv_n_spin_wait_rounds 次 spin 操作（默认 30 次），检查是否可以获得 lock_word ：
  • Spin 期间，并没有采用原子操作，属于 TTS 方案，规避了锁总线和缓存失效带来的性能下降问题；
  • 每次 spin 都进行一次 ut_delay ，延迟时间在 0 到 srv_spin_wait_delay （默认 6 微秒）之间随机，其实现方法最终调用的是 CPU 的 pause 或者 rep;nop 指令，时间只是近似值；
  • 如果 lock_word 满足条件，跳出 spin 循环，并调用 _sync_lock_test_and_+set 获取锁，获得则成功；
• step3 ：循环 srv_n_spin_wait_rounds 次仍然无法获得 mutex ，调用 sched_yield 让出 CPU 给其它优先级相等或者更高的任务；
• step4 ：调用 sync_array_wait_event 将自己阻塞在 event 对应的条件变量上，不过在阻塞前还会再尝试 4 次原子操作，以尽最后努力获得 mutex ；

可见，mutex_enter_func的执行序列是立刻获得;spin;sched_yield;再尝试4次;wait。而mutex_enter_nowait_func更加简单，直接通过_sync_lock_test_and_set进行一次立刻获取，获得则成功，否则失败，不会进行任何spin或者阻塞等动作。

Mutex_exit_func首先调用_sync_lock_test_and_set将lock_word置为0。如果有线程有阻塞在本mutex上（此时waiters等于1），调用pthread_cond_broadcast唤醒相关线程。从mutex的申请和释放来看，mutex有如下特点：

• 争抢是随机的，各线程争抢 lock_word 不进行任何排队；
• 争抢是不公平的，体现在两个方面，其一是 CPU 间不公平，更接近释放者的 CPU 更易于获得，其二释放期间新申请的线程比阻塞线程更易获得；
• 有大量线程阻塞在条件变量时，一旦持有者释放，这些线程同时被唤醒，进行新一轮争抢；

表5.5-2 MySQL常见Mutex

MySQL中常见mutex如表5.5-2所示，这些mutex对象大部分是嵌入在对象的内部数据结构中（也有一些全局mutex对象），同时又通过全局变量mutex_list将所有mutex对象管理起来，至于mutex的种类可以通过全局变量all_innodb_mutexes查看。

RW-Lock

表5.5-3 rw_lock_t结构

MySQL的Rw_lock和mutex类似，只是在mutex的基础上进一步区分了读和写（即X和S），S与S兼容，X与S、X与X不兼容（同一个线程递归申请X Lock除外）。一个rw_lock对应于一个rw_lock_t结构，rw_lock_t结构的详细情况如表5.5-3所示，其中的关键信息有：

• lock_word ： rw_lock 的核心变量，通过对该变量进行 CAS 原子操作从而获得互斥能力：
  • lock_word=0x00100000 ：空闲，没有 S lock ，也没有 X lock ；
  • 0<lock_word<0x00100000 ：已经被线程以 S 方式持有，每获得一次 S lock ， lock_word 减一；
  • lock_word=0 ：已经被线程以 X 方式持有；
  • -0x00100000<lock_word<0 ： X lock 已经被锁定，但尚未被持有，正在等待各线程释放 S lock ；
  • lock_word=-0x00100000 ： X lock 已经被持有，且被递归调用一次；
  • lock_word<-0x00100000 ： X lock 已经被持有，且被递归调用多次，每递归一次减一；
• event 、 wait_ex_event ：当进行多次尝试后仍然获取不到本 rw_lock ，线程将阻塞在 event 对应的条件变量上，等待本 rw_lock 的持有者线程唤醒， event 和 wait_ex_event 分别对应读线程（以 S 方式申请本 rw_lock 的线程）和写线程（以 X 方式申请本 rw_lock 的线程）；
• list ：系统中所有 rw_lock 都通过全局变量 rw_lock_list 进行管理，即通过 rw_lock_list 构建一个 rw_lock 的双向链表；

Rw_lock的相关函数主要有：

• rw_lock_create_func ：创建一个 rw_lock 互斥对象；
• rw_lock_free_func ：销毁一个 rw_lock 互斥对象；
• rw_lock_s_lock_func ：申请以 S 方式占用某个 rw_lock 互斥对象；
• rw_lock_x_lock_func ：申请以 X 方式占用某个 rw_lock 互斥对象；
• rw_lock_x_lock_func_nowait ：申请以 X 方式占用某个 rw_lock 互斥对象，但不会阻塞，申请不到立刻退出；
• rw_lock_s_unlock_func ：释放已经持有的 S 占用；
• rw_lock_x_unlock_func ：释放已经持有的 X 占用；

图5.5-2 rw_lock_s_lock_func示例代码

void rw_lock_s_lock_func(rw_lock_t *lock)

{

local_lock_word=lock->lock_word;

while(local_lock_word>0){

if(_sync_bool_compare_and_swap(&lock->lock_word,local_lock_word,

local_lock_word-1)){

//get s rw_lock successfully

return;

}

local_lock_word=lock->lock_word;

}

Loop:

while(lock->lock_word<0 && i<srv_n_spin_wait_rounds){

ut_delay(0, srv_spin_wait_delay);

i++;

}

if(i>=srv_n_spin_wait_rounds) sched_yield();

local_lock_word=lock->lock_word;

while(local_lock_word>0){

if(_sync_bool_compare_and_swap(&lock->lock_word,local_lock_word,

Local_lock_word-1)){

//get s rw_lock successfully

return;

}

local_lock_word=lock->lock_word;

}

if(i<srv_n_spin_wait_rounds) goto Loop;

lock->waiters=1;

local_lock_word=lock->lock_word;

while(local_lock_word>0){

if(_sync_bool_compare_and_swap(&lock->lock_word,local_lock_word,

Local_lock_word-1)){

//get s rw_lock successfully

return;

}

local_lock_word=lock->lock_word;

}

sync_arrary_wait_event();

}

图5.5-2是rw_lock_s_lock_func的伪代码，其实现的过程大致如下（简化了跨平台等不相关问题）：

• step1 ：调用 posix 接口原子函数 _sync_bool_compare_and_swap ，如果 lock_word 大于 0 意味着可以以 S 方式获取该 lock ，原子性地减 1 ，一旦成功表示获取 S lock 成功，直接退出；
• step2 ：对 lock_word 做 srv_n_spin_wait_rounds 次 spin 操作（默认 30 次），检查是否可以获得 lock_word ：
  • lock_word 大于 0 表示 lock 没有被其它线程以 X 方式持有，也没有线程正在申请 X lock ，最大取值 0x00100000 （ X_LOCK_DECR ）意味着同时最大允许 1,048,575 个线程同时获得 S lock ；
  • spin 期间没有采用原子操作，属于 TTS 方案，规避了频繁锁总线和缓存失效带来的性能下降问题；
  • 每次 spin 都进行一次 ut_delay ，延迟时间在 0 到 srv_spin_wait_delay （默认 6 微秒）之间随机，其实现方法最终调用的 CPU pause 或 rep;nop 指令，时间只是近似值；
  • 如果 lock_word 满足条件，跳出 spin 循环，并调用 _sync_bool_compare_and_swap 获取锁，获得则成功退出；
• step3 ：循环 srv_n_spin_wait_rounds 次仍然无法获得 lock ，调用 sched_yield 让出 CPU 给优先级相等或者更高的繁忙任务；
• step4 ：调用 sync_array_wait_event 将自己阻塞在 event 对应的条件变量上，不过在阻塞前再做一次原子操作，最后尝试获得 lock ；

可见，rw_lock_s_lock_func的执行序列为尝试立刻获取;spin;sched_yield;尝试立刻获取;wait。

图5.5-3 rw_lock_x_lock_func示例代码

void rw_lock_s_lock_func(rw_lock_t *lock)

{

Loop:

local_lock_word=lock->lock_word;

while(local_lock_word>0){

if(_sync_bool_compare_and_swap(&lock->lock_word,local_lock_word,

local_lock_word-0x00100000)){

//get x rw_lock successfully

goto Wait;

}

local_lock_word=lock->lock_word;

}

while(lock->lock_word<=0 && i<srv_n_spin_wait_rounds){

ut_delay(0, srv_spin_wait_delay);

i++;

}

if(i>=srv_n_spin_wait_rounds){

sched_yield();

}else{

goto Loop;

}

lock->waiters=1;

local_lock_word=lock->lock_word;

while(local_lock_word>0){

if(_sync_bool_compare_and_swap(&lock->lock_word,local_lock_word,

Local_lock_word-0x00100000)){

//get x rw_lock successfully

goto Wait;

}

local_lock_word=lock->lock_word;

}

sync_arrary_wait_event();

goto Loop;

Wait:

while(lock->lock_word<0 && i<srv_n_spin_wait_rounds){

ut_delay(0,srv_spin_wait_delay);

i++;

}

if(lock->lock_word<0){ 

sync_array_wait_event();

goto Wait;

}

}

图5.5-3是rw_lock_x_lock_func的伪代码，其实现的过程大致如下（简化了跨平台等不相关问题）：

• step1 ：调用 posix 接口原子函数 _sync_bool_compare_and_swap ，如果 lock_word 大于 0 意味着可以以 X 方式获取 lock （即当前既没有其它线程已经以 X 方式持有，也没有其它线程正在以 X 方式锁定），原子性地减 0x00100000 （ X_LOCK_DECR ），一旦成功表示锁定 X lock 成功，直接跳到 wait 步骤；
• step2 ：对 lock_word 做 srv_n_spin_wait_rounds 次 spin 操作（默认 30 次），检查是否可以获取 lock_word ：
  • lock_word 大于 0 表示 lock 没有被其它线程以 X 方式持有，也没有被其它线程以 X 方式锁定；
  • Spin 期间没有采用原子操作，属于 TTS 方案，规避了频繁锁总线和缓存失效带来的性能下降问题；
  • 每次 spin 都进行一次 ut_delay ，延时时间在 0 到 srv_spin_wait_delay （默认 6 微秒）之间随机，其实现方法最终调用的是 CPU 的 pause 或 rep;nop 指令，时间只是近似值；
  • 如果 lock_word 满足条件，跳出 spin 循环，并调用 _sync_bool_compare_and_swap 获取锁，成功获得则跳到 wait 步骤；
• step3 ：循环 srv_n_spin_wait_rounds 次仍然无法获得 lock ，调用 sched_yield 让出 CPU 给其它优先级相等或者更高的繁忙任务；
• step4 ：调用 sync_array_wait_event 将自己阻塞在 wait_ex_event 对应的条件变量上，不过在阻塞前在做一次原子操作，尝试获得 lock ；
• step5 ： wait 步骤，如果 lock_word 小于 0 表示其它线程持有的 S lock 尚未释放，循环 spin 等待，等待 srv_n_spin_wait_rounds 次。如果 spin 等待完成， S lock 仍然尚未释放，将自己阻塞在 wait_ex_event 对应的条件变量上，否则获取 X lock 成功；

Rw_lock_x_lock_func和rw_lock_s_lock_func的基本流程和原理是一致的，差别主要体现在如下几个方面：

• X 与 S 、 X 都是不兼容的，所以 X lock 一次性将 lock_word 减去 0x00100000 ；
• 锁定 X lock 后，并不能立刻返回，需要等待持有 S lock 的线程释放 S lock ，即需要等待 lock_word 等于 0 （不需要原子操作），可见 rw_lock 是 X 优先的；
• S lock 是在 event 对应的条件变量上等待，而 X lock 是在 wait_ex_event 的条件变量上等待，做这样的区分也是为了让 X 和 S 有不同的优先级（包括锁定态的 X lock ）；

Rw_lock_x_unlock_func和rw_lock_s_unlock_func分别用于释放X lock和S lock，基本流程和原理也是一致的，差别主要体现在如下几个方面：

• 两者都是调用原子函数 _sync_add_and_fetch 增加 lock_word ，不同的是 S lock 加 1 ，而 X lock 增加 0x00100000 ；
• 如果有 waiters 时， S lock 唤醒阻塞在 wait_ex_event 上的写线程， X lock 通知阻塞在 event 上的读线程；

从rw_lock的申请和释放来看，rw_lock有如下特点：

• X lock 的争抢是随机的，不公平的，各线程争抢 lock_word 不进行任何排队；
• X lock 和 S lock 同时争抢时， X lock 是优先的；
• X lock  和 S lock 的释放通知是轮流的，释放 X lock 会通知等待的 S lock 线程，释放 S lock 会通知等待的 X lock 线程；

表5.5-3 MySQL RW Lock保护的常见数据结构

MySQL中RW lock保护的常见数据结构如表5.5-3所示，rw_lock是嵌入在被保护对象的数据结构中的，同时又通过全局变量rw_lock_list将所有rw_lock组织成双向链表，从而统一管理。

PolicyMutex

MySQL从5.7版本开始对同步与互斥机制进行了重构，通过PolicyMutex定义了统一的访问接口，其实现部分同PolicyMutex的私有成员m_impl达成。M_impl是通过template实现的，具体有：

• TTASFutexMutex<GenericPolicy> FutexMutex ；
• TTASFutexMutex<BlockMutexPolicy> BlockFutexMutex ；
• TTASMutex<GenericPolicy> SpinMutex ；
• TTASMutex<BlockMutexPolicy> BlockSpinMutex ；
• OSTrackMutex<GenericPolicy> SysMutex ；
• OSTrackMutex<BlockMutexPolicy> BlockSysMutex ；
• TTASEventMutex<GenericPolicy> SyncArrayMutex ；
• TTASEventMutex<BlockMutexPolicy> BlockSyncArrayMutex ；

可见，有TTASFutexMutex、TTASMutex、OSTrackMutex、TTASEventMutex四种Mutex，GenericPolicy和BlockMutexPolicy两种Policy。Policy主要和跟踪相关，Mutex的行为区别如下：

• TTASFutexMutex ：首先通过 spin 与 CAS 检查锁状态，如果无法获得锁，则调用 futex 进行等待（实际上 Linux 的 mutex 在 spin 失败后也是通过调用 futex 进入等待状态的）；
• TTASMutex ：一直进行 spin 和 CAS ，直至成功获得锁；
• OSTrackMutex ：直接封装了 pthread_mutex ；
• TTASEventMutex ：通过 spin 与 CAS 检查锁状态，如果无法获得锁，调用条件变量进入等待状态（即 5.6 版本的 event ）；

总结与分析

仅仅依靠软件是无法建立同步与互斥能力的，必须要有硬件提供支撑。Intel CPU提供了TAS、CAS、LOCK等基础原子指令，操作系统、数据库都可以在此基础上构建自己的同步与互斥能力。不管是TAS、CAS还是LOCK，CPU底层的实现机制是一致的，都是通过锁总线或者锁Cache达成的。CPU一直在优化硬件层面的原子指令性能，但不管怎么优化其成本一般是普通指令的30~300倍，并且时延会随着CPU数量的增加进一步增加。

Linux操作系统在CPU指令基础上构建了大量的同步与互斥能力，包括posix和GCC两个版本的原子函数、spinlock、semaphore、mutex和RCU，尤其是spinlock和RCU在效率和公平性上做了大量优化。效率提升主要体现在区分场景和减少原子指令的调用上，从而在高竞争环境中也可以获得比较好的效果。然而Oracle、MySQL并没有直接使用这些能力，而是在原子函数、sched_yield、select（sleep）、semaphore、mutex（futex）基础上构建自己的同步与互斥能力，主要原因是：

• Linux 操作系统的上述能力也是在较长时间内逐步建立起来的， Oracle 、 MySQL 在设计时 Linux 的很多能力尚未具备；
• Oracle 、 MySQL 在同步与互斥能力上还需要解决可跟踪、可分析、可调优和可配置等一系列问题；
• Linux 的设计更加通用和基础，在高竞争场景下也有较好的性能表现， Oracle 、 MySQL 将同步与互斥机制用于保护临界资源，纯粹的同步互斥原语之间的竞争性相对较小；

在低竞争环境下的延时方面，Linux的spinlock、mutex、semaphore，Oracle的latch和mutex，MySQL的mutex、rw-lock都表现优越，都是通过一次原子操作获得互斥能力。不过Linux的mutex和semaphore由于涉及用户态和内核态的切换，成本相对较高。

在高竞争下的系统效率方面，Linux考虑得非常全面，mutex、semaphore直接进入阻塞态让出CPU，spinlock也延伸出大量的变种，从而解决各种场景下原子操作带来的性能降低。MySQL的mutex、rw-lock在进行简单地spin（默认30次）后进入阻塞态。Oracle更倾向于积极策略，latch在spin（默认20000）次之后才会进入阻塞态，而mutex更加激进，不会进入阻塞态，前几轮都是在spin（默认255次）和sched_yield之间来回切换，后期才会周期性调用sleep。可见，在纯互斥量的竞争环境下Linux、MySQL的系统资源利用率方面会更好，而Oracle更加积极，在获取时延方面会表现更优。哪种策略更合适，依赖于保护数据结构的粒度和竞争情况，两者是相辅相成的。

在公平性方面，Linux作为通用的操作系统，考虑的比较全面，而Oracle、MySQL在这方面基本没有考虑，或者考虑得比较少。

在可跟踪、可分析、可配置方面，Oracle是最优的。Oracle集成了大量的统计、跟踪能力，Latch做了大量的统计，并通过动态视图展示出来，同时通过level解决死锁问题，通过class还可以配置出非常丰富的竞争策略。MySQL次之，有简单的申请和wait统计，但配置是全局的。不过在MySQL5.7及后继版本中可跟踪性得到了一定程度的加强。Linux作为操作系统，通用性目的更强，可跟踪、可分析、可配置能力相对较弱。

最后在存储效率上，Linux同样由于通用性原因，存储空间的占用是最少的。Oracle提供了latch和mutex两种机制，前者较重，占用约100个字节，后者较轻，占用约16个字节。MySQL的mutex和rw-lock区别不大，占用60个字节左右。

PDF文档下载地址：http://blog.itpub.net/69912723/viewspace-2719232/