頁(yè)面置換算法實(shí)驗(yàn)報(bào)告

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

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

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

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

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

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

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

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

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

10、FO和CLOCK實(shí)現(xiàn)起來(lái)比較容易，F(xiàn)IFO算法的實(shí)現(xiàn)和CLOCK算法的實(shí)現(xiàn)很相似，F(xiàn)IFO可視為CLOCK的退化版。我先寫(xiě)了CLOCK算法，再刪去一些約束條件就退化為FIFO算法。這就是兩者的相同之處。理論上，CLOCK算法需要維持一個(gè)循環(huán)的主存緩沖區(qū)，需要一個(gè)循環(huán)隊(duì)列去實(shí)現(xiàn)，并且，F(xiàn)IFO算法保持先進(jìn)先出，因此需要一個(gè)先進(jìn)先出隊(duì)列。但是，我實(shí)現(xiàn)這兩個(gè)算法只用到了單向鏈表的數(shù)據(jù)結(jié)構(gòu)，剩下的由其中的指針去把握了。因此，必須對(duì)指針使用有敏銳的感覺(jué)。天下無(wú)難事，只怕有心人！八、 程序源碼（在兩個(gè)系統(tǒng)上都通過(guò)）#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 /指令流長(zhǎng)#define total_vp 32 /虛頁(yè)長(zhǎng)#define clear_period 50 /清周期typedef struct /頁(yè)面結(jié)構(gòu) int pn,/頁(yè)面序號(hào)pfn,/頁(yè)面所在內(nèi)存區(qū)的幀號(hào)counter,/單位時(shí)間內(nèi)訪問(wèn)次數(shù)time;/上次訪問(wèn)的時(shí)間pl_type;pl_type plt

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

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

14、10*getpid(); /*每次運(yùn)行時(shí)進(jìn)程號(hào)不同，用來(lái)作為初始化隨機(jī)數(shù)隊(duì)列的種子*/ s = (int)(float)(total_instruction-1)*(rand()/(RAND_MAX+1.0);printf(n-隨機(jī)產(chǎn)生指令流-n); for (i=0; itotal_instruction; i+=4) /產(chǎn)生指令隊(duì)列 ai=s; /任選一指令訪問(wèn)點(diǎn)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+) /將指令序列變換成頁(yè)地址流 pagei=ai/10; offseti=ai%10; printf(n-不同頁(yè)面工作區(qū)各種替換策略的命中率表-n); printf(Paget FIFOt LRUt OPTt CLOCKn); for(i=4;i=32;i+) /用戶內(nèi)存工作區(qū)從個(gè)頁(yè)面到個(gè)頁(yè)面 printf( %

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

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

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

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

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

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

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

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