MIT 6.1810 · Lab lock · 锁

Lab: 锁

在本实验中，你将获得重新设计代码以提高并行性的经验。多核机器上并行性差的常见症状是高锁竞争。

$ git fetch
$ git checkout lock
$ make clean

内存分配器 中等

程序 user/kalloctest 对 xv6 的内存分配器施加压力：三个进程增长和缩小其地址空间，导致对 kalloc 和 kfree 的许多调用。

$ kalloctest
start test1
test1 results:
--- lock kmem/bcache stats
lock: kmem: #test-and-set 18820 #acquire() 433058
lock: bcache: #test-and-set 0 #acquire() 1744
--- top 5 contended locks:
lock: uart: #test-and-set 97375 #acquire() 117
...
tot= 18820
test1 FAIL

kalloctest 中锁竞争的根因是 kalloc() 有一个受单个锁保护的空闲列表。要消除锁竞争，你必须重新设计内存分配器以避免单个锁和列表。

$ kalloctest
start test1
test1 results:
--- lock kmem/bcache stats
lock: kmem: #test-and-set 0 #acquire() 117911
lock: kmem: #test-and-set 0 #acquire() 169464
lock: kmem: #test-and-set 0 #acquire() 145786
lock: bcache: #test-and-set 0 #acquire() 1744
...
tot= 0
test1 OK
...
$ usertests -q
...
ALL TESTS PASSED

一些提示：

• 你可以使用 kernel/param.h 中的常量 NCPU
• 让 freerange 将所有空闲内存给运行 freerange 的 CPU
• cpuid 函数返回当前核心编号，但只有在关闭中断时调用它并使用其结果才是安全的。你应该使用 push_off() 和 pop_off()
• 查看 kernel/sprintf.c 中的 snprintf 函数了解字符串格式化想法
• 可选择使用 xv6 的 race detector 运行解决方案：make KCSAN=1 qemu

读写锁 中等

这部分任务与前一半独立；你可以完成这部分（并通过测试）无论是否完成前一半。

考虑 xv6 的 sys_pause 和 sys_uptime 函数，它们读取全局 ticks 变量。由于该变量可能被 clockintr 并发更新，这两个函数在读取 ticks 之前获取 tickslock 自旋锁。这防止了 clockintr 并发修改 ticks，但也防止了多个核心同时读取 ticks，而这本来是可以的。

// API
void            initrwlock(struct rwspinlock*);
void            read_acquire(struct rwspinlock*);
void            read_release(struct rwspinlock*);
void            write_acquire(struct rwspinlock*);
void            write_release(struct rwspinlock*);

读写锁的一个微妙问题是，如果有很多读者，写者可能永远得不到运行机会。为了解决这个问题，读写锁通常实现写者优先级方案：一旦写者尝试获取锁，后续读者必须等待写者成功获取并释放锁。

$ rwlktest
rwspinlock_test: step 1: initrwlock
rwspinlock_test: step 2: concurrent read_acquire
...
rwspinlock_test: step 31: done
rwspinlock_test(1): 0
rwspinlock_test(0): 0
rwspinlock_test(2): 0
rwspinlock_test(3): 0
rwlktest: 4/4 CPUs succeeded

一些提示：

• 首先查看 kernel/spinlock.c 中的 sys_rwlktest
• 注意可能的交错。例如，如果读者看到没有挂起的写者并想获取锁，你怎么知道它仍然安全获取锁？
• 阅读 gcc 内置函数了解原子操作

提交实验

时间花费

创建一个新文件 time.txt，放入一个整数，表示你花在实验上的小时数。

答案

如果本实验有问题，将答案写在 answers-lock.txt 中。

提交

运行 make zipball，上传到 Gradescope。