6.s081 Lab7 Lock

MIT6.s081
lab
发布日期:   2023-11-01

这个 lab 就是对原先的并发控制进行优化。

Preparation

切换到对应分支

$ git fetch
$ git checkout lock
$ make clean

Task1: Memory allocator

原来的内存分配模块持有一把大锁，每当要分配内存时都会将大锁锁定，直至分配完成。这样对多核的机器并不是很友好，因为每个 CPU core 都需要在大锁上竞争，造成资源浪费。

一种优化策略是，将空闲的内存划分为 CPU core 数量的区域，每个 core 对应整个空闲链表的一部分，且各自维护相应的锁，不同 core 只需要在自己负责那部分即可。当然有的 core 上运行的进程可能需要多个页，一旦自己那部分空闲内存不够了，就需要从其他 core 的空闲内存中「窃取」一页出来。

毕竟闲着也是闲着，不如最大化利用。

kernel/kalloc.c
...
// NCPU 个 freelist 与 lock
struct {
  struct spinlock lock;
  struct run *freelist;
} kmems[NCPU];
...
void
kinit()
{
  for (int i = 0; i < NCPU; i++) {
    initlock(&kmems[i].lock, "kmem"); // 初始化所有 kmem
  }
  ...
}

void
kfree(void *pa)
{
  // 将原本的 kmem 改为 kmems[cpu_id] 即可
}

void *
kalloc(void)
{
  ...
  // 从当前 core 开始遍历所有 core 负责的 kmem
  // 直到找到一个有空闲页的 kmem，直接拿来用
  // 最后 kfree 会将该页加到当前 core 的 kmem 里
  for (int i = 0; i < NCPU; i++) {
    acquire(&kmems[cpu_id].lock);
    r = kmems[cpu_id].freelist;
    if (r) {
      kmems[cpu_id].freelist = r->next;
    }
    release(&kmems[cpu_id].lock);
    if (r) {
      break;
    }
    cpu_id = (cpu_id+1)%NCPU;
  }
  ...
}

Task2: Buffer cache

这个 task 也是对并发控制进行优化，只不过针对的是磁盘块在内存中的 cache。kernel/bio.c 里有相关实现，结构体 bcache 内部维护了一个双向链表，用于支持 LRU 策略。同样的，每次操作都要对大锁进行竞争。

由于每个 disk block 都有各自的块号 blockno，那么可以划分为不同的 "bucket"，根据 blockno 映射到不同的 bucket，每个 bucket 有一把锁，这样就减少了竞争。

同时，根据 kernel/trap.c 里的 ticks 变量，我们也可以为每个 block 增加一个 timestamp 字段，用于标识最后访问该块的时间戳，这样就不需要双向链表来做 LRU 了，每次 victim 的时候找到 timestamp 最小的 block 即可。

kernel/buf.h
// 移除了 prev 和 next 字段，新增 timestamp 字段
struct buf {
  int valid;   // has data been read from disk?
  int disk;    // does disk "own" buf?
  uint dev;
  uint blockno;
  struct sleeplock lock;
  uint refcnt;
  uint timestamp; // (!new)
  uchar data[BSIZE];
};
kernel/bio.c
#define NBUCKETS 5

struct {
  struct spinlock lock;
  struct buf buf[NBUF]; // 这里相当于做了个 tricky，单纯增加 Cache 容量来降低 miss 概率
} bcache[NBUCKETS];

void
binit(void)
{
  struct buf *b;
  for (int i = 0; i < NBUCKETS; i++) {
    initlock(&bcache[i].lock, "bcache");
    for(b = bcache[i].buf; b < bcache[i].buf+NBUF; b++){
      initsleeplock(&b->lock, "buffer");
      b->timestamp = 0;
    }
  }
}

static struct buf*
bget(uint dev, uint blockno)
{
  struct buf *b;
  uint bucketno = blockno % NBUCKETS;
  uint earliest = __INT_MAX__;
  uint idx = -1;

  acquire(&bcache[bucketno].lock);
  for(int i = 0; i < NBUF; i++){
    b = &bcache[bucketno].buf[i];
    if (b->dev == dev && b->blockno == blockno) {
      // 意味着缓存命中
    }

    // 同时也进行 LRU 策略，如果 miss 就可以直接用，不用再次 for 遍历
    if (b->refcnt == 0 && b->timestamp < earliest) {
      earliest = b->timestamp;
      idx = i;
    }
  }

  if (idx != -1) { // 意味着有 block 被 victim，且就在 buf[idx] 处
    ...
  }

  panic("bget: no buffers");
}

void
brelse(struct buf *b)
{
  ...
  if (--b->refcnt == 0) {
    b->timestamp = 0; // 将其置 0，以便 victim
  }
}

void
bpin(struct buf *b) {
  // 根据 b->blockno 映射到 bucket
}

void
bunpin(struct buf *b) {
  // 根据 b->blockno 映射到 bucket
}

测试结果

$ make grade
...
== Test running kalloctest ==
$ make qemu-gdb
(70.1s)
== Test   kalloctest: test1 ==
  kalloctest: test1: OK
== Test   kalloctest: test2 ==
  kalloctest: test2: OK
== Test kalloctest: sbrkmuch ==
$ make qemu-gdb
kalloctest: sbrkmuch: OK (10.5s)
== Test running bcachetest ==
$ make qemu-gdb
(8.7s)
== Test   bcachetest: test0 ==
  bcachetest: test0: OK
== Test   bcachetest: test1 ==
  bcachetest: test1: OK
== Test usertests ==
$ make qemu-gdb
usertests: OK (134.2s)
== Test time ==
time: OK
Score: 70/70

最后的工作

  1. git commit -am "" 将所有修改提交到本地;
  2. 执行 make handin。由于 lab0 保存了 APIKey，故直接成功提交；

可选的挑战再说吧，没有什么想做的欲望。

MIT6.s081
  目录