实验概述¶

温（守）馨（住）提（红）示（线）

本课程实验已引入代码自动查重系统，请同学们保持学术诚信！

关于第二次实验课考核

我们将在第四次实验课进行第二次实验现场验收：

验收内容 ：前三次实验
- Lab1：XV6与Unix实用程序
- Lab2：进程与系统调用
- Lab3：锁机制的应用
验收目的 ：考察同学们是否是自己完成的实验代码，而不是“复制拷贝”。
验收形式 ：助教与同学们进行一对一问答

请同学们认真对待！

课程复习和预习要求

本节实验与理论课的 “多线程” 、 “信号量” 和 “死锁” 这三章课程内容相关，请同学们复习这三章课程内容。

在做实验之前，请同学们阅读xv6 book的以下章节及相关源代码：

[1] xv6 book, Chapter 6 Locking (锁)
[2] xv6 book, 3.5 Code: Physical memory allocator（物理内存分配器）
[3] xv6 book, Chapter 8 File system：8.1 Overview ~ 8.3 Code: Buffer cache（磁盘缓存）

实验背景

锁起到了保护作用，让一些关键的数据结构在并行环境下仍能保持一致性。

在这个实验中，我们需要为多CPU核的xv6内存分配器和磁盘缓存（buffer cache）重新设计代码以提高并行性。这两个实验分别用到了两种不同的设计方法，来适用自身的结构，大大减少锁争用（在保证功能正确的前提下）。

1. 实验目的¶

了解Lock的实现原理，理解CPU为Lock的实现提供的支持。
理解xv6的内存分配器kalloc以及磁盘缓存buffer cache的工作原理，掌握Lock在xv6中内存分配器/磁盘缓存中的作用。
掌握锁竞争对程序并行性的影响。
学习减少锁竞争的方法。

2. 实验学时¶

本实验为4学时。

3. 实验内容及要求¶

请先同步上游远程仓库，并注意切换到lock分支进行试验

本次实验基于 lock 分支，请同学们参考“Lab2：进程与系统调用”的3.1 切换分支进行切换。

3.1 任务一：内存分配器（Memory allocator）¶

修改内存分配器（主要修改kernel/kalloc.c） ，使每个CPU核使用独立的内存链表，而不是现在的共享链表。

XV6的内存分配器只有一个内存链表供多个CPU核使用。在使用kalloc()获取内存时，由于添加了内存锁kmem.lock，其他CPU如果要切换进行内存申请必须等待当前进程释放内存锁。要消除锁争用的情况，需要重新设计内存链表管理机制以避免单个锁和单个链表。实验基本任务是让每个CPU拥有自己的内存链表，每个链表都有自己的锁。其中最具挑战的就是，当一个CPU内存链表不足时，还可以从其他链表窃取内存块，这样，就不会让所有的CPU争抢一个空闲区域（窃取可能会引发锁争用，但这也是不可避免的情况）。

3.1.1 关于测评程序kalloctest¶

测评程序kalloctest（见user/kalloctest.c）有两个test，分别是test1和test2。

(1) 在test1中fork出多个进程，它们并发运行于不同CPU核心，用 sbrk() 进行频繁获取空闲内存（通过调用kalloc()实现），然后又释放（通过调用kfree()实现）。在获取内存的时候不同CPU核心可能会争抢锁。

(2) 在test2中测试所有空闲内存的获取和释放，由于test2未使用fork，只在单进程中测试。

测评程序kalloctest运行了上述两个测试（test1和test2），最终会打印出fetch-and-add的数目，也就是 自旋（CPU不停循环等待解锁）的次数 ，这种粗略测量锁争用的方式（实验前，即未修改前）如下：

$ kalloctest
start test1
test1 results:
--- lock kmem/bcache stats
lock: kmem: #fetch-and-add 46375 #acquire() 433016
lock: bcache: #fetch-and-add 0 #acquire() 1242
--- top 5 contended locks:
lock: kmem: #fetch-and-add 46375 #acquire() 433016
lock: proc: #fetch-and-add 21429 #acquire() 170067
lock: virtio_disk: #fetch-and-add 13306 #acquire() 114
lock: proc: #fetch-and-add 6023 #acquire() 170143
lock: proc: #fetch-and-add 3661 #acquire() 170147
tot= 46375
test1 FAIL
start test2
total free number of pages: 32499 (out of 32768)
.....
test2 OK

"lock: kmem"、"lock: bcache"、"lock: proc" 等指示了锁的类型。acquire()记录了每种锁 被请求的次数 。fetch-and-add就是 自旋（CPU不停循环等待解锁）的次数 。例如， lock: kmem: #fetch-and-add 46375 #acquire() 433016 这句话的意思是，kmem.lock请求了433016次，自旋了46375次。

这些计数来自于在kalloctest调用的ntas()，它通过执行statistics()函数，打开"statistics"设备文件，获取内核打印的那些针对kmem和bcache锁( 本实验的重点 )及5个竞争最激烈的锁的计数（见kernel/spinlock.c中的statslock()）。关于#acquire和#fetch-and-add的计数算法见测评程序kalloctest对锁的检测。

如果存在锁争用，fetch-and-add的数量将会很高，因为在acquire()获得锁之前要进行许多循环迭代，"statistics"设备文件会返回kmem和bcache锁的#test-and-set的总和（也就是tot的值，即没有获取到此锁的次数）。

test1失败，说明锁竞争太激烈，特别是在kmem锁。test2成功，说明内存分配和释放在测试期间没有问题。

3.1.2 具体要求¶

1) 请使用initlock()初始化锁，并要求锁名字以kmem开头；
2) 运行kalloctest查看实现的代码是否减少了锁争用（tot没有获取到此锁的次数小于10则为通过）；
3) 运行 usertests sbrkmuch 以测试修改代码后系统是否仍可以分配所有的内存；
4) 运行usertests，确保其能能够全部通过；
5) kalloctest和usertests的输出如下图（锁争用的次数大大减少），具体的数据会有所差别：

3.2 任务二：磁盘缓存（Buffer cache）¶

在访问文件数据的时候，操作系统会将文件的数据放置在磁盘缓存中。磁盘缓存是不同进程之间的共享资源，因此需要通过锁确保使用的正确性。如果有多进程密集地使用文件系统，他们可能会竞争磁盘缓存的bcache.lock锁。

目前，xv6采用单个锁来管理磁盘缓存。假设有三个进程大量读写磁盘，而由于磁盘缓存只有一个bcache.lock锁，这就导致三个进程的竞争异常激烈。因此，我们需要 修改磁盘缓存块列表的管理机制（主要修改kernel/bio.c） ，使得可用多个锁管理缓存块，从而减少缓存块管理的锁争用。

3.2.1 关于测评程序bcachetest¶

测评程序bcachetest（见user/bcachetest.c）通过创建多个进程重复去读取不同的文件，从而造成bcache.lock锁争用。

测试方式如下：

实验前（即未修改前），测评程序bcachetest的输出如下：

可以看到，bcache的fetch-and-add值非常大，说明磁盘缓存锁的争用非常严重。

修改buffer cache的设计后，所有锁的fetch-and-add的数目应当接近于0。

3.2.2 具体要求¶

关于bcache实验的补充说明

本实验要求大家在XV6原版的bcache基础上，修改磁盘缓存块列表的管理机制，主要修改kernel/bio.c。也就是，在原有的磁盘缓存大小的基础上，可采用多个哈希桶、时间戳、或CLOCK算法等优化策略来减少磁盘缓存的锁争用。以下修改是不允许的：

不允许修改NBUF的大小 ；
不允许修改buf的数量，比如设置N个struct buf [NBUF] ；
不允许随意修改锁的命名，本任务涉及到的锁必须以bcache开头来命名 。

理想状态下，bcachetest中数据块缓存相关的所有锁fetch-and-add的总和应该为0，但本实验中总和tot不超过500即可；
请修改bget()和brelse()，使得缓存区并发的查询和释放不容易发生锁争用，比如，不是所有流程都得等bcache.lock；
同样要求usertests中的用例全部通过，最后的输出如下（具体数据有所出入）：

关于bcache实验的测试说明

在运行make qemu测试bcachetest和usertests之前， 建议先运行make clean删除fs.img ，以防之前错误的代码把磁盘写坏了，后面即使是改成正确的代码也没法执行。

3.3 测试¶

当完成上述的两个实验后，在命令行输入 make grade 进行最终测试。