xv6：一个简单的unix-like操作系统译文（七）

第七章 锁

大多数内核（包括 xv6）都会交错执行多个活动。产生交错执行的一个来源是多处理器硬件：具有多个 CPU 独立执行的计算机，例如 xv6 的 RISC-V。这些多个 CPU 共享物理 RAM，而 xv6 利用这种共享来维护所有 CPU 都会读写的内核数据结构。这种共享带来了这样的可能性：一个 CPU 在另一个 CPU 正在更新数据结构的过程中读取该结构，甚至多个 CPU 同时更新同一个数据结构；如果没有精心设计，这样的并行访问很可能导致错误结果或破坏数据结构。即使在单处理器上，内核也可能在多个线程之间切换 CPU，从而导致它们的执行被交错。最后，如果设备中断处理程序修改了与某些可被中断代码相同的数据，而中断恰好发生在不合适的时间，也可能破坏数据。 并发（concurrency） 一词指的是由于多处理器并行、线程切换或中断而导致的多个指令流交错执行的情况。

内核中充满了被并发访问的数据。例如，两个 CPU 可能同时调用 kalloc，从而并发地从空闲链表的表头弹出元素。内核设计者通常希望允许大量并发，因为并行性可以提升性能和响应能力。然而，这也意味着内核设计者必须在并发存在的情况下仍然确信代码的正确性。实现正确代码的方法有很多种，其中有些更容易推理。那些旨在在并发环境下保证正确性的策略，以及支持这些策略的抽象，被称为并发控制技术。

xv6 根据不同场景使用了多种并发控制技术；实际上还有更多可能的技术。本章聚焦于一种被广泛使用的技术：锁（lock）。锁提供互斥（mutual exclusion），确保在任意时刻只有一个 CPU 能持有该锁。如果程序员为每个共享数据项关联一把锁，并且在使用该数据项时始终持有相应的锁，那么该数据项在任意时刻只会被一个 CPU 使用。在这种情况下，我们说这把锁保护了该数据项。尽管锁是一种易于理解的并发控制机制，但它的缺点是可能限制性能，因为它会将并发操作串行化。

本章余下部分将解释 xv6 为什么需要锁、xv6 如何实现锁，以及它是如何使用锁的。

图 7.1：简化的 SMP 架构

竞态

作为一个需要锁的例子，考虑两个具有已退出子进程的进程，在两个不同的 CPU 上调用 wait 系统调用。wait 会释放子进程的内存。因此，在每个 CPU 上，内核都会调用 kfree 来释放子进程的内存页。内核分配器维护着一个空闲页链表：kalloc()（3027）从链表中弹出一个内存页，而 kfree()（3005）将一个页压入链表。为了获得最佳性能，我们可能希望这两个父进程的 kfree 能够并行执行，而不必彼此等待，但在 xv6 的 kfree 实现下，这样做并不正确。

图 7.1 更详细地说明了这种场景：空闲页的链表位于两个 CPU 共享的内存中，这两个 CPU 使用 加载（load） 和 存储（store） 指令来操作该链表。（实际上，处理器具有缓存，但从概念上看，多处理器系统的行为就像只有一个共享内存一样。）如果没有并发请求，你可能会如下实现一个链表的 push 操作：

struct element {
  int data;
  struct element *next;
};

struct element *list = 0;

void
push(int data)
{
  struct element *l;

  l = malloc(sizeof *l);
  l->data = data;
  l->next = list;
  list = l;
}

图 7.2：竞态示例

如果该实现单独执行，它是正确的。然而，当多个副本并发执行时，这段代码就不再正确。如果两个 CPU 同时执行 push，它们都可能在任何一个执行第 16 行之前执行到第 15 行（如图 7.1 所示），从而导致如图 7.2 所示的不正确结果。这样就会出现两个链表元素，它们的 next 都被设置为 list 之前的同一个值。当第 16 行对 list 的两次赋值发生时，第二次赋值会覆盖第一次；第一次赋值所涉及的元素将会丢失。

第 16 行发生的这种丢失更新（lost update）是一个竞态（race）的例子。竞态是指一个内存位置被并发访问，并且至少有一次访问是写操作。竞态通常是 bug 的标志，要么是丢失更新（如果访问是写），要么是读取了一个尚未完全更新的数据结构。竞态的结果取决于编译器生成的机器代码、两个 CPU 的执行时序，以及内存系统对内存操作的排序方式，这使得由竞态引发的错误难以复现和调试。例如，在调试 push 时加入打印语句，可能会改变执行时序，从而让竞态“消失”。

避免竞态的常用方法是使用锁。锁确保互斥，使得在 push 的敏感代码行中，任意时刻只有一个 CPU 能够执行；这使得上述场景不可能发生。对上述代码进行正确加锁，只需要增加几行代码（已高亮）：

struct element *list = 0;
struct lock listlock;

void
push(int data)
{
  struct element *l;
  l = malloc(sizeof *l);
  l->data = data;

  acquire(&listlock);
  l->next = list;
  list = l;
  release(&listlock);
}

acquire 与 release 之间的指令序列通常被称为临界区（critical section）。我们说这把锁保护了 list。

当我们说一把锁保护数据时，真正的含义是：这把锁保护着一组适用于该数据的不变式（invariants）。不变式是指在操作之间始终被维护的数据结构属性。通常，一个操作的正确行为依赖于在操作开始时不变式成立。操作过程中可能会暂时破坏不变式，但在结束前必须重新建立它们。例如，在链表示例中，不变式是：list 指向链表的第一个元素，并且每个元素的 next 字段指向下一个元素。push 的实现会暂时违反该不变式：在第 17 行中，l 指向下一个链表元素，但 list 还没有指向 l（在第 18 行重新建立）。我们之前分析的竞态正是因为第二个 CPU 在不变式被暂时破坏时，执行了依赖这些不变式的代码。正确使用锁可以确保在临界区内任意时刻只有一个 CPU 操作该数据结构，因此不会有 CPU 在数据结构不变式不成立时执行相关操作。

你可以把锁看作是将并发的临界区串行化，使它们一次只运行一个，从而保持不变式（前提是临界区在单独执行时是正确的）。你也可以认为，由同一把锁保护的临界区彼此之间是原子的（atomic）：每个临界区只会看到之前临界区的完整修改结果，而永远不会看到部分完成的更新。

尽管锁对正确性很有用，但它们天生会限制性能。例如，如果两个进程并发调用 kfree，锁会将这两个临界区串行化，从而无法从在不同 CPU 上运行中获得好处。我们称多个进程在同一时间需要同一把锁为冲突，或者说这把锁出现了竞争（contention）。内核设计中的一个主要挑战，是在追求并行性的同时避免锁竞争。xv6 在这方面做得不多，但更复杂的内核会专门组织数据结构和算法，以避免锁竞争。

在链表示例中，内核可能为每个 CPU 维护一个独立的空闲链表，只有当当前 CPU 的链表为空、必须从其他 CPU “窃取”内存时，才会访问其他 CPU 的空闲链表。其他使用场景可能需要更复杂的设计。

锁的放置位置对性能也很重要。例如，将 acquire 提前到 push 的第 13 行之前在语义上是正确的，但这很可能会降低性能，因为这样一来，对 malloc 的调用也会被串行化。下面的“使用锁”一节将提供一些关于在何处插入 acquire 和 release 的指导原则。

代码：锁

请阅读 kernel/spinlock.h 和 kernel/spinlock.c。

xv6 有两种类型的锁：自旋锁（spinlocks） 和 睡眠锁（sleep-locks）。我们先从自旋锁开始。xv6 使用 struct spinlock（1201）来表示一个自旋锁。该结构中最重要的字段是 locked，当锁可用时该字段为零，当锁被持有时为非零。从逻辑上讲，xv6 应该通过执行如下代码来获取一把锁：

void
acquire(struct spinlock *lk) // does not work!
{
  for(;;) {
    if(lk->locked == 0) {
      lk->locked = 1;
      break;
    }
  }
}

不幸的是，在多处理器系统上，这种实现并不能保证互斥。可能会发生这样的情况：两个 CPU 同时执行到第 25 行，看到 lk->locked 为零，然后都在第 26 行“获取”了这把锁。此时，两 个不同的 CPU 同时持有同一把锁，这违反了互斥性。我们需要一种方法，使第 25 行和第 26 行能够作为一个 原子（即不可分割） 的步骤来执行。

由于锁被广泛使用，多核处理器通常提供一条指令，用来使第 25 行和第 26 行的操作原子化。在 RISC-V 上，这条指令是 amoswap r, a。amoswap 会读取内存地址 a 处的值，将寄存器 r 的内容写入该地址，并把读取到的值放入 r。也就是说，它交换了寄存器和被寻址内存位置的内容。该指令使用特殊硬件来保证在读和写之间，没有其他 CPU 能够使用该内存地址，从而实现原子性。

可移植的 C 库调用 __sync_lock_test_and_set(addr, value) 会被编译为 amoswap 指令；该函数返回 *addr 原来的（被交换出来的）内容。下面是一种在 acquire 中编写循环的好方式：

while(__sync_lock_test_and_set(&lk->locked, 1) != 0)
  ;

xv6 的 acquire（1271）使用了上述循环。每一次迭代都会把 1 原子地交换到 lk->locked 中，并检查之前的值；如果之前的值是零，说明我们成功获取了锁，同时交换操作也把 lk->locked 设为 1。如果之前的值是 1，说明有其他 CPU 正在持有这把锁，而我们原子地将 1 写入 lk->locked 并不会改变它的值。

一旦锁被获取，acquire 会记录（用于调试）获取该锁的 CPU。lk->cpu 字段由这把锁保护，必须只在持有锁的情况下才能修改。

函数 release（1302）与 acquire 相反：它会清除 lk->cpu 字段，然后释放锁。从概念上讲，释放锁只需要将 lk->locked 赋值为零即可。然而，C 标准允许编译器使用多条存储指令来实现一次赋值，因此一次 C 赋值在并发代码看来可能是非原子的。因此，release 使用了 C 库函数 __sync_lock_release 来执行一次原子赋值。该函数同样会被编译为一条 RISC-V 的 amoswap 指令。

代码：使用锁

xv6 在很多地方使用锁来避免竞态。如前所述，kalloc（3027）和 kfree（3005）就是一个很好的例子。尝试练习 1 和练习 2，看看如果这些函数省略锁会发生什么。你很可能会发现，很难触发明显的错误行为，这表明可靠地测试代码是否没有锁错误和竞态是很困难的。xv6 很可能仍然存在尚未被发现的竞态。

使用锁的一个难点在于，决定使用多少把锁，以及每把锁应当保护哪些数据和不变式。这里有一些基本原则。首先，只要某个变量可能被一个 CPU 写入，同时被另一个 CPU 读取或写入，就应该使用锁来防止这两个操作重叠。其次，要记住锁保护的是不变式：如果一个不变式涉及多个内存位置，那么通常需要用同一把锁来保护所有这些位置，以确保该不变式得以维持。

上述规则说明了什么时候必须使用锁，但并没有说明什么时候不需要锁。而为了效率，避免过度加锁非常重要，因为锁会降低并行性。如果并行性并不重要，那么可以只安排一个线程运行，从而不必担心锁的问题。一个简单的内核可以在多处理器上采用这种方式：使用一把全局锁；每当从用户空间进入内核（系统调用或中断）时，内核就获取这把锁；当返回用户空间时释放这把锁。许多单处理器操作系统就是通过这种方法被移植到多处理器上的，这种方法有时被称为大内核锁（big kernel lock）。但这种方法牺牲了并行性：任意时刻只有一个 CPU 能在内核中执行。如果内核消耗了大量 CPU 时间，那么通过用不同的锁来保护不同的对象或模块，可以获得更多并行性，从而允许不同的 CPU 同时在内核的不同部分执行。

作为粗粒度锁的一个例子，xv6 的 kalloc.c 分配器只有一个空闲链表，并由一把锁来保护。如果多个 CPU 上的多个进程同时尝试分配页面，每个进程都必须在 acquire 中自旋等待轮到自己。自旋会浪费 CPU 时间，因为它并没有做有用的工作。如果锁竞争浪费了相当一部分 CPU 时间，那么可以通过改进分配器来提升性能，例如：为每个 CPU 维护一个独立的空闲链表，并为每个链表配备自己的锁，从而实现真正的并行分配。

作为细粒度锁的一个例子，xv6 为每个文件都设置了一把独立的锁，这样，操作不同文件的进程通常可以无需等待彼此的锁而继续执行。如果希望允许进程同时写入同一文件的不同区域，还可以将文件锁方案设计得更加细粒度。最终，锁粒度的选择需要同时基于性能测量和实现复杂度来决定。

后续章节在解释 xv6 各个组成部分时，将会提到 xv6 使用锁来处理并发的具体例子。作为预览，图 7.3 列出了 xv6 中的所有锁。

图 7.3：xv6 中的所有锁

死锁与锁顺序

假设在 CPU C1 和 C2 上运行的函数，都在某个时刻需要同时持有锁 A 和锁 B，但它们获取锁的顺序不同：

CPU C1            CPU C2
acquire(&A);      acquire(&B);
acquire(&B);      acquire(&A);
...               ...
release(&B);      release(&A);
release(&A);      release(&B);

如果运气不好，C1 和 C2 可能在完全相同的时刻执行各自的第一次 acquire；由于它们请求的是不同的锁，这两次操作都会成功。但接下来，在第二次调用 acquire() 时，C1 和 C2 都必须等待，因为它们需要的锁已经被对方持有。由于两个 CPU 都在等待对方释放锁，而双方都无法继续执行并释放锁，于是它们将永远等待下去。这种情况称为死锁（deadlock）。

C1/C2 示例中的关键问题在于：两个 CPU 以不同的顺序获取锁。如果它们都先尝试获取 A，那么其中一个 CPU 会先获取 A，再获取 B，随后释放这两把锁，之后另一个 CPU 就可以继续执行。更一般地说，为了避免死锁，加锁代码必须遵循以下规则：

所有在同一代码路径中持有多把锁的地方，必须以相同的顺序获取这些锁。

这种对全局锁获取顺序的要求，意味着锁实际上是每个函数规范的一部分：调用者必须以一种方式调用函数，使得锁按照约定的顺序被获取。

xv6 中存在许多长度为二的锁顺序链，尤其涉及每进程锁（每个 struct proc 中的锁），这源于 sleep 的实现方式（见第九章）。例如，consoleintr（7107）是处理键盘输入的中断例程。当收到换行符时，任何等待控制台输入的进程都应被唤醒。为此，consoleintr 在持有 cons.lock 的情况下调用 wakeup，而 wakeup 会获取等待进程的锁以唤醒它。由此，全局的死锁规避锁顺序中就包含这样一条规则：必须先获取 cons.lock，再获取任何进程锁。

文件系统代码包含了 xv6 中最长的锁链。例如，创建一个文件需要同时持有：目录的锁、新文件 inode 的锁、一个磁盘块缓冲区的锁、磁盘驱动的 vdisk_lock，以及调用进程的 p->lock。为了避免死锁，文件系统代码始终按照上一句话中提到的顺序来获取这些锁。

遵守全局的死锁规避顺序可能出乎意料地困难。有时，锁顺序会与程序的逻辑结构发生冲突，例如：模块 M1 调用模块 M2，但锁顺序却要求先获取 M2 中的锁，再获取 M1 中的锁。有时，锁的身份事先并不清楚，可能必须先持有一把锁，才能发现接下来要获取的是哪一把锁。这种情况出现在文件系统按路径名逐级查找组件时，也出现在 wait 和 exit 系统调用遍历进程表以寻找子进程的代码中。最后，死锁风险通常也会限制锁机制能够做到多细粒度：锁越多，发生死锁的机会往往也越多。避免死锁的需求，常常是内核实现中的一个主要制约因素。

有时会出现这样一个问题：如果一个 CPU 试图获取一把它已经持有的锁，会发生什么？ 一种观点认为这是允许的：既然没有其他 CPU 能持有这把锁，就无需担心对受保护数据的并发干扰。允许 CPU 重新获取自己已经持有的锁的锁系统被称为可重入（re-entrant）或递归锁（recursive）。另一方面，如果一把锁已经被持有，即使是在同一个 CPU 上，也意味着某个操作可能暂时破坏了某些不变式而尚未恢复；在不变式尚未成立的情况下允许新的操作开始，似乎是在主动引入 bug。xv6 采纳了后一种观点，禁止一个已经持有某把锁的 CPU 再次获取该锁。在 acquire 中调用 holding 的目的，正是为了检测这种情况。

锁与中断

xv6 的某些自旋锁保护的数据，既会被线程使用，也会被中断处理程序使用。例如，定时器中断处理程序 clockintr 可能会递增 ticks（3482），而与此同时，某个内核线程可能在 sys_pause（3836）中读取 ticks。锁 tickslock 用来串行化这两次访问。

自旋锁与中断的交互会带来一种潜在的危险。假设 sys_pause 持有了 tickslock，而它所在的 CPU 又被定时器中断打断。clockintr 会尝试获取 tickslock，发现该锁已被持有，于是等待其释放。但在这种情况下，tickslock 永远不会被释放：只有 sys_pause 能释放它，而 sys_pause 必须等 clockintr 返回后才能继续运行。于是该 CPU 会发生死锁，任何需要这把锁的代码也都会被冻结。

为了避免这种情况，如果某把自旋锁会被中断处理程序使用，那么 CPU 在持有该锁时，绝不能启用中断。xv6 的做法更加保守：当一个 CPU 获取任何锁时，xv6 都会在该 CPU 上禁用中断。中断仍然可以在其他 CPU 上发生，因此，中断处理程序在获取自旋锁时，可以等待某个线程释放锁——只是不能发生在同一个 CPU 上。

当一个 CPU 不再持有任何自旋锁时，xv6 会重新启用中断；为了应对嵌套的临界区，它需要进行一些记账工作。acquire 调用 push_off（1355），release 调用 pop_off（1369），用来跟踪当前 CPU 上锁的嵌套层数。当该计数降为零时，pop_off 会恢复在最外层临界区开始时的中断使能状态。intr_off 和 intr_on 函数分别执行 RISC-V 指令来禁用和启用中断。

acquire 必须在设置 lk->locked 之前严格地调用 push_off（1277）。如果顺序颠倒，就会出现一个短暂的窗口：锁已经被持有，但中断仍然处于启用状态；若在此时发生一次不幸的中断，系统就会死锁。类似地，release 只能在释放锁之后再调用 pop_off（1321），这一点同样至关重要。

指令与内存顺序

人们很自然地认为程序会按照源代码语句出现的顺序执行。对于单线程代码来说，这是一个合理的心智模型；但当多个线程通过共享内存进行交互时，这种模型就是不正确的。原因之一是，编译器可能会以不同于源代码所暗示的顺序发出加载（load）和存储（store）指令，甚至可能完全省略它们（例如，将数据缓存到寄存器中）。另一个原因是，CPU 可能会乱序执行指令以提高性能。例如，CPU 可能会发现，在一串顺序指令中，指令 A 和 B 彼此并不依赖，于是可能先开始执行指令 B，要么是因为 B 的输入比 A 更早准备好，要么是为了重叠 A 和 B 的执行。

作为一个可能出错的例子，考虑 push 的如下代码：如果编译器或 CPU 将第 4 行对应的存储操作移动到第 6 行 release 之后，那将是灾难性的：

l = malloc(sizeof *l);
l->data = data;
acquire(&listlock);
l->next = list;
list = l;
release(&listlock);

如果发生了这样的重排序，就会出现一个时间窗口：另一个 CPU 可以获取该锁并观察到已经更新的 list，但却看到一个尚未初始化的 list->next。

好消息是，编译器和 CPU 通过遵循一组称为内存模型的规则，并提供一些原语来帮助程序员控制重排序，从而为并发程序员提供了支持。

为了告知硬件和编译器不要进行重排序，xv6 在 acquire（1271）和 release（1302）中都使用了 __sync_synchronize()。__sync_synchronize() 是一个内存屏障（memory barrier）：它告诉编译器和 CPU，不要跨越该屏障对加载或存储操作进行重排序。xv6 在 acquire 和 release 中使用的屏障，在几乎所有重要场景下都能强制执行所需的顺序，因为 xv6 使用锁来保护对共享数据的访问。第十一章将讨论少数例外情况。

睡眠锁

有时 xv6 需要长时间持有一把锁。例如，文件系统（第十章）在从磁盘读取或向磁盘写入文件内容时，会一直保持文件被加锁，而这些磁盘操作可能需要数十毫秒。如果在这么长的时间里持有一把自旋锁，当其他进程试图获取该锁时就会造成浪费，因为等待获取锁的进程会在自旋中长时间浪费 CPU。

自旋锁的另一个缺点是：进程在持有自旋锁时不能让出 CPU。但我们希望在进程等待磁盘时能够让出 CPU，这样其他进程就可以使用 CPU。持有自旋锁时让出 CPU 是非法的，因为如果另一个线程随后尝试获取该自旋锁，可能会导致死锁；由于 acquire 不会让出 CPU，第二个线程的自旋可能会阻止第一个线程运行并释放锁。在持有锁时让出 CPU 也会违反这样一条要求：持有自旋锁时必须关闭中断。因此，我们希望有一种锁：在等待获取锁时可以让出 CPU，并且在持有锁时也允许让出 CPU（以及允许中断）。

xv6 以睡眠锁（sleep-lock）的形式提供了这种锁。acquiresleep（4471）在等待期间会让出 CPU，其实现细节将在第九章中解释。从高层次来看，睡眠锁有一个 locked 字段，该字段由一个自旋锁保护；acquiresleep 对 sleep 的调用会原子地让出 CPU 并释放自旋锁。结果是，在 acquiresleep 等待期间，其他线程可以继续执行。

由于睡眠锁在持有期间保持中断开启，它们不能用于中断处理程序。由于 acquiresleep 可能会让出 CPU，睡眠锁也不能用在自旋锁的临界区内部（不过，自旋锁可以用在睡眠锁的临界区内部）。

自旋锁最适合用于短小的临界区，因为等待它们会浪费 CPU 时间；睡眠锁则非常适合用于耗时较长的操作。

真实世界

尽管在并发原语和并行性方面已经进行了多年的研究，使用锁进行编程仍然充满挑战。通常，最好将锁隐藏在更高层的抽象之中，例如同步队列，尽管 xv6 并未这样做。如果你直接使用锁进行编程，明智的做法是使用能够尝试识别竞态的工具，因为很容易遗漏某个需要锁保护的不变式。

大多数操作系统都支持 POSIX 线程（Pthreads），它允许一个用户进程在不同 CPU 上并发运行多个线程。Pthreads 支持用户级的锁、屏障等机制，并且还允许程序员选择性地指定锁是否为可重入。在用户级支持 Pthreads 需要操作系统的配合。例如，如果一个 pthread 在系统调用中阻塞，同一进程的另一个 pthread 应该能够在该 CPU 上继续运行。再如，如果某个 pthread 修改了进程的地址空间（例如映射或取消映射内存），内核必须确保在其他 CPU 上运行的该进程的线程，其硬件页表能够更新以反映地址空间的变化。

在没有原子指令的情况下也可以实现锁，但代价很高，因此大多数操作系统都会使用原子指令。

当许多 CPU 同时尝试获取同一把锁时，锁可能会非常昂贵。如果一个 CPU 在其本地缓存中持有该锁，而另一个 CPU 需要获取该锁，那么用于更新保存该锁的缓存行的原子指令，必须将该缓存行从一个 CPU 的缓存移动到另一个 CPU 的缓存中，并且可能需要使其他缓存中的该缓存行副本失效。从另一个 CPU 的缓存中获取缓存行，其代价可能比从本地缓存中获取高出几个数量级。

为了避免锁带来的开销，许多操作系统使用 无锁（lock-free） 的数据结构和算法。例如，可以实现本章开头提到的那种链表：在查找链表时不需要任何锁，而在向链表中插入元素时只需要一条原子指令。然而，无锁编程比基于锁的编程要复杂得多；例如，必须处理指令和内存重排序的问题。既然使用锁编程本身就已经很困难，xv6 选择避免无锁编程所带来的额外复杂性。