实验3虚拟存储器管理

1、淮海工学院计算机科学系实验报告书课程名：操作系统原理题目：实验三 虚拟存储器管理班级：Z软件52学号：2017140595姓名：郭文静评语：成绩：指导教师：批阅时间：年月日1、实验目的与要求本实验模拟请求页式虚存管理系统的页面置换情况。实验程序能模拟一个拥有若干个虚页的进程在给定的若干个实页中运行、并在缺页中断发生时分别使用 FIFO 和 LRU 算法进行页面置换的情形。要求程序运行时屏幕能显示出置换过程中的状态信息并输出访问结束时的页面命中率。并通过为该进程分配不同的实页数，来比较几种算法的稳定性。2、实验内容或题目本实验要求使用C/C+ 语言编程模拟一个拥有若干个虚页的进程在给定的若干个实

2、页中运行、并在缺页中断发生时分别使用FIFO 和 LRU 算法进行页面置换的情形。其中虚页的个数可以事先给定（例如10 个），对这些虚页访问的页地址流（其长度可以事先给定，例如20 次虚页访问）可以由程序随机产生，也可以事先保存在文件中。要求程序运行时屏幕能显示出置换过程中的状态信息并输出访问结束时的页面命中率。程序应允许通过为该进程分配不同的实页数，来比较两种置换算法的稳定性。实验说明：（1）设计中虚页和实页的表示本设计利用C/C+/Java 语言的结构体来描述虚页和实页的结构。pnpnpfnpfntimenext虚页结构实页结构在虚页结构中， pn 代表虚页号，因为共10 个虚页，所以 p

3、n 的取值范围是 09。pfn 代表实页号，当一虚页未装入实页时，此项值为 -1 ；当该虚页已装入某一实页时，此项值为所装入的实页的实页号 pfn 。time 项在 FIFO 算法中不使用，在 LRU中用来存放对该虚页的最近访问时间。在实页结构中中， pn 代表虚页号，表示 pn 所代表的虚页目前正放在此实页中。 pfn 代表实页号，取值范围（ 0n-1 ）由动态指派的实页数 n 所决定。 next 是一个指向实页结构体的指针， 用于多个实页以链表形式组织起来， 关于实页链表的组织详见下面第 4 点。（2）关于缺页次数的统计为计算命中率，需要统计在20 次的虚页访问中命中的次数。为此，程序应设

4、置一个计数器count ，来统计虚页命中发生的次数。每当所访问的虚页的pfn项值不为 -1 ，表示此虚页已被装入某实页内，此虚页被命中，count 加 1。最终命中率 =count/20*100% 。（3）LRU算法中“最近最久未用”页面的确定为了能找到“最近最久未用”的虚页面，程序中可引入一个时间计数器countime ，每当要访问一个虚页面时， countime 的值加 1，然后将所要访问的虚页的 time 项值设置为增值后的当前 countime 值，表示该虚页的最后一次被访问时间。当 LRU算法需要置换时，从所有已分配实页的虚页中找出 time 值为最小的虚页就是“最近最久未用”的虚页

5、面，应该将它置换出去。（4）算法中实页的组织因为能分配的实页数 n 是在程序运行时由用户动态指派的， 所以应使用链表组织动态产生的多个实页。 为了调度算法实现的方便， 可以考虑引入 free 和 busy 两个链表： free 链表用于组织未分配出去的实页， 首指针为 free_head ，初始时 n 个实页都处于 free 链表中； busy 链表用于组织已分配出去的实页，首指针为busy_head，尾指针为 busy_tail ，初始值都为 null 。当所要访问的一个虚页不在实页中时，将产生缺页中断。此时若free链表不为空，就取下链表首指针所指的实页，并分配给该虚页。若free 链表为

6、空，则说明n 个实页已全部分配出去，此时应进行页面置换：对于FIFO 算法要将 busy_head 所指的实页从busy链表中取下，分配给该虚页，然后再将该实页插入到busy 链表尾部；对于LRU算法则要从所有已分配实页的虚页中找出 time 值为最小的虚页，将该虚页从装载它的那个实页中置换出去，并在该实页中装入当前正要访问的虚页。3、实验步骤（ 1） 理解好相关实验说明。（ 2） 根据实验说明，画出相应的程序流程图。（ 3） 按照程序流程图，用 C/C+/Java 语言编程并实现。4、流程图主页面FIFO 算法OPT 算法LRU 算法开始取指令取指令中的页号查页表YN 发生缺页中断页标志 =

7、1 ？形成绝对地址输出 * 页号表示发生缺页中断输出绝对地址YN有后续指令取下一条指令结束5、源代码与测试数据与实验结果（可以抓图粘贴）#include iostream.hconst int DataMax=100;const int BlockNum = 10;int DataShowBlockNumDataMax; /用于存储要显示的数组bool DataShowEnableBlockNumDataMax; /用于存储数组中的数据是否需要显示/int DataDataMax=4,3,2,1,4,3,5,4,3,2,1,5,6,2,3,7,1,2,6,1; /测试数据/int N = 20

8、; /输入页面个数int DataDataMax; /保存数据int BlockBlockNum; /物理块int countBlockNum; /计数器int N ; /页面个数int M;/最小物理块数int ChangeTimes;void DataInput(); /void DataOutput();输入数据的函数void FIFO(); / FIFO函数void Optimal(); / Optimal函数void LRU(); / LRU /*函数int main(int argc, char* argv)DataInput();/ DataInput();/ FIFO();/

9、Optimal();/ LRU();/ return 0; int menu;while(true)coutendl;cout*菜单选择*endl;cout*endl;cout*1-FIFO*endl;cout*2-Optimal*endl;cout*3-LRU*endl;cout*0-EXIT*endl;cout*menu;switch(menu)case 1: FIFO();break;case 2: Optimal();break;case 3: LRU();break;default: break;if(menu!=1&menu!=2&menu!=3) break;/*/void Da

10、taInput()coutM;while(M BlockNum) /大于数据个数coutM;coutN;while(N DataMax) / 大于数据个数coutN;cout请输入页面访问序列：endl;for(int i=0;iDatai;void DataOutput()int i,j;for(i=0;iN;i+) /coutDatai ;coutendl;for(j=0;jM;j+)cout ;对所有数据操作for(i=0;iN;i+) /对所有数据操作if( DataShowEnableji )coutDataShowji ;elsecout ;coutendl;cout缺页次数 :

11、ChangeTimesendl;cout缺页率 : ChangeTimes*100/N%endl;void FIFO()int i,j;bool find;int point;int temp; /临时变量ChangeTimes = 0;for(j=0;jM;j+)for(i=0;iN;i+)DataShowEnableji = false; /初始化为false，表示没有要显示的数据for(i=0;i=3 的块，替换后计数值置1，/同时其它的块计数值加1 ，成了（1 3 2），见下面先进先出程序段for(i=0;iN;i+) /对有所数据操作/增加 countfor(j=0;jM;j+)co

12、untj+;find = false; /for(j=0;j M ) /因为i是从0 开始记，而M指的是个数，从1 开始，所以i+1/ 获得要替换的块指针temp = 0;for(j=0;jM;j+)if( temp countj )temp = countj;point = j; /else point = i;获得离的最远的指针/ 替换Blockpoint = Datai;countpoint = 0; /更新计数值/ 保存要显示的数据for(j=0;jM;j+)DataShowji = Blockj;DataShowEnableiM?(j=i?j:i):ji = true; /设置显示数

13、据/ 输出信息cout endl;cout endl;DataOutput();void Optimal()int i,j,k;bool find;int point;int temp; /临时变量，比较离的最远的时候用ChangeTimes = 0;for(j=0;jM;j+)for(i=0;iN;i+)DataShowEnableji = false; /初始化为 false ，表示没有要显示的数据/ for(i=0;iM;i+)/ / counti = 0 ; / for(i=0;iN;i+) /对有所数据操作find = false; /for(j=0;jM;j+)表示块中有没有该数据

14、if( Blockj = Datai )find = true;if( find ) continue; /块中有该数据，判断下一个数据/ 块中没有该数据，最优算法ChangeTimes+; /缺页次数 +for(j=0;jM;j+)/ 找到下一个值的位置find = false;for( k =i;k M ) /因为i 是从0 开始记，而BlockNum 指的是个数，从1 开始，所以i+1/ 获得要替换的块指针temp = 0;for(j=0;jM;j+)if( temp countj )temp = countj;point = j; /获得离的最远的指针else point = i;/

15、替换Blockpoint = Datai;/ 保存要显示的数据for(j=0;jM;j+)DataShowji = Blockj;DataShowEnableiM?(j=i?j:i):ji = true; /设置显示数据/ 输出信息cout endl;cout endl;DataOutput();void LRU()int i,j;bool find;int point;int temp; /临时变量ChangeTimes = 0;for(j=0;jM;j+)for(i=0;iN;i+)DataShowEnableji = false; /初始化为false，表示没有要显示的数据for(i=0

16、;iM;i+)counti = 0 ;for(i=0;iN;i+) /对有所数据操作/增加 countfor(j=0;jM;j+)countj+;find = false; /for(j=0;j M ) /因为i 是从0 开始记，而BlockNum 指的是个数，从1 开始，所以i+1/ 获得要替换的块指针temp = 0;for(j=0;jM;j+)if( temp countj )temp = countj;point = j; /else point = i;获得离的最远的指针/ 替换Blockpoint = Datai;countpoint = 0;/ 保存要显示的数据for(j=0;j

17、M;j+)DataShowji = Blockj;DataShowEnableiM?(j=i?j:i):ji = true; /设置显示数据/ 输出信息cout endl;cout endl;DataOutput();6、分析与思考比较不同实页数下的页面命中率，FIFO 和 LRU 两种置换算法的稳定性方面可以得出何种结论？答：先进先出（ FIFO）算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。 该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列， 并设置一个指针， 称为替换指针， 使它总是指向最老的页面。但该算法与进程实际运行的规律不相适应，

18、因为在进程中， 有些页面经常被访问，比如， 含有全局变量、 常用函数、例程等的页面， FIFO 算法并不能保证这些页面不被淘汰。FIFO 置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。最近最久未使用（ LRU）置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此， LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t, ，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最久未使用的页面予以淘汰。最佳（ OPT）页面置换算法是所有算法中产生页错误率最低的，而且绝对没有Belady异常的问题。它会置换最长时间不会使用的页。最佳页面（OPT）置换算法，是根据最长时间不会使用的页来决策的。这就意味着，需要注意内存中的页面和页面的距离了。因此OPT算法是选择最久未使用的页面进行淘汰的。该算法赋予内存中每个页面一个访问字段，用来记录距离此处的最近页面的距离，这样通过比较，就能把最久未使用的页面淘汰掉。7、实验心得与体会这次实验，通过请求页式虚存管理