XV6

XV6 支持多核 CPU,计算机上有多个同时运行代码的 CPU,但是所有 CPU 共享同一个地址空间,为了保护数据结构的一致性,XV6 需要某一种机制来防止它们互相干扰。

即使在单处理器的抢占内核中,也同样需要处理内核数据结构的互斥现象。XV6 以硬件提供的处理方式,采用了自旋锁来处理多核操作系统的互斥问题,因为一般情况下内核对数据结构的占用时间一般比较短,使用自旋锁能够简单处理同步时容易出现的死锁问题。

1. 自旋锁

变量 locked 代表锁的状态,当 locked1 表示当前访问的数据结构已经锁住,locked 为 0 表示未锁住,能够访问当前数据结构,spinlock 还附带有调试信息,比如锁的名字,当前占有锁的 cpu 和调用栈。 实际上按照普通方式访问并修改变量 locked 本身就存在竞争条件,可能有两个 CPU 同时读取 locked 的值为 0,并认为都可以获得锁占用数据结构,然后将 locked 置 1 占用锁,实际上有两个 CPU 同时获得了锁,违反了访问该数据结构的互斥性,出现这种现象的根本原因是读取变量和修改变量不是一个原子操作,如果读取变量和修改变量这两个过程连续进行不可打断,并在访问时只允许一个 CPU 进行,便能实现访问 locked 的原子操作。

XV6 使用了 X86 架构下的 xchg 指令实现, xchg 原子地交换一个寄存器和内存字的值,通过循环反复调用 xchg,如果返回的内存字值为 1,代表有 CPU 或者进程占用锁,继续循环 xchg,如果 xchg 返回为 0,代表目前没有人占用锁,通过将锁置 1 占用数据结构,然后跳出循环,通过这样的实现,每个 CPU 或进程在访问一个可能出现竞争的数据结构时,必须提前获得这个数据的锁,如果暂时无法获得锁则不断循环调用 xchg,直到锁被释放。

XV6 在处理可能出现互斥的数据结构时,都会使用锁机制来防止互相干扰,这些操作基本遵循一个规则:

acquire(lock);
...         // 临界区
release(lock);

但是在并发中,使用锁机制也很容易带来各种问题,这些问题往往难以发现,因为发生错误的概率低,大部分情况下都可以正常运行,一旦出现问题,便会造成非常严重的后果甚至宕机。

2. 单核锁机制问题

在单核情况下使用锁也会出现一系列的问题。

2.1 抢占式内核中断处理程序

XV6 在 acquire() 中只是简单地关闭所有的中断,之所以需要关闭中断是为了防止当在抢占式内核中,当前过程占用锁然后进入中断处理再次想要获得锁时出现的死锁现象,使用自旋锁非常容易出现死锁现象,尤其是在抢占式内核中,所以 XV6 在中断处理和自旋锁的关系上做的非常决绝:占用锁时禁止所有中断。 pushcli() 主要关闭外部中断并递增调用 pushcli() 关闭中断的次数,这样做的原因是如果代码中获得了两个锁,那么只有当两个锁都被释放后中断才会被允许。同时 acquire() 一定要在可能获得锁的 xchg 之前调用 pushcli()。如果两者颠倒了,就可能在几个时钟周期里,中断仍被允许,而锁也被获得了,如果此时不幸地发生了中断,系统就会死锁。类似的,release() 也一定要在释放锁的 xchg 之后调用 popcli()

2.2 模块化与递归锁

在同一个 CPU 中,使用自旋锁还会出现另一个问题。如果某一过程调用另一个过程中,调用者持有锁,若此时被调者申请锁,则出现死锁问题。

系统设计力求简单、模块化的抽象:最好是让调用者不需要了解被调者的具体实现。锁的机制则和这种模块化理念有所冲突。例如,当 CPU 持有锁时,它不能再调用另一个试图获得该锁的函数 f:因为调用者在 f 返回之前无法释放锁,如果 f 试图获得这个锁,就会造成死锁。

现在还没有一种透明方案可以让调用者和被调者可以互相隐藏所使用的锁。我们可以使用递归锁(recursive locks)使得被调者能够在此获得调用者已经持有的锁,这种方案虽然是透明通用的,但是十分繁复。

由于没有理想、透明的解决方法,我们不得不在函数的使用规范中加入锁。编程者必须保证一个函数不会在持有锁时调用另一个需要获得该锁的函数 f。就这样,锁也成为了我们的抽象中的一员。

2.3 锁的顺序容易引发的问题

如果一段代码要使用多个锁,那么必须要注意代码每次运行都要以相同的顺序获得锁,否则就有死锁的危险。假设某段代码的两条执行路径都需要锁 A 和 B,但路径 1 获得锁的顺序是 A、B,而路径 2 获得锁的顺序是 B、A。这样就有能路径 1 获得了锁 A,而在它继续获得锁 B 之前,路径 2 获得了锁 B,这样就死锁了。这时两个路径都无法继续执行下去了,因为这时路径 1 需要锁 B,但锁 B 已经在路径 2 手中了,反之路径 2 也得不到锁 A。为了避免这种死锁,所有的代码路径获得锁的顺序必须相同。避免死锁也是我们把锁作为函数使用规范的一部分的原因:调用者必须以固定顺序调用函数,这样函数才能以相同顺序获得锁。

由于 XV6 本身比较简单,它使用的锁也很简单,所以 XV6 几乎没有锁的使用链。最长的锁链也就只有两个锁。例如,ideintr() 在调用 wakeup() 时持有 ide 锁,而 wakeup 又需要获得 ptable.lock。还有很多使用 sleep / wakeup 的例子,它们要考虑锁的顺序是因为 sleepwakeup 中有比较复杂的不变量(被锁保护的变量)。文件系统中有很多两个锁的例子,例如文件系统在删除一个文件时必须持有该文件及其所在文件夹的锁。XV6 总是首先获得文件夹的锁,然后再获得文件的锁。

2.4 使用锁的原则

使用锁的一个难点在于要决定使用多少个锁,以及每个锁保护哪些数据、不变量。不过有几个基本原则。首先,当一个 CPU 正在写一个变量,而同时另一个 CPU 可能读 / 写该变量时,需要用锁防止两个操作重叠。第二,当用锁保护不变量时,如果不变量涉及到多个数据结构,通常每个数据结构都需要用一个单独的锁保护起来,这样才能维持不变量。

由于锁会降低并发程度,所以我们一定要避免过度使用锁。当效率不是很重要的时候,完全可以使用单处理器计算机,这样就完全不用考虑锁了。当我们要保护内核的数据结构时,使用一个内核锁还是值得的,当进入内核时必须持有该锁,而退出内核时就释放该锁。许多单处理器操作系统就用这种方法运行在了多处理器上,有时这种方法被称为 “内核巨锁(giant kernel lock)”,但使用这种方法就牺牲了并发性:即一时间只有一个 CPU 可以运行在内核上。如果我们想要依靠内核做大量的计算,那么使用一组更为精细的锁来让内核可以在多个 CPU 上轮流运行会更有效率。

最后,对于锁的粒度选择是并行编程中的一个重要问题。XV6 只使用了几个简单的锁;例如,XV6 中使用了一个单独的锁来保护进程表。更精细的做法是给进程表中的每一个条目都上一个锁,这样在不同条目上运行的线程也能并行了。但是在进程表中维护那么多个不变量就必须使用多个锁,这就让情况变得很复杂了。不过 XV6 中的例子已经足够让我们了解如何使用锁了。