頁面置換算法實驗報告

1、一、 實驗?zāi)康?通過模擬實現(xiàn)請求頁式存儲管理的幾種基本頁面置換算法，了解虛擬存儲技術(shù)的特點，掌握虛擬存儲請求頁式存儲管理中幾種基本頁面置換算法的基本思想和實現(xiàn)過程，并比較它們的效率。二、 實驗內(nèi)容 基于一個虛擬存儲區(qū)和內(nèi)存工作區(qū)，設(shè)計下述算法并計算訪問命中率。 1、最佳淘汰算法（OPT） 2、先進先出的算法（FIFO） 3、最近最久未使用算法（LRU） 4、簡單時鐘(鐘表)算法（CLOCK） 命中率頁面失效次數(shù)頁地址流(序列)長度三、 實驗原理UNIX中，為了提高內(nèi)存利用率，提供了內(nèi)外存進程對換機制；內(nèi)存空間的分配和回收均以頁為單位進行；一個進程只需將其一部分（段或頁）調(diào)入內(nèi)存便可運行；還支持

2、請求調(diào)頁的存儲管理方式。當(dāng)進程在運行中需要訪問某部分程序和數(shù)據(jù)時，發(fā)現(xiàn)其所在頁面不在內(nèi)存，就立即提出請求（向CPU發(fā)出缺中斷），由系統(tǒng)將其所需頁面調(diào)入內(nèi)存。這種頁面調(diào)入方式叫請求調(diào)頁。為實現(xiàn)請求調(diào)頁，核心配置了四種數(shù)據(jù)結(jié)構(gòu)：頁表、頁幀（框）號、訪問位、修改位、有效位、保護位等。當(dāng)CPU接收到缺頁中斷信號，中斷處理程序先保存現(xiàn)場，分析中斷原因，轉(zhuǎn)入缺頁中斷處理程序。該程序通過查找頁表，得到該頁所在外存的物理塊號。如果此時內(nèi)存未滿，能容納新頁，則啟動磁盤I/O將所缺之頁調(diào)入內(nèi)存，然后修改頁表。如果內(nèi)存已滿，則須按某種置換算法從內(nèi)存中選出一頁準(zhǔn)備換出，是否重新寫盤由頁表的修改位決定，然后將缺頁調(diào)入，

3、修改頁表。利用修改后的頁表，去形成所要訪問數(shù)據(jù)的物理地址，再去訪問內(nèi)存數(shù)據(jù)。整個頁面的調(diào)入過程對用戶是透明的。四、 算法描述本實驗的程序設(shè)計基本上按照實驗內(nèi)容進行。即使用srand( )和rand( )函數(shù)定義和產(chǎn)生指令序列，然后將指令序列變換成相應(yīng)的頁地址流，并針對不同的算法計算出相應(yīng)的命中率。（1）通過隨機數(shù)產(chǎn)生一個指令序列，共320條指令。指令的地址按下述原則生成： A：50%的指令是順序執(zhí)行的B：25%的指令是均勻分布在前地址部分C：25%的指令是均勻分布在后地址部分具體的實施方法是： A：在0，319的指令地址之間隨機選取一起點m B：順序執(zhí)行一條指令，即執(zhí)行地址為m+1的指令C：在

4、前地址0,m+1中隨機選取一條指令并執(zhí)行，該指令的地址為m D：順序執(zhí)行一條指令，其地址為m+1 E：在后地址m+2，319中隨機選取一條指令并執(zhí)行F：重復(fù)步驟A-E，直到320次指令（2）將指令序列變換為頁地址流設(shè)：頁面大小為1K； 用戶內(nèi)存（頁幀）容量為4頁32頁； 用戶虛存容量為32K。在用戶虛存中，按每K存放10條指令排列虛存地址，即320條指令在虛存中的存放方式為： 第 0 條-第 9 條指令為第0頁（對應(yīng)虛存地址為0，9） 第10條-第19條指令為第1頁（對應(yīng)虛存地址為10，19） 第310條-第319條指令為第31頁（對應(yīng)虛存地址為310，319） 按以上方式，用戶指令可組成32

5、頁。五、 算法實現(xiàn)與分析1.常量及變量#define total_instruction 320 /指令流長#define total_vp 32 /虛頁長#define clear_period 50 /清周期pfc_type pfctotal_vp, /主存區(qū)頁面控制結(jié)構(gòu)數(shù)組pfc_type *freepf_head, /主存區(qū)頁面控制結(jié)構(gòu)的空閑頁面頭指針pfc_type *busypf_head, /主存區(qū)頁面控制結(jié)構(gòu)的忙頁面頭指針pfc_type *busypf_tail; /主存區(qū)頁面控制結(jié)構(gòu)的忙頁面尾指針int diseffect;/頁錯誤計數(shù)器，初次把頁面載入主存時也當(dāng)做頁錯誤p

6、l_type pltotal_vp; /頁面結(jié)構(gòu)數(shù)組2.數(shù)據(jù)結(jié)構(gòu)typedef struct /頁面結(jié)構(gòu) int pn,/頁面序號pfn,/頁面所在內(nèi)存區(qū)的幀號counter,/單位時間內(nèi)訪問次數(shù)time;/上次訪問的時間pl_type;struct pfc_struct /頁面控制結(jié)構(gòu)，模擬內(nèi)存中的頁集 int pn,/頁面號 pfn;/內(nèi)存區(qū)頁面的幀號 struct pfc_struct *next;/頁面指針，用于維護內(nèi)存緩沖區(qū)的鏈?zhǔn)浇Y(jié)構(gòu);3.函數(shù)定義int initialize(int);/初始化頁面結(jié)構(gòu)數(shù)組和頁面控制結(jié)構(gòu)數(shù)組int FIFO(int);/先進先出算法int LRU(i

7、nt);/最近最久未使用算法int OPT(int);/最佳置換算法int CLOCK(int);/簡單時鐘(鐘表)算法六、 實驗結(jié)果分析理論上，四種替換算法的命中率由高到底排列應(yīng)該是OPTLRUCLOCKFIFO。實際上，從實驗數(shù)據(jù)觀測得到，存在這種由高到低的趨勢，由page=4時可以觀測到，但是效果不是很明顯。效果不明顯的原因：推測與指令流的產(chǎn)生方式有關(guān)系。因為指令流的產(chǎn)生方式要能體現(xiàn)局部性原理，所以該指令流產(chǎn)生設(shè)計為：50%的指令是順序執(zhí)的，25%的指令是均勻分布在前地址部分，25%的指令是均勻分布在后地址部分。但是這樣的指令流設(shè)計方式能否最佳地體現(xiàn)局部性原理，這還有待驗證。同時，估計和

8、指令數(shù)量有關(guān)系。因為320條指令太少了，通常一個稍大點的程序都幾千行指令了。而且由于隨即數(shù)產(chǎn)生具有一定的波動性，該命中率的計算也有一定的波動性。所以會有局部的實驗數(shù)據(jù)與理論不符。改進方法是多次實驗取平均值，這樣可以減小波動，讓實驗數(shù)據(jù)更加平滑。唯一顯著的是OPT算法的命中率與其他3個調(diào)度算法保持了比較大的差距。例如在page=26時，OPT算法就能達(dá)到0.9的命中率了。到后期，由于page越來越大，因此越來越容易命中，因此各替換算法的命中率差距變小了。這由最后幾行命中率相似可以看出。七、 實驗總結(jié) 這次實驗其實不一定要在linux操作系統(tǒng)下做，在windows操作系統(tǒng)一樣可以實現(xiàn)，只要把頭文件

9、稍作修改即可。為了保險起見，我在2個操作系統(tǒng)下都編譯過，都沒問題。在windows操作系統(tǒng)，要屏蔽/#include 這句話，在linux操作系統(tǒng)下則啟用。此次實驗借助于老師提供的主函數(shù)main模板，只需要寫FIFO，LRU，OPT,CLOCK等4個替換算法，所以阻力沒那么大。每個替換算法必須弄懂其中的細(xì)節(jié)，寫起來才得心應(yīng)手。一開始做這個實驗時，首先是看書，先把書上的替換算法知識點弄明白，要明白各種算法的優(yōu)缺點和相互之間衍生互補關(guān)系。這四個算法中，難以實現(xiàn)的是LRU算法，因為它涉及到訪問時間的計算，而且它的開銷也比較大。OPT算法次難，它需要計算最近訪問時間，并替換最近訪問時間最大的頁。而FI

10、FO和CLOCK實現(xiàn)起來比較容易，F(xiàn)IFO算法的實現(xiàn)和CLOCK算法的實現(xiàn)很相似，F(xiàn)IFO可視為CLOCK的退化版。我先寫了CLOCK算法，再刪去一些約束條件就退化為FIFO算法。這就是兩者的相同之處。理論上，CLOCK算法需要維持一個循環(huán)的主存緩沖區(qū)，需要一個循環(huán)隊列去實現(xiàn)，并且，F(xiàn)IFO算法保持先進先出，因此需要一個先進先出隊列。但是，我實現(xiàn)這兩個算法只用到了單向鏈表的數(shù)據(jù)結(jié)構(gòu)，剩下的由其中的指針去把握了。因此，必須對指針使用有敏銳的感覺。天下無難事，只怕有心人！八、 程序源碼（在兩個系統(tǒng)上都通過）#include #include #include /在window操作系統(tǒng)下要屏蔽此條指

11、令#include #ifndef _UNISTD_H#define _UNISTD_H#include #include #endif#define TRUE 1#define FALSE 0#define INVALID -1#define total_instruction 320 /指令流長#define total_vp 32 /虛頁長#define clear_period 50 /清周期typedef struct /頁面結(jié)構(gòu) int pn,/頁面序號pfn,/頁面所在內(nèi)存區(qū)的幀號counter,/單位時間內(nèi)訪問次數(shù)time;/上次訪問的時間pl_type;pl_type plt

12、otal_vp; /頁面結(jié)構(gòu)數(shù)組struct pfc_struct /頁面控制結(jié)構(gòu) int pn,/頁面號 pfn;/內(nèi)存區(qū)頁面的幀號 struct pfc_struct *next;/頁面指針，用于維護內(nèi)存緩沖區(qū)的鏈?zhǔn)浇Y(jié)構(gòu);typedef struct pfc_struct pfc_type; /主存區(qū)頁面控制結(jié)構(gòu)別名pfc_type pfctotal_vp, /主存區(qū)頁面控制結(jié)構(gòu)數(shù)組*freepf_head, /主存區(qū)頁面控制結(jié)構(gòu)的空閑頁面頭指針*busypf_head, /主存區(qū)頁面控制結(jié)構(gòu)的忙頁面頭指針*busypf_tail; /主存區(qū)頁面控制結(jié)構(gòu)的忙頁面尾指針int diseffe

13、ct; /頁錯誤計數(shù)器，初次把頁面載入主存時也當(dāng)做頁錯誤int atotal_instruction; /隨即指令流數(shù)組int pagetotal_instruction; /指令對應(yīng)的頁面號int offsettotal_instruction; /指令所在頁面中的偏移量int initialize(int);/初始化頁面結(jié)構(gòu)數(shù)組和頁面控制結(jié)構(gòu)數(shù)組int FIFO(int);/先進先出算法int LRU(int);/最近最久未使用算法int OPT(int);/最佳置換算法int CLOCK(int);/簡單時鐘(鐘表)算法int main( ) int s;/隨機數(shù)inti; srand(

14、10*getpid(); /*每次運行時進程號不同，用來作為初始化隨機數(shù)隊列的種子*/ s = (int)(float)(total_instruction-1)*(rand()/(RAND_MAX+1.0);printf(n-隨機產(chǎn)生指令流-n); for (i=0; itotal_instruction; i+=4) /產(chǎn)生指令隊列 ai=s; /任選一指令訪問點m ai+1=ai+1; /順序執(zhí)行一條指令 ai+2=(int)(float)ai*(rand()/(RAND_MAX+1.0); /執(zhí)行前地址指令m ai+3=ai+2+1; /順序執(zhí)行一條指令 printf(%6d%6d%6

15、d%6dn, ai,ai+1,ai+2,ai+3); s = (int)(float)(total_instruction-1)-ai+2)*(rand()/(RAND_MAX+1.0) + ai+2; printf(-n);for (i=0;itotal_instruction;i+) /將指令序列變換成頁地址流 pagei=ai/10; offseti=ai%10; printf(n-不同頁面工作區(qū)各種替換策略的命中率表-n); printf(Paget FIFOt LRUt OPTt CLOCKn); for(i=4;i=32;i+) /用戶內(nèi)存工作區(qū)從個頁面到個頁面 printf( %

16、2d t,i); FIFO(i); LRU(i); OPT(i); CLOCK(i); printf(n); return 0;/初始化頁面結(jié)構(gòu)數(shù)組和頁面控制結(jié)構(gòu)數(shù)組/total_pf; 用戶進程的內(nèi)存頁面數(shù)int initialize(int total_pf) int i; diseffect=0; for(i=0;itotal_vp;i+)pli.pn=i;pli.pfn=INVALID; /置頁面所在主存區(qū)的幀號為-1.表示該頁不在主存中pli.counter=0;/置頁面結(jié)構(gòu)中的訪問次數(shù)為pli.time=-1;/置頁面結(jié)構(gòu)中的上次訪問的時間為-1for(i=0;itotal_pf-

17、1;i+)pfci.next=&pfci+1; /建立pfci-1和pfci之間的鏈接pfci.pfn=i; /初始化主存區(qū)頁面的幀號pfctotal_pf-1.next=NULL;pfctotal_pf-1.pfn=total_pf-1;freepf_head=&pfc0;/主存區(qū)頁面控制結(jié)構(gòu)的空閑頁面頭指針指向pfc0return 0;/最近最久未使用算法/int total_pf; 用戶進程的內(nèi)存頁面數(shù)int LRU (int total_pf) int MinT;/最小的訪問時間，即很久沒被訪問過int MinPn;/擁有最小的訪問時間的頁的頁號int i,j;int CurrentT

18、ime;/系統(tǒng)當(dāng)前時間 initialize(total_pf);/初始化頁面結(jié)構(gòu)數(shù)組和頁面控制結(jié)構(gòu)數(shù)組 CurrentTime=0;diseffect=0;for(i=0;itotal_instruction;i+)if(plpagei.pfn=INVALID) /頁面失效diseffect+;/頁錯誤次數(shù)加 if(freepf_head=NULL) /無空閑頁面 MinT=; for(j=0;jplj.time&plj.pfn!=INVALID) MinT=plj.time; MinPn=j; freepf_head=&pfcplMinPn.pfn; /最久沒被訪問過的頁被釋放 plMin

19、Pn.pfn=INVALID; /最久沒被訪問過的頁被換出主存 plMinPn.time=-1;/最久沒被訪問過的頁的訪問時間置為無效 freepf_head-next=NULL; plpagei.pfn=freepf_head-pfn; /有空閑頁面,把相應(yīng)的頁面換入主存，并把pfn改為相應(yīng)的幀號 plpagei.time=CurrentTime;/令訪問時間為當(dāng)前系統(tǒng)時間 freepf_head=freepf_head-next; /減少一個空閑頁面elseplpagei.time=CurrentTime; /命中則刷新該單元的訪問時間CurrentTime+; /系統(tǒng)當(dāng)前時間加 prin

20、tf(%6.3ft,1-(float)diseffect/320);return 0;/最佳置換算法/int total_pf; 用戶進程的內(nèi)存頁面數(shù)int OPT(int total_pf)int i,j;int MaxD;/將來最近一次訪問的距離的最大值（以時間單元度量）int MaxPn;/將來最近一次訪問的距離的最大值的頁號int dis;/距離計數(shù)器int disttotal_vp;/距離數(shù)組，保存距離上一次訪問的時間差距個數(shù)initialize(total_pf);/初始化頁面結(jié)構(gòu)數(shù)組和頁面控制結(jié)構(gòu)數(shù)組diseffect=0;for(i=0;itotal_instruction;i

21、+)if(plpagei.pfn=INVALID)/頁面失效diseffect+;/頁錯誤次數(shù)加if(freepf_head=NULL)/無空閑頁面for(j=0;jtotal_vp;j+)if(plj.pfn!=INVALID)/如果該頁在主存中distj=;/ 該頁關(guān)聯(lián)的距離值改為最大值elsedistj=0;/如果不在該頁主存中，該頁關(guān)聯(lián)的距離值改為dis=1;/初始距離值為for(j=i+1;jtotal_instruction;j+) /從要替換的指令的下一條算起，if(plpagej.pfn!=INVALID &plpagej.counter=0)/如果該頁在主存中,并且是將要最近

22、訪問的頁/if(plpagej.pfn!=INVALID & distpagej=) /此條語句原理與上相同distpagej=dis;/距離值改為displpagej.counter=1;/使訪問次數(shù)標(biāo)志加，區(qū)別第一次訪問和第二次訪問dis+;MaxD=-1;for(j=0;jtotal_vp;j+)plj.counter=0;/重置訪問次數(shù)為if(MaxDnext=NULL;plMaxPn.pfn=INVALID;plpagei.pfn=freepf_head-pfn; /把當(dāng)前頁換入主存中，并且把當(dāng)前頁的pfn改為換入頁的幀號，freepf_head=freepf_head-next;

23、/減少一個空閑頁面/if/forprintf(%6.3ft,1-(float)diseffect/320);return 0;/簡單時鐘算法/int total_pf; 用戶進程的內(nèi)存頁面數(shù)int CLOCK(int total_pf)int i;int usetotal_vp; /使用位int swap;swap=0; /發(fā)生替換initialize(total_pf);pfc_type *pnext; /時鐘指針pfc_type *head; /隊列頭指針pnext=freepf_head;head=freepf_head;for(i=0;itotal_vp;i+)usei=0; /初始化使用位為diseffect=0;for(i=0;ipfn=1) /若時鐘指針指向的頁的使用位為，則改為并跳過usepnext-pfn=0;pnext=pnext-next;if(pnext=NULL) pnext=head; /如果時鐘指針到達(dá)隊列尾部，重新返回頭部/換出被替換的頁plpnext-pn.pfn=INVALID;swap=1;if(usepnext-pfn=0) /如果使用位為，則換入相應(yīng)的頁plpagei.pfn=pnext-pfn; /頁面結(jié)構(gòu)中要標(biāo)記幀號pnext-pn=pagei; /頁面控制結(jié)構(gòu)中要標(biāo)記頁號usepnext-pf