资源描述
软件学院综合性、设计性实验报告专业:java年级/班级:2012级 2013 2014学年第一学期课程名称计算机操作系统指导教师学号-姓名1228524012-王宇菲实验地点过街楼B区实验时间2014-12-23项目名称储存管理实验类型综合性/设计性实验目的通过请求页式存储管理中页面置换算法模拟程序,了解虚拟存储技术的特点,掌握请求页式存储管理的页面置换算法。实验仪器或设备实验机房pc电脑总体设计(设计原理、设计方案及流程等)1 .通过随机数产生一个指令序列,共320条指令,指令的地址按下述原则生产:50%的指令是顺序执行的;25 %的指令是均匀分布在前地址部分;25%的指令是均匀分布在后地址部分。2.将指令序列变换成为页地址流设页面大小为1K;用户内存容量为 4页到32页;用户虚存容量为 32K。在用户虚存中,按每 K存放10条指令排列虚存地址,即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 (i =0; i80; 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; k320; k+) pt=ak/10;pd= ak%10 ;(3) 计算不同算法的命中率rate= 1-1.0* U/320 ;其中 U 为缺页中断次数, 320 是页地址流长度。(4) 输出格式k fifo1ru4 0.230.2532 1.01.0四、实验步骤(包括主要步骤、代码分析等)1代码如下#include#include#include#include#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; /iint m = -1, n = -1;/printf(|-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-|n) /* 表格控制 */#define bsize 4 / 物理块大小#define psize 16 / 进程大小typedef struct pageint num; /* 记录页面号 */int time; /*记录调入内存时间 */页面逻辑结构,结构为方便算法实现设计*/内存单元数*/暂保存内存当前的状态:缓冲区 */记录调入队列 */调入队列计数变量*/物理块标号进程序列号进程等待次数( 存放最久未被使用的进程标志)表示进程序列号,j 表示物理块号物理块空闲和进程是否相同判断标志标记替换物理块进程下标int max = -1,maxflag = 0; /int count = 0;/统计页面缺页次数/*/随机产生/*/ 序列号函数/*int* build()printf( 随机产生一个进程序列号为: n);int i = 0;for(i=0; ipsize; i+)proi = 10*rand()/(RAND_MAX+1)+1; printf(%d ,proi);printf(n);return(pro);/*/ 查找空闲物理块/*int searchpb() for(j=0; jbsize; 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;ibsize;i+)phbi=0;count=0;/计数器置零/* / 先进先出页面置换算法/* void FIFO()for(i = 0; ipsize; i+)m=searchpb();n=searchpro();/ 找 flag 值最大的for(j = 0; j 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;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 Init(Page *b,int cbsizepsize)int i,j;for(i=0;ipsize;i+)bi.num=-1;bi.time=psize-i-1;for(i=0;ibsize;i+)for(j=0;jpsize;j+)cij=-1;/* 取得在内存中停留最久的页面, 默认状态下为最早调入的页面*/ int GetMax(Page *b)int i;int max=-1;int tag=0;for(i=0;imax)max=bi.time; tag=i;return tag;/* 判断页面是否已在内存中 */ int Equation(int fold,Page *b)int i;for(i=0;i=0)bval.time=0;for(i=0;ibsize;i+)if (i!=val) bi.time+;elsequeue+K=fold;/* val=GetMax(b); bval.num=fold;记录调入页面*/bval.time=0;for(i=0;ibsize;i+)if (i!=val)bi.time+;void LRU()int i,j;K=-1;Init(b, c);for(i=0;ipsize;i+)Lruu(proi,b);c0i=proi;/*记录当前的内存单元中的页面*/for(j=0;jbsize;j+)cji=bj.num;/* 结果输出 */printf( 内存状态为: n);Myprintf;for(j=0;jpsize;j+)printf(|%2d ,proj);printf(|n);Myprintf;for(i=0;ibsize;i+) for(j=0;jpsize;j+)if(cij=-1)printf(|%2c ,32);elseprintf(|%2d ,cij);printf(|n);Myprintf;printf(n 调入队列为 :);for(i=0;i :29先进先出FIFO算法执行结果:总结体会请求页式管理的基本原理是将逻辑地址空间分成大小相同的页,将存储地址空间分块,页和块的大小相等,通过页表进行管理。页式系统的逻辑地址分为页号和页内位移 量。页表包括页号和块号数据项,它们一一对应。根据逻辑空间的页号,查找页表对应项找到对应的块号, 块号乘以块长,加上位移量就行成存储空间的物理地址。每个作业的逻辑地址空间是连续的,重定位到内存空间后就不一定连续了。对不同算法的性能进行评价。FIFO算法较易实现,对具有线性顺序特征的程序比较适用,而对具有其他特征的 程序则效率不高,此算法还可能出现抖动现象( Belady)异常。LRU算法基于程序的 局部性原理,所以适用用大多数程序, 此算实现必须维护一个特殊的队列一一页面淘汰 队列。OPT算法虽然产生的缺页数最少,然而,却需要预测程序的页面引用串,这是 无法预知的,不可能对程序的运行过程做出精确的断言,不过此理论算法可用做衡量各种具体算法的标准。教师签名:
展开阅读全文