6.1: Races(数据访问竞争)

注释：该内容基于原版课程的textbook和源代码，在大模型辅助翻译的基础上进行的整理。

以下是我们为什么需要锁的一个示例：考虑两个有已退出子进程的进程在两个不同的 CPU 上调用 wait。 wait 会释放子进程的内存。因此，在每个 CPU 上，内核将调用 kfree 来释放子进程的内存页。
内核分配器维护了一个链表：kalloc()（kernel/kalloc.c:69）从空闲页列表中取出（pop）一页内存，
而 kfree()（kernel/kalloc.c:47）将一页内存推入(push)空闲列表。
为了获得最佳性能，我们可能希望两个父进程的 kfree 能并行执行，而不需要相互等待，但考虑到 xv6 的 kfree 实现，这样做并不正确。

注: SMP为一种常见的多处理器架构，所有处理器共享同一个主内存（RAM）和操作系统，可以平等地访问资源。这种架构下的处理器彼此对称，通常用于服务器和高性能计算系统。

上图更详细地说明了这种情形：两个 CPU 共享内存中的空闲页链表，并使用加载和存储指令操作该链表。（实际上，处理器有缓存，但在概念上，多处理器系统的行为就好像存在一个共享的内存。）
如果没有并发请求，你可以实现如下的链表推操作：

1 struct element {
2 int data;
3 struct element *next;
4 };
5
6 struct element *list = 0;
7
8 void
9 push(int data)
10 {
11 struct element *l;
12
13 l = malloc(sizeof *l);
14 l->data = data;
15 l->next = list;
16 list = l;
17 }

此实现如果单独执行是正确的。然而，如果有多个副本并发执行，这段代码就不正确了。如果两个 CPU 同时执行 push 操作，它们都可能在执行第 16 行之前执行第 15 行，
这会导致如图所示的不正确结果。此时，将会有两个链表元素的 next 被设置为 list 的先前值。当第 16 行的两个赋值操作发生时，后一个赋值将覆盖前一个赋值；涉及第一个赋值的元素将会丢失(如图所示的lost)。

上述16行的更新丢失是竞争条件的一个例子。竞争条件指的是一个内存位置被并发访问，并且至少有一次访问是写操作。
竞争条件通常是一个错误的迹象，可能导致更新丢失（如果访问是写操作）或读取尚未完全更新的数据结构。竞争条件的结果取决于编译器生成的机器代码、两个 CPU 的执行时序，以及内存系统对其内存操作的排序，这使得由竞争引起的错误很难重现和调试。
例如，在调试 push 时添加打印语句可能会改变执行的时序，从而使竞争条件消失。

避免竞争条件的常用方法是使用锁。锁可以确保互斥，以便在任意时刻只有一个 CPU 能执行 push 中的关键行；这使得上述场景无法发生。对上述代码进行正确加锁的版本只需添加几行代码（以黄色标出）：

6 struct element *list = 0;

7 struct lock listlock;

8
9 void
10 push(int data)
11 {
12 struct element *l;
13 l = malloc(sizeof *l);
14 l->data = data;
15

16 acquire(&listlock);

17 l->next = list;
18 list = l;

19 release(&listlock);

20 }

在获取和释放之间的指令序列通常被称为临界区。通常来说，我们认为锁在保护链表。

当我们说锁保护数据时，实际上是指锁保护了应用于该数据的一些不变性。不变性是指在各种操作之间保持的数据结构的属性。通常，一个操作的正确行为依赖于在操作开始时这些不变性成立。
操作过程中可能会暂时违反这些不变性，但必须在结束前重新建立。例如，在链表的情况下，不变性是list指向链表的第一个元素，并且每个元素的next字段指向下一个元素。
push的实现暂时违反了这种不变性：在第 17 行，l 指向下一个链表元素，但list尚未指向l（在第 18 行重新建立）。

正确使用锁可以确保一次只有一个 CPU 能在临界区中操作数据结构，从而避免在数据结构不满足不变性时有 CPU 执行操作。
你可以将锁理解为将并发的临界区串行化，使它们一次只运行一个，从而保持不变性（假设临界区在单独执行时是正确的）。
你还可以认为由相同锁保护的临界区在相互之间是原子的，因此每个临界区只能看到之前完整的变更集合，而不会看到部分完成的更新。

虽然锁对于确保正确性非常有用，但它们本质上限制了性能。例如，如果两个进程同时调用 kfree，锁会将两个临界区串行化，从而无法从在不同 CPU 上运行中获益。
我们称多个进程在同一时间想要获取相同锁时为冲突，或者称该锁发生了争用。内核设计中的一个主要挑战是为了实现并行性而避免锁争用。虽然 xv6 在这方面做得不多，但更复杂的内核会专门组织数据结构和算法来避免锁争用。

在链表示例中，内核可能为每个 CPU 维护一个单独的空闲链表，只有当当前 CPU 的链表为空并且必须从其他 CPU 获取内存时，才会访问其他 CPU 的空闲链表。其他用例可能需要更复杂的设计。

锁的放置对于性能也很重要。例如，将 acquire 移到 push 函数中第 13 行之前是正确的，但这可能会降低性能，因为这样会将 malloc 调用串行化。下面的“使用锁”部分提供了一些关于在哪里插入 acquire 和 release 调用的指南。