南昌大学操作系统实验报告存储管理的模拟实现

南 昌 大 学 实 验 报 告-（ 5） 存 储 管 理 的 模 拟 实 现学生姓名： 张皓然 学 号： 5501215001 专业班级： 本硕 151 实验类型： 验证 综合 设计 创新 实验日期： 实验成绩： 一、实验目的存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。本实验的目的是通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式管理的页面置换算法。二、实验内容1过随机数产生一个指令序列，共 320 条指令。其地址按下述原则生成：50%的指令是顺序执行的；25%的指令是均匀分布在前地址部分；25%的指令是均匀分布在后地址部分；#具体的实施方法是：A. 在0，319的指令地址之间随机选区一起点 M;B. 顺序执行一条指令，即执行地址为 M+1 的指令；C. 在前地址0，M+1中随机选取一条指令并执行，该指令的地址为 M;D. 顺序执行一条指令，其地址为 M+1；E. 在后地址M+2，319中随机选取一条指令并执行；F. 重复 AE，直到执行 320 次指令。2指令序列变换成页地址流设：（1）页面大小为 1K；（2） 用户内存容量为 4 页到 32 页；（3） 用户虚存容量为 32K。在用户虚存中，按每 K 存放 10 条指令排列虚存地址，即 320 条指令在虚存中的存放方式为：第 0 条第 9 条指令为第 0 页（对应虚存地址为0，9） ；第 10 条第 19 条指令为第 1 页（对应虚存地址为10，19） ；。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。第 310 条第 319 条指令为第 31 页（对应虚存地址为310，319） ；按以上方式，用户指令可组成 32 页。3. 计算并输出下述各种算法在不同内存容量下的命中率。A. FIFO 先进先出的算法B. LRU 最近最少使用算法CLFU 最少访问页面算法三、实验要求1、需写出设计说明；2、设计实现代码及说明3、运行结果；四、主要实验步骤代码如下：#include #include #include #include #ifndef _UNISTD_H#define _UNISTD_H#include #include #endif#define TRUE 1#define FALSE 0#define INVALID -1#define total_instruction 320 /指令流长#define total_vp 32 /虚页页长#define clear_period 50 /清零周期typedef struct /页面结构int pn, /页面序号pfn, /页面所在内存区的帧号counter, /单位时间内访问量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; /缺页计数器int atotal_instruction; /指令流数组int pagetotal_instruction; /指令对应的页面号int offsettotal_instruction; /指令所在页面的偏移量/初始化页面结构数组和页面控制结构数组int initialize(int);int FIFO(int); /先进先出int LRU(int); /最近最久未使用int OPT(int); /最佳置换算法int CLOCK(int); /clock 置换算法int main( )int s;int i;srand(10*getpid(); s = (int)(float)(total_instruction-1)*(rand()/(RAND_MAX+1.0);printf(n-随机产生指令流 -n);for (i=0; iplj.time&plj.pfn!=INVALID)MinT=plj.time;MinPn=j;/释放最久未访问的页面freepf_head= /最久未访问页面被换出主存plMinPn.pfn=INVALID;/最久未访问页面的访问时间设置为无效 plMinPn.time=-1;freepf_head-next=NULL;plpagei.pfn=freepf_head-pfn; plpagei.time=CurrentTime;freepf_head=freepf_head-next; elseplpagei.time=CurrentTime; CurrentTime+; printf(%6.3ft,1-(float)diseffect/320);return 0;/最佳置换算法int OPT(int total_pf)int i,j;int MaxD; /将来最近一次访问距离的最大值int MaxPn; /对应的页号int dis; /距离计数器int disttotal_vp;initialize(total_pf); diseffect=0;for(i=0;inext=NULL;plMaxPn.pfn=INVALID;plpagei.pfn=freepf_head-pfn; freepf_head=freepf_head-next;/if/forprintf(%6.3ft,1-(float)diseffect/320);return 0;int CLOCK(int total_pf)int i;int usetotal_vp; /使用位int swap;swap=0; initialize(total_pf);pfc_type *pnext; /时钟指针pfc_type *head; /队列头指针pnext=freepf_head;head=freepf_head;for(i=0;ipfn=1) usepnext-pfn=0;pnext=pnext-next;if(pnext=NULL) pnext=head; /形成循环队列/换出被替换的页plpnext-pn.pfn=INVALID;swap=1;if(usepnext-pfn=0) /换入相应的页 plpagei.pfn=pnext-pfn; pnext-pn=pagei; usepnext-pfn=1;pnext=pnext-next;if(pnext=NULL) pnext=head;if(swap=0) freepf_head=freepf_head-next; else/页面在主存中useplpagei.pfn=1; /使用位置 1 printf(%6.3ft,1-(float)diseffect/320);return 0;int FIFO(int total_pf)int i;int usetotal_vp;int swap=0;initialize(total_pf);pfc_type *pnext,*head;pnext=freepf_head;head=freepf_head;for(i=0;ipfn=1)usepnext-pfn=0;pnext=pnext-next;if(pnext=NULL) pnext=head;plpnext-pn.pfn=INVALID;swap=1;if(usepnext-pfn=0) plpagei.pfn=pnext-pfn; pnext-pn=pagei; usepnext-pfn=1;pnext=pnext-next;if(pnext=NULL) pnext=head;if(swap=0) freepf_head=freepf_head-next; printf(%6.3ft,1-(float)diseffect/320);return 0;FIFO 算法流程图：开始页面存入数组 p初始化内存块 page结束Pi是否已在内存中i+Page是否有空将最先装入 page中的页面置换出去直接将 pi装入内存i+i32输出当前页面的 命中率是否是否是否LRU 算法流程图：开始页面存入数组 p初始化内存块 page结束Pi是否已在内存中i+Page是否有空将最近最久未使用的页面从 page中的页面置换出去直接将 pi装入内存i+i32输出当前页面的 命中率是否是否是否OPT 算法流程图：开始页面存入数组 p初始化内存块 page结束Pi是否已在内存中i+Page是否有空将距离最远的页面从page中的页面置换出去直接将 pi装入内存i+i32输出当前页面的 命中率是否是否是否Clock 算法流程图：开始查询指针前进一步页面访问位=0 置页面访问位=0选择该页面淘汰结束是否五、实验数据及处理结果随机产生指令流，并给出不同置换策略的命中率表。发现 OPT 命中率较高。六、实验体会或对改进实验的建议存储管理子系统是操作系统中最重要的组成部分之一，它的目的是方便用户使用和提高存储器利用率。通过这次实验更加清楚了四种页面置换算法的实现过程，通过比较了解到了他们的异同之处。七、参考资料计算机操作系统西安电子科技大学出版社