實(shí)驗(yàn)五_請(qǐng)求頁(yè)式存儲(chǔ)管理中常用頁(yè)面置換算法模擬.ppt

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