操作系统实验——内存管理.zip

# 操作系统实验——内存管理 通过提供的底层模拟接口和细节，模拟实现操作系统的内存管理功能，包括存储保护、虚拟地址和物理地址的转换、实现虚拟内存等。 ## 底层模拟 ### 模拟设备细节 * 虚拟空间大小（磁盘可用交换区大小）：512MB * 物理空间大小（内存可用空间大小）：128MB * 字节可寻址 ### 设计说明 * 底层接口只负责： * 数据的读和写 * 对模拟设备的访问的记录 * 需要实现的功能： * 存储保护 * 虚拟地址到物理地址的转换 * 什么时候，将哪些数据，从内存写进磁盘，或从磁盘读进内存 ### 底层模拟接口 * 读取内存某个物理地址上的字节，若`address`越界，会退出程序，开销小 ```c data_unit mem_read(p_address address); ``` * 往内存某个物理地址写入字节，若`address`越界，会退出程序，开销小 ```c void mem_write(data_unit data, p_address address); ``` * 将硬盘某个地址开始的一段连续的数据加载到内存，若`x_offset + size`越界，会退出程序；开销与`size`大小有关，比内存读写开销大很多，且每次调用都有始动开销 ```c void disk_load(p_address mem_offset, p_address disk_offset, m_size_t size); ``` * 将内存某个地址开始的一段连续的数据保存到磁盘，若`x_offset + size`越界，会退出程序；开销与`size`大小有关，比内存读写开销大很多，且每次调用都有始动开销 ```c void disk_save(p_address mem_offset, p_address disk_offset, m_size_t size); ``` * 获取内存和硬盘的读写开销情况，并往控制台输出 ```c void evaluate(count_t *m_read, count_t *m_write, count_t *d_read, count_t *d_write); ``` ## 内存调用 ### 调用细节 * 进程号为 1-999，不会出现超过范围的`pid`。 * 每个进程可申请的内存空间无限制。 * 调用`allocate`的次数会有一个比较小的上限，因此不必太过担心一些 Corner Case。 * 大部分情况下，`read`和`write`调用会根据之前返回的`address`来调，但是有时候，测试用例里会故意调用错误的地址，这时候程序应该拒绝这样的非法调用。 * 在内存空间不足的时候（不管你有没有实现磁盘的虚拟内存），都可以返回申请内存失败。 * 测试用例会杂乱地访问各个进程的各个地址，但是对各个地址的访问会遵循一定的空间局部性原则，因此理想情况下程序不应该频繁地对磁盘数据换入换出。 ### 设计说明 * 实现的时候，不允许申请任何额外的内存，即不允许声明全局变量，不允许调用`malloc`函数。 * 需要使用数据记录内存使用状况的时候（如采用动态划分的话要用链表，用分页的话存储页表等），也需要调用底层模拟接口，不能自己申请内存来存储这些数据。 * 这样设计是保证为了不同实现方法之间的公平性，当然这样也使得实现起来需要额外花点功夫。建议根据自己的实现方式，抽象出一些工具函数并放到不同的文件里，这样会大大提高代码可读性和可维护性。 ### 内存调用接口 * 初始化函数，会在每个测试用例开始调用一次，你可以在这个函数里面做一些初始化操作。 ```c void init(); ``` * 进程号为`pid`的进程希望访问`address`处的数据。如果访问合法，往`data`指针里写入数据（通过`*data = xxx`），并返回0；如果访问不合法，返回-1。 ```c int read(data_unit *data, v_address address, m_pid_t pid); ``` * 进程号为`pid`的进程希望往`address`处写入数据。如果访问合法，往`address`处写入`data`，并返回0；如果访问不合法，返回-1。 ```c int write(data_unit data, v_address address, m_pid_t pid); ``` * 进程号为`pid`的进程希望申请大小为`size`的空间。如果空间有剩余，往`address`指针里写入申请到的地址（通过`*address = xxx`），并返回0；如果空间不足，返回-1。 ```c int allocate(v_address *address, m_size_t size, m_pid_t pid); ``` * 进程号为`pid`的进程希望归还`address`处开始的空间。如果访问合法，回收空间，返回0；如果访问不合法，即`address`处的空间不属于`pid`进程，返回-1。 ```c int free(v_address address, m_pid_t pid); ``` ## 测试说明 ### 测试步骤 1. test.c文件中的`main`方法包含一系列的测试用例，每个测试用例会先调用`init`进行初始化。 2. 每个测试用例内部会按各个测试用例的要求调用`read`、`write`、`allocate`和`free`方法，并检查返回的结果。 ### 测试种类 * 正确性测试 * 进程 A 试图访问不属于它的地址的时候，应拒绝访问。 * 往一个地址`address`里写入数据`data`，如果后面的访问没有修改`address`上的值，那么读取`address`的时候应返回`data`。 * 时间测试 * 对同一个进程的相近几个位置的访问，除了第一次可能需要在磁盘上换入换出，后续的访问应该都要能在较短的时间内完成。 * 多个进程的多个距离较远的地址轮流访问，如果调度做的足够好，那么不应该在磁盘上频繁地换入换出。 * 容量测试 * 多次申请比较小的空间，理想情况下应该都要能够申请成功。 * 多次申请比较小的空间，然后退回部分，再次申请几个较小的空间，理想情况下应该都要能够申请成功，而且不需要在磁盘上换入换出。 * 多次申请比较小的空间，然后退回部分，再次申请一个较大的空间（总用量不超过128MB），理想情况下应该都要能够申请成功，而且不需要在磁盘上换入换出，考察的是对内存碎片的处理。 * 一次申请超过128MB的空间，若支持磁盘换入换出，应该能够申请成功。 * 综合测试：综合上面的几种进行测试。 ### 注意事项 由于测试用例是一个接着一个跑的，因此请注意在`init`函数中把上次用过的变量重新初始化，避免上次的测试对本次测试造成干扰。 ## 实现细节 存储控制信息的数据全部位于物理内存的0MB～1MB上，因此物理内存实际可用于存储进程内存数据的区域为1MB～128MB，大小为127MB。 ### 系统参数 * 分页设定 * 逻辑内存分为4KB一页，共512MB／4KB = 128K页； * 物理内存分为4KB一页，共128MB／4KB = 32K页； * 物理磁盘分为4KB一页，共512MB／4KB = 128K页； * 其中逻辑内存的页与物理磁盘的页一一对应。 * 页表：存储逻辑内存中页面和物理内存或磁盘中页框的对应表，一条记录占7个字节，包含逻辑内存中页面编号`v_page_id`、物理内存中页面编号`p_page_id`、控制信息块`control`，结构如下： | 字节位 | 0 1 2 | 3 4 5 | 6 | | --- | --- | --- | --- | | 保存信息 | v_page_id | p_page_id | control | > 其中控制信息块包含载入位`in`（是否在内存中）、使用位`use`（最近是否使用）。 > 需要存储128K条记录，所以共需要128K * 7B = 896KB来存储。放在内存的0～896K处。 * 逻辑页位示图：表示逻辑内存的页使用情况，共有512MB／4KB = 128K页，每页1位，所以一共需要16KB的空间来存储。放在内存的896K～912K处。 * 物理页位示图：表示物理存储空间的页使用情况，共有127MB／4KB < 32K页，每页1位，所以一共需要4KB的空间来存储。放在内存的912K～916K处。 * 数据交换区：内存中数据换出时，暂时保存数据的区域，大小为1页，即4KB，放在内存的916K～920K处。 * 内存分配表：存储内存分配信息的表，一条记录占10个字节，包含进程号`pid`、逻辑内存中起始地址`start_address`、占用空间大小`size`，结构如下： | 字节位 | 0 1 | 2 3 4 5 | 6 7 8 9 | | --- | --- |