实验五存储管理实验报告

1、word计算机与信息技术学院综合性实验报告专业：计算机科学与技术 年级/班级：2009级 20222012学年第一学期课程名称计算机操作系统指导教师 齐娜学号姓名0908114006 司景霞实验地点过街楼D区实验时间周三晚工程名称基于优先数的进程调度实验类型综合性一、 实验目的通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式管理的页面置换算法。二、 实验仪器或设备微型计算机、Linux操作系统、dev C+三、 总体设计1、通过随机数产生一个指令序列，共320条指令。其地址按下述原那么生成：50%的指令是顺序执行的；25%的指令是均匀分布在前地址局部；25%的指

2、令是均匀分布在后地址局部；具体的实施方法是：A.在0，319的指令地址之间随机选取一起点M；B.顺序执行一条指令，即执行地址为M+1的指令；C.在前地址0，M+1中随机选取一条指令并执行，该指令的地址为M；D.顺序执行一条指令，其地址为M+1；E.在后地址M+2，319中随机选取一条指令并执行；F.重复AE，直到执行320次指令。2、指令序列变换成页地址流，设：页面大小为1K；用户内存容量为4页到32页；用户虚存容量为32K。在用户虚存中，按每页存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：第0条第9条指令为第0页对应虚存地址为0，9；第10条第19条指令为第1页对应虚存地址

3、为10，19；第310条第319条指令为第31页对应虚存地址为310，319；按以上方式，用户指令可组成32页。3、计算并输出下述算法在不同内存容量下的命中率。A. FIFO先进先出置换算法；B. LRU最近最久未使用置换算法；C. NUR最近未使用置换算法。命中率=1-页面失效次数/页地址流长度在本实验中，页地址流长度为320，页面失效次数为每次访问相应指令时，该指令所对应的页不在内存的次数。4、相关定义(1)数据结构页面类型typedef struct /*页面结构*/int pn,pfn,time;pl_type;其中pn为页面号，pfn为页帧号，time为访问时间页帧控制结构struc

4、t pfc_struct /*页帧控制结构*/int pn,pfn;struct pfc_struct *next;typedef struct pfc_struct pfc_type;pfc_type pfctotal_vp,*freepf_head,*busypf_head,*busypf_tail;其中pfc_type pfctotal_vp定义用户进程虚页控制结构*freepf_head为空闲页帧头的指针*busypf_head为忙页帧头的指针*busypf_tail忙页帧尾的指针(2)函数定义void initialize(int):初始化函数void FIFO(int):计算使用F

5、IFO算法时的命中率void LRU(int):计算使用LRU算法时的命中率void NRU(int):计算使用NRU算法时的命中率 (3)变量定义int atotal_instruction:指令流数组int diseffect:页面失效次数int pagetotal_instruction:每条指令所属页面号int offsettotal_instruction:每页装入10条指令后取模运算得出的页内偏移地址int total_pf:用户进程的内存页面数四、 实验步骤按照流程图编写代码、并上机调试运行 程序代码：#include <stdlib.h>#include <s

6、tio.h>#define TRUE 1#define FALSE 0#define INVALID -1#define total_instruction 320 /*指令流长*/#define total_vp 32 /*虚页长*/typedef struct /*页面结构*/int pn,pfn,time;pl_type;pl_type pltotal_vp; /*页帧结构数组*/struct pfc_struct /*页帧控制结构*/int pn,pfn;struct pfc_struct *next;typedef struct pfc_struct pfc_type;pfc_

7、type pfctotal_vp,*freepf_head,*busypf_head,*busypf_tail;int diseffect,atotal_instruction;int pagetotal_instruction,offsettotal_instruction;void initialize(int);void FIFO(int);void LRU(int);void NRU(int);int main( )int s,i; /*由于每次运行时进程号不同，故可用来作为初始化随机数队列的“种子*/srand(10*getpid();s=(float)319*rand( )/RAN

8、D_MAX+1;for(i=0;i<total_instruction;i+=4) /*产生指令队列*/ ai=s; /*任选一指令访问点m*/ ai+1=ai+1; /*顺序执行一条指令*/ ai+2=(float)ai*rand( )/RAND_MAX; /*执行前地址指令m' */ ai+3=ai+2+1; /*顺序执行一条指令*/ s=(float)(318-ai+2)*rand( )/RAND_MAX+ai+2+2; for (i=0;i<total_instruction;i+) /*将指令序列变换成页地址流*/ pagei=ai/10; offseti=ai%

9、10;for(i=4;i<=32;i+) /*用户内存工作区从4个页帧到32个页帧*/ printf("%2d page frames ",i);void FIFO(int);void LRU(int);void NRU(int); printf("n"); void initialize(int total_pf) /*初始化相关数据结构*/int i;diseffect=0;for(i=0;i<total_vp;i+) pli.pn=i; pli.pfn=INVALID; pli.time=-1; for(i=0;i<total_p

10、f-1;i+) pfci.next=&pfci+1; pfci.pfn=i; /*建立pfci-1和pfci之间的链接*/pfctotal_pf-1.next=NULL;pfctotal_pf-1.pfn=total_pf-1;freepf_head=&pfc0; /*空页面队列的头指针为pfc0*/void FIFO(int total_pf) /*先进先出算法*/int total_pf; /* 用户进程的内存页面数 */ int i,j;pfc_type *p, *t;initialize(total_pf); /* 初始化相关页面控制用数据结构*/busypf_head

11、=busypf_tail=NULL: /* 忙页面队列头,队列尾链接 */for(i=0;i=total_instruction;i+) if(p1pagei.pfn= =INVALID /* 页面失效 */ disaffect+=1； /* 失效次数 */ iffreep_headf= =NULL /* 无空闲页面 */ p=busypf_head->next; p1busypf_head->pn.pfn=INVALID; freepf_head=busypf_head; /*释放忙页面队列中的第一个页面*/ freepf_head->next=NULL: busypf_h

12、ead=p; p=freepf_head->next; /* 按FIFO方式调新页面入内存页面 */ freepf_head->next=NULL: freepf_head->pn=pagei; p1pagei.pfn=freepf_head->pfn; if(busypf_tail= =NULL) busypf_head=busypf_tail=freepf_head; else busypf_tail->next=freepf_head; busypf_tail=freepf_head; freepf_head=p; printf(“FIFO:%6.4f,1-

13、(float)disaffect/320);void LRU (int total_pf) /*最近最久未使用算法*/int total_pf; int min,minj,i,j,present_time; initialize(total_pf); present_time=0; for(i=0;i<total_instruction;i+) if(p1pagei.pfn= =INVALID) /* 页面失效 */ disaffect+; if(freepf_head= =NULL) /* 无空闲页面 */ min=32767; for(j=0;j<total_vp;j+) if

14、(min>p1j.time&&p1j.pfn !=INVALID) min=p1j.time;minj=j; freepf_head=&pfcp1minj.pfn; p1minj.pfn=INVALID; p1min.time=-1; freepf_head->next=NULL; p1pagei.pfn=freepf_head->pfn; p1pagei.time=present_time; freepf_head=freepf_head->next; else p1pagei.time=present_time; present_time+;

15、 printf(“LRU:%6.4f,1-(flaot)disaffect/320);void NRU(int total_pf) /*最近未使用置换算法*/int total_pf; int i,j,dp,cont_flag,old_dp; pfc_type *t; initialize(total_pf); dp=0; for(i=0;i<total_instruction;i+) if(p1pagei.pfn= =INVALID) /* 页面失效 */ diseffect+; if(freepf_head= =NULL) /* 无空闲页面 */ cont_flag=TRUE; ol

16、d_dp=dp; while(cont_flag) if(p1dp.counter= =0 && p1dp.pfn!=INVALID) cont_flag=FLASE; else dp+; if(dp= =total_vp) dp=0; if(dp= =old_dp) for(j=0;j<total_vp;j+) p1j.counter=0; freepf_head=&pfcp1dp.pfn; p1dp.pfn=INVALID; freepf_head->next=NULL: p1pagei.pfn=freepf_head->pfn; freepf_h

17、ead=freepf_head->next; else p1pagei.counter=1; if(i%clear_period= =0) for(j=0;j<total_vp;j+) p1j.counter=0; printf(“NUR:%6.4f,1-(float)disaffect/320);void OPT(total_pf)int total_pf; int i,j,max,maxpage,d,disttotal_vp; pfc_type *t; initialize(total_pf); for(i=0;i<total_instruction;i+) if(p1p

18、agei.pfn= =INVALID) diseffect+; if(freepf_head= =NULL) for(j=0;j<total_vp;j+) if(p1j.pfn !=INVALID) distj=32767; else distj=0; d=1; for(j=i+1;j<total_instruction;j+) if(p1pagej.pfn!=INVALID) distpagej=d; d+; max=-1; for(j=0;j<total_vp;j+) if(max<distj) max=distj; maxpage=j; freepf_head=&

19、amp;pfcp1maxpage.pfn; freepf_head->next=NULL; p1maxpage.pfn=INVALID; p1pagei.pfn=freepf_head->pfn; freepf_head=freepf_head->next; printf(“OPT:%6.4f,1-(float)disaffect/320);显示结果：4 page frames FIFO:0.4969 LRU:0.5000 NUR:0.50005 page frames FIFO:0.5188 LRU:0.5125 NUR:0.50626 page frames FIFO:0

20、.5281 LRU:0.5188 NUR:0.53447 page frames FIFO:0.5406 LRU:0.5500 NUR:0.55628 page frames FIFO:0.5500 LRU:0.5719 NUR:0.55319 page frames FIFO:0.5625 LRU:0.5812 NUR:0.578110 page frames FIFO:0.5844 LRU:0.5969 NUR:0.596911 page frames FIFO:0.5938 LRU:0.6094 NUR:0.625012 page frames FIFO:0.6156 LRU:0.628

21、1 NUR:0.659413 page frames FIFO:0.6375 LRU:0.6344 NUR:0.650014 page frames FIFO:0.6844 LRU:0.6625 NUR:0.650015 page frames FIFO:0.6844 LRU:0.6812 NUR:0.687516 page frames FIFO:0.7062 LRU:0.7062 NUR:0.709417 page frames FIFO:0.7094 LRU:0.7125 NUR:0.725018 page frames FIFO:0.7188 LRU:0.7281 NUR:0.734419 page frames FIFO:0.7281 LRU:0.7531 NUR:0.753120 page frames FIFO:0.7281 LRU:0.7656 NUR:0.759421 page frames FIFO:0.7812 LRU:0.7781 NUR:0.790622 page frames FIFO:0.7875 LRU:0.7937 NUR:0.812523 page frames FIFO:0.7960 LRU:0.8094 NUR:0.81872