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

通过提供的底层模拟接口和细节，模拟实现操作系统的内存管理功能，包括存储保护、虚拟地址和物理地址的转换、实现虚拟内存等。

底层模拟

模拟设备细节

• 虚拟空间大小（磁盘可用交换区大小）：512MB
• 物理空间大小（内存可用空间大小）：128MB
• 字节可寻址

设计说明

• 底层接口只负责：
  • 数据的读和写
  • 对模拟设备的访问的记录
• 需要实现的功能：
  • 存储保护
  • 虚拟地址到物理地址的转换
  • 什么时候，将哪些数据，从内存写进磁盘，或从磁盘读进内存

底层模拟接口

• 读取内存某个物理地址上的字节，若address越界，会退出程序，开销小

data_unit mem_read(p_address address);

• 往内存某个物理地址写入字节，若address越界，会退出程序，开销小

void mem_write(data_unit data, p_address address);

• 将硬盘某个地址开始的一段连续的数据加载到内存，若x_offset + size越界，会退出程序；开销与size大小有关，比内存读写开销大很多，且每次调用都有始动开销

void disk_load(p_address mem_offset, p_address disk_offset, m_size_t size);

• 将内存某个地址开始的一段连续的数据保存到磁盘，若x_offset + size越界，会退出程序；开销与size大小有关，比内存读写开销大很多，且每次调用都有始动开销

void disk_save(p_address mem_offset, p_address disk_offset, m_size_t size);

• 获取内存和硬盘的读写开销情况，并往控制台输出

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函数。
• 需要使用数据记录内存使用状况的时候（如采用动态划分的话要用链表，用分页的话存储页表等），也需要调用底层模拟接口，不能自己申请内存来存储这些数据。
• 这样设计是保证为了不同实现方法之间的公平性，当然这样也使得实现起来需要额外花点功夫。建议根据自己的实现方式，抽象出一些工具函数并放到不同的文件里，这样会大大提高代码可读性和可维护性。

内存调用接口

• 初始化函数，会在每个测试用例开始调用一次，你可以在这个函数里面做一些初始化操作。

void init();

• 进程号为pid的进程希望访问address处的数据。如果访问合法，往data指针里写入数据（通过*data = xxx），并返回0；如果访问不合法，返回-1。

int read(data_unit *data, v_address address, m_pid_t pid);

• 进程号为pid的进程希望往address处写入数据。如果访问合法，往address处写入data，并返回0；如果访问不合法，返回-1。

int write(data_unit data, v_address address, m_pid_t pid);

• 进程号为pid的进程希望申请大小为size的空间。如果空间有剩余，往address指针里写入申请到的地址（通过*address = xxx），并返回0；如果空间不足，返回-1。

int allocate(v_address *address, m_size_t size, m_pid_t pid);

• 进程号为pid的进程希望归还address处开始的空间。如果访问合法，回收空间，返回0；如果访问不合法，即address处的空间不属于pid进程，返回-1。

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
保存信息	pid	start_address	size

该表放在内存的924K～1M处，大小为100KB，最多可以存放10K条记录。

函数实现的调用过程

• 初始化
  1. 初始化数据区：清空物理内存和磁盘的数据区，每个data_unit都设置成0。
  2. 初始化页表：每个页表项根据v_page_id依次填入页表，每个页表项的p_page_id都设为2^24-1 （即24位全为1），载入位in设为0，写入位write设为0，使用位use设为0。
  3. 初始化页位示图：全部设为0，代表空闲。
  4. 初始化内存表：每条记录的pid都设为1000，代表空记录。
• 读取
  1. 检查要读取的内存是否越界（大小>512M）。
  2. 载入内存表，检查是否有权限访问这段内存区域（关于这段区域的记录中pid能够对应）。
  3. 根据逻辑地址计算出逻辑页号和偏移量，根据逻辑页号查页表获得对应的物理页框号。
  4. 如果这个物理页框不在内存中（p_page_id为2^24-1 ），则扫描页表，找出在内存中的使用位use为0的页表项，执行物理页框对换，并把换进内存的页表项use设为1，in设为1，而换出内存的页表项in设为0。
  5. 最后根据新的物理页框号和偏移量，读取需要的数据。
• 写入
  1. 检查要写入的内存是否越界（大小>512M）。
  2. 载入内存表，检查是否有权限访问这段内存区域（关于这段区域的记录中pid能够对应）。
  3. 根据逻辑地址计算出逻辑页号和偏移量，根据逻辑页号查页表获得对应的物理页框号。
  4. 如果这个物理页框不在内存中（p_page_id为2^24-1 ），则扫描页表，找出在内存中的使用位use为0的页表项，执行物理页框对换，并把换进内存的页表项use设为1，in设为1，而换出内存的页表项in设为0。
  5. 最后根据新的物理页框号和偏移量，写入需要的数据。
• 申请空间
  1. 检查要申请的内存是否越界（大小>512M）。
  2. 检查逻辑位示图，找出足够的连续可用页面，记录起始页号和页数（确定可用页面数足够后逻辑内存位示图设置占用）。
  3. 检查物理位示图，如果有空闲的页框，就分配给逻辑页面，更新页表和物理位示图占用。
  4. 添加内存表记录。
• 释放空间
  1. 检查要释放的内存是否越界（起始地址>512M）。
  2. 载入内存表，检查是否有权限释放这段内存区域（关于这段区域的记录中pid能够对应）。
  3. 根据页表更新逻辑位示图和物理位示图的占用信息，更新页表信息。
  4. 删除该条内存表记录，将后面的记录向前移动。