在多核设备中，存在两个甚至多个 CPU 同时读写同一块内存区域从而破坏数据一致性的可能，即使是在单核处理器中，也存在内核在多个进程中切换从而破坏数据一致性的可能。此外，如果中断发生的时机不当，还存在中断处理程序和被中断代码访问同一块内存区域的可能性。并发性一词指的是由多核处理器并行机制、进程切换或中断所导致的多条指令流交错的情况。

Xv6使用了多种并发控制技术，根据情况而变。本章主要介绍一种广泛使用的技术——锁。锁可以提供互斥性，确保在同一时刻只有一个CPU可以持有锁。如果程序员向被共享的数据加锁，并在使用时始终持有这个锁，那么这些数据同一时刻只能被一个CPU访问。此时我们称这些数据被锁保护了。尽管锁是一种易于理解的并发控制机制，但是这种技术的缺点是性能降低，因为并发操作被锁序列化了。

本章剩余的部分将解释 xv6 为什么需要锁，xv6 如何实现这些锁，以及如何使用它们。

竞争条件

下面是一个例子，向我们展示了为什么需要锁：

考虑位于不同CPU上的两个进程同时调用 wait ，其中 wait 会释放子进程的内存。那么，两个CPU中的每个CPU上，内核都会通过 kfree 来释放子进程的页面。注意内核的分配器维护了一个链表，其中： kalloc() 从空闲页面链表内弹出一个页面的空闲内存，而 kfree() 则将一个被释放的页面推入这个链表中。出于性能考虑，我们也许会希望两个父进程的 kfree 可以并行执行而不需要等待，然而在xv6的 kfree 实现中这样做会导致错误的结果。

Figure 6.1: Simplified SMP(Symmetric Multi-Processor) architecture

Figure 6.1: Simplified SMP(Symmetric Multi-Processor) architecture

图6.1向我们更具体地展示了这个例子的情境：页面链表存放在被两个CPU所共享的内存中，这两个CPU通过读取和存储指令来操控这个链表（实际上，现实中的处理器拥有缓存，但是从概念上来看，它们就好像只有一块被共享的内存）。如果不存在并发请求，你可以像下面的代码一样实现 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;
}

如果在适当的隔离下运行，上述代码不会出现问题。但是，如果多个 push 同时执行，就会出现错误。假设有两个 CPU 同时执行 push 操作，且都运行至上述代码的第 15 行。如果在两个 CPU 都还未执行第 16 行时，它们先后执行了第 15 行的代码，那么就会出现链表的前两个元素都指向原先链表的头部。但此时链表的头部只能指出这两个元素中的一个，即后执行第 16 行的那个，因为它会把先执行的那个 CPU 对链表头部的赋值覆盖。也就是说此时链表中的一个节点无法被访问到了。图 6.2 给出了上述例子中两个 CPU 执行指令的时间顺序的图例。

Figure 6.2: Example race

Figure 6.2: Example race

上面便是竞争条件的一个例子。竞争条件指的是一块内存被并发地访问且其中至少有一次写入的情况。竞争条件的发生往往象征了一个BUG，这个BUG要么是被覆盖的更新（后一个写入将前一个写入覆盖了，如果访问操作是写入的话），要么是脏数据的读取（程序读取了一个旧的数据之后另一个程序立刻将数据覆写）。竞争条件的后果取决于两个CPU执行代码的时机以及存储系统对这些指令的调度，因此由竞争导致的错误难以被定位及复现。比如说在DEBUG时我们在 push 中添加打印语句以进行调试，这有可能改变命令执行的时机，从而令竞争条件消失并最终无法定位到错误的存在。

通过锁，我们可以限制同时只有一个CPU可以可以执行 push 中敏感的代码，要做到这一点，我们只需要在之前的代码上添加几行即可，代码如下：

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);
}

当我们提到锁保护数据时，实际上指的是锁保护了这些数据上的某些不变量。不变量是指数据结构即使在并行指令中仍然保持条件或关系始终为真的性质。我们可以认为锁通过将并行的“关键部分”序列化以保护数据的不变量，或者通过将这些关键部分原子化，从而使其他CPU在数据结构的不变量被暂时释放时，执行与该数据结构有关的操作。

尽管锁的正确使用可以纠正错误的代码，但这是以性能为代价的。例如，如果两个进程并发地调用 kfree，锁将对这两个调用进行序列化，这样我们就无法从它们的多核运行中受益了。如果两个进程同时尝试持有锁，我们称它们发生了冲突，也称为锁竞争。操作系统设计的一个重要挑战是避免这种竞争。在上述链表示例中，内核可以在每个CPU中维护一个链表，且CPU除了在需要从其他CPU获取内存时不访问其他CPU的链表，以避免竞争。

锁的位置同样对性能十分重要。例如，在上述代码中，将 acquire 在 push 的位置提前不会导致代码出错。但是，如果我们将其放在第 13 行之前，由于此时对 malloc 的调用也被序列化了，性能可能会进一步遭到损失。我们将在“使用锁”小节中讨论插入acquire和release的时机。

锁的实现

在 xv6 中有两种锁：自旋锁和休眠锁。我们从自旋锁开始介绍。在 xv6 中，自旋锁被表示为 struct spinlock(kernel/spinlock.h:2)。这个结构体中有一个十分重要的字段 locked，它是一个字符型变量。当它的值为零时，代表这个锁当前是可用的。相反，当它的值不为零时，代表这个锁已被其他人持有。在 xv6 中获取锁的逻辑应该类似于下面的代码：