?? 頁面置換算法(最終版本).cpp
字號:
#include <stdio.h>//標準輸入/輸出函數#include <math.h>//數學函數 #include<stdlib.h>//動態存儲分配函數#include<time.h> //時間日期函數#define TRUE 1#define FALSE 0#define INVALID -1#define NULL 0#define total_instruction 320 /*指令流長*/#define total_vp 32 /*虛頁長*/#define clear_period 50 /*清零周期*/typedef struct{ /*頁面結構*/ int pn,pfn,counter,time;}pl_type;pl_type pl[total_vp]; /*頁面結構數組*/struct pfc_struct{ /*頁面控制結構*/ int pn,pfn; struct pfc_struct *next;};typedef struct pfc_struct pfc_type;pfc_type pfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;int diseffect, a[total_instruction];int page[total_instruction], offset[total_instruction]; void initialize(int);void FIFO(int);void LRU(int);void OPT(int);void LFU(int);void NUR(int);int main(){ int S,i,j; time_t t; //產生隨機數用 srand((unsigned) time(&t)); S= rand() % 319+1;//隨機數1到319 for(i=0;i<total_instruction;i+=4){ /*產生指令隊列*/ a[i]= S; /*任選一指令訪問點*/ a[i+1]=a[i]+1; /*順序執行一條指令*/ j=rand()%32767; a[i+2]=a[i]*j/32767; /*執行前地址指令m'*/ a[i+3]=a[i+2]+1; /*執行后地址指令*/ j=rand()%32767; S=j*(318-a[i+2])/32767+a[i+2]+2; } for(i=0;i<total_instruction;i++){ /* 將指令序列變換成頁地址流 */ page[i]=a[i]/10; offset[i]=a[i]%10; } i = rand()%32+4;/*用戶內存工作區隨機產生頁面(4-32個頁面) */
int a;do{printf("\n頁面置換算法模擬\n");//菜單printf("*********************************\n");printf("1。FIFO算法實現\n");printf("2。LUR算法實現\n");printf("3。OPT算法實現\n");printf("4。LFU算法實現\n");printf("5。NUR算法實現\n");printf("6。重新產生隨機頁面\n");printf("7。退出\n");printf("***********************************\n");printf("請輸入您的選擇(1,2,3,4,5,6,7)\n"); scanf("%d",&a);//選擇算法實現 switch(a){ case 1:{ printf("第%d頁面:",i); FIFO(i);break; } case 2:{ printf("第%d頁面:",i); LRU(i);break; } case 3:{ printf("第%d頁面:",i); OPT(i);break; } case 4:{ printf("第%d頁面:",i); LFU(i);break; } case 5:{ printf("第%d頁面:",i); NUR(i);break; } case 6:i = rand()%32+4;break; case 7:exit(0); printf("\n"); }}while(a<=7);getchar();} void FIFO(int total_pf) /* FIFO(First in First Out)ALGORITHM 先進先出*///int total_pf; /* 用戶進程的內存頁面數 */{ int i; pfc_type *p; initialize(total_pf); /* 初始化相關頁面控制用數據結構 */ busypf_head=busypf_tail=NULL; /* 忙頁面隊列頭,隊列尾鏈接 */ for(i=0;i<total_instruction;i++){ if(pl[page[i]].pfn==INVALID){ /* 頁面失效 */ diseffect+=1; /* 失效次數 */ if(freepf_head==NULL){ /* 無空閑頁面 */ p=busypf_head->next; pl[busypf_head->pn].pfn=INVALID; freepf_head=busypf_head; /* 釋放忙頁面隊列中的第一個頁面 */ freepf_head->next=NULL; busypf_head=p; } p=freepf_head->next; /* 按FIFO方式調新頁面入內存頁面 */ freepf_head->next=NULL; freepf_head->pn=page[i]; pl[page[i]].pfn=freepf_head->pfn; if(busypf_tail==NULL) busypf_head=busypf_tail=freepf_head; else{ busypf_tail->next=freepf_head; busypf_tail=freepf_head; } freepf_head=p; } } printf(" FIFO:%6.4f",1-(float)diseffect/320);}void LRU(int total_pf) /* LRU(Last Recently Used)ALGORITHM 最近最久未使用*///int total_pf; /* 用戶進程的內存頁面數 */{ int min,minj,i,j,present_time; initialize(total_pf); /* 初始化相關頁面控制用數據結構 */ present_time=0;//初定時間為0 for(i=0;i<total_instruction;i++){ if(pl[page[i]].pfn==INVALID){ /* 頁面失效 */ diseffect++; /* 失效次數 */ if(freepf_head==NULL){ /* 無空閑頁面 */ min=32767; for(j=0;j<total_vp;j++) if(min>pl[j].time && pl[j].pfn!=INVALID){ min=pl[j].time; minj=j; } freepf_head=&pfc[pl[minj].pfn];/* 按LRU方式調新頁面入內存頁面 */ pl[minj].pfn=INVALID; pl[minj].time=-1; freepf_head->next=NULL; } pl[page[i]].pfn=freepf_head->pfn; pl[page[i]].time=present_time; freepf_head=freepf_head->next; }else pl[page[i]].time=present_time; present_time++; } printf(" LRU:%6.4f",1-(float)diseffect/320);}void NUR(int total_pf)// NUR(No Used Recently) ALGORITHM最近未使用//int total_pf;{ int i,j,dp,cont_flag,old_dp; //pfc_type *t; initialize(total_pf);/* 初始化相關頁面控制用數據結構 */ dp=0; for(i=0;i<total_instruction;i++){ if(pl[page[i]].pfn==INVALID){ /* 頁面失效 */ diseffect++; /* 失效次數 */ if(freepf_head==NULL){ /* 無空閑頁面 */ cont_flag=TRUE;old_dp=dp; while(cont_flag) if(pl[dp].counter==0 && pl[dp].pfn!=INVALID) cont_flag=FALSE; else{ dp++;if(dp==total_vp)dp=0; if(dp==old_dp) for(j=0;j<total_vp;j++) pl[j].counter=0; } freepf_head=&pfc[pl[dp].pfn];/* 按NUR方式調新頁面入內存頁面 */ pl[dp].pfn=INVALID; freepf_head->next=NULL; } pl[page[i]].pfn=freepf_head->pfn; freepf_head=freepf_head->next; }else pl[page[i]].counter=1; if(i%clear_period==0) for(j=0;j<total_vp;j++) pl[j].counter=0; } printf(" NUR:%6.4f",1-(float)diseffect/320);}void OPT(int total_pf) /* OPT(Optimal Replacement)ALGORITHM最佳 *///int total_pf;{ int i,j,max,maxpage,d,dist[total_vp];// pfc_type *t; initialize(total_pf);/* 初始化相關頁面控制用數據結構 */ for(i=0;i<total_instruction;i++){ if(pl[page[i]].pfn==INVALID){/* 頁面失效 */ diseffect++; /* 失效次數 */ if(freepf_head==NULL){ /* 無空閑頁面 */ for(j=0;j<total_vp;j++) if(pl[j].pfn!=INVALID) dist[j]=32767; else dist[j]=0; d=1; for(j=i+1;j<total_instruction;j++){ if(pl[page[j]].pfn!=INVALID) dist[page[j]]=d; d++; } max=-1; for(j=0;j<total_vp;j++) if(max<dist[j]){ max=dist[j]; maxpage=j; } freepf_head=&pfc[pl[maxpage].pfn];/* 按OPT方式調新頁面入內存頁面 */ freepf_head->next=NULL; pl[maxpage].pfn=INVALID; } pl[page[i]].pfn=freepf_head->pfn; freepf_head=freepf_head->next; } } printf(" OPT:%6.4f",1-(float)diseffect/320);} void LFU(int total_pf) /* LFU(leat Frequently Used)ALGORITHM 最少使用*///int total_pf;{ int i,j,min,minpage;// pfc_type *t; initialize(total_pf);/* 初始化相關頁面控制用數據結構 */ for(i=0;i<total_instruction;i++){ if(pl[page[i]].pfn==INVALID){/* 頁面失效 */ diseffect++; /* 失效次數 */ if(freepf_head==NULL){ /* 無空閑頁面 */ min=32767; if(min>pl[j].counter && pl[j].pfn!=INVALID){ min=pl[j].counter;minpage=j; } pl[j].counter=0; } freepf_head=&pfc[pl[minpage].pfn];/* 按LFU方式調新頁面入內存頁面 */ pl[minpage].pfn=INVALID; freepf_head->next=NULL; } pl[page[i]].pfn=freepf_head->pfn; freepf_head=freepf_head->next; }else pl[page[i]].counter++; } printf(" LFU:%6.4f",1-(float)diseffect/320);} void initialize(int total_pf) /* 初始化相關數據結構 *///int total_pf; /* 用戶進程的內存頁面數 */{ int i; diseffect=0; for(i=0;i<total_vp;i++){ pl[i].pn=i;pl[i].pfn=INVALID; /*置頁面控制結構中的頁號,頁面為空 */ pl[i].counter=0;pl[i].time=-1; /* 頁面控制結構中的訪問次數為0,時間為-1 */ } for(i=1;i<total_pf;i++){ pfc[i-1].next=&pfc[i]; pfc[i-1].pfn=i-1; } /* 建立pfcD一門和pfcD]之間的鏈接 */ pfc[total_pf-1].next=NULL;pfc[total_pf-1].pfn=total_pf-1; freepf_head=&pfc[0]; /*空頁面隊列的頭指針為pfc[0] */}?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -