頁面置換算法模擬實驗報告

1、實驗編號4名稱頁面置換算法模擬實驗?zāi)康耐ㄟ^請求頁式存儲治理中頁面置換算法模擬設(shè)計,以便：1、了解虛擬存儲技術(shù)的特點2、掌握請求頁式存儲治理中頁面置換算法實驗內(nèi)容與步驟設(shè)計一個虛擬存儲區(qū)和內(nèi)存工作區(qū),并使用FIFO和LRU算法計算訪問命中率.<程序設(shè)計>先用srand()函數(shù)和rand()函數(shù)定義和產(chǎn)生指令序列,然后將指令序列變換成相應(yīng)的頁地址流,并針對不同的算法計算相應(yīng)的命中率.程序1>#include<windows.h>/Windows版,隨機函數(shù)需要,GetCurrentProcessId()需要/#include<stdlib.h>/Linux

2、版,隨機函數(shù)srand和rand需要#include<stdio.h>/printf()需要# defineTRUE1# defineFALSE0# defineINVALID-1# defineNULL0# definetotal_instruction320共320條指令# definetotal_vp32虛存頁共32頁# defineclear_period50訪問次數(shù)清零周期typedefstruct定義頁表結(jié)構(gòu)類型(頁面映射表PMT)intpn,pfn,counter,time;/頁號、頁框號(塊號)、一個周期內(nèi)訪問該頁面的次數(shù)、訪問時間PMT;PMTpmt32;type

3、defstructpfc_struct頁面限制結(jié)構(gòu)intpn,pfn;structpfc_struct*next;pfc_type;pfc_typepfc32;pfc_type*freepf_head,*busypf_head,*busypf_tail;/空閑頁頭指針,忙頁頭指針,忙頁尾指針intNoPageCount;缺頁次數(shù)intatotal_instruction;/指令流數(shù)組intpagetotal_instruction,offsettotal_instruction;每條指令的頁和頁內(nèi)偏移voidinitialize(int);voidFIFO(int);先進(jìn)先出voidLRU(i

4、nt);最近最久未使用voidNRU(int);最近最不經(jīng)常使用/*main()*voidmain()inti,s;/srand(10*getpid();用進(jìn)程號作為初始化隨機數(shù)隊列的種子/Linux版srand(10*GetCurrentProcessId();/用進(jìn)程號作為初始化隨機數(shù)的種子/Windows版s=rand()%320;/在0,319的指令地址之間隨機選取一起點mfor(i=0;i<totalinstruction;i+=4)產(chǎn)生指令隊列if(s<0|s>319)printf("wheni=%d,error,s=%dn",i,s);exi

5、t(0);ai=s;/任意選一指令訪問點m.(將隨機數(shù)作為指令地址m)ai+1=ai+1;/順序執(zhí)行下一條指令ai+2=rand()%(s+2);在0,m+1的前地址之間隨機選取一地址,記為m'ai+3=ai+2+1;/順序執(zhí)行一條指令s=ai+2+(int)rand()%(320-ai+2);/在m',319的指令地址之間隨機選取一起點if(ai+2>318)|(s>319)printf("a%d+2,anumberwhichis:%dands=%dn",i,ai+2,s);for(i=0;i<total_instruction;i+)/

6、將指令序列變成頁地址流pagei=ai/10;offseti=ai%10;for(i=4;i<=32;i+)內(nèi)存塊分別為4塊、5塊、32塊時的命中率printf("%2dpageframes",i);FIFO(i);/計算用FIFO置換時,有i個內(nèi)存塊時的命中率LRU(i);最近最久未使用NRU(i);最近最不經(jīng)常使用printf("n");/*initialize()形參：內(nèi)存塊數(shù)功能：初始化*/voidinitialize(inttotal_pf)初始化相關(guān)數(shù)據(jù)結(jié)構(gòu),形參total_pf是用戶進(jìn)程的內(nèi)存頁面數(shù)inti;NoPageCount=0

7、;/缺頁次數(shù),初始化為0for(i=0;i<total_vp;i+)pmti.pn=i;/填邏輯頁號pmti.pfn=INVALID;/物理頁面號為-1pmti.counter=0;/置頁面限制結(jié)構(gòu)中的訪問次數(shù)為0pmti.time=-1;置頁面限制結(jié)構(gòu)中的時間為-1二for(i=0;i<total_pf-1;i+)建立pfci-1和pfci之間的連接pfci.next=&pfci+1;pfci.pfn=i;pfctotal_pf-1.next=NULL;pfctotal_pf-1.pfn=total_pf-1;freepf_head=&pfc0;/頁面隊列的頭指針

8、為pfc0/*FIFO算法形參：內(nèi)存塊數(shù)輸出：命中率*/voidFIFO(inttotalpf)形參totalpf是用戶進(jìn)程的內(nèi)存頁面數(shù)inti;pfc_type*p;initialize(total_pf);初始化相關(guān)數(shù)據(jù)結(jié)構(gòu)busypf_head=busypf_tail=NULL;for(i=0;i<total_instruction;i+)/訪問每條指令if(pmtpagei.pfn=INVALID)缺頁NoPageCount+=1;/失效做頁)次數(shù)增1if(freepf_head=NULL)無空閑頁面p=busypf_head->next;pmtbusypf_head-&g

9、t;pn.pfn=INVALID;freepf_head=busypf_head;釋放忙頁面隊歹U的第一個頁面freepf_head->next=NULL;busypf_head=p;p=freepf_head->next;/按FIFO方式調(diào)新頁面入內(nèi)存freepf_head->next=NULL;freepf_head->pn=pagei;pmtpagei.pfn=freepf_head->pfn;if(busypf_tail=NULL)busypf_head=busypf_tail=freepf_head;elsebusypf_tail->next=fr

10、eepf_head;/free頁面減少一個busypf_tail=freepf_head;freepf_head=p;printf("FIFO:%6.4f",1-(float)NoPageCount/320);/*LRU算法(最近最久未使用)形參：內(nèi)存塊數(shù)輸出：命中率*/voidLRU(inttotalpf)/形參totalpf是給用戶進(jìn)程的內(nèi)存塊數(shù)intmin,minj,i,j,present_time;initialize(total_pf);present_time=0;for(i=0;i<total_instruction;i+)if(pmtpagei.pfn

11、=INVALID)頁面失效NoPageCount+;if(freepf_head=NULL)無空閑頁面min=32767;for(j=0;j<totalvp;j+)/找出time的最小值if(min>pmtj.time&&pmtj.pfn!=INVALID)min=pmtj.time;minj=j;freepf_head=&pfcpmtminj.pfn;騰出個單元pmtminj.pfn=INVALID;pmtminj.time=-1;freepf_head->next=NULL;pmtpagei.pfn=freepf_head->pfn;有空閑頁

12、面,改為有效pmtpagei.time=present_time;freepf_head=freepf_head->next;減少一個free頁面elsepmtpagei.time=present_time;更新該頁面的訪問時間(并非真的時間,而是循環(huán)次數(shù),每執(zhí)行一條指令,時間加1presenttime+;當(dāng)前時間力口1printf("LRU:%6.4f",1-(float)NoPageCount/320);/*NRU算法最近最不經(jīng)常使用形參：內(nèi)存塊數(shù)輸出：命中率*/voidNRU(inttotal_pf)inti,j,dp,cont_flag,old_dp;init

13、ialize(total_pf);dp=0;for(i=0;i<total_instruction;i+)if(pmtpagei.pfn=INVALID)缺頁NoPageCount+;if(freepfhead=NULL)無空閑頁面cont_flag=TRUE;old_dp=dp;while(cont_flag)if(pmtdp.counter=0&&pmtdp.pfn!=INVALID)cont_flag=FALSE;if(dp=old_dp)for(j=0;j<total_vp;j+)pmtj.counter=0;lfreepf_head=&pfcpmt

14、dp.pfn;pmtdp.pfn=INVALID;freepf_head->next=NULL;pmtpagei.pfn=freepfhead->pfn;freepf_head=freepf_head->next;Ielsepmtpagei.counter=1;if(i%clear_period=0)for(j=0;j<total_vp;j+)pmtj.counter=0;printf("NUR:%6.4f",1-(float)NoPageCount/320);|實驗結(jié)果寫生結(jié)果,截圖也可情輸A幣而長唐4B輛出隨機小Y3654?159H211一八,隔

15、人分配的物理按鬲之白>工:MFIF.曲面置掙頁面宜梆負(fù)面置界清選持頁面置掛法,F】FO違法頁面苜由清況如下:總結(jié)收獲,未實現(xiàn)的步驟這次操作系統(tǒng)課程設(shè)計,讓我們對操作系統(tǒng)有了更深的熟悉,首先操作系統(tǒng)是一治理電腦硬件與軟件資源的程序,同時也是計算機系統(tǒng)內(nèi)核與基石.操作系統(tǒng)是一個龐大的治理限制程序,大致包括5個方面的治理功能：進(jìn)程與處理機管理、作業(yè)治理、存儲治理、設(shè)備治理、文件治理.我們這次課程設(shè)計的題目是頁面置換算法,是屬于存儲器治理.在進(jìn)程運行過程中,假設(shè)其訪問的頁面不在內(nèi)存而需把它們調(diào)入內(nèi)存,但內(nèi)存以無空閑空間時,為了保證該進(jìn)程能正常的運行,系統(tǒng)必須從內(nèi)存中調(diào)出一頁程序或數(shù)據(jù)送磁盤的兌換

16、區(qū)中,但應(yīng)將哪個頁面調(diào)出,需根據(jù)一定的算法來確定.通常,把選擇換成頁面的算法稱為頁面置換算法.通過本次課程設(shè)計,我們對頁面置換算法的了解更加的深刻.主要有以下置換算法：OPT最正確置換算法、FIFO先進(jìn)先出置換算法、LRU最近最久未使用算法.每種算法都有各自的優(yōu)缺點,OPT算法是實際中不能實現(xiàn)的,但是可以利用該算法去評價其它算法；FIFO算法與進(jìn)程實際運行的規(guī)律不相適用,由于在進(jìn)程中,有些頁面經(jīng)常被訪問；LRU算法是根據(jù)頁面調(diào)入內(nèi)存后的使用情況進(jìn)行決策的.在這次課程設(shè)計中,遇到了一些困難,例如怎么實現(xiàn)各種算法,如何進(jìn)行函數(shù)調(diào)用及對數(shù)據(jù)的限制操作等,在遇到這些困難的時候,我們會去查閱資料,仔細(xì)看書,嘗試用不同的方法解決,在各種