竞争

作为为什么我们需要锁的一个例子，考虑两个进程，它们的子进程已经退出，在两个不同的 CPU 上调用 wait。wait 会释放子进程的内存。因此，在每个 CPU 上，内核都会调用 kfree 来释放子进程的内存页。内核分配器维护一个链表：kalloc() 从一个空闲页列表中弹出一个内存页，而 kfree() 将一个页推入空闲列表。为了获得最佳性能，我们可能希望两个父进程的 kfrees 能够并行执行，而无需等待对方，但考虑到 xv6 的 kfree 实现，这是不正确的。

图~\ref{fig:smp} 更详细地说明了这种情况：空闲页的链表位于由两个 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; // (1)
  list = l;  // (2)
}

如果单独执行，这个实现是正确的。但是，如果多个副本并发执行，代码就不正确了。如果两个 CPU 同时执行 push，它们都可能在执行第 (2) 行之前执行第 (1) 行，如图~\ref{fig:smp} 所示，这将导致图~\ref{fig:race} 所示的错误结果。这样就会有两个列表元素的 next 被设置为 list 的旧值。当两个对 list 的赋值发生在第 (2) 行时，第二个赋值会覆盖第一个；第一个赋值所涉及的元素将丢失。

第 (2) 行的更新丢失是竞争的一个例子。竞争是指一个内存位置被并发访问，并且至少有一个访问是写操作的情况。竞争通常是错误的标志，要么是更新丢失（如果访问是写操作），要么是读取了未完全更新的数据结构。竞争的结果取决于编译器生成的机器代码、两个相关 CPU 的时序以及内存系统如何对它们的内存操作进行排序，这使得由竞争引起的错误难以重现和调试。例如，在调试 push 时添加打印语句可能会改变执行的时序，从而使竞争消失。

避免竞争的常用方法是使用锁。锁确保互斥，以便一次只有一个 CPU 可以执行 push 的敏感代码行；这使得上述情况不可能发生。正确加锁的上述代码版本只添加了几行（以黄色突出显示）：

struct element *list = 0;
struct lock listlock;

void
push(int data)
{
  struct element *l;
  l = malloc(sizeof *l); // (1)
  l->data = data;

  acquire(&listlock); 
  l->next = list;     // (2)
  list = l;           // (3)
  release(&listlock); 
}

acquire 和 release 之间的指令序列通常被称为临界区。通常说锁在保护 list。

当我们说一个锁保护数据时，我们真正的意思是锁保护了适用于该数据的一些不变量集合。不变量是数据结构在操作中保持的属性。通常，一个操作的正确行为取决于操作开始时不变量为真。操作可能会暂时违反不变量，但必须在完成前重新建立它们。例如，在链表的情况下，不变量是 list 指向列表中的第一个元素，并且每个元素的 next 字段指向下一个元素。 push 的实现暂时违反了这个不变量：在第 (2) 行中， l 指向下一个列表元素，但 list 还没有指向 l （在第 (3) 行重新建立）。我们上面研究的竞争发生是因为第二个 CPU 在列表不变量被（暂时）违反时执行了依赖于这些不变量的代码。正确使用锁可以确保一次只有一个 CPU 可以在临界区内操作数据结构，这样就不会有 CPU 在数据结构的不变量不成立时执行数据结构操作。

你可以把锁看作是序列化并发的临界区，使它们一次一个地运行，从而保持不变量（假设临界区在隔离状态下是正确的）。你也可以认为由同一个锁保护的临界区彼此之间是原子的，这样每个临界区只能看到来自早期临界区的完整变更集，而永远不会看到部分完成的更新。

虽然锁对于正确性很有用，但它们天生会限制性能。例如，如果两个进程同时调用 kfree，锁将序列化这两个临界区，因此在不同的 CPU 上运行它们没有任何好处。我们说，如果多个进程同时想要同一个锁，它们就会发生冲突，或者说锁经历了争用。内核设计中的一个主要挑战是避免锁争用以追求并行性。Xv6 在这方面做得很少，但复杂的内核会专门组织数据结构和算法来避免锁争用。在列表的例子中，一个内核可能会为每个 CPU 维护一个单独的空闲列表，并且只有在当前 CPU 的列表为空并且必须从另一个 CPU 窃取内存时才接触另一个 CPU 的空闲列表。其他用例可能需要更复杂的设计。

锁的放置对性能也很重要。例如，在 push 中将 acquire 移到更早的位置，在第 (1) 行之前是正确的。但这可能会降低性能，因为这样一来，对 malloc 的调用就会被序列化。下面的“使用锁”一节提供了一些关于在何处插入 acquire 和 release 调用的指导方针。

竞争 ​

竞争