Locking

课前准备

无论是多核还是单核处理器，计算机都会交错运行多个进程。这种并发为对共享数据结构的操作的可见性带来了一定的破坏。常见的并发来源有：多处理器并行、线程切换、中断

本章重点介绍一种并发控制技术：锁。锁保护了某个数据结构，在同一时间只能由一个CPU持有。但锁可能让并发串行化，降低性能

Race conditions：以 kfree 为例

wait 会调用 kfree 释放子进程的内存，将物理页加入空闲页链表中。如果两个CPU同时执行了wait指令，那么后面的插入可能会被前面的插入覆盖掉——我们丢失跟踪了一个页，这是一种 更新丢失

race

竞争：一个内存被并发访问，且至少一个是写操作

通常会引发错误，比如 更新丢失、读取脏数据

其结果取决于CPU的精确时序以及内存系统如何排列它们的内存操作，这使得引发的 错误难以重现和调试

锁

一种避免竞争的方法是 锁。锁确保了互斥，使得一次只有一个CPU执行关键代码，操作共享数据结构

acquire 和 release 之间的指令序列通常被称为临界区。通常我们会说锁在保护链表。它将临界区的指令串行化，一次只能执行一个，临界区中的指令的原子性得到了保证。

锁限制了性能——毕竟我们串行化了一部分的指令。多个进程请求相同的锁的情况被称为 冲突/争用。不恰当的获取锁的位置极度影响性能——一部分代码完全不会操作数据结构，没必要串行化这部分代码

Code: Locks

xv6 有两种类型的锁：spinlock and sleep-lock。这里先看自旋锁

locked 为0代表锁可以被获取，非0时表示锁被持有

acquire

逻辑上来将可以这样获取锁，但实际上不行：

如果同时运行到 if，它们可以同时获得一把锁——这显然不行。单纯从软件级别无论如何也不能实现一个有效的锁，我们需要硬件的支持。

amoswap

在 risc-v 上，指令 amoswap r, a 读取a处内存的值，将值 r 存储到 a，并把a的值放到了寄存器r中，相当于交换了 寄存器 r 和内存地址 a 处的值。

硬件保证这个操作是原子的，它使用特殊的硬件防止在读写之间任何其他 CPU 使用这个内存地址。

acquire 与 release 实现

可移植函数 __sync_lock_test_and_set 对 amoswap 进行了封装，返回 lk->locked 的原值

在 acquire 的实现中，它不断重试（自旋）调用上述函数，如果它返回0，则成功获取了锁，并更新了 locked 为1。返回1则并没有改变它的值

可以看到，acquire 进行了大量无用操作。如果有大量锁的争用，那么对性能会有很严重的影响。所以能少用锁就少用锁

获取锁后记录持有锁的CPU id，用于调试。该字段受锁保护，必须持有锁才能更改。

release 理论上来说只需要对 locked 赋值为0即可，但这也可能是非原子的，所以使用了C库函数 __sync_lock_release 释放锁，它也封装了 amoswap

Code: Using locks

xv6 在许多地方使用锁来避免竞争条件，保护共享数据结构。比如前面的 kalloc 和 kfree

何时使用锁

使用锁的一个难点是决定使用多少锁，以及每个锁应该保护哪些数据和不变量。

一旦这个数据结构可能被多个CPU同时写入和访问，就应当用锁保护它，也即，应当保护 共享数据结构

何时不使用锁

为了提高效率，不要过度使用锁，因为锁会减少并行性。如果并行性不重要，那么可以安排只有一个线程，这样就不用担心锁的问题了。

以及可以考虑使用更细粒度的锁，以减少锁的争用

big kernel lock

在多处理器上，一个简单的内核可以通过使用一个全局锁来实现：在进入内核时获取锁，在退出内核时释放锁（尽管像管道读取或等待这样的系统调用可能会出现问题）。但这牺牲了并行性，一次只能有一个CPU执行内核代码

细粒度锁

比如 kalloc 的物理页分配器：

可以将其划分为更细粒度的锁，比如9个物理页分别使用三个分配器存放，每个分配器配一把锁即可。当本分配器耗尽时可能采取一些特殊机制。

比如文件锁，每个文件都有一把锁，这样处理不同文件的进程无需获取锁就可以操作文件

比如一个文件锁还可以更加细化，将文件划分为一个个区域，每个区域配一把锁，这样就允许不同进程同时写入一个文件

综上，锁粒度的决定需要根据性能测量以及复杂性考虑来做出

Deadlock and lock ordering

如果内核中的某段代码路径需要同时持有多个锁，那么所有代码路径都必须以相同的顺序获取这些锁，否则便可能出现死锁

e.g. 不同顺序获取锁

假设在 xv6 中有两段代码路径需要锁 A 和锁 B，但代码路径 1 按照顺序 A 然后 B 获取锁，而代码路径 2 按照顺序 B 然后 A 获取锁。假设线程 T1 执行代码路径 1 并获取了锁 A，而线程 T2 执行代码路径 2 并获取了锁 B。接下来 T1 将尝试获取锁 B，而 T2 将尝试获取锁 A。两个获取操作都会无限期地阻塞

全局锁链

sleep 中有很多长度为2的锁顺序链，文件系统中包含了xv6最长的锁链

锁遇到的一些问题

遵守全局的避免死锁的顺序可能会非常困难。有时锁的顺序与逻辑程序结构冲突，例如，代码模块 M1 调用模块 M2，但锁顺序要求在 M2 中的锁比 M1 中的锁先被获取。

有时锁的身份在事前无法确定，可能是因为必须持有一个锁才能确定下一个要获取的锁的身份。

死锁的危险通常限制了锁的粒度，因为更多的锁通常意味着更多的死锁机会

Locks and interrupt handlers

自旋锁与中断的交互可能引发潜在的危险

问题：死锁

假设 sys_sleep 持有 tickslock，然后其所在的 CPU 被计时器中断打断，clockintr 会尝试获取 tickslock，发现它已被占用，并等待其释放。

在这种情况下，tickslock 永远不会被释放：只有 sys_sleep 可以释放它，但 sys_sleep 不会继续运行，直到 clockintr 返回。

因此，CPU 将进入死锁状态，任何需要这个锁的代码也会因此停滞。

solution

如果中断程序需要使用锁，那么CPU持有该锁时必须关闭中断

xv6 更为保守：当 CPU 获取任何锁时，xv6 总是禁用该 CPU 上的中断。尽管如此，中断仍然可能在其他 CPU 上发生，因此中断的获取操作仍然可以等待线程释放自旋锁；只是不会在同一个 CPU 上发生。

当 CPU 不再持有任何自旋锁时，xv6 会重新启用中断。为此，需要一些数据记录CPU持有锁的嵌套层级

push_off 与 pop_off：锁嵌套层级

acquire 调用 push_off，而 release 调用 pop_off，以跟踪当前 CPU 上锁的嵌套层级。

push_off 会关闭中断——计数一定不为0；当计数达到零时，pop_off 恢复中断。intr_off 和 intr_on 函数分别执行 RISC-V 指令来禁用和启用中断。

一个顺序问题：先 push 后获取锁。否则可能获取了锁，然后没来得及push就被中断，然后中断程序获取这把锁，就形成了死锁。同样，需要先释放锁再 pop

Instruction and memory ordering

为了提高执行效率，编译器和CPU可能会打乱代码的执行顺序，并只对执行结果和串行代码结果的一致做保证。

内存模型

比如串行指令顺序是AB，但指令B需要较长的时间得到结果，而且它不与指令A互相依赖，那么很可能会先执行B再执行A。这种CPU 的排序规则被称为内存模型。

重排与并发

遗憾的是，这种重排序可能会改变并发代码的结果，比如把4移动到6后会带来灾难性的后果：

__sync_synchronize

为了告诉硬件和编译器不要执行这样的重排序，xv6 在 acquire和 release 中使用了 __sync_synchronize()。

__sync_synchronize() 是一个内存屏障，它告诉编译器和 CPU 不要跨越该屏障对加载或存储操作进行重排序。

xv6 在 acquire 和 release 中的屏障几乎在所有关键情况下都能强制保持顺序，因为 xv6 在访问共享数据时使用了锁。第九章将讨论少数几个例外情况。

Sleep locks

有时，xv6 需要长时间持有一个锁。在这种情况下，另一个进程想要获取这把自旋锁则会浪费大量的CPU时间，无法让出CPU。否则违反关闭中断的要求

我们希望能够这样做，以便在一个进程尝试获取锁时，其他进程可以使用 CPU，sleep-lock 为此而生

acquiresleep

acquiresleep 在等待时让出 CPU，使用的技术将在第7章解释。

简单来说，睡眠锁有一个受自旋锁保护的 locked 字段，acquiresleep 通过调用 sleep 原子性地让出 CPU 并释放自旋锁。这样，其他线程可以在 acquiresleep 等待时执行。

睡眠锁的使用场景

由于睡眠锁在持有锁时保持中断启用状态，因此不能在中断处理程序中使用。

由于 acquiresleep 可能会让出 CPU，睡眠锁不能在自旋锁的关键区内使用（尽管可以在睡眠锁的关键区内使用自旋锁）。

自旋锁最适合用于短暂的关键区，因为等待它们会浪费 CPU 时间；而睡眠锁更适合用于耗时较长的操作。

Real world

尽管关于并发原语和并行性的研究已经有多年历史，但使用锁进行编程仍然具有挑战性。

通常，最好将锁隐藏在更高级的构造中，例如同步队列，尽管 xv6 并没有这样做。

如果你要使用锁编程，明智的做法是使用工具来尝试识别竞争条件，因为很容易忽略某些需要锁保护的不变量。

POSIX 线程

大多数操作系统都支持 POSIX 线程（Pthreads），它允许一个用户进程在不同的 CPU 上并发运行多个线程。Pthreads 支持用户级锁、屏障等。

支持 Pthreads 需要操作系统的支持。例如，如果一个 Pthread 在系统调用中阻塞，那么同一进程的另一个 Pthread 应该能够在该 CPU 上继续运行。再比如，如果一个 Pthread 改变了其进程的地址空间（例如映射或取消映射内存），内核必须安排同一进程的其他线程在其他 CPU 上更新其硬件页表以反映地址空间的变化。

无原子指令锁

虽然可以在没有原子指令的情况下实现锁，但成本很高，如：

大多数操作系统使用原子指令。

锁与缓存

如果多个 CPU 同时尝试获取同一个锁，锁的开销可能很大。如果一个 CPU 在其本地缓存中缓存了一个锁，而另一个 CPU 需要获取该锁，那么用于更新保存锁的缓存行的原子指令必须将该缓存行从一个 CPU 的缓存移动到另一个 CPU 的缓存中，并可能会使缓存行的其他副本失效。从另一个 CPU 的缓存中获取缓存行的开销可能比从本地缓存获取缓存行的开销高出数个数量级。

无锁的数据结构和算法

为了避免与锁相关的开销，许多操作系统使用无锁的数据结构和算法。

例如，有可能实现一个链表（如本章开头提到的那个链表），在链表搜索时不需要锁，而在向链表中插入一个项目时只需使用一个原子指令。

然而，无锁编程比使用锁编程要复杂得多，例如，必须考虑指令和内存重排序。使用锁编程已经很难了，所以 xv6 避免了无锁编程的额外复杂性。

为什么要使用锁？

并发访问共享数据结构可能造成更新丢失、读取脏数据等现象，我们想要保证数据的正确性

• 并行可以看作是并发的一种特殊情况，但并发并不一定意味着并行
• 需要指出的是，并发不一定导致 race condition，它的结果具有相当的随机性，可能导致完全正确的结果

并行与锁：矛盾的处境

我们想要并行的在不同的CPU核上执行系统调用，但是如果这些系统调用使用了共享的数据，我们又需要使用锁，而锁又会使得这些系统调用串行执行，所以最后锁反过来又限制了性能。

为什么要依靠并行提升性能？

所以现在如果一个应用程序想要提升性能，它不能只依赖单核，必须要依赖于多核。这也意味着，如果应用程序与内核交互的较为紧密，那么操作系统也需要高效的在多个CPU核上运行。

锁如何避免 race condition？

锁就是一个对象，就像其他在内核中的对象一样。有一个结构体叫做lock，它包含了一些字段，这些字段中维护了锁的状态。锁有非常直观的API：

• acquire，接收指向lock的指针作为参数。acquire确保了在任何时间，只会有一个进程能够成功的获取锁。

• release，也接收指向lock的指针作为参数。在同一时间尝试获取锁的其他进程需要等待，直到持有锁的进程对锁调用release。

critical section

锁的acquire和release之间的代码，通常被称为critical section。

之所以被称为critical section，是因为通常会在这里以原子的方式执行共享数据的更新。所以基本上来说，如果在acquire和release之间有多条指令，它们要么会一起执行，要么一条也不会执行。

big kernel lock 与序列化

如果内核中只有一把大锁，基本上所有的系统调用都会被这把大锁保护而被序列化，这些系统调用会串行的执行

所以通常来说，例如XV6的操作系统会有多把锁，这样就能获得某种程度的并发执行。

什么时候使用锁？

锁限制了并发性，也限制了性能，这带来了一个问题，什么时候才必须要加锁呢？

可变共享数据结构

如果两个进程访问了一个共享的数据结构，并且其中一个进程会更新共享的数据结构，那么就需要对于这个共享的数据结构加锁

这个规则有时过于严格，有时又过于宽松，后文中会对此进行解释

printf

如果我们将一个字符串传递给它，XV6会尝试原子性的将整个字符串输出，而不是与其他进程的printf交织输出

自动加锁是否可行？

对于一些更复杂的场景，就不是那么容易探测到race condition。比如能否通过自动的对共享数据结构创建锁来自动避免race condition吗？

e.g. rename

假设我们有一个对于rename的调用，这个调用会将文件从一个目录移到另一个目录，我们现在将文件d1/x移到文件d2/y：

• 先对d1加锁，删除x，之后再释放对于d1的锁；之后我们会对d2加锁，增加y，之后再释放d2的锁

但这样可能得到错误的结果，两个操作的间隔会有一段真空期，即d1和d2中都不存在任何文件，正确的做法是：

• 在重命名的一开始就对d1和d2加锁，之后删除x再添加y，最后再释放对于d1和d2的锁

所以自动加锁在某些场景下会出问题

锁的使用完全是由程序员决定的

并没有强制说一定要使用锁，锁的使用完全是由程序员决定的 —— 程序员决定是否将锁与数据结构关联，以及决定何时对锁进行acquire和release。

锁的一般用途和问题

锁的一般用途

• 避免丢失更新
• 打包多个操作，使它们具有原子性
• 维护共享数据结构的不变性。使修改对所有人可见

锁的问题：死锁

单个锁

一个死锁的最简单的场景就是：首先acquire一个锁，然后进入到critical section；在critical section中，再acquire同一个锁

XV6会探测这样的死锁，如果XV6看到了同一个进程多次acquire同一个锁，就会触发一个panic。

多个锁：deadly embrace

CPU1会获取d1的锁的同时，CPU2获取d2的锁，然后CPU1尝试获取d2，CPU2尝试获取d1

这里的死锁就没那么容易探测了。解决方案是，如果你有多个锁，你需要对锁进行排序，所有的操作都必须以相同顺序获取锁。

锁的问题：破坏抽象

对于一个系统设计者，你需要确定对于所有的锁对象的全局的顺序。

不过在设计一个操作系统的时候，定义一个全局的锁的顺序会有些问题。如果一个模块m1中方法g调用了另一个模块m2中的方法f，那么m1中的方法g需要知道m2的方法f使用了哪些锁。因为如果m2使用了一些锁，那么m1的方法g必须集合f和g中的锁，并形成一个全局的锁的排序。这意味着在m2中的锁必须对m1可见，这样m1才能以恰当的方法调用m2。

但是这样又违背了代码抽象的原则。在完美的情况下，代码抽象要求m1完全不知道m2是如何实现的。但是不幸的是，具体实现中，m2内部的锁需要泄露给m1，这样m1才能完成全局锁排序。所以当你设计一些更大的系统时，锁使得代码的模块化更加的复杂了。

锁的问题：性能权衡与复杂性

基本上来说，如果你想获得更高的性能，你需要拆分数据结构和锁。但这又会引入大量的工作：

怎么拆分呢？通常不会很简单，有的时候还有些困难。比如说，你是否应该为每个目录关联不同的锁？你是否应该为每个inode关联不同的锁？你是否应该为每个进程关联不同的锁？或者是否有更好的方式来拆分数据结构呢？如果你重新设计了加锁的规则，你需要确保不破坏内核一直尝试维护的数据不变性。

如果你拆分了锁，你可能需要重写代码。如果你为了获得更好的性能，重构了部分内核或者程序，将数据结构进行拆分并引入了更多的锁，这涉及到很多工作，你需要确保你能够继续维持数据的不变性，你需要重写代码。通常来说这里有很多的工作，并且并不容易。

所以这里就有矛盾点了。我们想要获得更好的性能，那么我们需要有更多的锁，但是这又引入了大量的工作。

通常的开发流程

通常来说，开发的流程是：

• 先以coarse-grained lock（也就是大锁）开始。

• 再对程序进行测试，来看一下程序是否能使用多核。

• 如果可以的话，那么工作就结束了，你对于锁的设计足够好了；如果不可以的话，那意味着锁存在竞争，多个进程会尝试获取同一个锁，因此它们将会序列化的执行，性能也上不去，之后你就需要重构程序。

在这个流程中，测试的过程比较重要。

有的模块使用了coarse-grained lock，但是它并没有经常被并行的调用，那么其实就没有必要重构程序，因为重构程序设计到大量的工作，并且也会使得代码变得复杂。所以如果不是必要的话，还是不要进行重构。

xv6：UART 与锁

从代码上看UART只有一个锁，它保护了UART的的传输缓存、写指针、读指针：

这是一个 coarse-grained lock 的设计。另外，以上三个数据结构的设计模式叫做消费者-生产者模式

不变量

读指针的内容需要被显示，写指针接收来自例如printf的数据。

有一些不变的特性，例如读指针需要追赶写指针；从读指针到写指针之间的数据是需要被发送到显示端；从写指针到读指针之间的是空闲槽位，锁帮助我们维护了这些特性不变。

uartputc

获得锁–查看buf是否满了–是则放入槽位–释放锁

锁保证了对缓存的写入是原子操作

uartstart

这是处理发送缓存中数据的函数，它调用者的锁保证了清空缓存前不会再往缓存中存数据，也就不会覆盖缓存中的数据

uartintr：handler 或许也得加锁

锁保证了一个时间只有一个CPU上的进程可以写入UART的寄存器 THR。

而UART传输完毕后会产生中断，如果另一个CPU处理了这个中断，然后调用 uartstart，那么可能有多个CPU同时写入THR，所以我们需要在 handler 中也获取锁。

自旋锁的实现

主要难点在于锁的acquire接口。而一般的软件手段完全不能实现 acquire。

amoswap

最常见的手段依赖于一个特殊的硬件指令 amoswap（atomic memory swap

1

amoswap address, r1, r2

（amoswap的参数和课前介绍的不太一样）

这条指令会先锁定住address，将address中的数据保存在一个临时变量中（tmp），之后将r1中的数据写入到地址中，之后再将保存在临时变量中的数据写入到r2中，最后再对于地址解锁。

硬件保证了这一些列的操作具有原子性

amoswap 具体实现？

处理器的指令集通常像是一个说明文档，它不会有具体实现的细节，具体的实现依赖于内存系统是如何工作的，比如说：

• 多个处理器共用一个内存控制器，内存控制器可以支持这里的操作，比如给一个特定的地址加锁，然后让一个处理器执行2-3个指令，然后再解锁。因为所有的处理器都需要通过这里的内存控制器完成读写，所以内存控制器可以对操作进行排序和加锁。

• 如果内存位于一个共享的总线上，那么需要总线控制器（bus arbiter）来支持。总线控制器需要以原子的方式执行多个内存操作。

• 如果处理器有缓存，那么缓存一致性协议会确保对于持有了我们想要更新的数据的cache line只有一个写入者，相应的处理器会对cache line加锁，完成两个操作。

基本上都是对于地址加锁，读出数据，写入新数据，然后再返回旧数据

acquire

使用 amoswap 的test-and-set循环。开始时需要关闭中断，以避免可能的死锁

release

写个0——但也得依靠 amoswap，因为其他的处理器可能会向locked字段写入

store 并不总是原子操作，这取决于具体的实现——缓存等

其他原子指令

总结：自旋锁需要处理的并发

spinlock需要处理两类并发，一类是不同CPU之间的并发，一类是相同CPU上中断和普通程序之间的并发。针对后一种情况，我们需要在acquire中关闭中断。中断会在release的结束位置再次打开，因为在这个位置才能再次安全的接收中断。

memory fence

编译器或者处理器可能会重排指令以获得更好的性能，但临界区中的指令不能被放到外面。

我们需要使用memory fence或者叫做 synchronize 指令，来确定指令的移动范围：任何在它之前的load/store指令，都不能移动到它之后。

锁的acquire和release函数都包含了synchronize指令。