頁面置換算法

頁面置換算法1在地址映射過程中，若在頁面中發(fā)現(xiàn)所要訪問的頁面不再內(nèi)存中，則產(chǎn)生缺頁中斷。當(dāng)發(fā)生缺頁中斷時(shí)操作系統(tǒng)必須在內(nèi)存選擇一個(gè)頁面將其移出內(nèi)存，以便為即將調(diào)入的頁面讓出空間。而用來選擇淘汰哪一頁的規(guī)則叫做頁面置換算法

常見的置換算法有：1．最佳置換算法（OPT）（理想置換算法）2．先進(jìn)先出置換算法（FIFO）：3．最近最久未使用（LRU）算法4．Clock置換算法（LRU算法的近似實(shí)現(xiàn)）5．最少使用（LFU）置換算法6．工作集算法7.工作集時(shí)鐘算法8.老化算法（非常類似LRU的有效算法）9.NRU(最近未使用）算法10.第二次機(jī)會(huì)算法2操作系統(tǒng)頁面置換算法代碼#include<stdio.h>[1]#include<stdlib.h>#include<unistd.h>#defineTRUE1#defineFALSE0#defineINVALID-1#defineNUL0#definetotal_instruction320/*指令流長(zhǎng)*/#definetotal_vp32/*虛頁長(zhǎng)*/#defineclear_period50/*清零周期*/typedefstruct{/*頁面結(jié)構(gòu)*/intpn,pfn,counter,time;}pl_type;pl_typepl[total_vp];/*頁面結(jié)構(gòu)數(shù)組*/structpfc_struct{/*頁面控制結(jié)構(gòu)*/intpn,pfn;structpfc_struct*next;};3typedefstructpfc_structpfc_type;pfc_typepfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;intdiseffect,a[total_instruction];intpage[total_instruction],offset[total_instruction];voidinitialize(int);voidFIFO(int);voidLRU(int);voidNUR(int);intmain(){intS,i;srand((int)getpid());S=(int)rand()%390;for(i=0;i<total_instruction;i+=1)/*產(chǎn)生指令隊(duì)列*/{a[i]=S;/*任選一指令訪問點(diǎn)*/a[i+1]=a[i]+1;/*順序執(zhí)行一條指令*/a[i+2]=(int)rand()%390;/*執(zhí)行前地址指令m’*/a[i+3]=a[i+2]+1;/*執(zhí)行后地址指令*/4S=(int)rand()%390;}for(i=0;i<total_instruction;i++)/*將指令序列變換成頁地址流*/{page[i]=a[i]/10;offset[i]=a[i]%10;}for(i=4;i<=32;i++)/*用戶內(nèi)存工作區(qū)從4個(gè)頁面到32個(gè)頁面*/{printf("%2dpageframes",i);FIFO(i);LRU(i);NUR(i);printf("\n");}return0;}voidFIFO(inttotal_pf)/*FIFO(FirstinFirstout)ALGORITHM*//*用戶進(jìn)程的內(nèi)存頁面數(shù)*/5{inti;pfc_type*p,*t;initialize(total_pf);/*初始化相關(guān)頁面控制用數(shù)據(jù)結(jié)構(gòu)*/busypf_head=busypf_tail=NUL;/*忙頁面隊(duì)列頭，對(duì)列尾鏈接*/for(i=0;i<total_instruction;i++){if(pl[page[i]].pfn==INVALID)/*頁面失效*/{diseffect+=1;/*失效次數(shù)*/if(freepf_head==NUL)/*無空閑頁面*/{p=busypf_head->next;pl[busypf_head->pn].pfn=INVALID;/*釋放忙頁面隊(duì)列中的第一個(gè)頁面*/freepf_head=busypf_head;freepf_head->next=NUL;busypf_head=p;}6p=freepf_head->next;/*按方式調(diào)新頁面入內(nèi)存頁面*/freepf_head->next=NUL;freepf_head->pn=page[i];pl[page[i]].pfn=freepf_head->pfn;if(busypf_tail==NUL)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);}voidLRU(inttotal_pf){7intmin,minj,i,j,present_time;initialize(total_pf);present_time=0;for(i=0;i<total_instruction;i++){if(pl[page[i]].pfn==INVALID)/*頁面失效*/{diseffect++;if(freepf_head==NUL)/*無空閑頁面*/{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];pl[minj].pfn=INVALID;pl[minj].time=-1;8freepf_head->next=NUL;}pl[page[i]].pfn=freepf_head->pfn;pl[page[i]].time=present_time;freepf_head=freepf_head->next;}elsepl[page[i]].time=present_time;present_time++;}printf("LRU:%6.4f",1-(float)diseffect/320);}voidNUR(inttotal_pf){inti,j,dp,cont_flag,old_dp;pfc_type*t;initialize(total_pf);dp=0;9for(i=0;i<total_instruction;i++){if(pl[page[i]].pfn==INVALID)/*頁面失效*/{diseffect++;if(freepf_head==NUL)/*無空閑頁面*/{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;10}freepf_head=&pfc[pl[dp].pfn];pl[dp].pfn=INVALID;freepf_head->next=NUL;}pl[page[i]].pfn=freepf_head->pfn;freepf_head=freepf_head->next;}elsepl[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);}voidinitialize(inttotal_pf)/*初始化相關(guān)數(shù)據(jù)結(jié)構(gòu)*//*用戶進(jìn)程的內(nèi)存頁面數(shù)*/{11inti;diseffect=0;for(i=0;i<total_vp;i++){pl[i].pn=i;pl[i].pfn=INVALID;/*置頁面控制結(jié)構(gòu)中的頁號(hào)，頁面為空*/pl[i].counter=0;pl[i].time=-1;/*頁面控制結(jié)構(gòu)中的訪問次數(shù)為0，時(shí)間為-1*/