总的来说，这个题目的要求是细化自由表的互斥锁粒度：在原版的xv6中，所有CPU共享一个自由表，因此当多个CPU同时运行多个进程时，且这些进程同时调用 kalloc() 和 kfree() 时会被频繁地阻塞，效率十分低下。我们要做的就是为每个CPU创建一个专属的自由表，同时为每个自由表设置专属的互斥锁，以允许不同CPU上的进程并行地调用 kalloc() 和 kfree()。由于地址空间被分散至各个CPU所有，我们还需要设计一个“借用”函数，当某个CPU的自由表用尽时，从其他CPU的自由表处借用空间。
首先更改自由表的定义，将 kmem 改为大小为 NCPU 的数组：
struct mem {
struct spinlock lock;
struct run *freelist;
} kmem[NCPU];
而后，为 kmem[] 中的所有自由表分配一个互斥锁并为这些锁命名（可以通过 snprintf 得到格式化字符串，也可以直接为所有锁取相同的名字）：
void
kinit()
{
for (int i = 0; i < NCPU; ++i) {
char name[6] = {'k', 'm', 'e', 'm', '0' + i, 0};
initlock(&kmem[i].lock, name);
}
// initlock(&kmem.lock, "kmem");
freerange(end, (void*)PHYSTOP);
}
而后，我们先修改内存的回收，因为这个步骤不会涉及到CPU之间的内存借取。这里我们定义了一个辅助函数帮助我们获取CPU的编号，这是因为xv6中 mycpu() 的返回值是不稳定的，必须在每次调用时（通过 push_off() 和 pop_off()）关闭中断以确保其正确性，通过辅助函数我们以可以增加代码的可读性。随后，我们在每次调用 kfree() 时获取调用进程所在CPU的编号，获取对应的互斥锁，并将空闲内存回收至相应的自由表即可：
// Safely get the current cpuid.
int
cpuids()
{
int id;
push_off();
id = cpuid();
pop_off();
return id;
}
// Free the page of physical memory pointed at by v,
// which normally should have been returned by a
// call to kalloc(). (The exception is when
// initializing the allocator; see kinit above.)
void
kfree(void *pa)
{
// ...
int id = cpuids();
struct mem *nmem = kmem + id;
acquire(&nmem->lock);
r->next = nmem->freelist;
nmem->freelist = r;
release(&nmem->lock);
}
接着我们实现因涉及借取而相对复杂一些的 kalloc 函数，我们不妨假设 steal(int id) 可以从其他CPU处借得一页，那么 kalloc() 的修改也十分简单了：将所有涉及自由表的代码修改为使用对应CPU的自由表，当自由表为空时，调用 steal() 以借得内存即可：
void *
kalloc(void)
{
// ...
r = kmem[id].freelist;
if(r)
kmem[id].freelist = r->next;
else {
steal(id);
r = kmem[id].freelist;
if (r)
kmem[id].freelist = r->next;
}
release(&kmem[id].lock);
// ...
}
接着我们实现 steal 函数，这里我们采取比较简单的逻辑，即遍历所有CPU的自由表，从第一个有空闲页面的CPU处借取即可。
void
steal(int id) {
for (int i = 0; i < NCPU; ++i) {
if (i == id)
continue;
struct run *r;
acquire(&kmem[i].lock);
r = kmem[i].freelist;
if (!r) {
release(&kmem[i].lock);
continue;
}
kmem[i].freelist = r->next;
release(&kmem[i].lock);
// acquire(&kmem[id].lock);
r->next = kmem[id].freelist;
kmem[id].freelist = r;
// release(&kmem[id].lock);
return;
}
}
一个要注意的点是被我注释掉的互斥锁，由于我们在 kalloc() 中调用 steal() 时已经锁定了 kmem[id].lock（借用者），因此不能再次锁定；此外，无需考虑系统初始化时的内存问题，因为 kinit() 一定会将所有内存分配至该进程所在的CPU的自由表内，而其他CPU总是能向这个CPU借内存的。
迄今为止遇到的最 HARD 的题目（汗）。做这道题建议你先充分理解题目的要求之后再开始写代码。
如题所示，在原先的xv6中，块缓冲（即buffer cache，下同）在分配时存放于数组（即 bcache.buf[]）当中，在访问和管理时是通过一个链表来实现的，而整张链表由一个互斥锁来进行管理，无论是对块缓冲进行存取，抑或是对块缓冲进行管理，如替换等，都需要首先获取这个互斥锁以保证不变量（invariant)。本题的主要目标就是通过对粒度的细化，从而实现对互斥锁的竞争现象减少。测试程序 bcachetest 通过统计进程因等待相应的互斥锁而休眠的次数来量化这一点。