大多数内核，包括xv6，交错执行多个活动。其中一个交错的资源就是多处理器硬件：多个CPU独立运行的计算机，比如xv6赖以运行的RISC-V。这些CPU共享物理内存，xv6利用这个共享来管理所有CPU读写的数据结构。这个共享提升了如下可能性：一个CPU在读取数据结构而另一个CPU在更新它，多CPU同时更新相同的数据。对那样并行访问的情况如不仔细设计，很可能会产生错误的结果或被破坏的数据结构。即使是单处理器，内核也可能让CPU在多个线程间切换，导致它们交错执行。最后，中断处理例程也可能修改中断代码的数据，这也会导致数据的损坏。并发(concurrency)的意思就是指多个指令流交错的情况，由于多处理器并行、线程切换或中断。
内核中充满了并发访问的数据。如，两个CPU可能并发地调用kalloc，于是并发地从空闲列表里弹出了元素。内核的设计者倾向于允许大量的并发，因为它可以导致性能和响应能力的提升。然而，内核设计者不得不花大量的努力来证明引入并发后代码的正确性。有很多方法达到正确的代码，一些比较好解释，但另一些不好解释。让并发正确的策略和支持它们的抽象，被称为并发控制(concurrency control)。xv6根据情况使用了大量并发控制的技术，更多的并发控制是可能的。本章聚焦于一个广泛使用的技术：锁。
锁提供的是互斥，保证一个时间段内只有一个CPU可以持有锁。如果程序员把所有共享数据都关联了一个锁，且代码在使用那条数据的时候始终持有关联的锁，那么那条数据在一个时间段内只能被一个CPU使用。这种情况下，我们说锁保护了这条数据。
本章其余部分解释了为什么需要锁，怎么实现它，怎么使用它。
竞争条件
为什么需要锁呢？考虑一个链表，它可以被多处理器的任意CPU访问。链表支持push和pop操作，这些操作可能是并发的。xv6的内存分配器很大程度上就是这样工作的，kalloc从列表里弹出空闲页，kfree把页加到列表里。
在没有处理并发的情况下，如果两个CPU都在执行push操作，有可能两个元素都往同一个位置加，后加的元素会覆盖先加的元素。
上面的情况就是竞争条件(race condition)的一个例子。竞争条件就是并发地访问内存位置，且至少有一个访问是写操作。竞争经常标志着产生了错误，可能是写操作丢失了更新，也可能是读了未完全更新的数据结构。竞争的结果取决于两个CPU的时机和它们在内存系统里的内存操作次序，这使得竞争引起的错误难以复现和调试。比如调试push的时候添加打印语句足以改变执行的时机而使竞争消失。
避免竞争的常用方法就是使用锁。锁保证了互斥，这样一个时间段内只有只有一个CPU可以执行push里的敏感操作，从而使上述设想成为可能。在acquire和release之间的代码被称为 临界区(critical section)。
所谓的锁保护了数据，真的就是指保护了数据所特有的一些不变性(invariants)。不变性就是数据的属性，它在整个操作过程中保持不变。一般来说，一个操作的正确行为依赖于操作开始的时候不变性是真实的。操作可能临时修改不变性但必须在完成前恢复它们。比如，链表例子里，不变性是指列表要指向列表里的第一个元素，并且每个元素的next字段要指向它的下一个元素。push的实现临时修改了不变性，但随后又消除了这个影响。如上的竞争条件能发生，是因为第二个CPU执行的代码依赖于列表的不变性。正确使用锁以确保一个时间段内只有一个CPU可以操作临界区的数据结构，这样当数组结构的不变性没有被持有的情况下，没有CPU可以执行数据结构的操作。
可以把锁认为是序列化的并发临界区，这样就可以一个时间段只运行一个，并保护了不变性(假定临界区的分隔是正确的)。也可以认为被同一个锁保护的临界区相互之间是原子的，这样只能看到完整修改后的临界区。我们说进程之间相互 冲突(conflict)，如果它们同时想要相同的锁，或那个锁发生争用(contention)。
注意在push里把acquire往前移是正确的。这只是会降低并发性。
代码：锁
xv6里有两种锁：自旋锁和睡眠锁。xv6里的自旋锁是struct spinlock。其中最重要的字段是locked，为0时表示锁存在，为非0时表示锁被持有。
为避免多CPU同时持有一个锁，需要在临界区内执行原子性的步骤。
RISC-V提供了原子指令amoswap，用于原子性地交换内存地址和寄存器的值。当内存地址正在读写时，它使用了特殊硬件来防止CPU使用那个内存地址，从而实现了指令的原子性。
xv6的acquire定义在kernel/spinlock.c。acquire使用了内建函数__sync_lock_test_and_set，这个函数最终使用了amoswap指令，它返回的是lk->locked的原值。acquire在循环里实现的交换，不断的重试直到获得锁。每个循环都把1交换进lk->locked并检查之前的值。如果之前的值是0则获得锁，并且交换使得lk->locked的值为1。如果之前的值是1，表明有其它CPU持有这个锁，把1交换进lk->locked的操作不生效。
一旦获得锁，acquire为方便调试会记录获得锁的CPU。lk->cpu字段被锁保护，且只能在持有锁的时候被修改。
release函数是acquire的反操作，它清空lk->cpu字段并释放锁。从概念上说，释放锁只需给lk->locked赋值为0即可。C语言的赋值语句是多条指令完成的，所以它是不具有原子性的。release使用了内建函数__sync_lock_release来实现原子性地赋值。这个内建函数最终也使用了amoswap指令。
代码：使用锁
xv6在很多地方使用了锁。关于它的简单例子，可以看看kalloc和kfree。如果去掉锁也很难触发错误的行为，这意味着锁的错误和竞争是难以测试的。xv6里可能也有一些未被发现的竞争。
使用锁的难点在于，使用多少锁，锁应该保护哪些数据和不变性。有一些基本原则：一，当一个CPU写变量的时候，其它CPU也可以读或写这个变量，应该使用锁；二，记住锁保护的是不变性，如果一个不变性包含了多个内存位置，所有这些位置都需要被单一的锁保护起来。
上述规则说了什么时候使用锁，但没说什么时候可以不用锁，为了效率不应大量使用锁，因为锁会降低并发性。在并发性不重要的情况下，可以只安排一个线程而不使用锁。简单的内核可以在多处理器上通过只持有一个锁的方式来实现这点，即在进入内核的时候获得锁，在退出内核的时候释放锁(但在系统调用的时候可能会有问题，如读管道或wait)。许多单处理器操作系统通过这个方法在多处理器上运行，有时被叫做”大内核锁”(big kernel lock)，但这种方法牺牲了并行性，一个时间段内只有一个CPU可以运行。如果内核要进行大型运算，那么使用大量细粒度的锁要高效的多，因为内核是在多个CPU上并行执行的。
xv6的内存分配器是一个粗粒度锁的例子，它只用了一个锁来保护空闲列表。如果不同CPU上的进程在同时分配物理页，大家都要等待在acquire上的自旋(spinning)。自旋降低了性能，因为它是无效的工作。如果对锁的争用浪费了大量的CPU时间片段，可以把分配器设计为有多个空闲列表来提升性能，每个都有自己的锁，这样就可以真正的并行分配了。
作为细粒度锁的例子，xv6为每个文件都分配了锁，这样进程在处理多个文件的时候就不必等待彼此的锁了。文件锁的粒度可以更细，如果想并行地写文件的不同区域的话。最终，锁的粒度需要考虑性能和复杂性两方面的情况。
xv6中的所有锁如下表所示。详细的解释分散在各章之中。
| 锁 | 描述 |
|---|---|
| bcache.lock | 保护对块缓冲区缓存的分配 |
| cons.lock | 序列化访问控制台硬件，避免混合输出 |
| ftable.lock | 序列化访问文件列表里的结构体file |
| icache.lock | 保护对inode缓存入口的分配 |
| vdisk_lock | 序列化访问磁盘硬件和DMA描述符队列 |
| kmem.lock | 序列化内存访问 |
| log.lock | 序列化事务日志的操作 |
| pi->lock | 序列化管道的操作 |
| pid_lock | 序列化next_pid的增长 |
| p->lock | 序列化进程状态的改变 |
| tickslock | 序列化ticks计数器的操作 |
| ip->lock | 序列化每个inode和它的内容的操作 |
| b->lock | 序列化每个块缓冲区的操作 |
死锁和锁序
如果到内核的代码路径必须同时持有多个锁，则所有的代码路径以同样的次序获取这些锁是十分重要的。否则就会有死锁的危险。假定有两个代码路径需要锁A和B，代码路径一按从A到B的次序获取锁，代码路径二按从B到A获取锁。假定线程一执行代码路径一并获取了锁A，线程二执行代码路径二并获取了锁B。接下来，线程一尝试获取锁B，线程二尝试获取锁A。两个获取都会被永远阻塞，因为它们分别持有了对方需要的锁，并且在获取所需的锁之前都不会释放自己的锁。全局性的锁获取次序意味着，锁是函数规范的一部分：调用者在调用函数的时候，必须使锁按规定的次序被获取。
xv6包含很多长度为2的锁序链(lock-order chains)，包含每个进程的锁(struct proc里的锁)，这是由于sleep的工作方式。例如，consoleintr是处理输入字符的中断例程。当新行到达时，等待控制台输入的所有进程都应被唤醒。为实现此目的，consoleintr在调用wakeup的时候持有了锁cons.lock，获取等待进程的锁是为了唤醒它。因此，全局的避免死锁的锁序包含了一个规则，即必须在任何进程锁之前先获取cons.lock。xv6里最长的锁链(lock chains)在文件系统的代码里。例如，创建文件需要同时目录持有锁，新文件的inode持有锁，磁盘块缓冲区持有锁，磁盘驱动的vdisk_lock，和调用进程的p->lock。为避免死锁，文件系统代码总是按前述的次序获取锁。
实现一个全局性的避免死锁的序列可能极为困难。有时锁序和逻辑程序结构矛盾，比如代码模块M1调用M2，但锁序要求M2的锁在M1的锁之前获取。有的时候锁的身份无法预先知道，有可能是因为先持有一个锁才能发现这个锁的身份。这个情况出现在文件系统中，当它在路径名中查找连续组件的时候，在exit和wait的代码里当在进程表里搜索子进程的时候。最后，死锁的风险经常是对细粒度锁制定锁方案的限制，因为更多的锁意味着更多的死锁机会。避免死锁是内核实现的一个重要因素。
锁和中断处理例程
一些xv6自旋锁保护的数据被线程和中断处理例程两者使用。例如，在clockintr增加ticks的时候内核正在sys_sleep里读取ticks。锁tickslock序列化了这两个访问。
自旋锁和进程的交互提升了潜在的危险性。考虑sys_sleep持有tickslock，且它的CPU发生了计时器中断。clockintr尝试获取tickslock，看见它被持有了，一直等待这个锁的释放。这种情况下，tickslock永远不会被释放，只有sys_sleep能释放它，但clockintr不返回sys_sleep就不能继续执行。所以，CPU会死锁，任何需要锁的代码都会被冻结。
为避免这种情况，如果中断处理例程使用了自旋锁，当中断发生的时候CPU一定不能持有那个锁。xv6更保守一点，CPU获取锁之前会关闭那个CPU上的所有中断。其它CPU仍然能发生中断，所以一个中断的acquire仍然可以等待一个线程来释放自旋锁，只是不在同一个CPU而已。
当CPU不持有任何自旋锁的时候，xv6会重新开启中断，它必须做点簿记(book-keeping)来复制嵌套的临界区。acquire调用push_off，release调用pop_off来记录当前CPU上锁的嵌套层级。当记数为0，pop_off将恢复临界区最外层的中断状态。intr_off和intr_on分别执行RISC-V指令来关闭和开启中断。
acquire在设置lk->locked之前直接调用push_off是非常重要的。如果颠倒了两者的次序，当中断使能的情况下持有锁会有一个明显的窗口，这时如果发生计时器中断将锁死系统。同样地，release也要在释放锁后调用pop_off。
指令与访存排序
认为程序执行的次序就如源代码所显示的那样是很自然的。但是很多编译器和CPU为了实现更高的性能不按次序执行代码。对于需要多个周期才能完成的指令，CPU可能会提前发射这个指令，让它与其它指令重叠，以避免空等。例如，CPU在一个指令序列里可能会发现A和B不相互依赖。CPU可能会先执行指令B，也许是因为A的输入之前它的输入已经就绪，也许是为了重叠执行A和B。编译器也可能进行类似的重新排序。
编译器和CPU按其它次序执行要遵守的规则是，不能改变正常次序下执行的结果。但是，这个规则会改变并发代码的结果，并且很容易引发多处理器上的错误行为。CPU的次序规则被称为内存模型(memory model)。
如果编译器或CPU把临界区的代码放到临界区外执行，这就会引发灾难。
为了避免那样的问题，xv6在acquire和release里使用了__sync_synchronize()。__sync_synchronize()是一个内存屏障(memory barrier)：它告诉编译器不要跨屏障重新排序load和store。xv6的acquire和release的屏障在几乎所有重要的情况下强制了次序，因为xv6使用锁访问共享数据。
睡眠锁
有时xv6需要长时间持有锁。例如文件系统在读写一个文件在硬盘上的内容的时候要保持它的锁，这样的磁盘操作可能需要几十个毫秒。那么长时间持有自旋锁将导致浪费，因为其它想获取这个锁的进程会长时间地浪费CPU。自旋锁的另一个缺点是当进程持有锁的时候不可以让出CPU，我们会希望持有锁的进程在等待磁盘的时候其它进程可以使用这个CPU。持有自旋锁的时候让出CPU是非法的，因为其它线程想获取这个自旋锁的时候会触发死锁；因为acquire不让出CPU，第二个线程的自旋可能会阻止第一个线程运行和释放锁。持有锁的时候让出CPU也违背了持有自旋锁的时候必须关闭中断这一规定。所以我们就需要有一种锁，当等待获取的时候让出CPU，且持有锁的时候也允许yield和中断。
xv6提供了那样的锁，即睡眠锁。acquiresleep在等待的时候让出CPU，它使用的技术详见“调度”那一章。从较高的层面来看，睡眠锁有一个通过自旋锁保护的locked字段，acquiresleep调用sleep自动让出CPU并释放自旋锁。结果是acquiresleep等待的时候其它线程得以执行。
因为睡眠锁让中断打开了，它们不可以在中断处理例程中使用。因为acquiresleep可能让出CPU，睡眠锁不以在自旋锁的临界区内使用(但自旋锁可以在睡眠锁的临界区内使用)。
自旋锁适合于短的临界区，因为等待它们要浪费CPU时间；睡眠锁适合于长的操作。