6.s081 Lab：locks
Lab：locks
1.实验目的
在这个实验中，我们需要重新设计代码以提高并行性。多核计算机上并行性差的一个常见症状是高锁争用。为了减少争用，提高并行性通常需要同时改变数据结构和锁定策略。这需要我们为xv6内存分配器和块缓存执行此操作。
2.实验内容
1）实现每CPU空闲列表，并在一个CPU的列表为空时进行窃取。运行kalloctest查看您的实现是否减少了锁争用，并检查它是否仍然可以分配所有内存。
2）修改块缓存，以便在运行bcachetest时，bcache中所有锁的测试和集数接近于零。理想情况下，块缓存中涉及的所有锁的测试和集的总和应该为零，但是如果总和小于500，也可以。修改bget和brelse，使bcache中不同块的并发查找和释放不太可能在锁上发生冲突（例如，不必全部等待bcache.lock). 您必须保持不变，即最多缓存一个块的副本。
3.实验步骤（要细化如何实现的思路或流程图）
3.1 Memory allocator
1）首先先切换分支。
2）先测试一下，看没做改动之前竞争情况。
3）首先根据题意，出现大量竞争情况是因为kalloc()只有一个被单个锁保护的freelist。为了消除锁争用，我们要重新设计内存分配器，以避免单一的锁和列表。基本思想是为每个CPU维护一个空闲列表，每个列表都有自己的锁。然后根据提示，我们需要将其修改为多个，参考param.h的常量声明，修改结构体如下。
4）同时，由于我们修改了kmem，对于kinit、kalloc、kfree函数中对内存的操作，我们都需要做出相应修改。主要的挑战是如何处理一个CPU没有空闲列表，但另一个CPU的列表有空闲内存的情况；在这种情况下，该CPU必须“窃取”另一个CPU的空闲列表的一部分。窃取可能会导致锁争用，但我们希望这种情况很少发生。
5）注意，提示中提到了，在调用cpuid的时候，必须保证interrupts是turned off状态，而我们是通过push_off()和pop_off()来切换其状态的。
6） 代码全部更改完毕，进行测试，测试成功，而且确实比修改之前的竞争态数量下降了。
3.2 Buffer cache
1）先测试一下，看没做改动之前竞争情况。
2）首先根据题意，出现大量竞争情况是因为bio.c中，如果多个进程密集地使用文件系统，它们可能会争用bcache.lock，其保护着cached block buffers的链表和一些其他属性。修改函数使bcache中不同块的并发查找和释放不太可能在锁上发生冲突。而根据题目所说” We suggest you look up block numbers in the cache with a hash table that has a lock per hash bucket.”，我们需要将其从链表修改为哈希表，并为每个bucket都分配锁，同时去掉head。
3）由于我们修改了bcache，对于binit和bget也很显然需要作出修改。
4）注意，提示中提到了，用一个质数来设定buckets个数来防止冲突，而他所个的提示13太小了，通过不了测试，所以将其改大为97。
5） 代码全部更改完毕，进行测试，测试成功，而且确实比修改之前的竞争态数量下降了。
4.实验结论与心得体会
通过本次实验，对于锁的理解与使用更加深刻娴熟了，同时还查阅了很多资料，学习到了很多知识，并且顺带复习了之前操作系统理论课上所学到的知识，但锁的使用还是一门很深的学问，仍需要我继续学习研究。