读写自旋锁详解，第 1 部分

 

     引用：http://www.ibm.com/developerworks/cn/linux/l-cn-rwspinlock1/index.html?ca=drs-

 

 

 

读写自旋锁简介

什么是读写自旋锁

自旋锁（Spinlock）是一种常用的互斥（Mutual Exclusion）同步原语（Synchronization Primitive），试图进入临界区（Critical Section）的线程使用忙等待（Busy Waiting）的方式检测锁的状态，若锁未被持有则尝试获取。这种忙等待的做法无谓地消耗了处理器资源，故而只适用于临界区非常短小的代码片段，例如 Linux 内核的中断处理函数。

由于互斥的特点，使用自旋锁的代码毫无线程并发性可言，多处理器系统的性能受到限制。通过观察线程在临界区的访问行为，我们发现有些线程只是简单地读取信息，并不修改任何东西，那么允许它们同时进入临界区不会有任何危险，反而能大大提高系统的并发性。这种将线程区分为读者和写者、多个读者允许同时访问共享资源、申请线程在等待期内依然使用忙等待方式的锁，我们称之为读写自旋锁（Reader-Writer Spinlock）。

读写自旋锁的属性

上面提及的共享资源可以是简单的单一变量或多个变量，也可以是像文件这样的复杂数据结构。为了防止错误地使用读写自旋锁而引发的 bug，我们假定每个共享资源关联一把唯一的读写自旋锁，线程只允许按照类似大象装冰箱的方式访问共享资源：

1. 申请锁。
2. 获得锁后，读写共享资源。
3. 释放锁。

有些用户态实现的读写锁支持线程在持有锁的情况下继续申请相同类型的锁，以及读者在持有锁的情况下变换身份成写者。这 2 个特性对于适用于短小临界区的读写自旋锁而言并无实际意义，因此本文不作讨论。

对于线程的执行，我们假设：

1. 系统存在一个全局时钟，我们讨论的时间是离散的，不是连续的、数学意义上的时间。
2. 任意时刻，系统中活跃线程的总数目是 有限的。
3. 线程的执行不会因为调度、缺页异常等原因无限期地被延迟。理论上，线程的执行可以被系统无限期地延迟，因此任何互斥算法都有死锁的危险。我们希望排除系统的干扰，集中关注算法及具体实现本身。
4. 线程对共享资源的访问在有限步骤内结束。
5. 当线程释放锁时，我们 希望：线程在有限步骤内释放锁。
6. 因为每个程序步骤花费有限时间，所以如果满足上述 5 个条件，那么：获得锁的线程必然在有限时间内将锁释放掉。

我们说某个读写自旋锁算法是正确的，是指该锁满足如下三个属性：

1. 互斥。任意时刻读者和写者不能同时访问共享资源（即获得锁）；任意时刻只能有至多一个写者访问共享资源。

2. 读者并发。在满足“互斥”的前提下，多个读者可以同时访问共享资源。

3. 无死锁（Freedom from Deadlock）。如果线程 A 试图获取锁，那么某个线程必将获得锁，这个线程可能是 A 自己；如果线程 A 试图但是却永远没有获得锁，那么某个或某些线程必定无限次地获得锁。

读写自旋锁主要用于比较短小的代码片段，线程等待期间不应该进入睡眠状态，因为睡眠 / 唤醒操作相当耗时，大大延长了获得锁的等待时间，所以我们要求：

4. 忙等待。申请锁的线程必须不断地查询是否发生退出等待的事件，不能进入睡眠状态。这个要求只是描述线程执行锁申请操作未成功时的行为，并不涉及锁自身的正确性。

“无死锁”属性告诉我们，从全局来看一定会有申请线程获得锁，但对于某个或某些申请线程而言，它们可能永远无法获得锁，这种现象称为饥饿（Starvation）。一种原因源于计算机体系结构的特点：例如在使用基于单一共享变量的读写自旋锁的多核系统中，如果锁的持有者 A 所处的处理器和等待者 B 所处的处理器相邻（也许还能共享二级缓存），B 更容易获知锁被释放，增大获得锁的几率，而距离较远的处理器上的线程则难与之 PK，导致饥饿的发生。还有一种原因源于设计策略，即读写自旋锁刻意偏好某类角色的线程。

为了提高并发性，读写自旋锁可以选择偏好读者，即读者能够优先获得锁：

1. 读者优先（Reader Preference）。如果锁被读者持有，那么新来的读者可以立即获得锁，无需忙等待。至于当锁被“写者持有”或“未被持有”时，新来的读者是否可以“夹塞”到正在等待的写者之前，依赖于具体实现。

如果读者持续不断地到来，等待的写者很可能永远无法获得锁，导致饥饿。在现实中，写者的数目一般较读者少许多，而且到来的频率很低，因此读写自旋锁可以选择偏好写者来有效地缓解饥饿现象：

2. 写者优先（Writer Preference）。写者必须在后到的读者 / 写者之前获得锁。因为在写者之前到来的等待线程数目是有限的，所以可以保证写者的等待时间有个合理的上界。但是多个读者之间获得锁的顺序不确定，且先到的读者不一定能在后到的写者之前获得锁。可见，如果写者持续到来，读者仍然可能产生饥饿。

为了彻底消除饥饿现象，完美的读写自旋锁还需满足下面任一属性：

3. 无饥饿（Freedom from Starvation）。如果线程 A 试图获取锁，那么 A 必定能在有限时间内获得锁。当然，这个“有限时间”也许相当漫长。

4. 公平（Fairness）。我们把“锁申请”操作的执行分为两个阶段：准备阶段（Doorway Section），能在有限程序步骤结束；等待阶段（Waiting Section），也许永远无法结束等待阶段一旦结束，线程即获得读写自旋锁。如果线程 A 和 B 同时申请锁，但是 A 的等待阶段完成于 B 之前，那么公平读写自旋锁保证 A 在 B 之前获得锁。如果 A 和 B 的等待阶段在时间上有重叠，那么它们获得锁的顺序是不确定的（在第二章中我们彻底取消“重叠”概念）。

“公平”意味着申请锁的线程必定在有限时间内获得锁。若不然，假设 A 申请一个公平读写自旋锁但是永远不能获得，那么在 A 之后完成准备阶段的线程显然也永远不能获得锁。而在 A 之前或“重叠”地完成等待阶段的申请线程数目是 有限的，可见必然发生了“死锁”，矛盾。同时这也说明释放锁的时间也是有限的。使用公平读写自旋锁杜绝了饥饿现象的发生，如果假定线程访问共享资源和释放锁的时间有一个合理的上界，那么锁申请线程的等待时间只与前面等待的线程数目有关，不依赖其它因素。

以自动机的观点看读写自旋锁

上章关于读写自旋锁的定义和描述虽然通俗易懂，但是并不精确，很多细节比较含糊。例如，读者和写者这种角色到底是什么含义？“先来”，“后到”，“新来”以及“同时到来”如何界定？申请和释放锁的过程到底是怎样的？

现在，我们集中精力思考一下读写自旋锁到底是什么东西？读写自旋锁其实就是一个有限状态自动机（Finite State Machine）。自动机模型是一种强大的武器，可以帮助我们精确描述和理解各种算法。在给出严格定义之前，我们先规范一下上节中出现的各种概念：

1. 首先，我们把读写自旋锁看成一个独立的 串行系统，线程对锁函数的调用本质上是向其独立地提交操作（Operation）。操作必须是基本的，语义清晰的。所谓“基本”，是指任一种类操作的执行效果都不能由其它一种或多种操作的执行累积而成。

2. 读写自旋锁的函数调用的全过程现在可以建模为：线程提交了一个操作，然后等待读写自旋锁在某个时刻选择并执行该操作。我们举个读者申请锁的例子来具体说明。前面提到申请锁分成两个阶段，其中准备阶段我们认为线程向读写自旋锁提交了一个“读者申请”的操作。读者在等待阶段不停地测试锁的最新状态，其实就是在等待读写自旋锁的选择。最终读者在被许可的情况下“原子地”更新锁的状态，从而获得锁，说明读写自旋锁在某个合适的时刻选择并执行了该“读者申请”的操作。一旦某个操作被选中，它将不受干扰地在有限时间内成功完成并且在执行过程中读写自旋锁不能选择其它的操作。读者可能会有些奇怪，直观上锁的释放操作似乎是立即执行，难道也需要“等待”么？为了保证锁状态的一致性（Consistency），某些实现的释放函数使用了忙等待方式（参见本文的第一个实现），亦或由于调度、处理器相对速度等原因，总之锁的释放操作同样有一个不确定的等待执行的延时，因此可以和其它操作统一到相同的执行模型中。在操作成功提交至执行完毕这段时间内，线程不能睡眠。

3. 某个线程对锁的一次使用既可以用读者身份申请，也可以用写者身份申请，但是不能以两种身份同时申请。可见“角色”实质上是线程分别提交了“读者申请”或“写者申请”的操作，而不能提交类似“读者写者同时申请”的操作。

4. 读者 / 写者可以不停地到来 / 离去，这意味着线程能够持续地向读写自旋锁提交各种操作，但是每次只能提交一个。只有当上次提交的操作被执行后，线程才被允许提交新操作。读写自旋锁有能力知道某个操作是哪个线程提交的。

5. 线程对锁的使用必须采用前面提及的规范化流程，这是指线程必须提交配对的“申请”/“释放”操作，即“申请”操作成功执行后，线程应当在有限时间内提交相应的“释放”操作，且在此之前不准提交其它操作。

6. 关于读者 / 写者先来后到的顺序问题，我们转换成确定操作的提交顺序。我们认为操作的提交效果是“瞬间”产生的，即使多个线程在所谓的“同一时刻”提交操作，这些操作彼此之间也有严格的先后顺序，不存在两个或多个操作是“同时”提交成功的。在现实中，提交显然是需要一定时间的，不同线程的提交过程可能在时间上重叠，但是我们认为总可以按照一种策略规定它们的提交顺序，虽然这可能影响锁的实际执行过程，但并不影响正确性；对于同一线程提交的各个操作，它们彼此之间显然有着严格的时序关系，当然能够确定提交顺序。在此，我们彻底取消同时性的概念。令 A(t) 为在时间段 (0, t] 内所有提交的操作构成的集合，A(t) 中的任两个操作 o₁和 o₂，要么 o₁在 o₂之前提交，要么 o₁在 o₂之后提交，这种提交顺序是一种全序关系（Total Order）。

读写自旋锁的形式化定义是一个 6 元组（Q，O，T，S，q₀，q_f），其中：

1. Q = {q₀，q₁，…，q_n}，是一个有限集合，称为状态集。状态 q_i描述了读写自旋锁在某时刻 t₀所处于的一种真实状况。
2. O = {o₀，o₁，…，o_m}，是一个有限集合，称为操作种类集。
3. T：Q x O -> Q 是转移函数。T 是一个偏函数（Partial Function），即 T 的定义域是 Q x O 的子集。如果 T 在 (q, o) 有定义，即存在 q ’ = T(q, o)，我们称状态 q 允许操作 o，在状态 q 可以执行操作 o，成功完成后读写自旋锁转换到状态 q ’；反之，如果 T 在 (q, o) 没有定义，我们称状态 q 不允许操作 o，说明在状态 q 不能执行操作 o，例如在锁被写者持有时，不能选择 “读者申请获取锁”的操作。
4. S 是选择函数，从已提交但未执行的操作实例集合中选择一个让读写自旋锁执行，后文详细讨论。由于任意时刻活跃线程的总数目是有限的，这个集合必然是有限集，因此我们认为 S 的每一次选择能在有限步骤内结束。
5. q₀是初始状态。
6. q_f是结束状态，对于任一种操作 o，T 在 (q_f, o) 无定义。也就是说到达该状态后，读写自旋锁不再执行任何操作。

我们先画出与定义等价的状态图，然后描述 6 元组具体是什么。

图 1. 读写自旋锁的状态图
 

1. 状态图中的每个圆圈代表一个状态。状态集合 Q 至少应该有 3 个状态：“未被持有”，“读者持有”和“写者持有”。因为可能执行“析构”操作，所以还需要增加一个结束状态“停止”。除此之外不需要新的状态。
2. 有向边上的文字代表了一种操作。读写自旋锁需要 6 种操作： “初始化”，“析构”，“读者申请”， “读者释放”， “写者申请”和“写者释放”。操作后面括号内的文字，例如“最后持有者”，只是辅助理解，并不表示一种新的操作。
3. 有向边及其上的操作定义了转移函数。如果一条有向边从状态 q 射向 q ’，且标注的操作是 o，那么表明状态 q 允许 o，且 q ’ = T(q, o)。
4. 初始状态是“未被持有”。
5. 结束状态是“停止”，双圆圈表示，该状态不射出任何有向边，表明此后锁停止执行任何操作。

结合状态图，我们描述读写自旋锁的工作原理：

1. 我们规定在时刻 0 执行全局唯一一次的“初始化”操作，将锁置为初始状态“未被持有”，图中即为那条没有起点、标注“初始化“操作的有向边。如果决定停止使用读写自旋锁，则执行全局唯一一次的“析构”操作，将锁置为结束状态“停止”。

2. 读写自旋锁可以被看成一个从初始状态“未被持有”开始依次“吃”操作、不断转换状态的 串行机器。令 W(t) 为时间段 (0, t] 内已提交但未执行的操作构成的集合，W(t) 是 所有提交的操作集合 A(t) 的子集。在时刻 t，如果锁准备执行新的操作，假设当前处于状态 q，W(t) 不是空集且存在状态 q 允许的操作，那么读写自旋锁使用选择函数 S 在 W(t) 集合中选出一个来执行，执行完成后将自身状态置为 q ’ = T(q, o)。

3. 我们称序列 < q_I1，o_I1，q_I2，o_I2，…，o_In，q_I(n+1)> 是读写自旋锁在 t 时刻的执行序列，如果：

1.  
   1. o_Ik是操作，1 <= k <= (n + 1)。且 o_I1，o_I2，…，o_In属于集合 A(t)。
   2. q_Ik是状态，1 <= k <= (n + 1)。
   3. 读写自旋锁在 t 时刻的状态是 q_I(n+1)。
   4. q_I1= q₀。
   5. T 在 (q_Ik, o_Ik) 有定义，且 q_I(k+1)= T(q_Ik, o_Ik)（1 <= k <= n）。

3. 假如执行序列的最后一个状态 q_I(n+1)不是结束状态 q_f，且在时刻 t₀，W(t₀) 为空或者 q_I(n+1)不允许 W(t₀) 中的任一个操作 o，我们称读写自旋锁在时刻 t₀处于潜在死锁状态。这并不表明读写自旋锁真的死锁了，因为随后线程可以提交新的操作，使其继续工作下去。例如 q_I(n+1)是“写者持有”状态，而 W(t₀) 中全是“读者申请”的操作。但是我们知道锁的持有者一会定在 t₀之后的有限时间内提交“写者释放”操作，届时读写自旋锁可以选择执行它，将状态置为“未被持有”，而现存的“读者申请”的操作随后也可被执行了。

4. 如果存在 t₀> 0，且对于任意 t >= t₀，读写自旋锁在时刻 t 都处于潜在死锁状态，我们称读写自旋锁从时刻 t₀开始“死锁”。

以下是状态图正确性的证明概要：

1. 互斥。从图可知，状态“读者持有”只能转换到自身和“未被持有”，不能转换到“写者持有”，同时状态“写者持有”只能转换到“未被持有”，不能转换到“读者持有”，所以锁一旦被持有，另一种角色的线程只有等到“未被持有”的状态才有机会获得锁，因此读者和写者不可能同时获得锁。状态“写者持有”不允许“写者申请”操作，故而任何时刻只有至多一个写者获得锁。

2. 读者并发。状态“读者持有”允许“读者申请”操作，因此可以有多个读者同时持有锁。

3. 无死锁。证明依赖第一章中关于线程执行的 3 个假设。反证法，假设对任意 t >= t₀，锁在时刻 t 都处于潜在死锁状态。令 q 为 t₀时刻锁的状态，分 3 种情况讨论：

1.  
   1. “未被持有”。如果线程 A 在 t₁> t₀的时刻提交“读者申请”或“写者申请”的操作，那么锁在 t₁时刻并不处于潜在死锁状态。
   2. “读者持有”。持有者必须在某个 t₁> t₀的时刻提交“读者释放”的操作，那么锁在 t₁时刻并不处于潜在死锁状态。
   3. “写者持有”。持有者必须在某个 t₁> t₀的时刻提交“写者释放”的操作，那么锁在 t₁时刻并不处于潜在死锁状态。

从线程 A 申请锁的角度来看，由状态图知对于任意时刻 t₀，不论锁在 t₀的状态如何，总存在 t₁> t₀，锁在时刻 t₁必定处于“未被持有”的状态，那么在时刻 t₁允许锁申请操作，不是 A 就是别的线程获得锁。如果 A 永远不能获得锁，说明锁一旦处于“未被持有”的状态，就选择了别的线程提交的锁申请操作，那么某个或某些线程必然无限次地获得锁。

上面提到读写自旋锁有一种选择未执行的操作的能力，即选择函数 S，正是这个函数的差异，导致锁展现不同属性：

1. 读者优先。在任意时刻 t，如果锁处于状态“读者持有”，S 以大于 0 的概率选择一个尚未执行的“读者申请”操作。这意味着：首先，即使有先提交但尚未执行的“写者申请”操作，“读者申请”操作可以被优先执行；其次，没有刻意规定如何选“读者申请”操作，因此多个“读者申请”操作间的执行顺序是不确定的；最后，不排除连续选择“读者释放”操作，使得锁状态迅速变为“未被持有”，只不过这种几率很小。

2. 写者优先。在任意时刻 t，如果 o₁是尚未执行的“写者申请”操作，o₂是尚未执行的“读者申请”或“写者申请”操作，且 o₁在 o₂之前提交，那么 S 保证一定在 o₂之前选择 o₁。

3. 无饥饿。如果线程提交了操作 o，那么 S 必定在有限时间内选择 o。即存在时刻 t，读写自旋锁在 t 的执行序列 < q_I1，o_I1，q_I2，o_I2，…，o_In，q_I(n+1)> 满足 o = o_In。狭义上， o 限定为“读者申请”或“写者申请”操作。

4. 公平。如果操作 o₁在 o₂之前提交，那么 S 保证一定在在 o₂之前选择执行 o₁。狭义上，o₁和 o₂限定为“读者申请”或“写者申请”操作。

读写自旋锁的实现细节

上节阐述的自动机模型是个抽象的机器，用于帮助我们理解读写自旋锁的工作原理，但是忽略了很多实现的关键细节：

1. 操作的执行者。如果按照上节的描述，为读写自旋锁创建专门的操作执行线程，那么锁的实际性能将会比较低下，因此我们要求申请线程自己执行提交的操作。

2. 操作类别的区分。可以提供多个调用接口来区分不同种类的操作，避免使用额外变量存放类别信息。

3. 确定操作的提交顺序，即线程的到来的先后关系。写者优先和公平读写自旋锁需要这个信息。可以有 3 种方法：

1.  
   1. 假定系统有一个非常精确的实时时钟，线程到来的时刻用于确定顺序。但是寻找直接后继者比较困难，因为事先无法预知线程到来的精确时间。
   2. 参考银行的做法，即每个到来的线程领取一张号码牌，号码的大小决定先后关系。
   3. 将线程组织成一个先进先出（FIFO）的队列，具体实现可以使用单向链表，双向链表等。

4. 在状态 q，确定操作（线程）是否被允许执行。这有 2 个条件：首先 q 必须允许该操作；其次对于写者优先和公平读写自旋锁，不存在先提交但尚未执行的写者（读者 / 写者）申请操作。可以有 3 种方法：

1.  
   1. 不停地主动查询这 2 个条件。
   2. 被动等待前一个执行线程通知。
   3. 主动 / 被动相结合。

5. 选择执行的线程。在状态 q，如果存在多个被允许执行的线程，那么它们必须达成一致（Consensus），保证只有一个线程执行成功，否则会破坏锁状态的一致性。有 2 种简单方法：

1.  
   1. 互斥执行。原子指令（总线级别的互斥），或使用锁（高级互斥原语）。
   2. 投机执行。线程不管三七二十一先执行再说，然后检查是否成功。如果不成功，可能需要执行回滚操作。

6. 因为多个读者可以同时持有锁，那么读者释放锁时，有可能需要知道自己是不是最后一个持有者（例如通知后面的写者）。一个简单的方法是用共享计数器保存当前持有锁的读者数目。如果我们对具体数目并不关心，只是想知道计数器是大于 0 还是等于 0，那么用一种称为“非零指示器”（Non-Zero Indicator）的数据结构效果更好。还可以使用双向链表等特殊数据结构。

本系列文章所论述的算法只关注共享内存的系统。相关代码全部用 C 语言编写，主要目的是为了印证读写自旋锁的原理，故而性能并非最优，有兴趣的读者朋友可以尝试用汇编语言改写。代码中出现的 atomic_t 数据结构，cpu_relax()、atomic_*() 等函数引自 Linux 内核 [1]。

 

读写自旋锁的接口

我们将操作种类集合的 6 种操作定义为各种读写自旋锁提供给用户调用的通用接口函数：

1. init_lock()，初始化锁。
2. destroy_lock()，析构锁。
3. reader_lock()，读者申请获取锁。
4. reader_unlock()，读者释放锁。
5. writer_lock()，写者申请获取锁。
6. writer_unlock()，写者释放锁。

一般而言，destroy_lock() 可以简单地将动态分配的锁结构释放掉，或调用 init_lock() 将锁的状态置为初始值；且在系统的存活期内，读写自旋锁不会被析构。所以在后续文章的代码中，我们没有附上 destroy_lock() 的实现。

 

结束语

本系列文章详细论述读写自旋锁的原理和实现，本文是其中的第一部分，以自动机的观点阐述读写自旋锁的原理。