操作系统课程设计
专题：页面置换算法
任务：设计一个虚拟存储区和内存工作区,编程序演示下述算法的具体实现过程,并计算访问命中率：
要求设计主界面以灵活选择某算法，且以下算法都要实现
1）先进先出算法（FIFO）
2）最近最久未使用算法（LRU）
3）最佳置换算法（OPT）
思想：
1. 最佳置换算法：最佳置换算法是一种理论上的算法，其所选择的被淘汰页面，将是以
后永不使用的，或者是在最长（未来）时间内不再被访问的页面。采用最佳置换算法 ，
通常可保证获得最低的缺页率。
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
7 7 7 2 2 2 2 4 4 4 0 0 0 0 0 0 0 7 7 7
0 0 0 0 0 3 3 3 2 2 2 2 2 1 1 1 1 1 0 0
0 0 1 1 1 1 0 0 0 3 3 3 3 3 2 2 2 2 2 1
2. 先进先出页面置换算法:这是最早出现的置换算法。该算法总是淘汰最先进入内存的页
面，即使选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个
进程已调入内存的页面，按先后次序连接成一个队列，并设置一个指针，成为替换指
针，使它总是指向最老的页面。但该算法与进程实际运行的规律不相适应，因为在进
程中，有些页面经常被访问，所以先进先出算法并不能保证这些页面不被淘汰。
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
7 7 7 2 2 2 2 4 4 4 0 0 0 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 3 3 3 3 3 3 0 0 0 0 0
0 0 1 1 1 3 3 3 2 2 2 2 2 2 2 2 2 7 7 7
3. 最近最久未使用置换算法：最久最久未使用的页面置换算法，是根据页面调入的先后
的使用情况进行决策的。该算法赋予每个页面一个访问字段，用来记录一个页面自上
次被访问以来经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即
使最近最久未使用的页面予以淘汰。
最近最久未使用算法
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
7 7 7 2 2 2 2 2 2 2 2 2 2 2 2 2 2 7 7 7
0 0 0 0 0 0 0 4 4 4 0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1
任务目的：
1．通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟储技术的特点。
2．通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实
现过程的理解。
