这个 lab 就是对原先的并发控制进行优化。
Preparation
切换到对应分支
1$ git fetch
2$ git checkout lock
3$ make clean
Task1: Memory allocator
原来的内存分配模块持有一把大锁，每当要分配内存时都会将大锁锁定，直至分配完成。这样对多核的机器并不是很友好，因为每个 CPU core 都需要在大锁上竞争，造成资源浪费。
一种优化策略是，将空闲的内存划分为 CPU core 数量的区域，每个 core 对应整个空闲链表的一部分，且各自维护相应的锁，不同 core 只需要在自己负责那部分即可。当然有的 core 上运行的进程可能需要多个页，一旦自己那部分空闲内存不够了，就需要从其他 core 的空闲内存中「窃取」一页出来。
毕竟闲着也是闲着，不如最大化利用。
1...
2// NCPU 个 freelist 与 lock
3struct {
4 struct spinlock lock;
5 struct run *freelist;
6} kmems[NCPU];
7...
8void
9kinit()
10{
11 for (int i = 0; i < NCPU; i++) {
12 initlock(&kmems[i].lock, "kmem"); // 初始化所有 kmem
13 }
14 ...
15}
16
17void
18kfree(void *pa)
19{
20 // 将原本的 kmem 改为 kmems[cpu_id] 即可
21}
22
23void *
24kalloc(void)
25{
26 ...
27 // 从当前 core 开始遍历所有 core 负责的 kmem
28 // 直到找到一个有空闲页的 kmem，直接拿来用
29 // 最后 kfree 会将该页加到当前 core 的 kmem 里
30 for (int i = 0; i < NCPU; i++) {
31 acquire(&kmems[cpu_id].lock);
32 r = kmems[cpu_id].freelist;
33 if (r) {
34 kmems[cpu_id].freelist = r->next;
35 }
36 release(&kmems[cpu_id].lock);
37 if (r) {
38 break;
39 }
40 cpu_id = (cpu_id+1)%NCPU;
41 }
42 ...
43}
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 即可。
1// 移除了 prev 和 next 字段，新增 timestamp 字段
2struct buf {
3 int valid; // has data been read from disk?
4 int disk; // does disk "own" buf?
5 uint dev;
6 uint blockno;
7 struct sleeplock lock;
8 uint refcnt;
9 uint timestamp; // (!new)
10 uchar data[BSIZE];
11};
1#define NBUCKETS 5
2
3struct {
4 struct spinlock lock;
5 struct buf buf[NBUF]; // 这里相当于做了个 tricky，单纯增加 Cache 容量来降低 miss 概率
6} bcache[NBUCKETS];
7
8void
9binit(void)
10{
11 struct buf *b;
12 for (int i = 0; i < NBUCKETS; i++) {
13 initlock(&bcache[i].lock, "bcache");
14 for(b = bcache[i].buf; b < bcache[i].buf+NBUF; b++){
15 initsleeplock(&b->lock, "buffer");
16 b->timestamp = 0;
17 }
18 }
19}
20
21static struct buf*
22bget(uint dev, uint blockno)
23{
24 struct buf *b;
25 uint bucketno = blockno % NBUCKETS;
26 uint earliest = __INT_MAX__;
27 uint idx = -1;
28
29 acquire(&bcache[bucketno].lock);
30 for(int i = 0; i < NBUF; i++){
31 b = &bcache[bucketno].buf[i];
32 if (b->dev == dev && b->blockno == blockno) {
33 // 意味着缓存命中
34 }
35
36 // 同时也进行 LRU 策略，如果 miss 就可以直接用，不用再次 for 遍历
37 if (b->refcnt == 0 && b->timestamp < earliest) {
38 earliest = b->timestamp;
39 idx = i;
40 }
41 }
42
43 if (idx != -1) { // 意味着有 block 被 victim，且就在 buf[idx] 处
44 ...
45 }
46
47 panic("bget: no buffers");
48}
49
50void
51brelse(struct buf *b)
52{
53 ...
54 if (--b->refcnt == 0) {
55 b->timestamp = 0; // 将其置 0，以便 victim
56 }
57}
58
59void
60bpin(struct buf *b) {
61 // 根据 b->blockno 映射到 bucket
62}
63
64void
65bunpin(struct buf *b) {
66 // 根据 b->blockno 映射到 bucket
67}
测试结果
1$ make grade
2...
3== Test running kalloctest ==
4$ make qemu-gdb
5(70.1s)
6== Test kalloctest: test1 ==
7 kalloctest: test1: OK
8== Test kalloctest: test2 ==
9 kalloctest: test2: OK
10== Test kalloctest: sbrkmuch ==
11$ make qemu-gdb
12kalloctest: sbrkmuch: OK (10.5s)
13== Test running bcachetest ==
14$ make qemu-gdb
15(8.7s)
16== Test bcachetest: test0 ==
17 bcachetest: test0: OK
18== Test bcachetest: test1 ==
19 bcachetest: test1: OK
20== Test usertests ==
21$ make qemu-gdb
22usertests: OK (134.2s)
23== Test time ==
24time: OK
25Score: 70/70
最后的工作
git commit -am ""将所有修改提交到本地;- 执行
make handin。由于 lab0 保存了 APIKey，故直接成功提交；
可选的挑战再说吧，没有什么想做的欲望。