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

1、精选优质文档-倾情为你奉上操作系统实验报告实验五 请求页式存储管理的页面置换算法实验目的：通过请求页式存储管理中页面置换算法模拟程序，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。实验属性：设计实验内容：1.通过随机数产生一个指令序列，共320条指令，指令的地址按下述原则生产：50的指令是顺序执行的；25的指令是均匀分布在前地址部分；25的指令是均匀分布在后地址部分。2.将指令序列变换成为页地址流：设页面大小为1K；用户内存容量为4页到32页；用户虚存容量为32K。在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：第0条至第9条指令为第0页；第1

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

3、 1.0 rand( )/32767； aj+3aj+2+1 maj+3+(319-aj+3) 1.0rand( )/32767； (2) 将指令序列变换成为页地址流 for ( k0；k320；k+) ptak/10； pd= ak%10； (3) 计算不同算法的命中率 rate1-1.0U/320 ； 其中U为缺页中断次数，320是页地址流长度。 (4) 输出格式 k fifo 1ru 4 0.23 0.25 32 1.0 1.0实验内容：实现程序：主要的数据结构：void build();int searchpb();int searchpro();void Optimal();void

4、 FIFO();void LRU();void empty();void main();主程序:#include<stdio.h>#include<stdlib.h>#include<string.h>#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,

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

6、t;bsize; j+) if(phbj = 0) m = j; return m; break; return -1;/查找相同进程int searchpro()for(j = 0; j < bsize; j+) if(phbj = proi) n = j; return j; return -1;/初始化内存void empty()for(i=0;i<bsize;i+)phbi=0; count=0; /计数器置零/先进先出页面置换算法void FIFO() for(i = 0; i<psize; i+) m=searchpb(); n=searchpro();/找fla

7、g值最大的 for(j = 0; j < bsize;j+) if(flagj>maxflag) maxflag = flagj; max = j; if(n = -1) /不存在相同进程 if(m != -1) /存在空闲物理块 phbm = proi; /进程号填入该空闲物理块 count+; flagm = 0; for(j = 0;j <= m; j+) flagj+; m = -1; else /不存在空闲物理块 phbmax = proi; flagmax = 0; for(j = 0;j < bsize; j+) flagj+; max = -1; max

8、flag = 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("缺页次数为：%dn",count);printf("n");/主函数*void main()int sel;do printf("ttt-ttt");printf("ttt

9、 -欢迎进入操作系统界面- ttt");printf("ttt-tttn");printf("tttttt"); printf("ttt 虚拟内存 ttt");printf("ttt-ttt"); printf("ttt 1、产生随机序列 ttt");printf("ttt-ttt"); printf("ttt 2、最佳置换算法(OPT) ttt");printf("ttt-ttt"); printf("ttt 3、

10、先进先出(FIFO) ttt");printf("ttt-ttt"); printf("ttt 4、最久未使用(LRU) ttt");printf("ttt-ttt");printf("ttt 5、三种算法的比较 ttt");printf("ttt-ttt");printf("ttt 0、退出(Exit) ttt"); printf("ttttttn"); printf("请选择所要执行的操作(0/1/2/3/4/5):");

11、 scanf("%d",&sel); switch(sel) case0:printf("ttt-再见！- tttn");system("pause");break; case 1:build();break; case 2:printf(最佳置换算法n");Optimal();empty();break; case 3:printf("先进先出算法n");FIFO();empty();break; case 4:printf("最久未使用算法n");LRU();empty()

12、;break; case 5: printf("最佳置换算法n");Optimal();empty();printf("先进先出算法n");FIFO();empty();printf("最久未使用算法n");LRU();empty();break;default: printf("请输入正确的选项号！");printf("nn");break;while(sel!=0);实验结果：图1图2图3实验总结：1请求页式存储管理的实现原理：请求分页虚拟存储管理是将进程信息的副本存放在副主存储器中，当它被

13、调度投入运行时，并不把程序和数据全部装入主存，仅装入当前使用的页面，进程执行过程中访问不在主存的页面时，再把所需信息动态地装入。当需要执行某条指令或使用某个数据而发现他们不在主存时，产生缺页异常，系统从磁盘中把此指令或数据所在的页面装入，保证用不到的页面不会被装入主存。2写出这三种页面置换算法的实现思想。(1) 最佳置换算法(OPT):当要调入一页而必须淘汰旧页时应该淘汰以后不再访问的页或距现在最长时间后要访问的页面。(2) 先进先出(FIFO):基于程序总是按线性顺序来访问物理空间这一假设，总是淘汰最先调入主存的页面，即淘汰在主存中驻留时间最长的页面，认为驻留时间最长的页不再使用的可能性较大。(3) 最久未使用(LRU):最近最少使用页面替换算法淘汰的页面是在最近一段时间内最久未被访问的那一页，基于程序的局部性原理来考虑，认为那些刚被使用过的页面可能还要立即被使用，而那些在较长时间内未被使用的页面可能不会立即使用。3对不同算法的性能进行评价。(1) 最佳置换算法(OPT): 这种算法产生的缺页数最少，却