实验实现¶

这里，我们将对一些实现的细节做一定的提醒。但是完整的流程需要自己把握，我们 不会给出每一步实现步骤 。因此，最重要的还是阅读实验原理内容，得出自己的解决方案，然后参考实验实现这部分的内容。

值得注意的是，xv6的代码是可以参考的，可以看看相关实验原理是怎么实现的。同时，还可以插桩，使用printf/GDB等方法看看具体的内容。同时，还可以阅读 xv6 指导书，看看背后的设计机理。

0. 任务零：回答问题¶

回答问题

任务开始之前，我们应该先要首先回答一些原理性的问题，这部分应该被包含在实验报告中：

内存分配器
1. 什么是内存分配器？它的作用是？
2. 内存分配器的数据结构是什么？它有哪些操作（函数），分别完成了什么功能？
3. 为什么指导书提及的优化方法可以提升性能？
磁盘缓存
1. 什么是磁盘缓存？它的作用是？
2. buf结构体为什么有prev和next两个成员，而不是只保留其中一个？请从这样做的优点分析（提示：结合通过这两种指针遍历链表的具体场景进行思考）。
3. 为什么哈希表可以提升磁盘缓存的性能？可以使用内存分配器的优化方法优化磁盘缓存吗？请说明原因。

以上题目的答案几乎都能在指导书中找到，所以请仔细阅读指导书。

本实验的代码量较小，但这反而意味着难度较大。因此，建议大家以图的形式画出数据结构以及数据结构之间的关系以及在操作时他们发生了什么变化，同时主张以 简短而精炼 的文字回答所有问题。

1. 任务一内存分配器¶

1.1 流程¶

具体步骤如下：

Step 1 ：参考这个指南，切换到lock分支并同步上游仓库；

Step 2 ：理解kalloc内存分配的方式和其中锁的原理；

Step 3 ：修改内存分配器数据结构，例如，将kalloc的共享freelist改为每个CPU独立的freelist；

struct run {
  struct run *next;
};
struct kmem{
  struct spinlock lock;
  struct run *freelist;
};
struct kmem kmems[NCPU];

freerange为所有运行freerange的CPU分配空闲的内存。

Step 4 ：修改和内存管理器有关的所有操作，尽可能减少锁争用；

Step 5 ：启动测试程序进行测试。

1.2 实现提示¶

分配内存块：优先分配当前 CPU的freelist中的内存块；当前CPU没有空闲内存块，则从其他CPU的freelist中窃取内存块；所有CPU都没有空闲块时，返回0。
释放内存块：将内存块放入当前CPU的freelist中。
锁的机制：锁的使用和原来会有些不同，你需要注意你的设计应该要满足一致性。简单地说，也就是保证多个cpu访问同一个数据的时候，会出错的话就要加锁。
- 可以使用kernel/param.h中的宏NCPU，其表示CPU的数目。
- 使用cpuid()函数会返回当前CPU的id号（范围0~NCPU-1）。在调用cpuid()并使用其返回值的过程中需要关闭中断。使用push_off()可以关闭中断，使用pop_off()可以打开中断。
- 请使用initlock()初始化锁，并 要求锁名字以kmem开头 。
- 使用freerange为所有运行freerange的CPU分配空闲的内存。

2. 任务二磁盘缓存¶

具体要求：修改磁盘缓存块列表的管理机制 ，使得可用多个锁管理缓存块，从而减少缓存块管理的锁争用。

xv6 book中8.2 - 8.3 节有关于块缓存的描述。

2.1 流程¶

具体步骤如下：

Step 1 ：理解bio.c中代码的行为以及原理；

Step 2 ：理解bio.c中锁的作用以及原理；

Step 3 ：构建磁盘缓存数据结构，例如，可以构建13个哈希组；

#define NBUCKETS 13
struct {
  struct spinlock lock[NBUCKETS];
  struct buf buf[NBUF];
  // Linked list of all buffers, through prev/next.
  // head.next is most recently used.
  //struct buf head;
  struct buf hashbucket[NBUCKETS]; //每个哈希队列一个linked list及一个lock
} bcache;

Step 4 ：修改和磁盘缓存有关的所有操作，尽可能减少锁争用；