Lab8 Locks

两个实验，难度为 moderate 与 hard。

Memory allocator

这个实验的背景如下：

xv6 原本是使用一个空闲页面链表，但是这样就会导致不同 CPU 上的kalloc和kfree会产生锁争用，内存页面的分配被完全串行化了，降低了系统的性能。而一个改进策略就是为每个 CPU 核心分配一个空闲链表，kalloc和kfree都在本核心的链表上进行，只有当当前核心的链表为空时才去访问其他核心的链表。通过这种策略就可以减少锁的争用，只有当某核心的链表为空时才会发生锁争用。

我们要实现的就是这样一个改进策略。

首先，我们需要对 kmem 进行更改，每个 CPU 都要给一个锁，这样就有 NCPU 个 kmem ：

1
struct {
2
  struct spinlock lock;
3
  struct run* freelist;
4
  char lockname[10];
5
} kmem[NCPU];

这个 NCPU 是一个已被定义的宏。

随后，我们需要对每个锁都做一个初始化，锁的名称可以使用 snprintf 来传入：

1
void
2
kinit() {
3
  for (int i = 0;i < NCPU;i++) {
4
    snprintf(kmem[i].lockname, sizeof(kmem[i].lockname), "kmem_%d", i);
5
    initlock(&kmem[i].lock, kmem[i].lockname);
6
  }
7
  freerange(end, (void*)PHYSTOP);
8
}

这样，我们就完成了前置工作。

我们首先对 kfree() 进行修改（因为比较简单显然，不需要对其他 CPU 的 freelist 做什么操作）

1
void
2
kfree(void* pa) {
3
  struct run* r;
4

5
  if (((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
6
    panic("kfree");
7

8
  // Fill with junk to catch dangling refs.
9
  memset(pa, 1, PGSIZE);
10

11
  r = (struct run*)pa;
12

13
  // add code here
14
  push_off();
15
  int id = cpuid();
16

17
  acquire(&kmem[id].lock);
18
  r->next = kmem[id].freelist;
19
  kmem[id].freelist = r;
20
  release(&kmem[id].lock);
21

22
  pop_off();
23
}

这里注意 hint 中的说明，我们需要关闭中断才能进行操作。

对于 kalloc() 我们在页面不够的时候还需要去其他 CPU 的 freelist 上偷点来，具体偷多少对系统的性能是有很大影响的（这点在 kalloctest 的 test2 中有体现），如果我们每次只偷一页来，那么如果需要申请的内存比较多的话，就会频繁的使用锁，从而造成性能的降低。

当然，如果只想把实验过掉，那么每次偷一页是可行的，如下：

1
void*
2
kalloc(void) {
3
  struct run* r;
4

5
  // add code here
6

7
  push_off();
8
  int id = cpuid();
9

10
  acquire(&kmem[id].lock);
11
  r = kmem[id].freelist;
12
  if (r)
13
    kmem[id].freelist = r->next;
14
  else {
15
    int flag = 0;
16
    for (int i = 0;i < NCPU; i++) {
17
      if (i == id)
18
        continue;
19
      acquire(&kmem[i].lock);
20
      if (kmem[i].freelist) {
21
        struct run* p = kmem[i].freelist;
22
        kmem[i].freelist = p->next;
23
        kmem[id].freelist = p;
24
        p->next = 0;
25
        flag = 1;
26
      }
27
      release(&kmem[i].lock);
28
      if (flag)
29
        break;
30
    }
31
    r = kmem[id].freelist;
32
    if (r)
33
      kmem[id].freelist = r->next;
34
  }
35
  release(&kmem[id].lock);
36
  pop_off();
37

38
  if (r)
39
    memset((char*)r, 5, PGSIZE); // fill with junk
40
  return (void*)r;
41
}