实 验 报 告（三）
课程名称 操作系统实验
学生学院 计算机学院
专业班级 17网络工程一班
学生姓名 陈鸿
指导教师 林穗
2019 年 11 月 23 日
实验三 请求调页存储管理方式的模拟
一、实验目的
通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。
二、实验内容
（1）假设每个页面中可存放10条指令，分配给作业的内存块数为4。
（2）用c语言模拟一个作业的执行过程，该作业共有320条指令，即它的地址空间为32页，目前它的所有页都还未调入内存。在模拟过程中，如果所访问的指令已在内存，则显示其物理地址，并转下一条指令。如果所访问的指令还未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。如果4个内存块均已装入该作业，则需进行页面置换，最后显示其物理地址，并转下一条指令。在所有320指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。
（3）置换算法：采用先进先出（FIFO）、最近最久未使用（LRU）和最佳置换（OPT）算法置换算法。
（4）通过随机数产生一个指令序列，共320条指令。
1）指令的地址按下述原则生成：
① 50%的指令是顺序执行的；
② 25%的指令是均匀分布在前地址部分；
③ 25%的指令是均匀分布在后地址部分；
具体的实施方法是：
① 在[0，319]的指令地址之间随机选取一起点m；
② 顺序执行一条指令，即执行序号为m+1的指令；
③ 在前地址[0，m-1]中随机选取一条指令并执行，该指令的序号为m1；
④ 顺序执行一条指令，其序号为m1+1的指令；
⑤ 在后地址[m1+2，319]中随机选取一条指令并执行,该指令的序号为m2；
⑥ 顺序执行一条指令，其序号为m2+1的指令；
重复上述步骤①～⑥，直到执行320次指令。
2）将指令序列变换为页地址流
设页面大小为1K， 用户虚存容量为32K。在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：
第0条～第9条指令为第0页（对应虚存地址为[0，9]）；
第10条～第19条指令为第1页（对应虚存地址为[10，19]）；
……
……
第310条～第319条指令为第31页（对应虚存地址为[310，319]）。
按以上方式，用户指令可组成32页。
三、实现思路
（1）先进先出法（First In First Out）：
该算法总是淘汰最先进入内存的页面，既选择在内存中驻留时间最久的页面予以淘汰。
在该算法的模拟过程中，每当页面被置换进入内存时，将置换页面所在的物理块中访问标记设为-1；并且每执行一次指令，便将物理块的访问标记自动加1，需要置换时将访问标记最大的物理块中的页面置换出去，这样能防止当物理块访问标记出现两个以上相同的值的错误执行，更好地模拟了先进先出法；
（2）最近最久未使用（Least Recently Used）：
该算法以最近的过去作为不久将来的近似， 将过去最长一段时间里不曾被使用的页面置换掉。
在该算法的模拟过程中，每当物理块中的页面被访问时（包括原先存在的和后来置换进入的页面），便将其物理块访问标记置为－1。以后每执行一条指令，便将物理块中各页面的访问标记加1，需置换时访问标记最大的便是将要被置换的。
（3）最佳置换算法（OPT）：
从主存中移出永远不再需要的页面；如无这样的页面存在，则选择最长时间不需要访问的页面。于所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面，这样可以保证获得最低的缺页率。
四、主要的数据结构（展开批注可查看源代码）
typedef struct BLOCK//声明一种新类型——物理块类型
int count;//程序计数器，用来记录指令的序号
int n;//缺页计数器，用来记录缺页的次数
static int temp[320];//用来存储320条随机数
BLOCK block[size]; //定义一大小为4的物理块数组
void init( ); //程序初始化函数
int findExist(int curpage);//查找物理块中是否有该页面
int findSpace( );//查找是否有空闲物理块
int findReplace( );//查找应予置换的页面
void display ( );//显示
void Random( );//产生320条随机数,显示并存储到temp[320]
void pagestring( );//显示调用的页面队列
void OPT( );//OPT算法
void LRU( );// LRU算法
void FIFO( );//FIFO算法
void main( )
五、算法流程图
六、运行与测试
产生随机数：
FiFo:
七、总结
思考
如果增加分配给作业的内存块数，将会对作业运行过程中的缺页产生什么影响？
M=3时FIFO的命中率为：26.6667% M=3时LRU的命中率为：30%
M=4时FIFO的命中率为：36.6667% M=4时LRU的命中率为：36.6667%
M=5时FIFO的命中率为：50% M=3时LRU的命中率为：46.6667%
M=6时FIFO的命中率为：66.6667% M=6时LRU的命中率为：63.3333%
当分配给作业的内存块数增加时，缺页率将会降低
为什么一般情况下，LRU具有比FIFO更好的性能？
先进先出置换算法（FIFO）：是最简单的页面置换算法。这种算法的基本思想是：当需要淘汰一个页面时，总是选择驻留主存时间最长的页面进行淘汰，即先进入主存的页面先淘汰。其理由是：最早调入主存的页面不再被使用的可能性最大。
最近最久未使用（Least Recently Used）：该算法以最近的过去作为不久将来的近似，将过去最长一段时间里不曾被使用的页面置换掉。在该算法的模拟过程中，每当物理块中的页面被访问时（包括原先存在的和后来置换进入的页面），便将其物理块访问标记置为－1。以后每执行一条指令，便将物理块中各页面的访问标记加1，需置换时访问标记最大的便是将要被置换的。
FIFO 算法将页面进入内存后的时间长短作为淘汰依据，而LRU则是以使用频率作为淘汰依据，一般情况下，LRU之所以比FIFO具有更好的性能是因为长时间驻留并不一定代表不使用，FiFO的淘汰机制有可能增加了缺页率。