搜索
----计算机与信息技术学院综合性实验报告专业:计算机科学与技术年级/班级:2009级2０11—２012学年第一学期课程名称计算机操作系统指导教师齐娜学号姓名０９08114006司景霞实验地点过街楼D区实验时间周三晚项目名称基于优先数的进程调度实验类型综合性一、实验目的通过请求页式存储管理中页面置换算法模拟设计,了解虚拟存储技术的特点，掌握请求页式管理的页面置换算法。二、实验仪器或设备微型计算机、Linux操作系统、ｄevC＋+三、总体设计1、通过随机数产生一个指令序列,共32０条指令。其地址按下述原则生成：①50%的指令是顺序执行的；②25%的指令是均匀分布在前地址部分;③２5%的指令是均匀分布在后地址部分；具体的实施方法是:A.在［0,319］的指令地址之间随机选取一起点Ｍ;B.顺序执行一条指令，即执行地址为M＋1的指令;Ｃ.在前地址[0,Ｍ+１]中随机选取一条指令并执行，该指令的地址为M’；D.顺序执行一条指令,其地址为M’+1；Ｅ.在后地址[M’+２，３19]中随机选取一条指令并执行;F.重复A—Ｅ，直到执行３20次指令。2、指令序列变换成页地址流,设:①页面大小为１K;②用户内存容量为４页到３2页;③用户虚存容量为32K。在用户虚存中，按每页存放1０条指令排列虚存地址,即32０条指令在虚存中的存放方式为：第0条～第9条指令为第0页(对应虚存地址为[０,9])；第1０条～第19条指令为第1页(对应虚存地址为[１0，１９]）;…………----第３10条～第3１9条指令为第31页(对应虚存地址为［310,３19])；按以上方式，用户指令可组成３2页。3、计算并输出下述算法在不同内存容量下的命中率。A.FIFO先进先出置换算法；Ｂ．LRU最近最久未使用置换算法；C.ＮUR最近未使用置换算法。命中率=1-页面失效次数/页地址流长度在本实验中，页地址流长度为320，页面失效次数为每次访问相应指令时，该指令所对应的页不在内存的次数。4、相关定义(1)数据结构错误!页面类型tyｐｅdefstruct／*页面结构＊／{intpn,pfn,tiｍe;}pl_ｔｙｐe;其中pn为页面号,ｐｆｎ为页帧号,tiｍe为访问时间○，2页帧控制结构structｐfｃ＿stｒucｔ｛/＊页帧控制结构＊/ﻩintｐｎ,ｐｆn；ﻩstructpfc_strｕｃｔ*ｎext;};typeｄｅfstｒuctpfc_struｃtpfc_type;pfc_typepfc[tｏtal_ｖp］，*freepf_heaｄ，*busypf_head,*ｂｕsyｐf_tail;其中pfc＿typepfc[tｏtａl＿vp］定义用户进程虚页控制结构＊fｒeｅpｆ_head为空闲页帧头的指针＊busypｆ_hｅad为忙页帧头的指针＊busyｐf_ｔail忙页帧尾的指针（２)函数定义voidinｉtialize(int)：初始化函数voidFIFＯ(ｉnｔ):计算使用ＦIFO算法时的命中率ｖoiｄLRU(ｉnｔ）:计算使用LRU算法时的命中率voidNRU(ｉnt）:计算使用NＲU算法时的命中率(3）变量定义inta[totaｌ_inｓtruction］:指令流数组ｉntdiseffｅｃt:页面失效次数intｐａｇe[ｔotal_inｓtｒuｃtion］:每条指令所属页面号ｉntoffset[tｏtaｌ_instrｕction]:每页装入１0条指令后取模运算得出的页内偏移地址intｔotal＿pf：用户进程的内存页面数----四、实验步骤按照流程图编写代码、并上机调试运行程序代码:#ｉｎcｌudestdｌｉb.h＞#ｉnｃlｕde＜sｔio.ｈ＞#defｉneTRUE1#ｄeｆineFALSE０#ｄefineINＶALＩD-1＃deｆｉnetotaｌ_instrｕctｉon320／*指令流长＊/#defiｎetotaｌ＿vp３2/*虚页长＊/typedeｆstrｕｃt/*页面结构*/{ﻩiｎｔpn,pfｎ,tiｍｅ;}pl＿typｅ;pl＿tｙpepl[total_ｖp］;/＊页帧结构数组*／sｔructpfｃ_ｓtruct{/*页帧控制结构*/intpn,ｐfn;stｒuctpfｃ_struct*next；};tｙpｅdefstｒuctpfc＿stｒuｃｔpfc_type;pfc_ｔypeｐfｃ［total_vp］,＊freepｆ_head,*ｂｕsypf＿heaｄ,*busypf_taｉｌ;intdisｅffeｃｔ,ａ［ｔｏtal＿inｓtructｉon];ｉｎtpaｇe[toｔal_ｉｎstrucｔion］，ｏffseｔ[totaｌ_insｔｒｕｃｔiｏｎ];voidｉniｔializｅ(int);voidFIFO（iｎt);voidＬRU(inｔ);ｖoiｄNRU(inｔ);ｉntmain(){iｎtｓ,i；／*由于每次运行时进程号不同，故可用来作为初始化随机数队列的“种子”*/ｓrand(１０*getpid(））;s=(flｏat)319*rａnｄ（)/RＡND_MAX＋1;ｆｏr（ｉ＝0；iｔotａｌ_iｎｓtructｉｏｎ;i+＝4)/*产生指令队列*／{ａ[i］=ｓ;/＊任选一指令访问点m*/a［ｉ+1]=a[i］+1;／*顺序执行一条指令*／a[ｉ＋2］＝（flｏat）a[ｉ］*rａnd（)/ＲAＮD＿ＭAX;/*执行前地址指令ｍ＇*/a［ｉ+3]=a[i＋2]+1;/*顺序执行一条指令＊/ｓ=(flｏａｔ）（31８-ａ［i+2])*rand(）/RANＤ_MＡＸ+a[i+2］+２;}fｏｒ(i=０;iｔoｔａl＿iｎstｒuｃtion;i++)/*将指令序列变换成页地址流*/｛paｇe[i]=a[i]/10;----ofｆseｔ[ｉ］=a[i]%10;}for(i=4;i＝32；ｉ++）/*用户内存工作区从4个页帧到3２个页帧*/｛printf(＂%２dpagefｒａmes,i);voｉｄFＩＦO（ｉｎt)；ｖoidLRU(inｔ);voidNRＵ(inｔ）；ﻩﻩpriｎｔf(＂＼ｎ);}}voｉdinｉｔiaｌｉze（ｉnｔtｏｔal_pｆ)/＊初始化相关数据结构*／｛ｉnti；diｓｅffｅct=０;fｏr(i=0;i＜ｔｏtal_vp；ｉ++){pl［ｉ]．pn=i;pｌ[i］.pfn=IＮVＡLIＤ;pｌ[i］.tｉmｅ=-1;}fｏr(i=0;i＜total_pf-1;i+＋){pfｃ［i］.ｎeｘt=&pｆc[ｉ＋1];pfc[i]．ｐfn=ｉ；｝/*建立pfｃ[i-1]和ｐfc[i]之间的链接*／pfｃ[total_pf－１］．nｅxｔ=NULＬ;ｐfc[total＿pf－1].pｆn＝tｏｔaｌ_pf-1；freepf_heaｄ=＆ｐfc[0];/*空页面队列的头指针为pｆc[0］*/｝vｏidFIFＯ(inｔtotａｌ_pf）/＊先进先出算法*／inttotal＿pf;/*用户进程的内存页面数＊/{inti，j;ｐfc_tyｐe*p,＊t；initialiｚe(ｔoｔａl_ｐf);/*初始化相关页面控制用数据结构*/busyｐf＿ｈeａd=busypf＿ｔail=NＵLＬ：/*忙页面队列头，队列尾链接*/for(i=0;i=toｔal_instｒuctioｎ;i+＋){if(p1[ｐａge[i]].pfn＝=INＶALID)/＊页面失效＊／｛disaffeｃｔ＋=1；/*失效次数＊/if(freep_ｈeadｆ==NULＬ）/＊无空闲页面*/{ｐ=bｕsypｆ_heaｄ-nexｔ；p１[busyｐｆ_head-ｐn].pｆn＝IＮVＡLＩD；frｅeｐf_head=buｓypf_heaｄ;/＊释放忙页面队列中的第一个页面*/freｅpｆ_head－＞nｅxt=NULＬ:ｂusyｐf_ｈeaｄ=ｐ;}p=freｅpｆ_hｅad－next；/＊按FIFO方式调新页面入内存页面*/----freｅｐf_ｈead-ｎｅxt=NULL:ﻩﻩfreepｆ_hｅad-pn＝paｇe[i];p1[page[i]].ｐｆn=freeｐf_head－＞ｐfn;if(ｂuｓypf_taｉl＝＝ＮUＬL)ｂusyｐf_ｈeａｄ=busｙｐf＿tａil=fｒｅepf_head;else{busypｆ＿tａil-next=fｒeepf_heａd;busypｆ_tail=freepf＿heaｄ;}freepf_head＝ｐ;}}pｒintｆ(“ＦＩＦＯ:%6．4ｆ”,1－(flｏat）ｄiｓａfｆｅct/320）;}ｖoiｄLRU(inttｏtaｌ_pf)/*最近最久未使用算法*/iｎttotal_pf;{intmin,miｎj,i,ｊ，prｅsent_tｉmｅ；initialize(ｔotal_pf);ｐresent_timｅ=0;for(i＝0；iｔｏｔal_inｓｔruｃtiｏｎ;i+＋）{ｉｆ(p１[pagｅ［i]］．pｆn==INVＡLID）／*页面失效*／{disaffect++；ｉf(freepf＿heaｄ==NUＬL)/*无空闲页面*/｛min＝32767;ｆor（j=０;ｊtotaｌ＿ｖp;j++)if(mｉnp1[ｊ].ｔｉｍe&&p1[ｊ].pｆn!=INVAＬIＤ)｛ｍiｎ=p１[ｊ]．timｅ;minj=j；}ｆｒeepf_heaｄ＝&ｐｆc［p１［minj]．pfn];p1[ｍinj］.pfn=INVALID；p１[ｍiｎ］.ｔime＝-1;freepf＿head－nexｔ=NULＬ;}p1［ｐａｇe[ｉ］].pｆn=ｆｒｅｅｐf_heａd-ｐｆn;p1[ｐage[i]].time=ｐｒｅsenｔ_timｅ;freeｐf_ｈeaｄ＝fｒeepf＿ｈead-nｅxｔ;}elseｐ1[paｇｅ［i］］.ｔimｅ=prｅsｅnｔ_time；present_tｉｍｅ++；}pｒinｔf（“ＬRＵ:％6.4ｆ”,1－(flaoｔ）disaｆｆｅct/320);｝voｉｄNRU(ｉnttotal_pf)ﻩ/*最近未使用置换算法*/inｔｔotal＿pf;{ｉｎtｉ,j,dp,coｎt_ｆｌag,olｄ_dp;----pfc_tｙpe*t;initialize(total_ｐf）;dp=0;fｏｒ(i＝0；itｏｔａl＿insｔrｕcｔｉon；ｉ+＋){ｉf（p1[page［i］］．ｐｆn==INVAＬＩD)/*页面失效＊/｛ｄiseffeｃt++;ｉf（freepf_heaｄ=＝NUＬL)／*无空闲页面*/{cｏnｔ＿flａg=TＲUE;oｌｄ_dp=dｐ;wｈile(cｏnt_flag)if(p1[dp].ｃoｕntｅｒ==0&&p1[ｄｐ].pfn！=INVALＩＤ)cont_flag＝ＦLASE;eｌse{dp+＋；if(dｐ==tｏtal_vｐ)dp=0；if(dp=＝old_dp)ｆoｒ(j=0;j＜tｏtａl＿vp;j++）p1[j].couｎter=0;}fｒeｅpf＿heaｄ＝&pｆｃ[p1［ｄp］.pｆn］；p1[dp].pfn＝ＩNＶAＬＩD;freｅpf_ｈｅad－＞next=NUＬL:}p1[ｐaｇe[i]].pfn＝freeｐf_head-ｐfn;fｒeepｆ_head＝ｆreepf_head-next;}elsep１[paｇe[i]].counteｒ=1;if(ｉ％clear＿ｐeｒｉod==0)ｆor（ｊ=0;jtoｔal＿ｖp；j++）p１[j].cｏunter=０；}ｐrintf（“NUR:%6.4f”,１-(flｏａt)ｄｉsaffecｔ／３20);}voidOPT（totａl_pf)inttotａl_pf;{inti,j，max,ｍaxｐagｅ，d，dist［tｏtaｌ＿vp];pfc＿type*t;ｉniｔｉaｌiｚe（toｔal_pf);for（ｉ=0;itｏｔal_instrｕctｉon；i++){iｆ(p1[ｐage[i]].pfｎ==INVALＩD