柳暗花明，又一村
⭐学习课程
XV6的锁和并行

XV6的锁和并行

March 4, 2025
<p>性能快 -&gt; 性能慢</p>

硬件的提升

其实早在 21 世纪初的时候 CPU 的单核的性能可以说到达了一个瓶颈，单个 CPU 已经不可以满足需求了，计算机科学家们需要找一个突破瓶颈的方法。我们的需求是什么，要更加快速的性能和计算能力，有一个比较：如果强行给一个 CPU 提升性能，那么它的功耗也是增加的而且加得很多，但新加入一个 CPU 不仅仅提升了性能，而且功耗增加在接受范围，因此，多核的时代来临了。

为什么要使用锁

首先，为什么在多核系统中我们需要锁？锁又是什么东西？这要从应用程序想要使用多个 CPU 核开始。我们知道使用多个 CPU 核可以带来性能的提升，如果一个应用程序运行在多个 CPU 核上，并且执行了系统调用，那么内核需要能够处理并行的系统调用。如果系统调用以并行的方式运行在多个 CPU 核上，那么它们可能会并行的访问内核中共享的数据结构或是数据。当并行的访问数据结构时，例如：一个核在读取数据，另一个核在写入数据，我们需要使用锁来协调对于共享数据的更新，以确保数据的一致性。所以，我们需要锁来控制并确保共享的数据是正确的。

但是实际的情况有些令人失望，因为我们想要通过并行来获得高性能，我们想要并行的在不同的 CPU 核上执行系统调用，但是如果这些系统调用使用了共享的数据，我们又需要使用锁，而锁又会使得这些系统调用串行执行，所以最后锁反过来又限制了性能。

所以现在我们处于一个矛盾的处境，出于正确性，我们需要使用锁，但是考虑到性能，锁又是极不好的。这就是我说的 性能越快 -> 性能越慢 。

首先，我们需要了解一下锁用在哪里？前面说锁是控制并确保共享的数据 的 标志 。这个数据是什么？其实说锁像标志不如像一个仓库管理员，一旦有人来改变仓库的东西都要 他 出面管理防止出问题。

来看 xv6 中的 kfree() :

acquire(&kmem.lock)
r->next = kmem.freelist;
kmem.freelist = r;
release(&kmem.lock)

其中，在锁的 acquire 和 release 之间的代码，通常被称为critical section。它就是我们要管理的数据

为了确保数据的正确性，我们用锁来管理 critical section 区。当一份共享数据同时被读写时，如果没有锁的话，可能会出现 race condition （竞争条件），进而导致程序出错。如：在 r->next = kmem.freelist; 中 CPU0 和 CPU1 同时进行，那么 r->next 可能指向的是 CPU0 的数据，也可能是 CPU1 的数据，这里会出现使我们不愿意看到的巨大错误。

race condition 是比较讨厌的，值得一提的是 race condition 可以有不同的表现形式，并且它可能发生，也可能不发生。我们不希望发生。

接下来让就具体的介绍一下锁。锁就是一个对象，就像其他在内核中的对象一样。有一个结构体叫做lock，它包含了一些字段，这些字段中维护了锁的状态。锁有非常直观的 API：

  • acquire，接收指向 lock 的指针作为参数。acquire 确保了在任何时间，只会有一个进程能够成功的获取锁。
  • release，也接收指向 lock 的指针作为参数。在同一时间尝试获取锁的其他进程需要等待，直到持有锁的进程对锁调用 release。

所以，用锁来避免数据结构的资源竞争（race condition）和保护资源。

什么时候使用锁

在使用锁之前要了解一个机制 — 原子操作（atomic operation）。 简单来讲，一般在程序中 i+=1 有三个动作：

ld  t0, 0(a0)
addi t0, t0, 1
sd  t0, 0(a0)

原子操作就是把这三个操作由一个操作完成。

而之前的被保护的数据之所以被称为 critical section，是因为通常会在这里以原子的方式执行共享数据的更新。所以基本上来说，如果在 acquire 和 release 之间有多条指令，它们要么会一起执行，要么一条也不会执行。所以（CPU）永远也不可能看到位于 critical section 中的具体代码，反之，在 race condition 中多个 CPU 在 critical section 区上交织的执行。所以这样就能避免 race condition。

现在的程序通常会有许多锁。实际上，XV6中就有很多的锁。为什么会有这么多锁呢？因为锁序列化了代码的执行。如果两个处理器想要进入到同一个 critical section 中，只会有一个能成功进入，另一个处理器会在第一个处理器从 critical section 中退出之后再进入。所以这里以串行执行完全没有并行执行。

如果让内核中只有一把大锁，我们暂时将之称为 big kernel lock。基本上所有的系统调用都会被这把大锁保护而被序列化。系统调用会按照这样的流程处理：一个系统调用获取到了 big kernel lock，完成自己的操作，之后释放这个 big kernel lock，再返回到用户空间，之后下一个系统调用才能执行。这样的话，如果我们有一个应用程序并行的调用多个系统调用，这些系统调用会串行的执行，因为我们只有一把锁。所以通常来说，例如 XV6的操作系统会有多把锁，这样就能获得某种程度的并发执行。如果两个系统调用使用了两把不同的锁，那么它们就能完全的并行运行。

很明显，锁限制了并发性，也限制了性能。没有很好的规则来规定锁的使用。如：如果两个进程访问了一个共享的数据结构，并且其中一个进程会更新共享的数据结构，那么就需要对于这个共享的数据结构加锁。 矛盾的是，有时候这个规则太过严格，而有时候这个规则又太过宽松了。除了共享的数据，在一些其他场合也需要锁，例如对于 printf，如果我们将一个字符串传递给它，XV6会尝试原子性的将整个字符串输出，而不是与其他进程的 printf 交织输出。尽管这里没有共享的数据结构，但在这里锁仍然很有用处，因为我们想要 printf 的输出也是序列化的。

因此，锁应该与操作而不是数据关联，和操作的顺序相关。

锁的特性和死锁

  • 锁可以避免丢失更新。如果你回想我们之前在 kalloc.c 中的例子，丢失更新是指我们丢失了对于某个内存 page 在 kfree 函数中的更新。如果没有锁，在出现 race condition 的时候，内存 page 不会被加到 freelist 中。但是加上锁之后，我们就不会丢失这里的更新。
  • 锁可以让操作具有原子性。我们之前介绍了加锁解锁之间的区域是 critical section，在 critical section 的所有操作会都会作为一个原子操作执行。
  • 锁可以维护共享数据结构的**不变性**。共享数据结构如果不被任何进程修改的话是会保持不变的。如果某个进程acquire了锁并且做了一些更新操作，共享数据的不变性暂时会被破坏，但是在release锁之后，数据的不变性又恢复了。
<p>数据结构的<strong>不变性</strong>是在不同的 CPU 中相对的，比如：CPU0 改变了某数据结构对它而言是变化的，但对于 CPU1 看到的就是不变的</p>

死锁（Deadlock），在用锁的时候经常遇到，一个死锁的最简单的场景就是：首先 acquire 一个锁，然后进入到 critical section；在 critical section 中，再 acquire 同一个锁；第二个 acquire 必须要等到第一个 acquire 状态被 release 了才能继续执行，但是不继续执行的话又走不到第一个 release，所以程序就一直卡在这了。这就是一个死锁。让我想起著名的哲學家就餐問題。还有一个现实场景：堵车。

死锁的解决方案是：如果你有多个锁，你需要对锁进行排序，所有的操作都必须以相同的顺序获取锁。然后以相同的顺序丢弃锁。

锁与性能

我们想要获得更好的性能，那么我们需要有更多的锁，但是这又引入了大量的工作。

通常来说，开发的流程是：

  • 先以coarse-grained lock（大锁）开始。
  • 再对程序进行测试，来看一下程序是否能使用多核。
  • 如果可以的话，那么工作就结束了，你对于锁的设计足够好了；如果不可以的话，那意味着锁存在竞争，多个进程会尝试获取同一个锁，因此它们将会序列化的执行，性能也上不去，之后你就需要重构程序。

在这个流程中，测试的过程比较重要。有可能模块使用了coarse-grained lock，但是它并没有经常被并行的调用，那么其实就没有必要重构程序，因为重构程序设计到大量的工作，并且也会使得代码变得复杂。所以如果不是必要的话，还是不要进行重构。

实现锁

我在这里有具体的笔记。 一定要注意的点是： !!! 不要把锁变成 critical section 区 !!! !!! 不要把锁变成 critical section 区 !!! !!! 不要把锁变成 critical section 区 !!!

所以 spinlock 需要处理两类并发，一类是不同 CPU 之间的并发，一类是相同 CPU 上中断和普通程序之间的并发 我们需要在 acquire 中关闭中断。

Sleep & Wakeup

Sleep 函数中最后一件事情就是重新获取 condition lock。

总结

硬件性能瓶颈是指当单个 CPU 核的性能已经不能满足应用程序的需求时，计算机科学家们需要寻找突破瓶颈的方法。多核系统中的锁用于控制并确保共享数据的更新，以确保数据的一致性。然而，锁也会限制性能，因为它会使得系统调用串行执行。为了解决这个问题，我们可以考虑使用更多的锁，以便在某种程度上获得并发执行。但是，这会引入大量的工作，因此需要对锁的设计和使用进行充分考虑。

在实际应用中，我们可以通过测试程序来判断是否需要重构锁的设计，如果程序可以并行执行，那么锁的设计可能足够好；如果不能，那么需要对锁进行重构，以提高并发性能。

总之，硬件性能瓶颈推动了计算机科学家们寻找突破方法，而锁是一种解决共享数据竞争的方法。然而，锁也会限制性能，因此需要在设计和使用中进行充分考虑。

使用锁的原因主要有以下几点：

  1. 保证资源共享性：当多个线程同时访问共享资源时，使用锁可以确保资源在同一时间只被一个线程访问，从而避免资源不同步和错误。
  2. 避免资源竞争：当多个线程同时访问共享资源时，可能导致资源竞争，导致未预期的结果。使用锁可以避免资源竞争，确保资源的正确使用。
  3. 提高代码可重用性：使用锁可以将多线程访问的代码封装成一个线程安全的单元，从而提高代码的可重用性。
  4. 降低开发难度：使用锁可以简化编程者需要关注的事物，降低开发难度。
  5. 保证线程安全：使用锁可以确保程序中的线程安全问题，避免因线程不安全导致的错误和异常。
最后更新于
XV6的进程和线程XV6 的中断