1、摘摘 要要 在 linux 中，为了提高内存利用率，提供了内外存进程对换机制，内存空间 的分配和回收均以页为单位进行，一个进程只需要将其一部分调入内存便可运 行；当操作系统发生缺页中断时，必须在内存选择一个页面将其移出内存，以 便为即将调入的页面让出空间。因而引入一种用来选择淘汰哪一页的算法 页面置换算法。页面置换算法是操作系统中虚拟存储管理的一个重要部分。页 面置换算法在具有层次结构存储器的计算机中，为用户提供一个比主存储器容 量大得多的可随机访问的地。 常见的页面置换算法有先来先服务算法(FIFO)， 最 近最久未使用算法(LRU)和最佳适应算法(OPT)。 关键字关键字：操作系统；FIF
2、O；LRU；OPT；Linux 目目 录录 1 绪论. 1 1.1 设计任务 1 1.2 设计思想. 1 1.3 设计特点. 1 1.4 基础知识. 2 1.4.1 先进先出置换算法(FIFO) . 2 1.4.2 最近最久未使用算法(LRU) 3 1.4.3 最佳置换算法(OPT) . 3 2 各模块伪代码算法. 4 2.1 伪代码概念. 4 2.2 伪代码算法. 4 2.2.1 主函数伪代码算法 4 2.2.2 延迟时间函数伪代码算法 6 2.2.3 FIFO 算法的伪代码 7 2.2.4 LRU 算法的伪代码. 7 2.2.5 OPT 算法的伪代码 . 10 3 函数调用关系图. 12
3、3.1 函数声明. 12 3.1.1 主要算法函数 12 3.1.2 辅助函数 12 3.2 程序函数调用关系图. 13 4 测试结果. 14 4.1 数据初始化. 14 4.2 页面调度算法. 14 4.2.1 先进先出算法 15 4.2.2 最近最久未使用 LRU. 15 4.2.3 最佳置换算法 OPT . 17 5 源程序. 18 6 设计总结. 30 参考文献. 31 致 谢. 32 1 绪论绪论 1.1 设计任务设计任务 1、了解 UNIX 的命令及使用格式，熟悉 UNIX/LINUX 的常用基本命令， 练习并掌握 UNIX 提供的 vi 编辑器来编译 C 程序，学会利用 gcc、
4、gdb 编译、调 试 C 程序。 2、设计一个虚拟存储区和内存工作区，并使用最佳淘汰算法（OPT）、先 进先出算法（FIFO）、最近最久未使用算法（LRU）计算访问命中率。（命中 率页面失效次数页地址流长度=1-缺页率） 1.2 设计思想设计思想 在进程运行过程中，若期所有要访问的页面不在内存，而需把它们调入内 存，但内存已无空闲空间时，为了保证进程正常进行，系统必须从内存中调出 一页程序或数据送到磁盘的对换区中。但应将哪个页面调出，须根据一定的算 法来确定。通常，把选择换出页面的算法称为页面置换算法。置换算法的好坏 将直接影响到系统的性能。 不适当的算法可能会导致进程发生“抖动”，即刚被换出的页很快又要被 访问，需要将它重新调入，此时又需要再选一页调出；而此刚被调出的页很快 又被访问，有需将它调入，如此频繁地更换页面，以致一个进程在运行中把大 部分的时间都花费在页面置换工作上。 通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储 技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本 思想和实现过程， 并比较它们的效率。 改进页面置换算法,可以
