B求分页存储管理页面OptimalFIFOLRU置换算法

1、学号：_湖南农业大学信息科学技术学院学生实验报告姓名：年级专业班级 0707 级计算机 1 1 班日期 0909 年 1212 月 2222 日 成绩【实验目的、要求】目的：（1）通过编写程序实现请求分页存储管理页面Optimal、FIFO、LRU 调度算法，使学生掌握虚拟存储管关缺页处理方法等内容，巩固有关虚拟存储管理的教案内容。（2）了解 Windows2000/XP 中内存管理机制，掌握页式虚拟存储技术。（3）理解内存分配原理，特别是以页面为单位的虚拟内存分配方法。要求：（1）经调试后程序能够正常运行。（2） 采用多进程或多线程方式运行，体现了请求分页存储管理页面Optimal、FIFO

2、、LRU 调度算法的关系。（3）程序界面美观【实验内容】在 Windows XP、Windows2000 等操作系统下，使用的VG VB java 或 C 等编程语言，实现请求分页存储面 Optimal、FIFO、LRU 调度算法。【实验环境】 （含主要设计设备、器材、软件等）VCVC、VBVB、javajava 或 G G 等编程语言 windowswindows xpxp【实验步骤、过程】（含原理图、流程图、关键代码，或实验过程中的记录、数据等）（1）需求分析：了解基本原理，确定程序的基本功能，查找相关资料，画出基本的数据流图；（2）概要设计：确定程序的总体结构、模块关系和总体流程；（3）

3、详细设计：确定模块内部的流程和实现算法；（4）上机编码和调试；（5）运行测试；（6）编写实验报告。源代码：#defi ne TRUE 1#defi ne FALSE 0#defi ne INVALID -1#defi ne NULL0#defi netotal_i nstructio n320#defi netotal_vp32#defi neclear_period50/*指令流长*/*虚页长*/*清 0 周期*/typedef structint pn,pfn ,cou nter,time。/*页面结构*/课程名称计算机操作系统实验名称编程实现请求分页存储管理页面OptimalOptima

4、l、FIFOFIFO、LRULRU 置换算法实验类型/*页面结构数组*/struct pfc_struct/* 页面控制结构 */int pn,pfn 。struct pfc_struct *n ext。typedef struct pfc_struct pfc_type。pfc_type pfctotal_vp,*freepf_head,*busypf_head,*busypf_tail。int diseffect,atotal_ in structi on。int pagetotal_ in structi on,offsettotal_ in structi on。intin itial

5、ize(i nt)。intFIFO(i nt)。intLRU(i nt)。intLFU(i nt)。intNUR(i nt)。intOPT(i nt)。int main()int s,i,j。srand(10*getpid()。/*由于每次运行时进程号不同，故可用来作为初始化随机数“种子” */s=(float)319*ra nd( )/32767/32767/2+1。/for(i=0 。itotal_instruction。i+=4) /* 产生指令队列 */if(s319)prin tf(When i=%d,Error,s=%dn,i,s)。exit(0)。ai=s 。/*任选一指令访问点

6、m*/ai+1=ai+1。/*顺序执行一条指令 */ai+2=(float)ai*rand( )/32767/32767/2。/* 执行前地址指令 m */ai+3=ai+2+1。/*顺序执行一条指令 */s=(float)(318-ai+2)*ra nd( )/32767/32767/2+ai+2+2。if(ai+2318)|(s319)prin tf(a%d+2,a number which is :%d and s=%dn,i,ai+2,s)。for (i=0。itotal_instruction。i+) /*将指令序列变换成页地址流*/pagei=ai/10。offseti=ai%10

7、 。for(i=4 。i=32。i+)/*用户内存工作区从 4 个页面到 32 个页面*/prin tf(-%2d page frames- n,i)。FIFO(i)。LRU(i)。LFU(i)。int LRU (total pf)int total pf/*初始化相关数据结构*/*用户进程的内存页面数*/*页面控制结构中的访问次数为0,时间为-1*/for(i=0 。inext=freepf_head。 /*free页面减少一个 */busypf_tail=freepf_head 。freepf_head=p 。pri ntf(FIFO:%6.4fn,1-(float)diseffect/3

8、20)。return 0NUR(i)OPT(i)return 0I*最近最久未使用算法*int initialize(tint total_pfint i 。diseffect=pli.time=-1/*空页面队列的头指针为pfc0*/*int FIFO(total_pf)存页面数*/int i,j 。178先进先出算法*int total_pfin itialize(total_pf)/*初始化相关页面控制用数据结构*/*/busypf_head=busypf_tail=NULL/*用户进/*忙页面队列头，队列尾链接*/ipn .pfn=INVALIDnext=NULL 。freepf_he

9、ad=busypf_headbusypf_head=p 。/*页面失效*/面*/* 释放忙页面p=freepf_head-n extdiseffect+=1p=busypf_head-next。plbu的第一个页面 */fr/*按 FIFO 方式调新页面入*/freepf_head-n ext=NULLfreepf_head-p n二pageiplpagei.pf n二freepf_head-pf nint min,min j,i,j,prese nt_time in itialize(total_pf)。prese nt_time=O 。for(i=0 。itotal_instruction

10、。i+)if(plpagei.pfn=INVALID) diseffect+ 。 if(freepf_head=NULL)min=32767。for(j=0 。j plj.time&plj.pfn!=INVALID)min=plj.time。minj=j 。 freepf_head=&pfcplm in j.pf nplminj.pfn=INVALID 。 plm in j.time=-1。freepf_head-n ext=NULL。plpagei.pf n=freepf_head-pf n。plpagei.time=prese nt_time。freepf_head=fre

11、epf_head-n extelseplpagei.time=present_time/命中则增加该单元的访问次数prese nt_time+ 。prin tf(LRU:%6.4fn,1-(float)diseffect/320) return 0 。/*页面失效*/*无空闲页面*/*找岀 time 的最小值*/腾出一个单元/有空闲页面，改为有效/减少一个 free 页面/*intNUR(total_pf)inttotal_pf。 inti,j,dp,cont_flag,old_dppfc_type *t 。initialize(t近未使用算*/。i+)/*页面失效*/*无空闲页面*/else

12、*佳置换算*int OPT(total_pf)int total_pfint i,j, max,maxpage,d,disttotal_vppfc_type *t 。in itialize(total_pf)。for(i=0 。itotal_instruction。i+) pri ntf(In OPT for 1,i=%dn,i)274,275,276,277,278。if(plpagei.pfn=INVALID)diseffect+ 。i=86 。i=176。206。250。220,221。192,193,194/*页面失效*/258if(freepf_head=NULL)/*无空闲页面*/

13、for(j=0 。jtotal_vp 。j+)else distj=0if(plj.pfn!=INVALID) distj=32767o/* 最大“距离“ */d=1for(j=i+1ojtotal_instruction。j+)if(plpagej.pfn!=INVALID)distpagej=dd+o max=-1ofor(j=0ojtotal_vpoj+) if(maxdistj)max=distjdp+。if(dp=total_vp)dp=0。if(dp=old_dp)for(j=0 。jn ext=NULL。plpagei.pf n=freepf_head-pf n。freepf_h

14、ead=freepf_head-n ext。elseplpagei.cou nter=1。if(i%clear_period=0)for(j=0 。jn ext=NULL。plmaxpage.pfn=INVALID 。plpagei.pf n=freepf_head-pf n。freepf_head=freepf_head-n ext。pri ntf(OPT:%6.4fn,1-(float)diseffect/320)。return 0。不经常使用置换*int LFU(total_pf)int total_pf 。int i,j,mi n, mi npage。pfc_type *t 。in i

15、tialize(total_pf)。for(i=0 。itotal_instruction。i+) if(plpagei.pfn=INVALID)/* 页面失效 */ diseffect+ 。if(freepf_head=NULL)/* 无空闲页面 */ min=32767。for(j=0 。jp lj.cou nter&plj.pfn!=INVALID)min=plj.cou nter。min page=j 。plj.cou nter=0freepf_head=&pfcplm in page.pf nplminpage.pfn=INVALIDfreepf_head-next=

16、NULL plpagei.pf n=freepf_head-pf n。plpagei.cou nter+ freepf_head=freepf_head-n ext 。elseplpagei.cou nter+pri ntf(LFU:%6.4fn,1-(float)diseffect/320) return 0实验数据-4 page frames-FIFO:0.5531LRU:0.5594LFU:0.5312NUR:0.56560PT:0.5844-FIFO:0.5813LRU:0.5813LFU:0.5406NUR:0.57810PT:0.6062-6pageFIFO:0.5938LRU:0.6062LFU:0.5531NUR:0.5844OPT:0.6312-7pageFIFO:Q.6125LRU:Q.6156LFU:Q.575QNUR:Q.6156OPT:Q.65QQ 其余均为列出*/*/有空闲页面，改为有效page fi fifr【实验结果或总结】（对实验结果进