请求页式存储管理的页面置换算法

1、操作系统实验报告班级：计科0801班 姓名：边佳 学号：08407102日期：20n年5月19日实验五请求页式存储管理的页面置换算法实验目的：通过请求页式存储管理中页面置换算法模拟程序，了解虚拟存储技术的特点，掌握请求页式 存储管理的页面置换算法。实验属性：设计实验内容：.通过随机数产生一个指令序列，共320条指令，指令的地址按下述原那么生产：50%的指令是顺序执行的；25%的指令是均匀分布在前地址局部；25%的指令是均匀分布在后地 址局部。.将指令序列变换成为页地址流：设页面大小为1K；用户内存容量为4页到32页；用户虚存容量为32KO在用户虚存中，按每K存放10条指令排列虚存地址，即320

2、条指令在虚存中的存放方式为：第0 条至第9条指令为第0页；第10条至19条指令为第1页；第310条至319条指令为第31页。 3.计算并输出下述各种算法在不同内存容量下的命中率。(1)先进先出算法(FIFO)(2)最近最少使用算法(LRU)(3)最正确使用算(OPT)命中率=1 一页面失效次数/页地址流长度本实验中，页地址流长度为320,页面失效次数为每次访问相应指令时，该指令所对应的页不在 内存的次数。实验思路：关于随机数的产生方法，首先要初始化设置随机数，产生序列的开始点，可通过以下语句实现： srand (400)；(1)计算随机数，产生320条指令序列m=160；for(i=0； i8

3、0； i+ = (j=i * 4；aj = m；aj+1=m+1 ；afi+2 =a0 * 1.0 * rand( )/32767；aj+3 =a0+2+1m=aj+3+(319-aj+3) * 1.0 * rand( )/32767； (2)将指令序列变换成为页地址流for(k=0； k320； k+)pt =ak/10；pd= ak%10；(3)计算不同算法的命中率rate=1-1.0 * U/320 ；其中U为缺页中断次数，320是页地址流长度。(4)输出格式k fifo 1 ru4 0.23 0.25 32 1.01.0实验内容：实现程序：主要的数据结构：void build();in

4、t searchpb();int searchpro();void OptimalQ;void FIFO();void LRU();void empty();void main();主程序：#include#include#include#define bsize 4物理块大小#define psize 16/进程大小int phbbsize = 0;物理块标号int propsize = 0;迸程庠列号int flagbsize=0; 进程等待次数(存放最久未被使用的进程标志) int i = 0, j=0,k=0;/i表示进程序列号，j表示物理块号int m = -1, n=-1; 物理块

5、空闲和进程是否相同判断标志int max = -1, maxflag = 0; 标记替换物理块进程下标int count=0;统计页面缺页次数随机产生序列号函数void build()printf (随机产生一个进程序列号为：n);int i = 0;for(i=0; ipsize; i+)proi= 10*rand()/(RAND_MAX+1)+1;printf(%d ,proi);Iprintf (，n,，);查找空闲物理块int searchpb()for(j=0; jbsize; j+)if (phbj = 0) m = j;return m;break; return T;)查找相同

6、进程int searchpro()for(j = 0; j bsize; j+) if(phbj = proi) n = j; return j;) return -1;/初始化内存void empty()for (i=0;ibsize;i+)phbi=0; count=0;计数器置零先进先出页面置换算法void FIFOO for(i = 0; ipsize; i+) m=searchpb();n=searchpro();找flag值最大的for(j = 0; j maxflag) maxflag = flagj; max = j;) )if(n = -1)不存在相同进程 if(m != -

7、1)存在空闲物理块 phbm = proi;进程号填入该空闲物理块count+;flagm = 0;for(j = 0;j二叫 j+) flagj+;)m = -1; else不存在空闲物理块 phbmax= proi;flagmax= 0;for(j = 0;j bsize; j+) flagj+;)max = -1;maxflag = 0; count+; else存在相同的进程phbn= proi;for(j = 0;j bsize; j+) flagj+; n = -1;for(j = 0 ;j bsize; j+)(printf(d ，phbj);printf(n);)printf

8、(缺页次数为：%dnz，, count);printf(n);主函数*void main()int sei;doprintf (，ztttttt);printf (z，ttt欢迎进入操作系统界面八 ttt);printf (z/ttttttn，/);printf;printf (z，ttt虚拟内存 ttt)；printf (z，tttttt);printf (z/ttt1、产生随机序列ttt)；printf (/ztttttt);printf (z，ttt2、最正确置换算法(OPT)ttt)；printf (，ztttttt);printf (/zttti3、先进先出(FIFO)ttt)；pr

9、intf (/ztttttt);printf (z，ttt4、最久未使用(LRU)ttt)；printf (z，tttttt);printf (ttt5、三种算法的比拟 ttt)；printf (/ztttttt);printf (ttt0、退出(Exit) ttt)；printf;printf (请选择所要执行的操作(0/1/2/3/4/5):);scanf(%d, &sel);switch (sei)case。: printf (ttt 八一八再见！ 八一八 tttn)； system (pause) ; break;case 1:build();break;case 2:printf (

10、最正确置换算法n)； Optimal () ; empty () ; break;case 3:printf (先进先出算法n);FIFO() ;empty() ;break;case 4:printf (最久未使用算法n) ;LRU() ;empty() ;break;case 5: printf (最正确置换算法n)；Optimal ();empty ();printf (先进先出算法、n) ;FIFO() ;empty();printf (最久未使用算法n);LRU() ;empty() ;break;default: printf(请输入正确的选项号! )；printf(nn);bre

11、ak;while(sei!=0);实验结果：人-人欢迎进入操作系统界面人-人 虚拟内存1、产生随机序列 2、最久未使用（LRID 3、先进先出FIFO 4、最正确置换算法“PT 5,三种算法的比拟退出Exit会我请选择所要执行的操作 0/1/2 Z3 Z4/5 ： 1髓机产生一个进程序列号为，人欢迎进入操作系统界面人 虚拟内存人产生随机序列2、最久未使用LRU 3、先进先出FIFO 4、最正确置换算法OPT 5、三种算法的比拟。、退出Exit您: 要 匿态 择泰 选久存作(0/1/2/3/4/5)1您: 要 匿态 择泰 选久存作(0/1/2/3/4/5)1：1：1：1：1：5：5：5：5：5：

12、2：2：2：2：4：4： ：6：6：6：6：6：6：6：6：8：8：8：8：8：8：8： !：2：2：2：2：4：4：4：4：4：4：4：6：6：6：!J !9!9J9!9!9!9!9!9!9!9：9!9：1!调入队列为：缺典次数为：调入队列为：缺典次数为：11缺页率：0.687500八一欢迎进入操作系统界面人一虚拟内存1、产生随机序列2,最久未使用LRU)3、先进先出FIFO八一欢迎进入操作系统界面人一虚拟内存1、产生随机序列2,最久未使用LRU)3、先进先出FIFO4、最正确置换算法OPT5、三种算法的比拟70、退出Exit)熟舞懿行的操作0 0222000999999641t页次数为:时

13、，冉北见而恬居、切念地受入。3帝笠外仃呆汆指令取1更用呆T双阳叩友如他11小.写出这三种页面置换算法的实现思想。(1)最正确置换算法(OPT):当要调入一页而必须淘汰旧页时应该淘汰以后不再访问的页或距现在最 长时间后要访问的页面。(2)先进先出(FIFO):基于程序总是按线性顺序来访问物理空间这一假设，总是淘汰最先调入主存 的页面，即淘汰在主存中驻留时间最长的页面，认为驻留时间最长的页不再使用的可能性较大。(3)最久未使用(LRU):最近最少使用页面替换算法淘汰的页面是在最近一段时间内最久未被访问 的那一页，基于程序的局部性原理来考虑，认为那些刚被使用过的页面可能还要立即被使用，而 那些在较长时间内未被使用的页面可能不会立即使用。.对不同算法的性能进行评价。(1)最正确置换算法(OPT):这种算法产生的缺页数最少，