2022年实验五、存储管理实验报告.docx
精选学习资料 - - - - - - - - - 运算机与信息技术学院综合性试验报告专业：运算机科学与技术 年级 / 班级： 2022 级 20222022 学年第一学期课程名称 运算机操作系统 指导老师 齐娜学号姓名 0908114006 司景霞试验地点 过街楼 D区 试验时间 周三晚项目名称 基于优先数的进程调度 试验类型 综合性一、试验目的通过恳求页式储备治理中页面置换算法模拟设计,明白虚拟储备技术的特点,把握恳求页式治理的页面置换算法；二、试验仪器或设备微型运算机、 Linux 操作系统、 dev C+ 三、总体设计1、通过随机数产生一个指令序列,共 50%的指令是次序执行的；320 条指令；其地址按下述原就生成：25%的指令是匀称分布在前地址部分；25%的指令是匀称分布在后地址部分；详细的实施方法是：A. 在0 ,319 的指令地址之间随机选取一起点 M；B. 次序执行一条指令,即执行地址为 M+1的指令；C.在前地址 0 ,M+1中随机选取一条指令并执行,该指令的地址为 M ；D.次序执行一条指令,其地址为 M+1；E. 在后地址 M+2, 319 中随机选取一条指令并执行；F. 重复 A E,直到执行 320 次指令；2、指令序列变换成页地址流,设：页面大小为 1K；用户内存容量为 4 页到 32 页；用户虚存容量为 32K；在用户虚存中, 按每页存放 10 条指令排列虚存地址,即 320 条指令在虚存中的存放方式为：第 0 条第 9 条指令为第0 页（对应虚存地址为0 , 9 ）；第 10 条第 19 条指令为第1 页（对应虚存地址为10 ,19 ）； 河南师范高校运算机与信息技术学院名师归纳总结 - - - - - - -第 1 页,共 8 页精选学习资料 - - - - - - - - - 第 310 条第 319 条指令为第31 页（对应虚存地址为310 ,319 ）；按以上方式,用户指令可组成 32 页；3、运算并输出下述算法在不同内存容量下的命中率；A. FIFO 先进先出置换算法；B. LRU 最近最久未使用置换算法；C. NUR 最近未使用置换算法；命中率 =1- 页面失效次数 / 页地址流长度在本试验中,页地址流长度为 页不在内存的次数；4、相关定义 1 数据结构1 页面类型320,页面失效次数为每次拜访相应指令时,该指令所对应的typedef struct /* 页面结构 */ int pn,pfn,time; pl_type; 其中 pn为页面号, pfn 为页帧号, time 为拜访时间2 页帧掌握结构struct 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 initializeint: 初始化函数void FIFOint: 运算使用 FIFO算法时的命中率void LRUint: 运算使用 LRU算法时的命中率void NRUint: 运算使用 NRU算法时的命中率 3 变量定义int atotal_instruction: 指令流数组int diseffect: 页面失效次数int pagetotal_instruction: 每条指令所属页面号int offsettotal_instruction:每页装入 10条指令后取模运算得出的页内偏移地址 河南师范高校运算机与信息技术学院名师归纳总结 - - - - - - -第 2 页,共 8 页精选学习资料 - - - - - - - - - int total_pf: 用户进程的内存页面数 四、试验步骤 根据流程图编写代码、并上机调试运行程序代码：#include <stdlib.h> #include <stio.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_type pfctotal_vp,*freepf_head,*busypf_head,*busypf_tail; int diseffect,atotal_instruction; int pagetotal_instruction,offsettotal_instruction; void initializeint; void FIFOint; void LRUint; void NRUint; int main int s,i; /* 由于每次运行时进程号不同,故可用来作为初始化随机数队列的“ 种子”*/ srand10*getpid; s=float319*rand /RAND_MAX+1; fori=0;i<total_instruction;i+=4 /* 产生指令队列 */ ai=s; /*任选一指令拜访点m*/ ai+1=ai+1; /*次序执行一条指令*/ ai+2=floatai*rand /RAND_MAX; /*执行前地址指令m' */ ai+3=ai+2+1; /*次序执行一条指令*/ s=float318-ai+2*rand /RAND_MAX+ai+2+2; for i=0;i<total_instruction;i+ /*将指令序列变换成页地址流*/ pagei=ai/10; 河南师范高校运算机与信息技术学院名师归纳总结 - - - - - - -第 3 页,共 8 页精选学习资料 - - - - - - - - - offseti=ai%10; fori=4;i<=32;i+ /*用户内存工作区从4个页帧到 32个页帧 */ printf"%2d page frames ",i; void FIFOint; void LRUint; void NRUint; printf"n" void initializeint total_pf /*初始化相关数据结构*/ int i; diseffect=0; fori=0;i<total_vp;i+ pli.pn=i; pli.pfn=INVALID; pli.time=-1; fori=0;i<total_pf-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 FIFOint total_pf /* 先进先出算法 */ int total_pf; /* 用户进程的内存页面数 */ int i,j; pfc_type *p, *t; initializetotal_pf; /* 初始化相关页面掌握用数据结构*/ busypf_head=busypf_tail=NULL: /* fori=0;i=total_instruction;i+ 忙页面队列头 , 队列尾链接 */ ifp1pagei.pfn= =INVALID） /* 页面失效 */ disaffect+=1； /* 失效次数 */ if（ freep_headf= =NULL ） /* 无闲暇页面 */ p=busypf_head->next; p1busypf_head->pn.pfn=INVALID; freepf_head=busypf_head; /*释放忙页面队列中的第一个页面*/ freepf_head->next=NULL: busypf_head=p; p=freepf_head->next; /* 按 FIFO 方式调新页面入内存页面 */ freepf_head->next=NULL: 河南师范高校运算机与信息技术学院名师归纳总结 - - - - - - -第 4 页,共 8 页精选学习资料 - - - - - - - - - freepf_head->pn=pagei; p1pagei.pfn=freepf_head->pfn; ifbusypf_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-floatdisaffect/320; void LRU int total_pf /*最近最久未使用算法*/ int total_pf; int min,minj,i,j,present_time; initializetotal_pf; present_time=0; fori=0;i<total_instruction;i+ ifp1pagei.pfn= =INVALID /* 页面失效 */ disaffect+; iffreepf_head= =NULL /* 无闲暇页面 */ min=32767; forj=0;j<total_vp;j+ ifmin>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+; printf“LRU:%6.4f ” ,1-flaotdisaffect/320; void NRUint total_pf /* 最近未使用置换算法*/ int total_pf; int i,j,dp,cont_flag,old_dp; pfc_type *t; 河南师范高校运算机与信息技术学院名师归纳总结 - - - - - - -第 5 页,共 8 页精选学习资料 - - - - - - - - - initializetotal_pf; dp=0; fori=0;i<total_instruction;i+ ifp1pagei.pfn= =INVALID /* 页面失效 */ diseffect+; iffreepf_head= =NULL /* 无闲暇页面 */ cont_flag=TRUE; old_dp=dp; whilecont_flag ifp1dp.counter= =0 && p1dp.pfn.=INVALID cont_flag=FLASE; else dp+; ifdp= =total_vp dp=0; ifdp= =old_dp forj=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_head=freepf_head->next; else p1pagei.counter=1; ifi%clear_period= =0 forj=0;j<total_vp;j+ p1j.counter=0; printf“NUR:%6.4f” ,1-floatdisaffect/320; void OPTtotal_pf int total_pf; int i,j,max,maxpage,d,disttotal_vp; pfc_type *t; initializetotal_pf; fori=0;i<total_instruction;i+ ifp1pagei.pfn= =INVALID diseffect+; iffreepf_head= =NULL forj=0;j<total_vp;j+ ifp1j.pfn .=INVALID 河南师范高校运算机与信息技术学院名师归纳总结 - - - - - - -第 6 页,共 8 页精选学习资料 - - - - - - - - - distj=32767; else distj=0; d=1; forj=i+1;j<total_instruction;j+ ifp1pagej.pfn.=INVALID distpagej=d; d+; max=-1; forj=0;j<total_vp;j+ ifmax<distj max=distj; maxpage=j; freepf_head=&pfcp1maxpage.pfn; freepf_head->next=NULL; p1maxpage.pfn=INVALID; p1pagei.pfn=freepf_head->pfn; freepf_head=freepf_head->next; printf“ OPT:%6.4f ” ,1-floatdisaffect/320; 显示结果：4 page frames FIFO:0.4969 LRU:0.5000 NUR:0.5000 5 page frames FIFO:0.5188 LRU:0.5125 NUR:0.5062 6 page frames FIFO:0.5281 LRU:0.5188 NUR:0.5344 7 page frames FIFO:0.5406 LRU:0.5500 NUR:0.5562 8 page frames FIFO:0.5500 LRU:0.5719 NUR:0.5531 9 page frames FIFO:0.5625 LRU:0.5812 NUR:0.5781 10 page frames FIFO:0.5844 LRU:0.5969 NUR:0.5969 11 page frames FIFO:0.5938 LRU:0.6094 NUR:0.6250 12 page frames FIFO:0.6156 LRU:0.6281 NUR:0.6594 13 page frames FIFO:0.6375 LRU:0.6344 NUR:0.6500 14 page frames FIFO:0.6844 LRU:0.6625 NUR:0.6500 15 page frames FIFO:0.6844 LRU:0.6812 NUR:0.6875 16 page frames FIFO:0.7062 LRU:0.7062 NUR:0.7094 17 page frames FIFO:0.7094 LRU:0.7125 NUR:0.7250 18 page frames FIFO:0.7188 LRU:0.7281 NUR:0.7344 19 page frames FIFO:0.7281 LRU:0.7531 NUR:0.7531 20 page frames FIFO:0.7281 LRU:0.7656 NUR:0.7594 21 page frames FIFO:0.7812 LRU:0.7781 NUR:0.7906 22 page frames FIFO:0.7875 LRU:0.7937 NUR:0.8125 23 page frames FIFO:0.7960 LRU:0.8094 NUR:0.8187 河南师范高校运算机与信息技术学院名师归纳总结 - - - - - - -第 7 页,共 8 页精选学习资料 - - - - - - - - - 24 page frames FIFO:0.8000 LRU:0.8219 NUR:0.8219 25 page frames FIFO:0.8344 LRU:0.8312 NUR:0.8344 26 page frames FIFO:0.8625 LRU:0.8438 NUR:0.8594 27 page frames FIFO:0.8625 LRU:0.8652 NUR:0.8781 28 page frames FIFO:0.8750 LRU:0.8656 NUR:0.8812 29 page frames FIFO:0.8844 LRU:0.8781 NUR:0.8812 30 page frames FIFO:0.8875 LRU:0.8875 NUR:0.8906 31 page frames FIFO:0.8875 LRU:0.8906 NUR:0.9000 32 page frames FIFO:0.9000 LRU:0.9000 NUR:0.9000 五、结果分析与总结从上述结果可知,当内存页面数较少（ 45 页面） 时,5 种算法的命中率差别不大,都是 50%左右；当内存页面为 725 个页面之间时, 5 种算法的拜访命中率大致在 52%至 87%之间变化；但是,FIFO 算法与 OPT算法之间的差别一般在 610 个百分点左右； 当内存页面为 2532 个页面时,由于用户进程的全部指令基本上都已装入内存,从而命中率已增加较大；从而算法之间的差别不大；比较上述 3 种算法,以 NUR算法的命中率最高,LRU算法次之,最终是 FIFO 算法；通过本次综合性试验, 我对储备器治理有了更深一步的学习,同时将这几种算法比较分析,提高自己分析问题和解决问题的才能；老师签名：年月日河南师范高校运算机与信息技术学院名师归纳总结 - - - - - - -第 8 页,共 8 页
