頁(yè)面置換算法代碼實(shí)現(xiàn)(完整版).doc

_實(shí)驗(yàn)原理：在內(nèi)存運(yùn)行過(guò)程中，若其所要訪問(wèn)的頁(yè)面不在內(nèi)存而需要把他們調(diào)入內(nèi)存，但內(nèi)存已經(jīng)沒(méi)有空閑空間時(shí)，為了保證該進(jìn)程能正常運(yùn)行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁(yè)程序或數(shù)據(jù)送磁盤(pán)的對(duì)換區(qū)中。但應(yīng)將那個(gè)頁(yè)面調(diào)出，需根據(jù)一定的算法來(lái)確定。通常，把選擇換出頁(yè)面的算法成為頁(yè)面置換算法。置換算法的好壞，將直接影響到系統(tǒng)的性能。一個(gè)好的頁(yè)面置換算法，應(yīng)具有較低的頁(yè)面更換頻率。從理論上講，應(yīng)將那些以后不再會(huì)訪問(wèn)的頁(yè)面置換出，或者把那些在較長(zhǎng)時(shí)間內(nèi)不會(huì)在訪問(wèn)的頁(yè)面調(diào)出。目前存在著許多種置換算法（如FIFO，OPT，LRU），他們都試圖更接近理論上的目標(biāo)。實(shí)驗(yàn)?zāi)康模?熟悉FIFO，OPT和LRU算法2比較三種算法的性能優(yōu)劣實(shí)驗(yàn)內(nèi)容：寫(xiě)出FIFO，OPT和LRU算法的程序代碼，并比較它們的算法性能。實(shí)驗(yàn)步驟：代碼如下：#include #define M 4 /物理頁(yè)數(shù)#define N 20/需要調(diào)入的頁(yè)數(shù)typedef struct pageint num;int time;Page;/物理頁(yè)項(xiàng)，包括調(diào)入的頁(yè)號(hào)和時(shí)間 Page mmM; /4個(gè)物理頁(yè)int queue120,queue220,queue320;/記錄置換的頁(yè)int K=0,S=0,T=0;/置換頁(yè)數(shù)組的標(biāo)識(shí)int pos=0;/記錄存在最長(zhǎng)時(shí)間項(xiàng)/初始化內(nèi)存頁(yè)表項(xiàng)及存儲(chǔ)內(nèi)存情況的空間void INIT()int i;for(i=0;iM;i+)mmi.num =-1;mmi.time =0;/取得內(nèi)存中存在時(shí)間最久的位置int GetMax()int max=-1;int i;for(i=0;i max)max=mmi.time ;pos=i;return pos;/檢查最長(zhǎng)時(shí)間不使用頁(yè)面 int longesttime(int fold)int i;int max=-1;for(i=fold;iN;i+)if(mm0.num!=i)mm0.time+;if(mm1.num!=i)mm1.time+;if(mm2.num!=i)mm2.time+;if(mm3.num!=i)mm3.time+;for(i=0;imax)max=mmi.time;pos=i;return pos;/檢查某頁(yè)是否在內(nèi)存int Equation(int fold)int i;for(i=0;iM;i+)if(mmi.num = fold)return i;return -1;/檢查物理內(nèi)存是否已滿(mǎn),-1表滿(mǎn)，其他不滿(mǎn)int Check()int i;for(i=0;iM;i+)if(mmi.num = -1)return i;return -1;/先進(jìn)先出void FIFO(int fold)int i;int a,b,c;a=Equation(fold);/頁(yè)已存在if(a != -1)/頁(yè)不存在elseb=Check();/內(nèi)存還有空閑if(b != -1)mmb.num = fold;/內(nèi)存已滿(mǎn)，需要置換else c=GetMax();mmc.num = fold;mmc.time = 0;queue1K+=fold;for(i=0;iM;i+)if(mmi.num != -1)mmi.time +;void OPT(int fold)int a,b,c;a=Equation(fold);if(a = -1)/頁(yè)不在內(nèi)存b=Check();/內(nèi)存還有空閑if(b != -1)mmb.num = fold;/內(nèi)存已滿(mǎn)，需要置換elsec=longesttime(fold);mmc.num = fold;mmc.time = 0; queue3T+=fold;void LRU(int fold)int i;int a,b;int p;a=Equation(fold);if(a != -1)/頁(yè)已在內(nèi)存/把此項(xiàng)移動(dòng)到鏈表最后一項(xiàng)if(a=3)/此項(xiàng)已經(jīng)在最后，不需要做任何改動(dòng)return;elsep=Equation(-1);if(p=-1)/鏈表是滿(mǎn)的for(;a3;a+)mma.num=mma+1.num;mm3.num=fold;else if(p=3)/鏈表不滿(mǎn)for(;ap-1;a+)mma.num=mma+1.num;mma.num=fold;else b=Check();if(b!=-1)/不滿(mǎn)mmb.num=fold;elsefor(i=0;i3;i+)mmi.num=mmi+1.num;mm3.num=fold;queue2S+=fold;void main()int AN,BN;int i;INIT();printf(請(qǐng)依次輸入%d個(gè)頁(yè)面號(hào)：n,N);for(i=0;iN;i+)scanf(%d,&Ai);/FIFOfor(i=0;iN;i+)Bi=Ai;for(i=0;iN;i+)FIFO( Bi );printf(FIFO的);printf(調(diào)入隊(duì)列為：);for(i=0;iK;i+)printf(%3d,queue1i);printf(n缺頁(yè)次數(shù)為：%6dn缺頁(yè)率：%16.6fnn,K,(float)K/N);/LRUINIT();for(i=0;iN;i+)Bi=Ai;for(i=0;iN;i+)LRU( Bi );printf(LRU的);printf(調(diào)入隊(duì)列為：);for(i=0;iS;i+)printf(%3d,queue2i);printf(n缺頁(yè)次數(shù)為：%6dn缺頁(yè)率：%16.6fnn,S,(float)S/N);/OPTINIT();for(i=0;iN;i+)Bi=Ai;for(i=0;iN;i+)OPT( Bi );printf(OPT的);printf(調(diào)入隊(duì)列為：);for(i=0;iT;i+)printf(%3d,q