读写自旋锁简介什么是读写自旋锁自旋锁（Spinlock）是一种常用的互斥（Mutual Exclusion）同步原语（Synchronization Primitive），试图进入临界区（Critical Section）的线程使用忙等待（Busy Waiting）的方式检测锁的状态，若锁未被持有则尝试获取。这种忙等待的做法无谓地消耗了处理器资源，故而只适用于临界区非常短小的代码片段，例如 Linux 内核的中断处理函数。
由于互斥的特点，使用自旋锁的代码毫无线程并发性可言，多处理器系统的性能受到限制。通过观察线程在临界区的访问行为，我们发现有些线程只是简单地读取信息，并不修改任何东西，那么允许它们同时进入临界区不会有任何危险，反而能大大提高系统的并发性。这种将线程区分为读者和写者、多个读者允许同时访问共享资源、申请线程在等待期内依然使用忙等待方式的锁，我们称之为读写自旋锁（Reader-Writer Spinlock）。
读写自旋锁的属性上面提及的共享资源可以是简单的单一变量或多个变量，也可以是像文件这样的复杂数据结构。为了防止错误地使用读写自旋锁而引发的 bug，我们假定每个共享资源关联一把唯一的读写自旋锁，线程只允许按照类似大象装冰箱的方式访问共享资源：
有些用户态实现的读写锁支持线程在持有锁的情况下继续申请相同类型的锁，以及读者在持有锁的情况下变换身份成写者。这 2 个特性对于适用于短小临界区的读写自旋锁而言并无实际意义，因此本文不作讨论。
对于线程的执行，我们假设：
- 系统存在一个全局时钟，我们讨论的时间是离散的，不是连续的、数学意义上的时间。
- 任意时刻，系统中活跃线程的总数目是 有限的。
- 线程的执行不会因为调度、缺页异常等原因无限期地被延迟。理论上，线程的执行可以被系统无限期地延迟，因此任何互斥算法都有死锁的危险。我们希望排除系统的干扰，集中关注算法及具体实现本身。
- 线程对共享资源的访问在有限步骤内结束。
- 当线程释放锁时，我们 希望：线程在有限步骤内释放锁。
- 因为每个程序步骤花费有限时间，所以如果满足上述 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) 中的任两个操作 o1和 o2，要么 o1在 o2之前提交，要么 o1在 o2之后提交，这种提交顺序是一种全序关系（Total Order）。 |
