實驗五_請求頁式存儲管理中常用頁面置換算法模擬.ppt

實驗五 請求頁式存儲管理中常用頁面置換算法模擬,一、實驗?zāi)康?（1）了解內(nèi)存分頁管理策略 （2）掌握調(diào)頁策略 （3）掌握一般常用的調(diào)度算法 （4）學(xué)會各種存儲分配算法的實現(xiàn)方法。 （5）了解頁面大小和內(nèi)存實際容量對命中率的影響。,二、實驗內(nèi)容 （1）采用頁式分配存儲方案，通過分別計算不同算法的命中率來比較算法的優(yōu)劣，同時也考慮頁面大小及內(nèi)存實際容量對命中率的影響； （2）實現(xiàn)OPT 算法 (最優(yōu)置換算法) 、LRU 算法 (Least Recently) 、 FIFO 算法 (First IN First Out)的模擬； （3）會使用某種編程語言。,三、實驗原理 分頁存儲管理將一個進(jìn)程的邏輯地址空間分成若干大小相等的片，稱為頁面或頁。 在進(jìn)程運行過程中，若其所要訪問的頁面不在內(nèi)存而需把它們調(diào)入內(nèi)存，但內(nèi)存已無空閑空間時，為了保證該進(jìn)程能正常運行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁程序或數(shù)據(jù)，送磁盤的對換區(qū)中。但應(yīng)將哪 個頁面調(diào)出，須根據(jù)一定的算法來確定。通常，把選擇換出頁面的算法稱為頁面置換算法(Page_Replacement Algorithms)。 一個好的頁面置換算法，應(yīng)具有較低的頁面更換頻率。從理論上講，應(yīng)將那些以后不再會訪問的頁面換出，或?qū)⒛切┰谳^長時間內(nèi)不會再訪問的頁面調(diào)出。 1、最佳置換算法OPT(Optimal) 它是由Belady于1966年提出的一種理論上的算法。其所選擇的被淘汰頁面，將是以后永不使用的或許是在最長(未來)時間內(nèi)不再被訪問的頁面。采用最佳置換算法，通?？杀ＷC獲得最低的缺頁率。但由于人目前還無法預(yù)知一個進(jìn)程在內(nèi)存的若干個頁面中，哪一個頁面是未來最長時間內(nèi)不再被訪問的，因而該算法是無法實現(xiàn)的，便可以利用此算法來評價其它算法。 2、先進(jìn)先出(FIFO)頁面置換算法 這是最早出現(xiàn)的置換算法。該算法總是淘汰最先進(jìn)入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時間最久的頁面予以淘汰。該算法實現(xiàn)簡單只需把一個進(jìn)程已調(diào)入內(nèi)存的頁面，按先后次序鏈接成一個隊列，并設(shè)置一個指針，稱為替換指針，使它總是指向最老的頁面。,3、最近最久未使用置換算法 （1）LRU(Least Recently Used)置換算法的描述 FIFO置換算法性能之所以較差，是因為它所依據(jù)的條件是各個頁面調(diào)入內(nèi)存的時間，而頁面調(diào)入的先后并不能反映頁面的使用情況。最近最久未使用（LRU）置換算法，是根據(jù)頁面調(diào)入內(nèi)存后的使用情況進(jìn)行決策的。由于無法預(yù)測各頁面將來的使用情況，只能利用“最近的過去”作為“最近的將來”的近似，因此，LRU置換算法是選擇最近最久未使用的頁面予以淘汰。該算法賦予每個頁面一個訪問字段，用來記錄一個頁面自上次被訪問以來所經(jīng)歷的時間t,，當(dāng)須淘汰一個頁面時，選擇現(xiàn)有頁面中其t值最大的，即最近最久未使用的頁面予以淘汰。 （2）LRU置換算法的硬件支持 LRU置換算法雖然是一種比較好的算法，但要求系統(tǒng)有較多的支持硬件。為了了解一個進(jìn)程在內(nèi)存中的各個頁面各有多少時間未被進(jìn)程訪問，以及如何快速地知道哪一頁是最近最久未使用的頁面，須有以下兩類硬件之一的支持： a）寄存器 為了記錄某個進(jìn)程在內(nèi)存中各頁的使用情況，須為每個在內(nèi)存中的頁面配置一個移位寄存器，可表示為 R=Rn-1Rn-2Rn-3R2R1R0 當(dāng)進(jìn)程訪問某物理塊時，要將相應(yīng)寄存器的Rn-1位置成1。此時，定時信號將每隔一定時間(例如100ms)將寄存器右移一位。如果我們把n位寄存器的數(shù)看作是一個整數(shù)，那么具有最小數(shù)值的寄存器所對應(yīng)的頁面，就是最近最久未使用的頁面。如圖1示出了某進(jìn)程在內(nèi)存中具有8個頁面，為每個內(nèi)存頁面配置一個8位寄存器時的LRU訪問情況。這里，把8個內(nèi)存頁面的序號分別定為18。由圖可以看出，第7個內(nèi)存頁面的R值最小，當(dāng)發(fā)生缺頁時首先將它置換出去。,b)棧 可利用一個特殊的棧來保存當(dāng)前使用的各個頁面的頁面號。每當(dāng)進(jìn)程訪問某頁面時，便將頁面的頁面號從棧中移出，將它壓入棧頂。因此，棧頂始終是最新被訪問頁面的編號民，而棧底則是最近最久未使用的頁面的頁面號。,int findSpace(int Nsize) /查找是否有空閑內(nèi)存 for(int i=0; i= blocka.biaoji) a = i;/找到應(yīng)予置換頁面，返回BLOCK中位置 return a; ,void display(int Nsize) /顯示 for(int i=0; iNsize; i+) if(blocki.yemian != -1)/非空閑內(nèi)存 coutblocki.yemian“ “; coutendl; /*FIFO核心部分*/ void FIFO(int Nsize) /先進(jìn)先出頁面置換算法 int exist,space,aition ; float score=0; for(int i=0; iPsize; i+) exist = findExist(i,Nsize); if(exist != -1)/內(nèi)存中有該頁面 cout“不缺頁“endl; score+=1;/統(tǒng)計不缺頁次數(shù) else space = findSpace(Nsize); if(space != -1)/找到空閑內(nèi)存 blockspace = pagei; display(Nsize); ,else aition = findReplace(Nsize);/找到應(yīng)予置換頁面 blockaition = pagei; display(Nsize); for(int j=0; jNsize; j+) blockj.biaoji+;/BLOCK中所有頁面biaoji+ cout“缺頁次數(shù)為：“20-scoreendl; cout“缺頁率為： “(20-score)*100/20“%“endl; /*LRU核心部分*/ void LRU(int Nsize) /最近最久未使用置換算法 int exist,space,aition ; float score=0; for(int i=0; iPsize; i+) exist = findExist(i,Nsize); if(exist != -1) blockexist.biaoji=0; cout“不缺頁“endl;,void OPT(int Nsize) /最優(yōu)頁置換算法 int exist,space,aition; float score=0; for(int i=0; iPsize; i+) exist = findExist(i,Nsize); if(exist != -1)/內(nèi)存中有該頁面 cout“不缺頁“endl; score+=1;/統(tǒng)計不缺頁次數(shù) else space = findSpace(Nsize); if(space != -1)/找到空閑內(nèi)存 blockspace = pagei; display(Nsize); else for(int j=0; jNsize; j+) for(int l =i;lPsize;l+) if(blockj.yemian=pagel.yemian)/計算誰是最長時間沒使用的 blockj.biaoji=l-i; break; else blockj.biaoji=Psize-i; aition = findReplace(Nsize);/找到應(yīng)予置換頁面 blockaition = pagei; display(Nsize); cout“缺頁次數(shù)為：“20-scoreendl; cout“缺頁率為： “(20-score)*100/20“%“endl; ,void BlockClear(int Nsize) /塊清除 for(int i=0; i應(yīng)用FIFO算法-+“應(yīng)用LRU算法-+“應(yīng)用OPT算法-+“插入新的頁面號引用串+“退出-+“select; switch(select) case 0: break; case 1: coutNsize; while(1) if(Nsi