在这个实验中，我们使用伙伴分配器替换了 Xv6 内核中的页分配器。你需要修改 Xv6 使其能够使用这个分配器分配释放文件结构体，让 Xv6 拥有比现在系统层面的限制NFILE更多的文件描述符。进一步地，你需要实现一个减少伙伴分配器内存使用的优化。要完成这个实验，你修改过的内核需要通过所有的 alloctest 和 usertest 。

在实验开始前请切换到alloc分支：

git checkout alloc

在这个实验中，你只需要修改kernel/buddy.c和kernel/file.c

问题

Xv6 只有一个页分配器且不能动态地分配小于一个页的空间。为了绕过这个限制，Xv6 静态地声明小于一个页的空间。例如，Xv6 声明文件结构体数组，进程结构体数组等等。这导致系统能够打开的文件数量被静态声明文件数组的大小所限制，这个大小是NFILE（见kernel/file.c和kernel/param.h）。

解决方法

解决方法是使用 分配器课程 中的伙伴分配器，我们已经把它添加到了 Xv6 的kernel/buddy.c和kernel/list.c中。

你要做的事

你要做的事是从两方面进一步优化 Xv6 的内存分配：

  • 修改kernel/file.c以使用伙伴分配器让文件结构体的数量被内存限制而不是NFILE。
  • 伙伴分配器的空间利用率不高。alloc数组为每个大小的每个块保留了一位。存在一个巧妙地减少空间使用的优化，即为两个块保留一位。这个位是作为一对伙伴的块B1和块B2的B1_is_free XOR B2_is_free。每次一个块被分配或是释放，你翻转这个位以表示变化。例如，如果B1和B2已被分配，这个位为0并且如果B1被释放这个位变为1。如果这个位为1且B2已被释放，那么我们就知道B1和B2应该被合并。为每个块节省二分之一位很有用，当Xv6使用伙伴分配器管理大约128MB的空闲内存：这个优化可以节省大约1MB的内存。

测试程序

为了帮助测试你的实现，我们提供了一个名为 alloctest 的 Xv6 程序（见user/alloctest.c）。它包含两个测试：

第一个测试通过创建很多打开大量文件描述符进程以分配超过NFILE的文件结构体。未被修改的 Xv6 无法通过这个测试。

第二个测试创建一个进程并分配尽可能多的内存，如果不能分配超过一定数量的空闲内存将不能通过测试。它是一个查看内核使用了多少内存的高效测试。未被优化的伙伴分配器无法通过这个测试。

要完成这个实验，你的内核应该能够通过所有的 alloctest 和 usertest ：

$ alloctest
filetest: start
filetest: OK
memtest: start
memtest: OK
$ usertests
...
ALL TESTS PASSED
$

提示

  • 你需要删除kernel/file.c中的第19行，这里声明了file[NFILE]。作为替代，使用filealloc中的bd_malloc分配struct file。在fileclose你需要释放已分配的内存。注意你可以简化fileclose，因为我们不再需要ff。
  • fileclose仍然需要获取ftable.lock因为这个锁能保护f->ref。
  • bd_malloc不会对它返回的内存清零。也就是说，分配的内存仍然会保有它在上次使用中的内容。调用者不能假定它已被清零。
  • 你可以使用bd_print以打印分配器的状态。
  • 与课程中讲到的不同，我们修改了bd_init让它以可供分配的空闲物理内存的范围调用。bd_init为从这块内存为伙伴数据结构分配内存。它初始化数据结构的依据是：bd_init标记被伙伴数据结构使用的内存以避免其被重复分配。进一步地，我们修改了bd_init以通过标记不可用的内存为已分配来处理大小不是2的幂的内存。最后，我们修改了伙伴分配器以使用锁序列化并发的调用。

可选的挑战

动态分配 Xv6 中静态分配的其他数据结构。有一些需要相当数量的修改（例如动态分配进程结构体）。但其他的比较简单。