页式虚拟存储管理FIFO、LRU和OPT页面置换算法.pdf

1需求分析......................................................2
目的和要求.................................................2
研究内容...................................................2
2概要设计......................................................2
2．1FIFO算法.............................................3
2．2LRU算法...............................................3
2．3OPT算法..............................................3
2．4输入新的页面引用串....................................3
3详细设计.....................................................4
3．1FIFO（先进先出）页面置换算法：.........................4
3．2LRU（最近最久未使用）置换算法：........................4
3．3OPT（最优页）置换算法..................................4
4测试..........................................................5
5运行结果......................................................5
6课程设计总结.................................................10
7参考文献.....................................................10
8附录：源程序清单.............................................10

需求分析

目的和要求

在熟练掌握计算机虚拟存储技术的原理的基础上，利用一种程序设计语言模
拟实现几种置换算法，一方面加深对原理的理解，另一方面提高学生通过编程根
据已有原理解决实际问题的能力，为学生将来进行系统软件开发和针对实际问题
提出高效的软件解决方案打下基础。

研究内容

模拟实现页式虚拟存储管理的三种页面置换算法（FIFO(先进先出)、LRU（最
近最久未使用）和OPT（最长时间不使用）），并通过比较性能得出结论。
前提：

（1）页面分配采用固定分配局部置换。
（2）作业的页面走向和分得的物理块数预先指定。可以从键盘输入也可以
从文件读入。

（3）置换算法的置换过程输出可以在显示器上也可以存放在文件中，但必
须清晰可读，便于检验。

2概要设计

本程序主要划分为4个功能模块，分别是应用FIFO算法、应用LRU算法、
应用OPT算法和页面引用串的插入。

主界面

FIFO算法LRU算法OPT算法新的页面引用

串

2．1FIFO算法

该模块的主要功能是对相应页面引用串进行处理，输出经过FIFO算法处理
之后的结果。

2．2LRU算法

该模块的主要功功能是对相应的页面引用串进行处理，输出经过LRU算法处
理之后的结果。

2．3OPT算法

该模块的主要功功能是对相应的页面引用串进行处理，输出经过OPT算法处
理之后的结果。

2．4输入新的页面引用串

该模块的主要功能是用户自己输入新的页面引用串，系统默认的字符串是0
0000000000000000000，用户可以自定义全新的20个数
字页面引用串。

详细设计

在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但
内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页
程序或数据，送磁盘的对换区中。但应将哪个页面调出，须根据一定的算法来确
定。
一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应
将那些以后不再会访问的页面换出，或将那些在较长时间内不会再访问的页面调
出。

3．1FIFO（先进先出）页面置换算法：

这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在
内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内
存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它
总是指向最老的页面。但该算法与