虚拟存储管理

实验 虚拟存储管理 1、实验目的 页面置换算法是虚拟存储管理实现的关键，通过本次实验理解内存页面调度的机制，在模拟实现FIFO、LRU等页面置换算法的基础上，比较它们的效率及优缺点，从而了解虚拟存储实现的过程，要求做到： (1) 理解内存页面调度的机理。 (2) 掌握几种页面置换算法的实现。 (3) 通过实验比较各种调度算法的优劣。 2、预备知识 参阅教材第五章的相关。 3、实验内容 模拟实现下列几种页面置换算法，对比它们的命中率： (1) 先进先出算法FIFO (FirstInFirstOut) (2) 最近最少使用算法LRU (LeastRecentlyUsed) [提示] 拥有页面交换机制的操作系统总是把当前进程中急需处理的部分页面换入到内存中，而把更多暂时不需要处理的页面放置在外存中。由于进程需要处理的页面顺序不同，因此必须在内存与外存之间进行页面交换，交换算法也就应运而生。 本实验并没有进入系统空间对实际进程页面进行控制，而是在用户空间用线性的连续存储方式对进程页面交换进行模拟。 (1) FIFO页面置换算法 (1) 原理简述 1 在分配内存页面数(AP)小于进程页面数(PP)时，将最先运行的AP个页面放入内存。 2 若需要处理新的页面，则将原来在内存中的AP个页面中最先进入的调出，然后将新页面放入。 3 以后如果再有新页面需要调入，则都按2的规则进行。 (2) 算法特点：所使用的内存页面构成一个队列。 (3) 算法实现 要得到“命中率”，必然应该有一个常量total_instruction来记录页面总共使用的次数；此外还需要一个变量记录总共换入页面的次数（需要换出页面，总是因为缺页中断而产生）diseffect。利用 可以得到命中率。 1 初始化。设置两个数组page[ap]和pagecontrol[pp]分别表示进程页面数和内存分配的页面数，并产生一个随机数序列main[total_instruction]（这个序列由page[]的下标随机构成）表示待处理的进程页面顺序，diseffect置0。 2 看main[]中是否有下一个元素，若有，就由main[]中获取该页面下标，并转到③；如果没有就转到⑦。 3 如果该page已在内存中，就转到②；否则就到④，同时未命中的diseffect加1。 4 观察pagecontrol是否占满，如果占满须将使用队列（一种先进先出的数据结构）中最先进入的（就是队列第一个单元）pagecontrol单元“清干净”，同时将对应的page[]单元置为“不在内存中”。 5 将新调入内存的page[]与pagecontrol[]建立关系（可以改变pagecontrol[]的标志位，也可以采用指针链接，总之至少要使对应的pagecontrol单元包含两个信息：一是它被使用了，二是哪个page[]单元使用的。page[]单元也包含两个信息：对应的pagecontrol单元号和本page[]单元已在内存中）。 6 将用到的pagecontrol置入使用队列，返回②。 7 显示命中率的计算结果，完成。 (2) LRU页面置换算法 (1) 原理简述 1 当分配内存页面数(AP)小于进程页面数(PP)时，把最先执行的AP个页面放入内存。 2 当需要调页面进入内存，而当前分配的内存页面全部不空闲时，选择将其中最长时间没有用到的那个页面调出，以空出内存来放置新调入的页面。 (2) 算法特点：每个页面都有属性来表示有多长时间未被CPU使用的信息。 (3) 算法实现 与前述算法一样，只有先得到diseffect才能获得最终的“命中率” 1 初始化。主要是进程页面page[]和分配的内存页面pagecontrol[]，同时产生随机序列main[]，diseffect置0。 2 看序列main[]是否有下一个元素，如果有，就从main[]获取该page[]的下标，并转到③；如果没有就转到⑥。 3 如果该page[]单元在内存中便改变页面属性，使它保留“最近使用”的信息，转到②；否则转到④，同时diseffct加1。 4 判断是否有空闲的内存页面，如果有，就返回页面指针，转到⑤；否则，在内存页面中找出最长时间没有使用到的页面，将其“清干净”，并返回该页面指针。 5 需要处理的page[]与④中得到的pagecontrol[]之间建立联系，同时让对应的page[]单元保存“最新使用”的信息，返回②。 6 如果序列处理完成，就输出命中率的计算结果，并结束。