这次实验中我们将重新设计 xv6 的内存分配和磁盘块缓存机制以提高它们的并行性。并行性的性能可以由锁争用的次数反应出来——差的并行代码会导致高锁争用。

Memory allocator

任务：原本的 kalloc.c 导致高锁争用的原因是 xv6 只维护了一个空闲页面链表，该链表有一个锁。为了减少锁争用，我们可以给每一个 CPU 维护一个空闲页面链表，这样不同 CPU 就可以并行地内存分配和释放，因为它们之间相互独立。但是，当一个 CPU 的空闲页面被分配完之后，它需要从其他的 CPU 的空闲页面链表中窃取一部分空闲页面。窃取过程可能导致锁争用，但是不会很频繁。

我们的任务就是实现每一个 CPU 一个空闲链表，且在链表为空时窃取页面。所有锁的名字必须以 kmem 开头。kalloctest 检测是否减少了锁争用，usertests sbrkmuch 检测是否仍然能够分配所有内存。

首先把原来的一个 kmem 结构体改成一个数组 kmems，使每个 CPU 有一个对应的空闲页面链表：

1
2
3
4
5
// kernel/kalloc.c
struct kmem{
  struct spinlock lock;
  struct run *freelist;
} kmems[NCPU];

然后每个 CPU 分别初始化，这里我偷了个懒，先给 0 号 CPU 分配所有内存，其他 CPU 不分配。由于一个 CPU 没有空闲页面时会去其他 CPU 处窃取，所以我希望足够长时间之后，页面能够大致平均分配开（这其实是一个数学问题……有时间可以研究一下……）。

1
2
3
4
5
6
7
8
9
10
11
// kernel/kalloc.c
void
kinit()
{
  for(int i = 0; i < NCPU; i++){
    initlock(&kmems[i].lock, "kmem");
    freerange(i == 0 ? end : (void*)PHYSTOP, (void*)PHYSTOP);
  }
  /*initlock(&kmem.lock, "kmem");
  freerange(end, (void*)PHYSTOP);*/
}

kalloc 从当前 CPU 空闲页面链表中取一个页面，如果不存在则窃取（steal）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// kernel/kalloc.c
void *
kalloc(void)
{
  struct run *r;
  ...
  push_off(); int ci = cpuid(); pop_off();
  acquire(&kmems[ci].lock);
  r = kmems[ci].freelist;
  if(r)
    kmems[ci].freelist = r->next;
  else // Steal from other CPU when freelist is empty.
    r = steal(ci);
  release(&kmems[ci].lock);
  ...
}

窃取我实现的很暴力，逐一检查各个 CPU 是否有空闲页面，有就窃取过来：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// kernel/kalloc.c
struct run *
steal(int ci)
{
  struct run *r = 0;
  for(int i = 0; i < NCPU; i++){
    if(i == ci) continue;
    acquire(&kmems[i].lock);
    if((r = kmems[i].freelist)){
      kmems[i].freelist = r->next;
      release(&kmems[i].lock);
      break;
    }
    release(&kmems[i].lock);
  }
  return r;
}

Buffer cache

xv6 在 bio.c 中实现了磁盘块的缓存机制，它是一个双向链表，每个元素是一个缓存块。一个缓存块（struct buf, kernel/buf.h）不仅包含数据，还包含有效位 valid、脏位 disk、设备号、磁盘块号、被引用次数等信息。整个双向链表由一个自旋锁保护，每个缓存块都由一个睡眠锁保护。

任务：由于整个缓存双向链表由一个自旋锁保护，所以多个进程反复读不同文件时会产生高锁争用。我们要更改缓存机制以减少锁争用。