1、實驗八頁面置換模擬程序設計一、【實驗目的】加深對請求貞式存儲治理實現原理的理解,掌握頁面置換算法.二、【實驗內容】1 .假設分給一作業(yè)的內存塊數為 4,每個頁面中可存放10條指令.2 .用C語言設計一個程序,模擬一作業(yè)的執(zhí)行過程.設該作業(yè)共有 320條 指令,即它的地址空間為32頁,目前它的所有頁面都還未調入內存.在模擬過程中, 如果所訪問的指令已經在內存,那么顯示其物理地址,并轉下一條指令.如果所訪問的指令尚未裝入內存,那么發(fā)生缺貞,此時需記錄缺貞的次數,并將相應貞調入內存. 如果4個內存塊中均已裝入該作業(yè)的虛頁面,那么需進行頁面置換.最后顯示其物理 地址,并轉下一條指令.在所有 320條指

2、令執(zhí)行完畢后,請計算并顯示作業(yè)運行過 程中發(fā)生的缺貞率.3 .置換算法：請分別考慮 OPT FIFO和LRU算法.4.作業(yè)中指令的訪問次序要求按下述原那么生成：50%的指令是順序執(zhí)行的.25%的指令是均勻分布在前地址(即低地址)局部.25%的指令是均勻分布在后地址(即高地址)局部. 具體的實施方法是： 在0 , 319之間隨機選取一條起始執(zhí)行指令,其序號為m 順序執(zhí)行下一條指令,即序號為 m+1的指令； 通過隨機數,跳轉到前地址局部0 , m-1 中的某條指令處,其序號為 m1; 順序執(zhí)行下一條指令,即序號為 m1+1的指令； 通過隨機數,跳轉到后地址局部m1+2, 319中的某條指令處,其序

3、號為m2 順序執(zhí)行下一條指令,即序號為 m2+1的指令； 重復“跳轉到前地址局部、順序執(zhí)行、跳轉到后地址局部、順序執(zhí)行的過 程,直至執(zhí)行完全部320條指令.5.隨機數產生方法,Linux或UNIX系統(tǒng)提供函數strand()和rand(),分別進行初始 化和產生隨機數.例如：strand ();語句可初始化一個隨機數；a0=10*rand()/65535*319+1; a1=10*rand()/65535*a0;語句可用來產生 a0與a1中的隨機數.三、【實驗指導】本實驗的程序設計根本上根據實驗內容進行.即首先用srand()和rand()函數定義和產生指令序列,然后將指令序列變換成相應的貞地

4、址流,并針對不同的算法計算出 相應的命中率.相關定義如下： 1數據結構(1)頁面類型typedef structint pn,pfn,counter,time;pl-type;其中pn為頁號,pfn為面號,counter為一個周期內訪問該頁面的次數,time為訪問時間.(2)頁面限制結構pfc-struct(int pn,pfn;struct pfc_struct *next;typedef struct pfc_struct pfc_type;pfc_type pfc_structtotal_vp,*freepf_head,*busypf_head;pfc_type *busypf_tail

5、;其中pfctotal_vp定義用戶進程虛貞限制結構,*freepf_head為空頁面頭的指針,*busypf_head為忙頁面頭的指針,*busypf_tail為忙頁面尾的指針.2. 函數定義(1) Void initialize.：初始化函數,給每個相關的頁面賦值.(2) Void FIFO():計算使用FIFO算法時的命中率.(3) Void LRU():計算使用LRlM法時的命中率.(4) Void OPT():計算使用OP法時的命中率.3. 變量定義(1)int atotal_instruction:指令流數據組.int pagetotal_instruction:每條指令所屆的頁號

6、.int offsettotal_instruction:每貞裝入10條指令后取模運算頁號偏移值int total_pf:用戶進程的內存頁面數.int disaffect:頁面失效次數.4.程序參考源碼及結果 < 程序>#include <stdio.h>#include <stdlib.h>#include <unistd.h>#define TRUE 1#define FALSE 0#define INVALID -1#define NUL 0#define total_instruction 320 /* 指令流長 */#define to

7、tal_vp 32 /*虛貞長 */#define clear_period 50 /*活零周期 */typedef struct /*頁面結構 */int pn,pfn,counter,time;pl_type;pl_type pltotal_vp; /*頁面結構數組 */struct pfc_struct /*頁面限制結構 */int pn,pfn; struct pfc_struct *next; ;typedef struct pfc_struct pfc_type; pfc_typepfctotal_vp,*freepf_head,*busypf_head,*busypf_tail;

8、int diseffect,atotal_instruction;int pagetotal_instruction, offsettotal_instruction;int main() int S,i;srand(int)getpid();S=(int)rand()%390; for(i=0;i<total_instruction;i+=1) /*產生指令隊歹U */ ai=S; /*任選一指令訪問點*/ai+1=ai+1; /*順序執(zhí)行一條指令*/ai+2=(int)rand()%390; /*執(zhí)行前地址指令 m' */ai+3=ai+2+1; /*執(zhí)行后地址指令*/S=(

9、int)rand()%390; for(i=0;i<total_instruction;i+) /*將指令序歹0變換成貞地址流 */ pagei=ai/10; offseti=ai%10; for(i=4;i<=32;i+) /* 用戶內存工作區(qū)從4個頁面到32個頁面*/ printf("%2d page frames",i);FIFO(i); LRU(i); OPT(i); printf("n"); return 0; void FIFO(total_pf) /*FIFO(First in First out)ALGORITHM*/int

10、total_pf; /*用戶進程的內存頁面數*/ int i; pfc_type *p, *t; initialize(total_pf); /*初始化相關頁面限制用數據結構*/busypf_head=busypf_tail=NUL; /*忙頁面隊歹0頭,對歹U尾鏈接 */for(i=0;i<total_instruction;i+)if(plpagei.pfn=INVALID) /*頁面失效 */diseffect+=1; /*失效次數 */if(freepf_head=NUL) /* 無空閑頁面 */p=busypf_head->next;plbusypf_head->p

11、n.pfn=INVALID; /*釋放忙頁面隊歹0中的第一個頁面 */freepf_head=busypf_head;freepf_head->next=NUL;busypf_head=p;p=freepf_head->next; /*按方式調新頁面入內存頁面*/freepf_head->next=NUL;freepf_head->pn=pagei;plpagei.pfn=freepf_head->pfn;if(busypf_tail=NUL)busypf_head=busypf_tail=freepf_head;elsebusypf_tail->next=

12、freepf_head;busypf_tail=freepf_head;freepf_head=p;printf("FIFO:%6.4F",1-(float)diseffect/320);void LRU(total_pf)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) /

13、* 無空閑頁面 */min=32767;for(j=0;j<total_vp;j+)if(min>plj.time&&plj.pfn!=INVALID)(min=plj.time;minj=j;freepf_head=&pfcplminj.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;elseplpa

14、gei.time=present_time;present_time+;printf("LRU:%6.4f",1-(float)diseffect/320);void OPT(total_pf) /*OPT(Optimal Replacement)ALGORITHM*/int total_pf; int i,j,max,maxpage,d,disttotal_vp;pfc_type *t;initialize(total_pf);for(i=0;i<total_instruction;i+) if(plpagei.pfn=INVALID) diseffect+; if

15、(freepf_head=NUL) for(j=0;j<total_vp;j+)if(plj.pfn!=INVALID) distj=32767; else distj=0; d=1;for(j=i+1;j<total_instruction;j+) if(plpagej.pfn!=INVALID) distpagej=d; d+; max=-1;for(j=0;j<total_vp;j+) if(max<distj) max=distj;maxpage=j; freepf_head=&pfcplmaxpage.pfn; freepf_head->next=NUL; plmaxpage.pfn=INVALID; plpagei.pfn=freepf_head->pfn;freepf_head=freepf_head->next; printf("OPT:%6.4f",1-(float)diseffect/320); void initialize(total_pf) /*初始化相關數據結構 */int total_pf; /* 用戶進程的內存頁面數*/ int i; diseffect=0; for(i=0;i<total_vp;i+) pli.pn=i;pli.pfn=INVALID; /*置頁面限制