MIT 6.S081 实验8：locks 笔记与心得

Lab 8: locks

实验准备

在这个实验室中，你将获得重新设计代码以提高并行性的经验。在多核机器上并行性差的一个常见症状是高锁争用。提高并行性通常需要改变数据结构和锁策略，以减少争用。你将为xv6内存分配器和块缓存做这件事。

在编写代码之前，请确保阅读xv6书中的以下部分。

• 第6章："锁定 "和相应的代码。
• 第3.5节：“代码。物理内存分配器”
• 第8.1节到8.3节：“概述”、"缓冲区缓存层 "和 “代码。缓冲区高速缓存”

内存分配器

题目翻译

user/kalloctest程序强调xv6的内存分配器：三个进程增加和减少他们的地址空间，导致对kalloc和kfree的多次调用。 kalloctest打印（作为 “#fetch-and-add”）由于试图获取另一个核已经持有的锁而在aquire中循环迭代的数量，对于kmem锁和其他一些锁。获取中的循环迭代次数是对锁竞争的一个粗略衡量。在你完成实验之前，kalloctest的输出看起来与此相似。

$ kalloctest
start test1
test1 results:
--- lock kmem/bcache stats
lock: kmem: #fetch-and-add 83375 #acquire() 433015
lock: bcache: #fetch-and-add 0 #acquire() 1260
--- top 5 contended locks:
lock: kmem: #fetch-and-add 83375 #acquire() 433015
lock: proc: #fetch-and-add 23737 #acquire() 130718
lock: virtio_disk: #fetch-and-add 11159 #acquire() 114
lock: proc: #fetch-and-add 5937 #acquire() 130786
lock: proc: #fetch-and-add 4080 #acquire() 130786
tot= 83375
test1 FAIL

kalloctest调用一个系统调用，使内核打印出kmem和bcache锁（这是本实验的重点）以及5个争夺最激烈的锁的计数。如果存在锁的争夺，那么获取循环的迭代次数将会很大。系统调用返回kmem锁和bcache锁的循环迭代次数之和。

在这个实验中，你必须使用一台有多个内核的专门的无负载机器。如果你使用一台正在做其他事情的机器，那么kalloctest所打印的计数将是无稽之谈。你可以使用专用的Athena工作站，或者你自己的笔记本电脑，但不要使用拨号机。

kalloctest中锁争用的根本原因是kalloc()有一个单一的自由列表，由一个锁保护。为了消除锁的争夺，你必须重新设计内存分配器，以避免单一的锁和列表。基本的想法是为每个CPU维护一个空闲列表，每个列表有自己的锁。不同CPU上的分配和释放可以并行运行，因为每个CPU将对不同的列表进行操作。主要的挑战是如何处理这样的情况：一个CPU的空闲列表是空的，但另一个CPU的列表有空闲内存；在这种情况下，一个CPU必须 "偷 "走另一个CPU的空闲列表的一部分。偷窃可能会带来锁的争夺，但希望这种情况不常发生。

你的工作是实现每个CPU的自由列表，并在一个CPU的自由列表为空时进行窃取。你必须给你所有的锁起一个以 "kmem "开头的名字。也就是说，你应该为你的每个锁调用initlock，并传递一个以 "kmem "开头的名字。运行kalloctest，看看你的实现是否减少了锁的争夺。为了检查它是否仍然可以分配所有的内存，运行usertests sbrkmuch。你的输出将类似于下图所示，在kmem锁上的争夺大大减少，尽管具体数字会有所不同。确保usertests中的所有测试都通过了。 make grade应该说kalloctests通过了。

：

$ kalloctest
start test1
test1 results:
--- lock kmem/bcache stats
lock: kmem: #fetch-and-add 0 #acquire() 42843
lock: kmem: #fetch-and-add 0 #acquire() 198674
lock: kmem: #fetch-and-add 0 #acquire() 191534
lock: bcache: #fetch-and-add 0 #acquire() 1242
--- top 5 contended locks:
lock: proc: #fetch-and-add 43861 #acquire() 117281
lock: virtio_disk: #fetch-and-add 5347 #acquire() 114
lock: proc: #fetch-and-add 4856 #acquire() 117312
lock: proc: #fetch-and-add 4168 #acquire() 117316
lock: proc: #fetch-and-add 2797 #acquire() 117266
tot= 0
test1 OK
start test2
total free number of pages: 32499 (out of 32768)
.....
test2 OK
$ usertests sbrkmuch
usertests starting
test sbrkmuch: OK
ALL TESTS PASSED
$ usertests
...
ALL TESTS PASSED
$

一些提示:

• 你可以使用kernel/param.h中的常数NCPU
• 让freerange把所有的空闲内存给运行freerange的CPU。
• 函数cpuid返回当前的核心号，但只有在关闭中断时调用它并使用其结果才是安全的。你应该使用 push_off() 和 pop_off() 来关闭和开启中断。
• 看一下kernel/sprintf.c中的snprintf函数，了解一下字符串格式化的想法。不过，把所有的锁命名为 "kmem "也是可以的。

题目答案

该题的主要目的是想让我们将减少kmem锁的竞争，但由于在进行分配内存时，需要对freelist进行修改，为此需要保护该全局变量，但在原来的设计中，只有一个锁对此进行保护，这就造成许多进程对该锁的竞争。为此需要为每一个CPU分配一个自己的freelist，这样就不会出现竞争，这里的难点是理解题意，第一个是让freerange把所有的空闲内存给运行freerange的CPU，我们知道只有kinit函数才会调用该函数，所以只有第一个CPU会调用这个函数，这使得第一个CPU会获得所有的空闲链表，第二个一个CPU必须 "偷 "走另一个CPU的空闲列表的一部分，这就涉及到第二个CPU必须从第一个CPU中取走一部分freelist，这里为了方便只取一半，而当CPU发现自己没有内存就向其他CPU取走，这里需要跳过自己，然后返回获得的free list指针。代码如下：

首先是针对每一个CPU生成一个freelist，对应一个自旋锁：

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

然后初始化所有锁：

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

接着是对kfree中每个CPU的链表进行free：

  acquire(&kmem[id].lock);
  r->next = kmem[id].freelist;
  kmem[id].freelist = r;
  release<