面置换算法FIFONURLRULFU

1、09 号 编学生实习报告20112012学年第一学期实习类别 科研训练学生姓名 某某某专 业软件开发与测试学 号 0913117XX指导教师 陈占芳学 院软件学院2011年12月起止周17 18周数2实习地点软件学院专业实验室实训目的：操作系统是计算机专业的核心专业课，“操作系统课程设计”是理解和巩固操作系统基本理论、原理和方法的重要的实践环节。主要任务是实现操作系统和相关系统软件的设计，其中涉及进程创建，同步，进程间的通信，存储管理，文件系统等操作系统概念。实训要求：1）对需要上机完成的题目进行认真分析，列出实验具体步骤，写出符合题目要求的程 序清单，准备出调试程序使用的数据。2）以完整的作

2、业包的形式提交原始代码、设计文档和可运行程序。课程设计报告字数 不少于2000字。实训进度安若卜及主要内容：第一周：查阅资料、总体设计第二周：详细设计、文档编写成绩：指导教师/带队教师（签字）目录第一章概述 2 -第二章设计基本原理 3 - 第三章 总体设计 5 -3.1 分析算法结构- 5 -3.2 算法流程图- 6 -3.2.1 FIFO 页面置换算法 - 6 -3.2.2 LRU页面置换算法 - 7 -3.2.3 LFU页面置换算法 - 8 - 第四章详细设计 9 -4.1 main 函数- 9 -4.2 FIFO 函数- 9 -4.3 LRU 函数- 10 -4.4 NUR 函数- 1

3、1 -4.5 LFU 函数 - 12 -4.6 initialize 主函数 - 13 -第五章测试 14 - 第六章总结 16 - 第七章参考文献 16 -第一章概述设计任务：请求页式管理是一种常用的虚拟存储管理技术。本设计通过请求页式存储管理中 页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式管理的页面置换算 法。通过随机数产生一个指令序列，共 320条指令。指令的地址按下述原则生成:50%的指令是顺序执行的；25%的指令是均匀分布在前地址部分；25%的指令是均匀分布在后地址部分。实施方法：在0,319的指令地址之间随机选取一起点 m；顺序执行一条指令；在前地址0,m+1中随机选

4、取一条指令并执行，该指令的地址为m'顺序执行一条指令，其地址为 m' +1;在后地址m ' +2,319中随机选取一条指令并执行 ；重复上述步骤，直到执行320次指令。将指令序列变换成为页地址流设：页面大小为1K;用户内存容量为4页到32页；用户虚存容量为32K 。在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中 的放方式为：第0条第9条指令为第0页（对应虚存地址为0,9）;第10条第19条指令为第1页（对应虚存地址为10,19）;第310条第319条指令为第31页（对应虚存地址为310,319）按以上方式，用户指令可组成 32页。计算并输出下述各

5、种算法在不同内存容量下的命中率。先进先出的算法（FIFO）;最近最少使用算法（LRu）;最少访问页面算法（LFu）;最近最不经常使用算法（NUR）。第二章设计基本原理（1） .请求页式存储管理的实现原理请求页式管理的基本原理是将逻辑地址空间分成大小相同的页，将存储地址空间分块,页和块的大小相等，通过页表进行管理。页式系统的逻辑地址分为页号和页内位移量。页表包括页号和块号数据项，它们一一对应。根据逻辑空间的页号，查找页表对应项 找到对应的块号，块号乘以块长，加上位移量就行成存储空间的物理地址。每个作业 的逻辑地址空间是连续的，重定位到内存空间后就不一定连续了。（2） .各种页面置换算法的实现思想

6、FIFO算法总是淘汰最先调入主存的页面，即淘汰在主存中驻留时间最长的页面，认为 驻留时间最长的页不再使用的可能性较大。LRU算法淘汰的页面是最近一段时间内最久未被访问的那一页，它是基于程序局部性 原理来考虑的，认为那些刚被使用过的页面可能还要立即被使用，而那些在较长时间 内未被使用的页面可能不会立即使用。LFU即最不经常使用页置换算法，要求在页置换时置换引用计数最小的页，因为经常 使用的页应该有一个较大的引用次数。但是有些页在开始时使用次数很多，但以后就 不再使用，这类页将会长时间留在内存中，因此可以将引用计数寄存器定时右移一位, 形成指数衰减的平均使用次数。算法提示：2.1 中率=1 - 页

7、面失效次数/页地址流长度在本实验中，页地址流长度为 320,页面失效次数为每次访问相应指令时，该指 令所对应的页不在内存的次数。2.2 机数产生办法关于随机数产生办法， Windwos系统提供函数srand()和rand(),进行初始化 和产生随机数。例如：#include <time.h>srand( (unsigned)time( NULL );语句可初始化一个随机数；ao=10 * rand( ) / 32767 * 319 + 1;a1= 10 * rand( ) / 32767 * ao;语句可用来产生a0与a1中的随机数。第三章总体设计3.1分析算法结构3.2算法流程图

8、3.2.1 FIFO页面置换算法N3.2.2 LRU页面置换算法3.2.3 LFU页面置换算法第四章详细设计2.3 main 函数int main()int S,i;srand(int)time(NULL);S=(int)rand()%320;for(i=0;i<total_instruction;i+=1).ai=S;ai+1=ai+1;ai+2=(int)rand()%320;ai+3=ai+2+1;S=(int)rand()%320;for(i=0;i<total_instruction;i+)pagei=ai/10;offseti=ai%10;2.4 FIFO 函数void

9、 FIFO(int total_pf)int i,j;pfc_type *p;initialize(total_pf);busypf_head=busypf_tail=NULL;for(i=0;i<total_instruction;i+).if(plpagei.pfn=INVALID)diseffect+=1;if(freepf_head=NULL).p=busypf_head->next;plbusypf_head->pn.pfn=INVALID;freepf_head=busypf_head;freepf_head->next=NULL; busypf_head=

10、p;.p=freepf_head->next;freepf_head->next=NULL;freepf_head->pn=pagei;plpagei.pfn=freepf_head->pfn;if(busypf_tail=NULL)busypf_head=busypf_tail=freepf_head; elsebusypf_tail->next=freepf_head;busypf_tail=freepf_head; 一一freepf_head=p;.printf(" %6.4付",1-(float)diseffect/320);2.5 L

11、RU函数void LRU(int total_pf)int min,minj,i,j,present_time;initialize(total_pf);present_time=0;for(i=0;i<total_instruction;i+).if(plpagei.pfn=INVALID)diseffect+;if(freepf_head=NUL).min=32767;for(j=0;j<total_vp;j+)if(min>plj.time&&plj.pfn!=INVALID)min=plj.time;minj=j;freepf_head=&pf

12、cplminj.pfn;plminj.pfn=INVALID;plminj.time=-1;freepf_head->next=NUL;.plpagei.pfn=freepf_head->pfn;plpagei.time=present_time;freepf_head=freepf_head->next;elseplpagei.time=present_time;present_time+;.printf(" %6.4付",1-(float)diseffect/320);2.6 NUR函数void NUR(int total_pf).int i,j,dp

13、,cont_flag,old_dp;pfc_type *t;initialize(total_pf);dp=0;for(i=0;i<total_instruction;i+).if(plpagei.pfn=INVALID)diseffect+;if(freepf_head=NUL)cont_flag=TRUE;old_dp=dp;while(cont_flag)if(pldp.counter=0&&pldp.pfn!=INVALID) cont_flag=FALSE;elsedp+;if(dp=total_vp)dp=0;if(dp=old_dp)for(j=0;j<

14、;total_vp;j+)plj.counter=0;freepf_head=&pfcpldp.pfn;pldp.pfn=INVALID;freepf_head->next=NUL;plpagei.pfn=freepf_head->pfn;freepf_head=freepf_head->next;elseplpagei.counter=1;if(i%clear_period=0)for(j=0;j<total_vp;j+)plj.counter=0;printf(" %6.4付",1-(float)diseffect/320);2.7 LF

15、U函数void LFU (int total_pf)int i,j,min,minpage;pfc_type *t;initialize(total_pf);for(i=0;i<total_instruction;i+) if(plpagei.pfn=INVALID) diseffect+;if(freepf_head=NULL) min=32767;for(j=0;j<total_vp;j+)if(min>plj.counter&&plj.pfn!=INVALID) min=plj.counter;minpage=j;plj.counter=0;freepf

16、_head=&pfcplminpage.pfn;plminpage.pfn=INVALID;freepf_head->next=NULL;plpagei.pfn=freepf_head->pfn;plpagei.counter+;freepf_head=freepf_head->next;elseplpagei.counter+;printf(" %6.4fn”,1-(float)diseffect/320);2.8 initialize 主函数void initialize(int total_pf)int i;diseffect=0;for(i=0;i&

17、lt;total_vp;i+)pli.pn=i;pli.pfn=INVALID;pli.counter=0;pli.time=-1;for(i=1;i<total_pf;i+)pfci-1.next=&pfci;pfci-1.pfn=i-1;pfctotal_pf-1.next=NUL;pfctotal_pf-1.pfn=total_pf-1;freepf_head=&pfc0;第五章测试运行程序，如图:1 *E:£flQ5?gxsDeb uggxs.exe * = 回-1Jfc页面置操算法开始Designed by gx等U-=l物理块数FIFOLRUNURL

18、FU4 paee Frames6.125B0,1375目.15y40.12815 page Franes0.16250.1B25B-12810.1594G page Frames0.18440-19370.1S940_17507 page frames0.21250.22500.18440.215G8 page frames0.25620.25310.23120.23759 page fp&mes0.29370.27810.24690.290G10 pge fiMines0.32810.30630.29690.306011 pa$re Frames0.35940.3531目*3313g

19、.325H12 past franesg.393B0.3R12目.3281R.353113 page Franes0.42199.4031月*36250.37811 E：fefi!gxsDe b uggxs.exe'q 画14page fpanes0.4031.3*380.38126.4313剧15pae Framesa42190.42500.40940.4S00.16page Fpanes0.45800.44370,44690.468B17page Frames0.4S120,471?0-47190.493818page frames0.49690-48750-52500.52191

20、9page £ panes0.51250.515它0.54fc9.26page frames0.281B.SE0。0.S2S0.S71V.21page frames0.S40G0.5750回.56250.60J1.22page frames0.60000.59690.57810.6375.23page frants0.60940.61880.62500.6531.?ApSfe f panes配69所0 »65940*6687R-fi«7S.25page Fpanes0.6969H.715E0.7169R. 7f»fi 326page Frames0.71560.TC620V74S&6.7312EJ27 page fratines0,74060.77810,75910.753128 p