1、在所有 320 指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。3（置换算法:请分别考虑最佳置换算法（OPT）、先进先出（FIFO）算法和最近最久未使用（LRU）算法。4（作业中指令的访问次序按下述原则生成;50%的指令是顺序执行的;25%的指令是均匀分布在前地址部分;25%的指令均匀分布在后地址部分。具体的实现办法是:（1）在0，319之间随机选取一条起始执行指令，其序号为 m; （2）顺序执行下一条指令，其序号为 m+1 条指令;（3）通过随机数，跳转到前地址部分0，m-1中的某条指令处，其序号为 m1; （4）顺序执行下一条指令，即序号为 m1+1 的指令;（5）通过随机数，跳转
2、到后地址部分m1+2,319中的某条指令处，其序号为 m2; （6）顺序执行下一条指令，则序号为 m2+1 的指令;（7）重复跳转到前地址部分，顺序执行，跳转到后地址部分;顺序执行的过程， 直至执行 320 条指令。二、 实验目的 1（通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟储技术的特点。2（ 通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。3（掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。三、 设计思想 在进程运行过程中，若其所要访问的页面不在内存需把它们调入内存，但内存已无空闲空间时，
3、为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪个页面调出，所以需要根据一定的算法来确 定。在这一过程中，选择换出页面的算法称为页面置换算法。一个好的页面置换算法，应具有较低的页面更换频率。页面置换算法的好坏，将直接影响到系统的性 能。以下分别是实验要求的两个页面置换算法的介绍及设计思想。（1） 先进先出法（First In First Out）:该算法总是淘汰最先进入内存的页面，既选择在内存中驻留时间最久的页面予以淘汰。在该算法的模拟过程中，每当页面被置换进入内存时，将置换页面所在的物理块中访问标记设为-1;并且每执行一次指令，便将物理块的访问标记自动
4、加 1，需要置换时将访问标记最大的物理块中的页面置换出去，这样能防止当物理块访问标记出现两个以上相同的值的错误执行，更好地模拟了先进先出法;（2） 最近最久未使用（Least Recently Used）:该算法以最近的过去作为不久将来的近似， 将过去最长一段时间里不曾被使用的页面置换掉。在该算法的模拟过程中，每当物理块中的页面被访问时（包括原先存在的和后来置换进入的页面），便将其物理块访问标记置为,1。以后每执行一条指令，便将物理块中各页面的访问标记加 1，需置换时访问标记最大的便是将要被置换的。（3） 最佳置换算法（OPT）:发生缺页时，有些页面在内存中，其中有一页见很快被访问（也包含紧接
5、着的 下一条指令的那页），而其他页面则可能要到 10、100 或者 1000 条指令后才会被访问，每个页面都可以用在该页面首次被访问前所要执行的指令数进行标记。最佳页面置换算法只是简单地规定:标记最大的页应该被置换。如果某页在八 百万条指令内不会被使用，另一页在 600 万条指令内不会被使用，则置换前一个页面，从而把因需要调回这一页发生的缺页推到将来，越远越好。这个算法唯一的一个问题就是它无法实现。当缺页发生时，操作系统无法知道各个页面下一次是在什么时候被访问。虽然这个算法不可能实现，但是最佳页面置换算法可以用于对可实现算法的性能进行衡量比较。四、 程序流程图及数据结构内存物理块320 条待执
6、行指令 输入一个随机数1-319 显示随机产生的指令执行顺序和页面的调用顺序 选择调页存储算法 OPT LRU 算法FIFO 算法 程序结束 数据结构:typedef struct BLOCK/声明一种新类型物理块类型 int pagenum;/页号 int accessed;/访问字段，其值表示多久未被访问 BLOCK;int count;/程序计数器，用来记录指令的序号int n;/ 缺页计数器，用来记录缺页的次数 static int temp320;/用来存储 320 条随机数 BLOCK blocksize; /定义一大小为 4 的物理块数组void init（ ）; / 程序初始化
7、函数 int findExist（int curpage）;/查找物理块中是否有该页面int findSpace（ ）;/查找是否有空闲物理块 int findReplace（ ）;/查找应予置换的页面void display （ ）;/显示 void Random（ ）;/产生 320 条随机数,显示并存储到 temp320 void pagestring（ ）;/显示调用的页面队列 void OPT（ ）;/OPT 算法void LRU（ ）;/ LRU 算法void FIFO（ ）;/FIFO 算法 五、 程序清单#include #includeconio.h#include #def
8、ine size 4 typedef struct BLOCK/声明一种新类型物理块类型 int pagenum;/ 缺页计数器，用来 记录缺页的次数static int temp320;/ 用来存储 320 条随机数BLOCK blocksize;int findExist（int curpage）;/查找是否有空闲物理块int findReplace（ ）;/ 查找应予置换的页面void display （ ）;/ 显示 /FIFO 算法void init（ ） for（int i=0;isize;i+） blocki.pagenum=-1; blocki.accessed=0; coun
9、t=n=0; int findExist（int curpage） /查找物理块中是否有该页面 iblockpos.accessed） pos = i;/找到应予置换页面，返回 BLOCK 中位置 return pos;void display（ ） if（blocki.pagenum != -1） /物理块不空 printf（ %02d,blocki.pagenum）; coutcount;cout*按照要求产生的 320 个随机数:* for（int i=0;320; tempi=count;if（flag%2=0）count=+count%320;/产生 50%的顺序执行指令（flag=
10、0 或 2 时顺序执行） if（flag=1） count=rand（ ）% （count-1）; /产生 25%的均匀分布在前地址部分指令 if（flag=3） count=count+1+（rand（ ）%（320-（count+1）; /产生 25%的均匀分布在后地址部分指令 flag=+flag%4; %03d,tempi）; if（i+1）%10=0） coutvoid pagestring（ ） /显示调用的页面队列 ,tempi/10）;/最佳置换算法void OPT（ ） int exist,space,position ; int curpage;if（i%100=0） ge
11、tch（ ）; count=tempi; curpage=count/10;exist = findExist（curpage）; if（exist=-1） space = findSpace （ ）; if（space != -1） blockspace.pagenum = curpage; display（ ）;n=n+1; else for（int k=0;kk+） for（int j=i;jj+） if（blockk.pagenum!= tempj/10） blockk.accessed = 1000;/将来不会用，设置为一个很大数 else blockk.accessed = j;
12、break;position = findReplace（ ）; blockposition.pagenum = curpage;n+;缺页次数:n缺页率:（n/320.0）*100%/最近最少使用算法void LRU（ ） int exist,space,position ;int curpage; /getch 直接从键盘获取键值count=tempi; /指令在数组中的位置 curpage=count/10; /指令所在页面 /查找物理块中是否有该页面,若有返回物理块号 if（exist=-1） /物理块中不存在该页 space = findSpace（ ）; /查找是否有空闲物理块if
13、（space != -1） /有空闲物理块 else /无空闲物理块，则寻找置换页面 /查找应予置换的页面blockposition.pagenum = curpage;blockposition.accessed = -1; /恢复刚调入的 BLOCK 中页面 accessed 为-1 display（ ）; n+;else blockexist.accessed = -1;/恢复存在的并刚访问过的 BLOCK 中页面accessed 为-1 for（int j=0; j4; j+） blockj.accessed+; /-先进先出算法void FIFO（ ） /查找物理块中是否有该页面if
14、（exist=-1） blockposition.accessed-; /置换页面所在的物理块中访问标记设为-1 else/若存在该页 if（blocki.pagenum != -1） /物理块不空printf（ %02d 指令已经存在! 其物理块地址为:&blockexist j+） blockj.accessed+; void main（ ） int select;请输入第一条指令号（1320）: ; Random（ ）;*对应的调用页面队列* pagestring（ ）;do cout* coutselect; init（ ）;switch（select） case 1:最佳置换算法 O
15、PT:*OPT（ ）;case 2:最近最久未使用置换算法 LRU:*LRU（ ）;break;case 3:先进先出置换算法 FIFO:*FIFO（ ）; default: ;while（select!=4）;六、 使用说明及运行结果分析运行程序依次测试相应的算法:1、 先输入一个指令号（1-319）随意输入;2、 然后选择测试算法;本程序能通过输入第一条指令号（用 3 位整数代表指令号），产生 320 个随机数，并以每行 10 个显示出来。再把这 320 个随机数转换成对应的页面号，并以每行 10 个显示出来。然后，通过输入选择键，分别执行两个置换算法。各个置换算法能显示页面置换的情况，如
16、果所访问的指令已在内存，则显示“该指令已经存 在”并显示其物理地址;如果所访问的指令还未装入内存，则显示“调入的页面是。”，并显示其调入后的物理地址。所有指令执行完毕后显示缺页次数，和缺页率。基本实现了对请求调页存储器管理方式的模拟。本程序的另一个亮点是使用 getch（ ）使程序的执行过程能够暂停。本程序基本实现了实验要求，但是仍有一定的不足之处。七、 总结 通过本次操作系统实验，使我们对操作系统这门课程有了更进一步的认识和了解，通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟储技术的特点。通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。
17、本实验的难点之一在于如何用c 语言按要求模拟生成随机指令，即 50%的指令是顺序执行的，25%的指令是均匀分布在前地址部分，25%的指令是均匀分布在后地址部分，小组花了大量时间讨论和研究该算法，并参考了相关的资料、运用了随机函数，最终通过一个函数 Random（ ）予以实现。第二，如何较好地模拟出先进先出算法（FIFO）、最近最少使用算法（LRU）也花费了较多时间。在本次设计过程中，用到了许多 C+的基本知识和操作系统的基本原理，是对 平时所学知识的一次考验，尽管这些知识都学过，但运用到实际时，却不知从何下手，而且错误不断，往往为了找一个错误而花了大量的时间，这是专业知识掌握不够，缺乏实践动手能力的表现。在设计的过程中我们发现了许多自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固，以后还要多加努力。总之，通过该实验，使我学到很多知识以及认识到实践的重要性。也使我了解到编写程序不是首要任务，而是一种实现手段。我们最重要的是如何做好需求分析和理清思路，做出正确、简洁的流程设计，这样可以达到事半功倍的效果。教师评语成 绩 : 年 月 日
