东南大学-操作系统实验3-页替换算法.pdf

操作系统实验报告 何博伟 2013 年5 月22 日 实验内容 编写程序实现 LRU 算法及其近似算法，并分析各算法的时间复杂度、空间复杂度和实现难 度；通过随机生成页面访问序列，测试所实现算法的的页错误率，并加以比较和分析。 实验目的 通过实验，理解 LRU 页面置换算法的算法思想及其实现方法，比较各种实现算法的复杂度 和实现难度，体会LRU 算法与各种近似算法间的区别，并进而加深对虚拟内存概念的理解。 设计思路及流程图 主函数根据实验材料提供的思路，用如下形式运行： while(已测页面数要求测试页面数) { 1）随机产生新的访问页号 2 ）调用算法决定是否需要置换页面，如需要，调整内存相关状态，更新页错误数 } 其中随机访问的页号由srand 函数根据时间等生成随机种子，然后产生伪随机数。 程序流程图如下： 1 / 9 程序入口 用户输入最大 内存帧数 初始化各变量及容器 N 已测页面数 要求测试页面数？ Y 随机产生访问页号 调用各算法决定是否 要替换页面 统计替换结果，写入 log 程序结束 主要数据结构及其说明 LRU 的计数器实现 使用自定义结构 LRU_w_counter 实现每一个帧项目的数据结构，里面存储页面ID 号以及计 数器值。运行时，遍历一个这个结构的数组lru_w_counter_list 实现替换算法。 2 / 9 LRU 的栈实现 栈顶指针 Item … Item Item … Item 栈底指针 使用自定义结构LRU_s_Item 来实现每一个帧项目的数据结构，里面存储页面ID 号，头 指针、尾指针以实现双向链表的结构。 容器使用自定义结构LRU_s_Container 来实现一个栈，作为帧的容器。结构中有栈顶、 栈底指针，容量以及实际使用量。使用函数Push 来向栈顶增加一个元素(如果空间没有填满)， 函数Replace 来将栈底的元素（最少访问的元素）替换为某个新元素，函数TryAccess 实现尝 试页面的访问，如果出现页错误那替换或是增加相关的页，当出现页错误时返回true