并发（concurrency）一词指的是由于多处理器并行、线程切换或中断而导致多个指令流交错的情况。

以并发下的正确性为目标的策略，以及支持这些策略的抽象，被称为并发控制技术（concurrency control techniques）。

Xv6根据不同的情况，使用了很多并发控制技术，还有更多的可能。本章重点介绍一种广泛使用的技术：锁（lock）。锁提供了相互排斥的功能，确保一次只有一个CPU可以持有锁。如果程序员为每个共享数据项关联一个锁，并且代码在使用某项时总是持有关联的锁，那么该项每次只能由一个CPU使用。在这种情况下，我们说锁保护了数据项。虽然锁是一种简单易懂的并发控制机制，但锁的缺点是会扼杀性能，因为锁将并发操作串行化了。

6.1 Race conditions

第16行的丢失更新是竞争条件(race condition）的一个例子。竞争条件是指同时访问一个内存位置，并且至少有一次访问是写的情况。竞争通常是一个错误的标志，要么是丢失更新（如果访问是写），要么是读取一个不完全更新的数据结构。竞争的结果取决于所涉及的两个CPU的确切时间，以及它们的内存操作如何被内存系统排序，这可能会使竞争引起的错误难以重现和调试。例如，在调试push时加入print语句可能会改变执行的时机，足以使竞争消失。

当我们说锁保护数据时，我们真正的意思是锁保护了一些适用于数据的不变式(invariant）集合。invariant是跨操作维护的数据结构的属性，这些属性在不同的操作中都得到了维护。通常情况下，一个操作的正确行为取决于操作开始时的invariant 是否为真。操作可能会暂时违反invariant，但必须在结束前重新建立invariant。例如，在链表的情况下，invariant是list指向列表中的第一个元素，并且每个元素的next字段指向下一个元素。push的实现暂时违反了这个invariant：在第17行，l指向下一个list元素，但list还没有指向l（在第18行重新建立）。我们上面所研究的竞争条件之所以发生，是因为第二个CPU执行了依赖于链表invariant的代码，而它们被（暂时）违反了。正确地使用锁可以保证一次只能有一个CPU对临界区中的数据结构进行操作，所以当数据结构的invariant不成立时，没有CPU会执行数据结构操作。

你可以把锁看成是把并发的临界区串行化(serializing)的一种工具，使它们同时只运行一个，从而保护invariant（假设临界区是独立的）。你也可以认为由同一个锁保护的临界区，相互之间是原子的，这样每个临界区都只能看到来自之前临界区的完整变化，而永远不会看到部分完成的更新。

虽然正确使用锁可以使不正确的代码变得正确，但锁会限制性能。例如，如果两个进程同时调用kfree，锁会将两个调用串行化，我们在不同的CPU上运行它们不会获得任何好处。我们说，如果多个进程同时想要同一个锁，或者该锁发生争用（contention），我们就会说多个进程冲突（multiple processes conflict）。内核设计的一个主要挑战是避免锁的争用。Xv6在这方面做得很少，但是复杂的内核会专门组织数据结构和算法来避免锁争用。例如链表，一个内核可以为每个CPU维护一个空闲页链表，只有当自己的链表为空时，并且它必须从另一个CPU获取内存时，才会接触另一个CPU的空闲链表。其他用例可能需要更复杂的设计。

6.2 Code: Locks

由于锁被广泛使用，多核处理器通常提供了一些原子版的指令。在RISC-V上，这条指令是amoswap r, a。amoswap读取内存地址a处的值，将寄存器r的内容写入该地址，并将其读取的值放入r中，也就是说，它将寄存器和内存地址的内容进行了交换。它原子地执行这个序列，使用特殊的硬件来防止任何其他CPU使用读和写之间的内存地址。

Xv6的acquire (kernel/spinlock.c:22)使用了可移植的C库调用__sync_lock_test_and_set，它本质上为amoswap指令；返回值是lk->locked的旧（交换）内容。acquire函数循环交换，重试（自旋）直到获取了锁。每一次迭代都会将1交换到lk->locked中，并检查之前的值；如果之前的值为0，那么我们已经获得了锁，并且交换将lk->locked设置为1。如果之前的值是1，那么其他CPU持有该锁，而我们原子地将1换成lk->locked并没有改变它的值。

函数release (kernel/spinlock.c:47)与acquire相反：它清除lk->cpu字段，然后释放锁。从概念上讲，释放只需要给lk->locked赋值为0。C标准允许编译器用多条存储指令来实现赋值，所以C赋值对于并发代码来说可能是非原子性的。相反，release使用C库函数__sync_lock_release执行原子赋值。这个函数也是使用了RISC-V的amoswap指令。

6.3 Code: Using locks

使用锁的一个难点是决定使用多少个锁，以及每个锁应该保护哪些数据和invariant。有几个基本原则。首先，任何时候，当一个CPU在另一个CPU可以读写变量的同时，写入变量，就应该使用锁来防止这两个操作重叠。其次，记住锁保护的是invariant：如果一个invariant涉及到多个内存位置，通常需要用一个锁保护所有的位置，以确保invariant得到维护。

上面的规则说了什么时候需要锁，但没说什么时候不需要锁，为了效率，不要太多锁，因为锁会降低并行性。如果并行性不重要，那么可以只安排一个线程，而不用担心锁的问题。一个简单的内核可以在多处理器上像这样做，通过一个单一的锁，这个锁必须在进入内核时获得，并在退出内核时释放（尽管系统调用，如管道（pipe）读取或wait会带来问题）。许多单处理器操作系统已经被改造成使用这种方法在多处理器上运行，有时被称为“大内核锁（big kernel lock）“，但这种方法牺牲了并行性：内核中一次只能执行一个CPU。如果内核做任何繁重的计算，那么使用一组更大的更精细的锁，这样内核可以同时在多个CPU上执行，效率会更高。

作为粗粒度锁（coarse-grained locking）的一个例子，xv6的kalloc.c分配器有一个单一的空闲页链表，由一个锁保护。如果不同CPU上的多个进程试图同时分配内存页，每个进程都必须通过在acquire中自旋来等待获取锁。自旋会降低性能，因为这是无意义的。如果对锁的争夺浪费了很大一部分CPU时间，也许可以通过改变分配器的设计来提高性能，使其拥有多个空闲页链表，每个链表都有自己的锁，从而实现真正的并行分配。

作为细粒度锁（offine-grained locking）的一个例子，xv6对每个文件都有一个单独的锁，这样操作不同文件的进程往往可以不等待对方的锁就可以进行。如果想让进程同时写入同一文件的不同区域，文件锁方案可以做得更细。最后，锁粒度的决定需要考虑性能以及复杂性。

6.4 Deadlock and lock ordering

如果一个穿过内核的代码路径必须同时持有多个锁，那么所有的代码路径以相同的顺序获取这些锁是很重要的。如果他们不这样做，就会有死锁（deadlock）的风险。假设xv6中两个代码路径需要锁A和B,但代码路径1以顺序A然后B获取锁，而其他路径以顺序B然后A获取锁。假设线程T1执行代码path1并获取锁A，线程T2执行代码path2并获取锁B，接下来T1会尝试获取锁B，T2会尝试获取锁A，这两次获取都会无限期地阻塞，因为在这两种情况下，另一个线程都持有所需的锁，并且不会释放它，直到它的获取返回。为了避免这样的死锁，所有的代码路径必须以相同的顺序获取锁。对全局锁获取顺序的需求意味着锁实际上是每个函数规范的一部分：调用者调用函数的方式必须使锁按照约定的顺序被获取。

由于sleep的工作方式（见第7章），Xv6有许多长度为2的锁序链，涉及到每个进程的锁（struct proc中的锁）。例如，consoleintr(kernel/console.c:138)是处理键入字符的中断routine。当一个新的行到达时，任何正在等待控制台输入的进程都应该被唤醒。为此，consoleintr在调用wakeup时持有cons.lock，以获取正在等待的进程锁来唤醒它。因此，全局避免死锁的锁顺序包括了cons.lock必须在任何进程锁之前获取的规则。文件系统代码包含xv6最长的锁链。例如，创建一个文件需要同时持有目录的锁、新文件的inode的锁、磁盘块缓冲区的锁、磁盘驱动器的vdisk_lock和调用进程的p->lock。为了避免死锁，文件系统代码总是按照上一句中提到的顺序获取锁。

遵守全局避免死锁的顺序可能会非常困难。有时锁的顺序与逻辑程序结构相冲突，例如，也许代码模块M1调用模块M2，但锁的顺序要求M2中的锁在M1中的锁之前被获取。有时锁的身份并不是事先知道的，也许是因为必须持有一个锁才能发现接下来要获取的锁的身份。这种情况出现在文件系统中，因为它在路径名中查找连续的组件，也出现在wait和exit的代码中，因为它们搜索进程表寻找子进程。最后，死锁的危险往往制约着人们对锁方案的细化程度，因为更多的锁往往意味着更多的死锁机会。避免死锁是内核实现的重要需求。

6.5 Re-entrant locks

似乎可以通过使用重入锁(re-entrant locks，也称为递归锁，recursive locks)来避免某些死锁和锁顺序挑战。其思想是，如果锁由某个进程持有，并且如果该进程再次尝试获取锁，则内核可以只需允许这样做(因为该进程已经拥有锁)，而不是像xv6内核那样调用panic。

然而，事实证明，可重入锁使得对并发性进行推理变得更加困难：可重入锁打破了锁导致临界区相对于其他临界区是原子的直觉。考虑以下两个函数f和g：

查看这段代码，我们的直觉是call_once只会被调用一次：要么由f调用，要么由g调用，但不能同时由f和g调用。
但是，如果允许重入锁，并且h恰好调用g，则call_once将被调用两次。
如果不允许重入锁，那么h调用g会导致死锁，这也不是很好。但是，假设调用call_once会是一个严重的错误，那么死锁更可取。内核开发人员将观察到死锁(内核死机)，并可以修复代码以避免死锁，而调用call_once两次可能会悄悄导致难以跟踪的错误。

6.6 Locks and interrupt handlers

一些xv6自旋锁保护的数据会被线程和中断处理程序两者使用。例如，clockintr定时器中断处理程序可能会在内核线程读取sys_sleep (kernel/sysproc.c:64)中的ticks的同时，递增ticks (kernel/trap.c:163)。锁 tickslock将串行化这两次访问。

自旋锁和中断的相互作用带来了一个潜在的危险。假设sys_sleep持有tickslock，而它的CPU被一个定时器中断。clockintr会尝试获取tickslock，看到它被持有，并等待它被释放。在这种情况下，tickslock永远不会被释放：只有sys_sleep可以释放它，但sys_sleep不会继续运行，直到clockintr返回。所以CPU会死锁，任何需要其他锁的代码也会冻结。

为了避免这种情况，如果一个中断处理程序使用了自旋锁，CPU决不能在启用中断的情况下持有该锁。Xv6比较保守：当一个CPU获取任何锁时，xv6总是禁用该CPU上的中断。中断仍然可能发生在其他CPU上，所以一个中断程序acquire会等待一个线程释放自旋锁；它们不在同一个CPU上。

xv6在CPU没有持有自旋锁时重新启用中断；它必须做一点记录来应对嵌套的临界区。acquire调用push_off(kernel/spinlock.c:89)和release调用pop_off(kernel/spinlock.c:100)来跟踪当前CPU上锁的嵌套级别。当该计数达到零时，pop_off会恢复最外层临界区开始时的中断启用状态。intr_off和intr_on函数分别执行RISC-V指令来禁用和启用中断。

在设置lk->locked之前，严格调用push_off是很重要的(kernel/spinlock.c:28)。如果两者反过来，那么在启用中断的情况下，锁会有一个短暂的窗口（未锁到的位置）在未禁止中断时持有锁，不幸的是，一个定时的中断会使系统死锁。同样，释放锁后才调用pop_off也很重要（kernel/spinlock.c:66）。

6.7 Instruction and memory ordering

人们很自然地认为程序是按照源代码语句出现的顺序来执行的。然而，许多编译器和CPU为了获得更高的性能，会不按顺序执行代码。如果一条指令需要很多周期才能完成，CPU可能会提前发出该指令，以便与其他指令重叠，避免CPU停顿。例如，CPU可能会注意到在一个串行序列中，指令A和B互不依赖。CPU可能先启动指令B，这是因为它的输入在A的输入之前已经准备好了，或者是为了使A和B的执行重叠。 编译器可以执行类似的重新排序，在一条语句的指令之前发出另一条语句的指令，由于它们原来的顺序。
编译器和CPU在re-order 时遵循相应规则，以确保它们不会改变正确编写的串行代码的结果。然而，这些规则确实允许re-order，从而改变并发代码的结果，并且很容易导致多处理器上的不正确行为[2，3]。CPU的ordering 规则称为内存模型（memory model）。
例如，在这段push的代码中，如果编译器或CPU将第4行对应的存储移到第6行release后的某个点，那将是一场灾难。

如果发生这样的re-order，就会有一个窗口，在这个窗口中，另一个CPU可以获取锁并观察更新的list，但看到的是一个未初始化的list->next。
为了告诉硬件和编译器不要执行这样的re-ordering，xv6在获取(kernel/spinlock.c:22)和释放(kernel/spinlock.c:47)中都使用了sync_synchronize()。syncsynchronize() 是一个**内存屏障(_memory barrier)：它告诉编译器和 CPU 不要跨越屏障re-order加载或存储。xv6中的屏障几乎在所有重要的情况下都会acquire和release**强制顺序，因为xv6在访问共享数据的周围使用了锁。第9章讨论了一些例外情况。

6.8 Sleep locks

有时xv6需要长时间保持一个锁。例如，文件系统（第8章）在磁盘上读写文件内容时，会保持一个文件的锁定，这些磁盘操作可能需要几十毫秒。如果另一个进程想获取一个自旋锁，那么保持那么长的时间会导致浪费，因为获取进程在自旋的同时会浪费CPU很长时间。自旋锁的另一个缺点是，一个进程在保留自旋锁的同时不能让出CPU；我们希望做到这一点，这样其他进程可以在拥有锁的进程等待磁盘的时候使用CPU。在持有自旋锁的同时让出是非法的，因为如果第二个线程试图获取自旋锁，可能会导致死锁；因为acquire自旋锁不会让出CPU，第二个线程的自旋可能会阻止第一个线程运行并释放锁。在持有锁的同时让出也会违反在持有自旋锁时中断必须关闭的要求。因此，我们希望有一种锁，在等待获取的过程中产生CPU，并在锁被持有时允许让出CPU（和中断）。

Xv6以睡眠锁__(sleep-locks)的形式提供了这样的锁。acquiresleep(kernel/sleeplock.c:22)在等待的过程中让出CPU，使用的技术将在第7章解释。在高层次上，sleep-lock有一个由spinlock保护的locked字段，而acquiresleep对sleep的调用会原子性地让出CPU并释放spinlock。其结果是，在acquiresleep等待时，其他线程可以执行。

因为睡眠锁会使中断处于启用状态，所以不能在中断处理程序中使用睡眠锁。因为acquiresleep可能会让出CPU，所以睡眠锁不能在spinlock临界区内使用（虽然spinlocks可以在睡眠锁临界区内使用）。·

自旋锁最适合短的临界区，因为等待它们会浪费CPU时间；睡眠锁对长时间的操作很有效。

6.9 Real world

尽管对并发基元和并行进行了多年的研究，但使用锁进行编程仍然具有挑战性。通常最好的方法是将锁隐藏在更高级别的构造中，比如同步队列，但xv6没有这样做。如果您使用锁编程，明智的做法是使用一个可以识别竞争条件的工具，因为很容易错过一个需要锁的invariant 。

大多数操作系统都支持POSIX线程（Pthreads），它允许一个用户进程在不同的CPU上有多个线程并发运行。Pthreads对用户级锁、屏障(barriers)等都有支持。Pthread还允许程序员有选择地指定锁应该是可重入的。

在用户级别支持Pthreads需要操作系统的支持。例如，如果一个pthread在系统调用中阻塞，同一进程的另一个pthread应该可以在该CPU上运行。另一个例子，如果一个pthread改变了进程的地址空间（例如，映射或取消映射内存），内核必须安排同一进程中其他线程，在其他CPU更新它们的硬件页表以反映地址空间的变化。

在没有原子指令的情况下实现锁是可能的[8]，但成本很高，而且大多数操作系统都使用原子指令。

如果多个CPU试图在同一时间获取同一个锁，那么锁的代价会很高。如果一个CPU在它的本地缓存（cache）中缓存了一个锁，而另一个CPU必须获取该锁，那么更新持有该锁的缓存行的原子指令必须将该行从一个CPU的缓存中移到另一个CPU的缓存中，也许还会使该缓存行的任何其他副本无效。从另一个CPU的缓存中获取缓存行的成本可能比从本地缓存中获取行的成本高几个数量级。

为了避免与锁有关的消耗，许多操作系统都采用无锁的数据结构和算法[5，10]。例如，可以实现像本章开头的链表，在链表搜索过程中不需要锁，插入一个项目时，只需要一条原子指令就可以在链表中插入项。不过，无锁编程比有锁编程更复杂，例如，必须担心指令和内存的re-order问题。有锁编程已经很难了，所以xv6没有使用无锁编程来额外复杂性。