


版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、一、实验目的通过模拟实现请求页式存储管理的几种基本页而置换算法,了解虚拟存储技术的特 点,掌握虚拟存储请求页式存储管理中几种基本页而巻换算法的基本思想和实现过程, 并比较它们的效率。二、实验内容基于一个虚拟存储区和内存工作区,设汁下述算法并计算访问命中率。1、最佳淘汰算法(OPT)2、先进先出的算法(FIFO)3、最近最久未使用算法(LRU)4、简单时钟(钟表)算法(CLOCK)命中率=1 一页而失效次数/页地址流(序列)长度三、实验原理UNIX中,为了提髙内存利用率,提供了内外存进程对换机制:内存空间的分配和回收均以 页为单位进行:一个进程只需将苴一部分(段或页)调入内存便可运行:还支持请求
2、调页的存储 管理方式。当进程在运行中需要访问某部分程序和数据时,发现其所在页而不在内存,就立即提岀请求 (向CPU发出缺中断),由系统将其所需页而调入内存。这种页面调入方式叫请求调页。为实现请求调页,核心配宜了四种数据结构:页表、页帧(框)号、访问位、修改位、有效位、 保护位等。当CPU接收到缺页中断信号,中断处理程序先保存现场,分析中断原因,转入缺页 中断处理程序。该程序通过查找页表,得到该页所在外存的物理块号。如果此吋内存未 满,能容纳新页,则启动磁盘I/O将所缺Z页调入内存,然后修改页表。如果内存己满, 则须按某种置换算法从内存屮选出一页准备换出,是否重新写盘由页表的修改位决定, 然后将
3、缺页调入,修改页表。利用修改后的页表,去形成所要访问数据的物理地址,再 去访问内存数据。整个页面的调入过程对用户是透明的。四、算法描述本实验的程序设计基本上按照实验内容进行。即使用snmd()和rand()函数定义 和产生指令序列,然后将指令序列变换成相应的页地址流,并针对不同的算 法计算 出相应的命中率。(1)通过随机数产生一个指令序列,共320条指令。指令的地址按下述原则生成:A: 50%的指令是顺序执行的B: 25%的指令是均匀分布在前地址部分C: 25%的指令是均匀分布在后地址部分具体的实施方法是:A:在0, 319的指令地址之,间随机选取-起点mB:顺序执行一条指令,即执行地址为m+
4、1的指令C:在前地址O.m+1屮随机选取一条指令并执行,该指令的地址为nfD:顺序执行一条指令,其地址为m,+lE:在后地址nf+2, 3中随机选取条指令并执行F:重复步骤A-E,直到320次指令(2)将指令序列变换为页地址流设:页面大小为1K;用户内存(页帧)容量为4页32页;用户虚存容量为32K。在用户虚存中,按每K存放10条指令排列虚存地址,即320条指令在虚存中的存放 方式为:第0条第9条指令为第0页(对应虚存地址为0, 9)第10条第19条指令为第1页(对应虚存地址为110, 19)第310条第319条指令为第31页(对应虚存地址为310, 319) 按以上方式,用户指令可组成32页
5、。五、算法实现与分析1. 常量及变量define total_instruction 320 define total_vp 32define clear_period 50 pfc_type pfctotal_vp, pfc_type *freepf_head, pfc_type *busypf_head, pfc_type *busyrpf_tail;mt diseffect: pl_type plltotal_vp;2. 数据结构typedef structint pn,pfn,counter,time;?pl_type;struct pfc_structint pn,pfn;struc
6、t pfc_struct *next;3. 函数定义mt initialize(int);mt FIFO(int);mt LRU(int):int OPT(int);int CLOCK(int);/抬令流长/虚页故/清周期主存区贞面控制结构数组主存区贞面控制结构的空闲页血头抬针主存区贞面控制结构的忙贞面头抬针主存区贞面控制结构的忙贞面尾描针页错误计数器,初次把贞而载入主存时也X做贞错误/贞面结构数组/贞而结构页面序号/页面所在内存区的帧号/单位时间内访问次数/上次访问的时间/页面控制结构模拟内存中的页集/页面号内存区页面的帧号/页面指针,用于维护内存缓冲区的链式结构/初始化页面结构数组和页面控
7、制结构数组/先进先出算法/最近最久未使用算法最佳置换算法/简单时钟(钟表)算法六、实验结果分析理论上,四种替换算法的命中率由髙到底排列应该是OPT>LRU>CLOCK>FIFO。实际上, 从实验数据观测得到,存在这种由高到低的趋势,由page=4时可以观测到,但是效果不是很 明显。效果不明显的原因:推测与指令流的产生方式有关系。因为指令流的产生方式要能体现局部性原理,所以该 指令流产生设讣为:50%的指令是顺序执的,25%的指令是均匀分布在前地址部分,25%的指 令是均匀分布在后地址部分。但是这样的指令流设计方式能否最佳地体现局部性原理,这还 有待验证。同时,估计和指令数疑有
8、关系。因为320条指令太少了,通常一个稍大点的程序都几千 行指令了。而且由于随即数产生具有一定的波动性,该命中率的汁算也有一立的波动性。所以会有 局部的实验数据与理论不符。改进方法是多次实验取平均值,这样可以减小波动,让实验数 据更加平滑。唯一显著的是OPT算法的命中率与其他3个调度算法保持了比较大的差距。例如在 page二26时,OPT算法就能达到0. 9的命中率了。到后期,由于page越来越大,因此越来越容易命中,因此各替换算法的命中率差距变小 了。这由最后几行命中率相似可以看出。七、实验总结这次实验其实不一立要在linux操作系统下做,在windows操作系统一样可以实现,只要把头 文件
9、稍作修改即可。为了保险起见,我在2个操作系统下都编译过,都没问题。在windows操作系 统,要屏蔽/ffinclude <unistd. h>这句话,在linux操作系统下则启用。此次实验借助于老师提供的主函数main模板,只需要写FIFO, LRU, OPT, CLOCK等4个替换算 法,所以阻力没那么大。每个替换算法必须弄懂英中的细节,写起来才得心应手。一开始做这个实验时,首先是看书,先把书上的替换算法知识点弄明白,要明白各种算法的优缺点和相 互之间衍生互补关系。这四个算法中,难以实现的是LRU算法,因为它涉及到访问时间的计算, 而且它的开销也比较大。OPT算法次难,它需要计
10、算最近访问时间,并替换最近访问时间最大的 页。而FIFO和CLOCK实现起来比较容易,FIFO算法的实现和CLOCK算法的实现很相似,FIFO可视为 CLOCK的退化版。我先写了CLOCK算法,再删去一些约朿条件就退化为FIFO算法。这就是两者的相 同之处。理论上,CLOCK算法需要维持一个循环的主存缓冲区,需要一个循环队列去实现,并且, FIFO算法保持先进先岀,因此需要一个先进先岀队列。但是,我实现这两个算法只用到了单向链 表的数据结构,剩下的由其中的指针去把握了。因此,必须对指针使用有敏锐的感觉。天下无难事,只怕有心人!八、程序源码(在两个系统上都通过)-完整版学习资料分享牡includ
11、e include 社include ttinclude Cifndef<stdio. h> <stdlib. h><unistd. h>/在window操作系统下婆屏蔽此条招令<string h> UNISTD HCdefme _UNISTD_H include <10. H> include <PROCESS. H>»defme TRUE 1define FALSE 0 define INVALID TSdefme total_instruction 320 define total_vp 32define
12、clear_period 50/抬令流长/虚页长/清周期typedef struct /贞面结构tint pn,页面序号ttendifcounter,time;?Pl_type;上次访问的时间pl_type pl2total_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;diseffect;atotal_i
13、nstruction; pagetotal_instruction; offsetCtotal_instruction;/贞面控制结构页面号内存区页向的帧号/页面指针,用于维护内存缓冲区的链式结构mt int mt mt主存区贞面控制结构别名/主存区贞面控制结构数组主存区页面控制结构的空闲页1111头指针/主存区贞面控制结构的忙贞面头指针/主存区贞面控制结构的忙贞面尾抬针贞锚误计数器.初次把贞面载入主存时也"I做贞钳误随即指令流数组/指令对应的页面号指令所在页而中的偏移虽mt mt mt mt mtinitialize(int);FIFO(int);LRU(int);OPT(int)
14、;CLOCK(int);/初始化页面结构数组和页面控制结构数组/先进先岀算法/嵌近最久未使用算法/巌佳置换算法/简单时钟(钟表)算法mtmain()/随机数ai=s; /任选令访问点m ai+l=ai+l; /顺序执行-条指令 ai+21 = (mt)(float)ai*(rand()/(RAND_MAX+1.0); 执行前地址描令m' ai+3=ai+2+l; /顺序执行一条指令printf ( %6d%6d:6d%6dn , a.i, a.il, a.12, ai+3);s = (int)(float)(total_instruction"l)-aLi+2)*(rand(
15、)/(RAXD_MAX+l. 0) + ai+2;mt s;int i,srand(10*getpid(); /*§欢正行时世Q;不同川米作为初始化随机数队列的种子冷/ s = (int)(float)(total_instructionl)*(rand()/(RAXD_MAX+1. 0);printfCn陆机产生抬令流一一十);for (i=0; i<total_instruction; i+=4) /7产生抬令队列printf CW);for (i=0;i<total_instruction;令序列变换成贞地J pagei=ai/10; offset i=a 12 %
16、10;printf Cn一不同页面工作区并种替换策略的命中率表一rT); printfCPaget FIFOt LRUt OPTt CLOCK'n");for (i=4; i<=32; i+)/JU户内存匸作区从个贞面到个贞(filprintfC %2d t",i);FIFO(i);LRU(i);OPT(i);CLOCK(i); printf Cn");return 0; /初始化页面结构数组和页面控制结构数组 /totalpf;用户进程的内存页而数 int initialize (int total_pf)int i; diseffect=O;fo
17、r (1=0;i<total_vp;Dpli.pn=i; plCi.pfn=IWALID; pl ) counter=0; pli time=-l;for(i=0;i<total.pf-l;i+) /貝页血所在主存区的帧号为-1表示该贞不在主存中/置页面结构中的访问次数为/a页面结构中的上次访问的时间为-1Ipfci:. next=&pfci+1;pfciLpfn=i;pfc total_pf-l next=NULL; pfc total pfn=total_pf"l;/建v:pfci-l和pfc 订之间的链接初始化主存区贞倆的帧号freepf_head=&
18、;pfc0; return 0;/主存区贞面控制结构的空闲贞而头抬针指InJpfc 0)/最近最久未使用算法/int total_pf:用户进程的内存页面数int LRU (intmt MinT;int MinPn;鸞箫銀勰 构数组和贞面控制结构数组int i, j;int CurrentTime;initialize(total_pf);CurrentTime=0;diseffect=O;for (i=0; i<total_instruction: ")页面失效if(plpagei pfn=INVALID) diseffect+;if(freepf_head=NULL)MmT
19、=100000;for (j=0; j<total_vp; j+) if (MmT>pljl. time&&plj. pfn!=INVALID)无空能斜误次数加/找出time的最小值,表明该页很久没被访问过MmT=plj time;MinPn=j;freepf_head=&pfcplMinPn pfn; plEMinPnJ.pIALID; time=-l;freepf_head->next=NULL;pltMinPn從娥翻牖般llfll主存/锻久没被访问过的页的访问时何宜为无效pllpageij pfn=freepf_head>pfn; 相应的帧
20、号"plpageLi. time=CurrentTlme;freepf_head=freepf_head->next;elseplpagei time=CurrentTime; CurrentTime+;pnntf (* :6. 3ft", l"(float)diseffect/320); return 0;/有空闲贞【仏把相应的页面换入主存,并把pfn改为/令访问时间为当前系统时间 减少一个空闲页ifti像赠驕錯元的访问时间/垠佳宜换算法./int total_pf;用户进程的内存页ifti数mt OPT (int total_pf)int i, j;in
21、t MaxD;int MaxPn;int dis;int distLtotal_vp;initialize(total_pf); diseffect=0;for(i=0;i<total_instruction;i卄)以时同甲兀氏敞)/将來最近一次访问的距离的最大值的贞号 距离il数器/距离数组,保存距离上一次访问的时间差距个数/初始化页面结构数组和页面控制结构数组if(plpagei. pfn=INVALID) diseffect卄; if(freepf_head=NULL)/页面失效页错谋次数加/无空闲页面for (j=0; j<total_vp; j+)if(plj.pfn!=
22、INVALID) distj=100000;''如縈i雑嬴錨距离值改为最大值elsedistj=O;/如果不在该贞主存中该页关联的跆离值改为dis=l;for (j=i+l; j<total_instruction; j+).从要柠倏的扌旨令的下一条滋起,if (plpagej. pfn! =INVALID &&plpagej. counter=0),7如果该页在 I:.存中.并L是将要最近访问的页/if (plpage.j pfn!=INVALID && dist page j=100000)/此条倍句原理与/初始距离值为上相同次访问di
23、stpage;二dis; pl IpageLjJ counter=l;彳需鯛吳籍去加.区别第一次访何和第二序号入页的帧号. dis十+;MaxD=-l;for (j=0; j<total_vp; j 卄) 'pl j counter=0;if(MaxD<dist LjJ)從臺緞統岁次访问的距离的最大值及其MaxD=distj;MaxPn=j;freepf_head=&pfcpl BfaxPnpfn ;/替换将來段时间最久访问的freepf_head->next=NULL;plMaxPn.pfn=INVALID;plpagei pfn=freepf_head&g
24、t;pfn;/把当前页换入主存中并且把当前页的pfri改为换/iffreepf_head=freepf_head->next;/减少一个空闲贞面/forprintf (* :6. 3ft", l"(float)diseffect/320); return 0;/简单时钟算法/int total_pf;用户进程的内W页面数mt CLOCK(int total_pf)int i;int usetotal_vp;int swap:/使用位swap=0;'发生替换initialize(total_pf);pfc_type *pnext;/时钟抬针pfc.type *h
25、ead;虞歹lj 头指针pnext=freepf_head;head=freepf_head;for (i=0; i<total_vp; i+) useli=0;/初始化使川位为diseffect=O;for (i=0; i<total_instruction; ")if (plpagei.pfn=INVALID) diseffect+; if(freepf_head=NULL)/页面失效不在主存中/页错误次数加/无空闲贞面while(useLpnext>pfnJ=1)的使川位为.则改为片卡JE过usepnext->pfn=0: pnext=pnext&quo
26、t;>next;if(pnext=NULL) pnext=head; 如果时钟指针到达队列尾部.小i® 换出被替换的页 pl pnext">pn. pfn=INV*ALID; swap=l;if (use pnext->pfn =0) /,如果使用位为.则携入相应的页 plpage12 pfn=pnext->pfn; pnext>pn=pageliJ; usepnext->pfn=1; pnext=pnext>next; if(pnext=NULL) pnext=head;if(swap=0) freepf_head=freepf_head->next: ' '/贞面结构中耍标记帧号/页面控制结构中要标记页号重宜使用位为/时钟指针下移如果时钟扌斤针到达队列尾部,重新返回头部)else/页面在主存中use plpage:i pfn
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- GB/T 45828-2025共享闲置物品质量信息描述
- TD/T 1044-2014生产项目土地复垦验收规程
- JJG(烟草)15-2010烟草专用吸阻标准棒检定规程
- 2025学年环翠区八年级上学期历史期末试题:中外历史时间轴历史人物解读
- 化学●广东卷丨2022年广东省普通高中学业水平选择性考试化学试卷及答案
- 被害人陈述38课件
- 考研复习-风景园林基础考研试题附参考答案详解【培优】
- 考研复习-风景园林基础考研试题(研优卷)附答案详解
- 风景园林基础考研资料试题及参考答案详解【基础题】
- 《风景园林招投标与概预算》试题A带答案详解(研优卷)
- 4-02-02-01 国家职业标准客运车辆驾驶员 (2025年版)
- 2024北京西城区四年级(下)期末语文试题及答案
- 【航线补贴绩效评估实证研究-以华夏航空公司为例19000字(论文)】
- 《中国老年高血压管理指南(2023版)》解读
- 电梯五方对讲设计方案
- 24 唐诗三首 《茅屋为秋风所破歌》课件
- 2025年初一下册语文-课内现代文复习23课.《蛟龙探海》(解析版)
- 小升初英语作文写作专题训练题100题(含范文详解)
- 国际化创新型人才培养模式与中俄合作办学实践案例分析
- 附件6工贸高风险企业高危领域较大以上安全风险管控清单
- 一次性使用无菌医疗器械管理制度
评论
0/150
提交评论