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

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

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

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

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

5、t(0);ai=s;/任意選一指令訪問點m.(將隨機數作為指令地址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+)內存塊分別為4塊、5塊、32塊時的命中率printf("%2dpageframes",i);FIFO(i);/計算用FIFO置換時,有i個內存塊時的命中率LRU(i);最近最久未使用NRU(i);最近最不經常使用printf("n");/*initialize()形參：內存塊數功能：初始化*/voidinitialize(inttotal_pf)初始化相關數據結構,形參total_pf是用戶進程的內存頁面數inti;NoPageCount=0

7、;/缺頁次數,初始化為0for(i=0;i<total_vp;i+)pmti.pn=i;/填邏輯頁號pmti.pfn=INVALID;/物理頁面號為-1pmti.counter=0;/置頁面限制結構中的訪問次數為0pmti.time=-1;置頁面限制結構中的時間為-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算法形參：內存塊數輸出：命中率*/voidFIFO(inttotalpf)形參totalpf是用戶進程的內存頁面數inti;pfc_type*p;initialize(total_pf);初始化相關數據結構busypf_head=busypf_tail=NULL;for(i=0;i<total_instruction;i+)/訪問每條指令if(pmtpagei.pfn=INVALID)缺頁NoPageCount+=1;/失效做頁)次數增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方式調新頁面入內存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算法(最近最久未使用)形參：內存塊數輸出：命中率*/voidLRU(inttotalpf)/形參totalpf是給用戶進程的內存塊數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)次數,每執(zhí)行一條指令,時間加1presenttime+;當前時間力口1printf("LRU:%6.4f",1-(float)NoPageCount/320);/*NRU算法最近最不經常使用形參：內存塊數輸出：命中率*/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);|實驗結果寫生結果,截圖也可情輸A幣而長唐4B輛出隨機小Y3654?159H211一八,隔

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

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