小作业2：内存与系统调用

截止时间：4月28日23:59

任务1：动态内存分配器

任务要求

在这个任务中，你需要在 xv6 中实现一个用户态的内存分配器。具体而言，你需要使用 xv6 的 sbrk 系统调用来实现以下函数：

int mm_init(void);
void *mm_malloc(uint size);
void mm_free(void *ptr);
void *mm_realloc(void *ptr, size_t size);

具体而言，每个函数分别需要实现：

• mm_init：在调用其他函数之前，测试程序会首先调用 mm_init 。你可以在这个函数中完成必要的初始化，例如申请必要的堆空间等。如果初始化顺利完成，mm_init 应该返回 0，否则返回 -1
• mm_malloc ：该函数会返回一个指针，指向的内存区域大小为 size 字节，位于堆空间中，且与之前已经分配的内存区域不相交。为了保持和 libc 中malloc一致，我们要求分配出的指针必须是 8 字节对齐的。
• mm_free ：该函数的参数 ptr 保证是一个之前由 mm_malloc 或 mm_realloc 分配出的指针，且没有被释放过。调用 mm_free 之后，这一内存区域被释放，可以在之后被重新分配。
• mm_realloc ：
  • 如果 ptr 为 NULL，则调用该函数的效果等同于 mm_malloc(size) ；
  • 如果 size 为 0，则调用该函数的效果等同于 mm_free(ptr) 并返回 NULL；
  • 如果 ptr 不是 NULL， 那么保证它是一个之前由 mm_malloc 或 mm_realloc 分配出的指针，且没有被释放。 该函数会将原本 ptr 指向的内存区域大小更改为 size ，并返回指向新的内存区域的指针。注意这里返回的指针可以与旧的指针相同，也可以是新的指针。另外，新指针指向的内存区域上的内容需要与原内存区域相同。具体而言，如果 size > old_size ，那么新的内存区域上前 old_size 字节需要与旧的内存区域相同，之后的内容是未初始化的；如果 size <= old_size 那么新的内存区域上的内容为旧内存区域的前 size 字节。

仓库中的 user/ummalloc.c 中已经实现了一个最简单（但低效）的版本，你可以在此基础上修改完成你的实现。最终你只需要提交 user/ummalloc.c 即可。

评分标准

此任务满分为100%。

评分项目	分数	说明
正确性	50%	各个函数的运行结果满足规定的语义
内存使用效率	30%	得分取决于分配器总共使用的堆空间大小
运行时间	20%	以运行使用的CPU时间计分

对于每个测试点，达到以下标准即可得到满分

测试点	使用堆空间大小（Byte）	运行时间（周期数）
amptjp-bal.rep	2061756	412366546
binary-bal.rep	2097324	750190031
binary2-bal.rep	1122472	1337562006
cccp-bal.rep	1708542	391218264
coalescing-bal.rep	12432	750566446
cp-decl-bal.rep	3262472	437277898
expr-bal.rep	3448656	259369793
random-bal.rep	16240032	249850130
random2-bal.rep	16031944	326382116
realloc-bal.rep	2459648	940527441
realloc2-bal.rep	97536	789587301
short1-bal.rep	12396	503556
short2-bal.rep	20588	288177

测试

测试程序为 user/ummalloc_test.c ，使用 make qemu 启动 xv6 后，在终端中使用 ummalloc_test <tracefile> 即可进行测试，仓库中的 traces 文件夹中包含了所有用于测试的样例（即所有可用的 <tracefile>）。每个测试样例的前两行为该样例中的最大内存区域数量和操作数量，接下来的每一行会是：

• a <id> <size> ：执行ptr[id] = mm_malloc(size);
• f <id>：执行mm_free(ptr[id]);
• r <id> size>：执行ptr[id] = mm_realloc(ptr[id],size);

测试程序最后会输出测试过程中使用的堆空间大小以及运行时间（即评分标准中的两个指标）

任务2：共享内存页

任务要求

在这个任务中，你需要自行设计一套关于共享内存页的系统调用，并在xv6中实现这一设计。你的设计需要实现以下功能：

1. 创建共享内存页
2. 在不同进程中绑定并读写该共享内存页
3. 释放共享内存页
4. 查询、修改共享内存页的配置
5. （可选）对共享内存页的访问控制

评分标准

评分项目	分数	说明
设计	30%	主要评估设计的合理性，以及是否能实现要求的功能
实现	70%	通过CR考察是否基本实现了设计的系统调用