1、操作系统课程设计 1 操作系统课程设计报告操作系统课程设计报告 题 目：页面置换算法模拟程序设计 专 业：软件工程 院 系：信息管理学院 年 级：大三软件 Q1141 学 号： 姓 名： 指导教师： 职 称：副教授 操作系统课程设计 2 目录目录 第一部分第一部分 概述概述 第二部分第二部分 设计的基本概念和原理设计的基本概念和原理 第三部分第三部分 总体设计总体设计 3.1 算法流程图算法流程图 3.2 算法算法的简要实现方法的简要实现方法 3.2.1 OPT 页面置换算法页面置换算法 3.2.2 FIFO 页面置换算法页面置换算法 3.2.3 LRU 页面置换算法页面置换算法 3.2.4
2、LFU 页面置换算法页面置换算法 第四部分第四部分 详细设计详细设计 4.1 main 函数函数 4.2 OPT 函数函数 4.2 FIFO 函数函数 4.3 LRU 函数函数 4.5 LFU 函数函数 4.6 辅助函数辅助函数 4.6.1 Designer函数函数 4.6.2 mDelay 函数函数 4.6.3 Download 函数函数 4.6.4 Compute 函数函数 4.6.5 showTable 函数函数 第五部分第五部分 实现源代码实现源代码 第六部分第六部分 简要的使用说明简要的使用说明及主要运行界面及主要运行界面 第七部分第七部分 总结总结 第八部分第八部分 参考文献参考文
3、献 操作系统课程设计 3 第一部分 概述 设计任务： 页面置换算法是虚拟存储管理实现的关键， 通过本次课程设计理解内存页面 调度的机制，在模拟实现 OPT、FIFO、LRU 和 LFU 几种经典页面置换算法的基 础上，比较各种置换算法的效率及优缺点，从而了解虚拟存储实现的过程。 操作系统课程设计 4 第二部分 设计的基本概念和原理 (1)(1)页面淘汰机制页面淘汰机制 页面淘汰又称为页面置换。若请求调页程序要调进一个页面，而此时该作业 所分得的主存块已全部用完，则必须淘汰该作业已在主存中的一个页。这时，就 产生了在诸页面中淘汰哪个页面的问题，这就是淘汰算法（或称为置换算法）。 置换算法可描述为
4、，当要索取一个页面并送入主存时，必须将该作业已在主存中 的某一页面淘汰掉，用来选择淘汰哪一页的规则就叫做置换算法。 (2)(2)各种页面置换算法的实现思想各种页面置换算法的实现思想 OPT 算法是当要调入一新页而必须先淘汰一旧业时，所淘汰的那一页应是以 后不要再用的或是以后很长时间才会用到的页。 FIFO 算法的实质是，总是选择在主存中居留时间最长（即最老）的一页淘 汰。其理由是最先调入主存的页面，其不再被使用的可能性比最近调入主存的页 的可能性大。 LRU 算法的实质是，当需要置换一页时，选择最长时间未被使用的那一页淘 汰。如果某一页被访问了，它很可能马上还要被访问；相反，如果它很长时间未
5、曾用过，看起来在最近的未来是不大需要的。 LFU 即最不经常使用页置换算法，要求在页置换时置换在一定时期内引用计 数最小的页，因为经常使用的页应该有一个较大的引用次数。本次设计取整个页 面访问时期为计算周期，实际问题中应根据页面数量多少来确定周期。 操作系统课程设计 5 第三部分 总体设计 3.1 算法流程图 3.2 算法的简要实现方法 选择置换算法，先输入所有页面号，为系统分配物理块，依次进行置换： 最佳置换算法（最佳置换算法（OPTOPT） ： 是用一维数组 pagePSIZE存储页面号序列，memeryMSIZE是存储装入物 理块中的页面，用 pflagPSIZE数组标记缺页中断处。数组
6、 nextMSIZE记录物 输入页面访问序列 取访问的页号 查页表 是否缺页 否 是 置缺页标志 flag为* 按算法不同淘汰一页面 调入所访问的页面 操作系统课程设计 6 理块中对应页面的最后访问时间。每当发生缺页时， 就从物理块中找出最后访问 时间最大的页面，调出该页，换入所缺的页面，然后初始化 nextMSIZE，便于 下次使用。 【特别声明】【特别声明】 若物理块中的页面都不再使用，则每次都置换物理块中第一个位置的页面。若物理块中的页面都不再使用，则每次都置换物理块中第一个位置的页面。 先进先出置换算法（先进先出置换算法（FIFOFIFO） ： 是用一维数组 pagePSIZE存储页面号序列，memeryMSIZE是存储装入物 理块中的页面，用 pflagPSIZE数组标记缺页中断处。采用队列的思想，总是把 最先进入物理块中的页面放在第一个
