前面的很多实验中都涉及到了加锁的问题。锁作为一种互斥机制，对于开发者而言实现简单，理解其行为也不复杂，且能提供可靠的互斥保障。但过多的加锁操作会显著地降低系统的并行性，从而使得多处理机系统无法发挥其应有的性能。本部分实验中，主要涉及对于加锁机制的优化，从而增加 xv6 内核的并行性。

首先切换到 lock 分支

8.1 实现每个 CPU 独占的内存分配器

第一部分涉及到内存分配的代码，xv6 将空闲的物理内存 kmem 组织成一个空闲链表 kmem.freelist，同时用一个锁 kmem.lock 保护，所有对 kmem.freelist 的访问都需要先取得锁，所以会产生很多竞争。解决方案也很直观，给每个 CPU 单独开一个 freelist 和对应的 lock，这样只有同一个 CPU 上的进程同时获取对应锁才会产生竞争。

需要注意的是，每个 CPU 的 freelist 是从 kmem 的全局 freelist 中分离出来的，因此每个 CPU 仍然可以访问所有的物理内存。只是在分配内存时，系统会优先考虑当前 CPU 的 freelist，从而避免多个 CPU 之间的竞争，提高内存分配的效率。

<aside> 💡 资源重复设置与减小加锁开销

从另一个角度看，这里为每个 CPU 设置一个内存分配器属于资源的重复设置。通过重复设置资源，可以使得进程直接获得锁而无需等待的概率大大提高，从而降低了进程等待时间的期望值，故整个系统的效率能够得到提高。但是，资源重复设置可能会引起诸如数据一致性等问题，故而会大大增加软件的复杂度。

</aside>

所以我们首先修改 kalloc.c 中的数据结构，使单一的空闲链表变为多个空闲链表的数组：

struct {
  struct spinlock lock;
  struct run *freelist;
} kmem[NCPU];

同时得修改对应的 kinit 和 kfree 的代码以适应数据结构的修改：

kinit 需要初始化每个 CPU 的空闲链表和锁：

void
kinit()
{
  char buf[10];
  for (int i = 0; i < NCPU; i++)
  {
    snprintf(buf, 10, "kmem_CPU%d", i);
    initlock(&kmem[i].lock, buf);
  }
  freerange(end, (void*)PHYSTOP);
}

<aside> 💡 调用 freerange 的 CPU 会在初始化时获得所有的空闲页面，不过无需担心分配不均，这些页面会在一次次的 kalloc() 和 kfree() 的过程中进入其它 CPU 的空闲链表中。

</aside>

具体分析如下：

首先定义一个 char 类型的数组 buf，用于存储每个 CPU 对应的锁的名称。
然后使用 for 循环为每个 CPU 分配一个独立的 freelist 和对应的锁。循环的次数是 NCPU，即 CPU 的数量。
在循环中，使用 snprintf 函数将 CPU 的编号与字符串 "kmem_CPU" 连接起来，生成一个字符串 buf，用于作为锁的名称。
然后调用 initlock 函数，为当前 CPU 的 freelist 分配一个锁，并将锁的名称设置为 buf。initlock 函数是 xv6 中的一个锁初始化函数，用于初始化一个互斥锁。
循环结束后，调用 freerange 函数，将空闲的物理内存块添加到全局 freelist 中。该函数用于将一段物理内存块添加到 freelist 中，以便后续的内存分配操作可以从 freelist 中获取空闲的物理内存块。

对分配内存的 kalloc() 修改完成后，我们还需要修改对应的用于释放内存的 kfree() ，直接将页面加入到当前的 CPU 空闲链表中（即便是借来的页面，也不归还了），实现如下：