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

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

2、320条指令在虚存中的存放方式为：第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 (

3、i = 0； i< 80； i+ =j = i * 4； aj = m； aj+1 = m+1 ； aj+2 = aj * 1.0 * rand( )/32767 ； aj+3 = aj+2+1m = aj+3+(319-aj+3)* 1.0* rand( )/32767 ；(2) 将指令序列变换成为页地址流for ( k = 0; kv320; k+) pt = ak/10 ;pd= ak%10 ；(3) 计算不同算法的命中率rate= 1-1.0* U/320 ;其中 U 为缺页中断次数， 320 是页地址流长度。(4) 输出格式kfifo1ru40.230.25321.01.0五实

4、验报告1 写出你编写的 C 语言程序。 #include<conio.h>#include<stdio.h>#include<stdlib.h>#include<string.h>#defineMyprintfPage;/*Page bbsize; /* int cbsizepsize; /*int queue100;/*int K;/*记录调入队列 */调入队列计数变量 */int phbbsize=0; / int propsize=0; / int flagbsize = 0; /int i = 0, j = 0,k = 0; /i int

5、 m = -1, n = -1;/物理块标号进程序列号进程等待次数 ( 存放最久未被使用的进程标志 ) 表示进程序列号 ,j 表示物理块号 物理块空闲和进程是否相同判断标志int max = -1,maxflag = 0; /int count = 0;/标记替换物理块进程下标统计页面缺页次数/*/*/随机产生printf("|-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-|n ") /* 表格控制 */#define bsize 4/物理块大小#define psize 16/进程大小typedef struct pageint num; /*记录页面

6、号 */int time; /*记录调入内存时间 */*/页面逻辑结构，结构为方便算法实现设计 内存单元数 */ 暂保存内存当前的状态：缓冲区 */序列号函数/* int* build()printf(" 随机产生一个进程序列号为： n"); int i = 0;for(i=0; i<psize; i+)proi = 10*rand()/(RAND_MAX+1)+1; printf("%d ",proi);printf("n"); return(pro);查找空闲/* 物理块*int searchpb()for(j=0; j&l

7、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();/ 找 flag 值最

8、大的 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;maxflag = 0;coun

9、t+;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 Init(Page *b,int cbsizepsize)int i,j;for(i=0;i<psize;i+)bi.num

10、=-1;bi.time=psize-i-1;for(i=0;i<bsize;i+)for(j=0;j<psize;j+) cij=-1;/* 取得在内存中停留最久的页面 , 默认状态下为最早调入的页面 */ int GetMax(Page *b)int i;int max=-1;int tag=0;for(i=0;i<bsize;i+) if(bi.time>max) max=bi.time; tag=i;return tag;/* 判断页面是否已在内存中 */ int Equation(int fold,Page *b)int i;for(i=0;i<bsize

11、;i+)if (fold=bi.num) return i;return -1;/*LRU 核心部分 */void Lruu(int fold,Page *b)int i;int val; val=Equation(fold,b);if (val>=0)bval.time=0; for(i=0;i<bsize;i+) if (i!=val) bi.time+;else记录调入页面 */queue+K=fold;/* val=GetMax(b); bval.num=fold; bval.time=0;for(i=0;i<bsize;i+)if (i!=val) bi.time+

12、;void LRU()int i,j;K=-1;Init(b, c); for(i=0;i<psize;i+) Lruu(proi,b);c0i=proi;/* 记录当前的内存单元中的页面 */ for(j=0;j<bsize;j+) cji=bj.num;/* 结果输出 */printf(" 内存状态为： n");Myprintf; for(j=0;j<psize;j+) printf("|%2d ",proj);printf("|n");Myprintf;for(i=0;i<bsize;i+) for(j=

13、0;j<psize;j+) if(cij=-1) printf("|%2c ",32);else printf("|%2d ",cij); printf("|n");Myprintf; printf("n 调入队列为 :");for(i=0;i<K+1;i+) printf("%3d",queuei);printf("n 缺页次数为： %6dn 缺页率： %16.6f",K+1,(float)(K+1)/psize);主函数*void mai n()int sei

14、 ;doprintf("tttttt");printf("ttt A-A 欢迎进入操作系统界面A-A ttt");printf("tttttt n");prin tf("ttt ttt");prin tf("ttt 虚拟内存 ttt");prin tf("ttt ttt");prin tf("ttt1、产生随机序列ttt");prin tf("ttt ttt");printf("ttt2、最久未使用(LRU)ttt"

15、);prin tf("ttt ttt");printf("ttt3、先进先出(FIFO)ttt");prin tf("ttt ttt");printf("ttt4、最佳置换算法(OPT)ttt");prin tf("ttt ttt");prin tf("ttt5、三种算法的比较()ttt");prin tf("ttt ttt");printf("ttt0、退出(Exit)ttt");prin tf("ttttttn"

16、);printf(”请选择所要执行的操作(0/1/2/3/4/5):");scan f("%d", &sel);switch(sel) 再见! a-a tttn");system("pause");break;caseO:pri ntf("tttA-A case 1:build();break;case 2:pri ntf(”case 3:pri ntf(”case 5:pri ntf(”prin tf("最久未使用算法default: printf("while(sel!=O);最久未使用算 n

17、");LRU();empty();printf("n");break; 先进先出算 n");FIFO();empty();printf("n");break;先进先出算法 n");FIFO();empty();n ");LRU();empty();break;请输入正确的选项号！");pri ntf("nn ”);break;产生的随机序列:随机产生二个进穩序列号为:最近最少使用算法执行结果如下:1作 一 6 操 -; 的 一 ? 虐+-， aw k 2 要用为1 I 所使态一 6 俘乘L ;

18、霎帝一 1 清氏I8 I 6 ! 4 ： 18 264 ! 9 I 9 ： 9 5 9 : 9为为 籟: 队枕率 入页页先进先出FIFO算法执行结果:2 总结体会请求页式存储管理的实现原理。请求页式管理的基本原理是将逻辑地址空间分成大小相同的页，将存储地址空间分块， 页和块的大小相等，通过页表进行管理。页式系统的逻辑地址分为页号和页内位移量。页表包括页号和块号数据项， 它们一一对应。根据逻辑空间的页号， 查找页表对应项找到对应的 块号，块号乘以块长，加上位移量就行成存储空间的物理地址。每个作业的逻辑地址空间是连续的，重定位到内存空间后就不一定连续了。3.写出这三种页面置换算法的实现思想。FIFO算法总是淘汰最先调入主存的页面，即淘汰在主存中驻留时间最长的页面，认为 驻留时间最长的页不再使用的可能性较大。LRU算法淘汰的页面是最近一段时间内最久未被访问的那一页，它是基于程序局部性 原理来考虑的，认为那些刚被使用过的页面可能还要立即被使用，而那