LRU頁(yè)面置換算法模擬

1、頁(yè)面置換算法模擬 -最近最久未使用置換算法 |課程設(shè)計(jì) |計(jì)算機(jī)數(shù)據(jù)庫(kù)課程設(shè)計(jì)一、設(shè)計(jì)目的1、用 C 語(yǔ)言實(shí)現(xiàn)最近最久未使用（ LRU ）置換算法。2、了解內(nèi)存分頁(yè)管理策略3、掌握調(diào)頁(yè)策略4、掌握一般常用的調(diào)度算法5、選取調(diào)度算法中的典型算法，模擬實(shí)現(xiàn)二、設(shè)計(jì)任務(wù)在 Window98/2000 系統(tǒng)的 TC2.0 環(huán)境下運(yùn)行程序；通過(guò)從一般常用的調(diào)頁(yè)算法中選取典型算法 LRU ，了 解頁(yè)面管理的相關(guān)細(xì)節(jié)，并用程序設(shè)計(jì)實(shí)現(xiàn)LRU 。三、設(shè)計(jì)內(nèi)容與步驟分頁(yè)存儲(chǔ)管理將一個(gè)進(jìn)程的邏輯地址空間分成若干大小相等的片，稱為頁(yè)面或頁(yè)。一、調(diào)頁(yè)策略1）何時(shí)調(diào)入頁(yè)面如果進(jìn)程的許多頁(yè)是存放在外存的一個(gè)連續(xù)區(qū)域中，則

2、一次調(diào)入若干個(gè)相鄰的頁(yè)，會(huì)比一次調(diào)入一頁(yè)的效 率更高效一些。但如果調(diào)入的一批頁(yè)面中的大多數(shù)都未被訪問(wèn)，則又是低效的?？刹捎靡环N以預(yù)測(cè)為基礎(chǔ) 的預(yù)調(diào)頁(yè)策略，將那些預(yù)計(jì)在不久之后便會(huì)被訪問(wèn)的頁(yè)面，預(yù)先調(diào)入內(nèi)存。如果預(yù)測(cè)較準(zhǔn)確，那么，這種 策略顯然是很有吸引力的。但目前預(yù)調(diào)頁(yè)的成功率僅為50%。且這種策略主要用于進(jìn)程的首次調(diào)入時(shí)，由程序員指出應(yīng)該先調(diào)入哪些頁(yè)。2）請(qǐng)求調(diào)頁(yè)策略當(dāng)進(jìn)程在運(yùn)行中需要訪問(wèn)某部分程序和數(shù)據(jù)時(shí)，若發(fā)現(xiàn)其所在的頁(yè)面不在內(nèi)存，便即提出請(qǐng)求，由 OS 將 其所需頁(yè)面調(diào)入內(nèi)存。由請(qǐng)示調(diào)頁(yè)策略所確定調(diào)入的頁(yè)，是一定會(huì)被訪問(wèn)的，再加之請(qǐng)求調(diào)頁(yè)策略比較易 于實(shí)現(xiàn)，故在目前的虛擬存儲(chǔ)器中，大多

3、采用此策略。但這種策略每次僅調(diào)入一頁(yè)，故須花費(fèi)較大的系統(tǒng) 開(kāi)銷(xiāo)，增加了磁盤(pán) I/O 的啟用頻率。2、從何處調(diào)入頁(yè)面在請(qǐng)求分頁(yè)系統(tǒng)中的外存分為兩部分：用于存放文件的文件區(qū)和用于存放對(duì)換頁(yè)面的對(duì)換區(qū)。通常， 由于對(duì)換區(qū)是采用連續(xù)分配方式，而事件是采用離散分配方式，故對(duì)換區(qū)的磁盤(pán) I/O 速度比文件區(qū)的高。 這樣，每當(dāng)發(fā)生缺頁(yè)請(qǐng)求時(shí)，系統(tǒng)應(yīng)從何處將缺頁(yè)調(diào)入內(nèi)存，可分成如下三種情況：(1) 系統(tǒng)擁有足夠的對(duì)換區(qū)空間，這時(shí)可以全部從對(duì)換區(qū)調(diào)入 所需頁(yè)面，以提高調(diào)頁(yè)速度。為此，在進(jìn) 程運(yùn)行前，便須將與該進(jìn)程有關(guān)的文件，從文件區(qū)拷貝到對(duì)換區(qū)。(2) 系統(tǒng)缺少足夠的對(duì)換區(qū)空間，這時(shí)凡是不會(huì)被修改的文件，都直接

4、從文件區(qū)調(diào)入；而當(dāng)換出這些頁(yè)面 時(shí)，由于它們未被修改而不必再將它們換出時(shí)，以后需要時(shí)，再?gòu)膶?duì)換區(qū)調(diào)入。(3) UNIX 方式。由于與進(jìn)程有關(guān)的文件都放在文件區(qū)，故凡是未運(yùn)行過(guò)的頁(yè)面，都從文件區(qū)調(diào)入。而對(duì) 于曾經(jīng)運(yùn)行過(guò)但又被換出的頁(yè)面，由于被放在對(duì)換區(qū)，因此在下次時(shí)，應(yīng)從對(duì)換區(qū)調(diào)入。由于 UNIX 系統(tǒng) 允許頁(yè)面共享，因此，某進(jìn)程所請(qǐng)求的頁(yè)面有可能已被其它進(jìn)程調(diào)入內(nèi)存，此時(shí)也就無(wú)須再?gòu)膶?duì)換區(qū)調(diào)入。3 頁(yè)面調(diào)入過(guò)程每當(dāng)程序所要訪問(wèn)的頁(yè)面未在內(nèi)存時(shí)， 便向 CPU 發(fā)出一缺頁(yè)中斷， 中斷處理程序首先保留 CPU 環(huán)境， 分析中斷原因后，轉(zhuǎn)入缺頁(yè)中斷處理程序。該程序通過(guò)查找頁(yè)表，得到該頁(yè)在外在原物理

5、塊后，如果此時(shí) 內(nèi)存能容納新頁(yè)，則啟動(dòng)磁盤(pán) I/O 將所缺之頁(yè)調(diào)入內(nèi)存，然后修改頁(yè)表。如果內(nèi)存已滿，則須先按照某種 置換算法從內(nèi)存中選出一頁(yè)準(zhǔn)備換出；如果該頁(yè)未被修改過(guò)，可不必將該頁(yè)寫(xiě)回磁盤(pán)；但如果此頁(yè)已被修 改，則必須將它寫(xiě)回磁盤(pán)，然后再把所缺的頁(yè)調(diào)入內(nèi)存，并修改頁(yè)表中的相應(yīng)表項(xiàng)，置其存在位“1”，并將此頁(yè)表項(xiàng)寫(xiě)入快表中。在缺頁(yè)調(diào)入內(nèi)存后，利用修改后的頁(yè)表，去形成所要訪問(wèn)數(shù)據(jù)的物理地址，再去訪 問(wèn)內(nèi)存數(shù)據(jù)。整個(gè)頁(yè)面的調(diào)入過(guò)程對(duì)用戶是透明的。二、頁(yè)面置換算法在進(jìn)程運(yùn)行過(guò)程中，若其所要訪問(wèn)的頁(yè)面不在內(nèi)存而需把它們調(diào)入內(nèi)存，但內(nèi)存已無(wú)空閑空間時(shí)，為 了保證該進(jìn)程能正常運(yùn)行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁(yè)

6、程序或數(shù)據(jù)，送磁盤(pán)的對(duì)換區(qū)中。但應(yīng)將哪 個(gè)頁(yè)面 調(diào)出，須根據(jù)一定的算法來(lái)確定。通常，把選擇換出頁(yè)面的算法稱為頁(yè)面置換算法 (Page_Replacement Alg orithms) 。一個(gè)好的頁(yè)面置換算法，應(yīng)具有較低的頁(yè)面更換頻率。從理論上講，應(yīng)將那些以后不再會(huì)訪問(wèn)的頁(yè)面 換出，或?qū)⒛切┰谳^長(zhǎng)時(shí)間內(nèi)不會(huì)再訪問(wèn)的頁(yè)面調(diào)出。常見(jiàn)置換算法 最佳置換算法 (Optimal) ：它是由 Belady 于 1966 年提出的一種理論上的算法。其所選擇的被淘汰頁(yè)面，將是以后永不使用的或許是 在最長(zhǎng) (未來(lái) )時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面。采用最佳置換算法，通常可保證獲得最低的缺頁(yè)率。但由于人目 前還無(wú)法預(yù)知一個(gè)

7、進(jìn)程在內(nèi)存的若干個(gè)頁(yè)面中，哪一個(gè)頁(yè)面是未來(lái)最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)的，因而該算法 是無(wú)法實(shí)現(xiàn)的，便可以利用此算法來(lái)評(píng)價(jià)其它算法。 先進(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è)面。 LRU置換算法：這是本次設(shè)計(jì)的重點(diǎn) CLOCK置換算法：a,簡(jiǎn)單CLOCK置換算法；b,改進(jìn)型CLOCK算法。LRU算法是較好的一種算法， 而由于LRU在硬件上要求較多，在實(shí)際應(yīng)用中多采用 LRU的近似算

8、法。CLOCK算法就是用得較多的一種 LRU近似算法。 最少使用(LFU:Least Frequently Used置換算法：在采用該算法時(shí)，應(yīng)為在內(nèi)存中的每個(gè)頁(yè)面設(shè)置一 個(gè)移位寄存器骼來(lái)記錄該頁(yè)面被訪問(wèn)的頻率。該置換算法選擇在最近時(shí)期使用最少的頁(yè)面為淘汰頁(yè)。 頁(yè)面緩沖算法(PBA : Page Buffering Algorithm)、最近最久未使用置換算法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)

9、存后的使用情況進(jìn) 行決策的。由于無(wú)法預(yù)測(cè)各頁(yè)面將來(lái)的使用情況，只能利用最近的過(guò)去”作為 最近的將來(lái)”的近似，因此，LRU置換算法是選擇最近最久未使用的頁(yè)面予以淘汰。該算法賦予每個(gè)頁(yè)面一個(gè)訪問(wèn)字段，用來(lái)記錄一個(gè) 頁(yè)面自上次被訪問(wèn)以來(lái)所經(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)程訪問(wèn)，以及如何快速地知道哪一頁(yè)是最近最久未使用的頁(yè)面，須有以下 兩類(lèi)硬件之一的支持：1) 寄存器為了記錄某個(gè)進(jìn)程在內(nèi)存中各

10、頁(yè)的使用情況，須為每個(gè)在內(nèi)存中的頁(yè)面配置一個(gè)移位寄存器，可表示 為R=Rn-1Rn-2Rn-3R2R1R0當(dāng)進(jìn)程訪問(wè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訪問(wèn)情況。這里，把 8個(gè)內(nèi)存頁(yè)面的序號(hào)分別定為 1 ?8由圖可以看岀，第 7個(gè)內(nèi)存頁(yè)面的R值最小，當(dāng)發(fā)生缺頁(yè)時(shí)首先將它置換岀去。R實(shí)頁(yè)R7R6R5R4R3R2R1R0101010

11、0102101011003000001004011010115110101106001010117000001118011011012)?？衫靡粋€(gè)特殊的棧來(lái)保存當(dāng)前使用的各個(gè)頁(yè)面的頁(yè)面號(hào)。每當(dāng)進(jìn)程訪問(wèn)某頁(yè)面時(shí)，便將頁(yè)面的頁(yè)面 號(hào)從棧中移出，將它壓入棧頂。因此，棧頂始終是最新被訪問(wèn)頁(yè)面的編號(hào)民，而棧底則是最近最久未使用 的頁(yè)面的頁(yè)面號(hào)。（三）、程序設(shè)計(jì)流程圖（四）LRU算法實(shí)現(xiàn)。#include#include#define M 4#define N 17/*表格控制*/#define Myprintfprintf(|-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-|n)ty

12、pedef struct pageint num; /*記錄頁(yè)面號(hào)*/int time; /*記錄調(diào)入內(nèi)存時(shí)間*/Page;/*頁(yè)面邏輯結(jié)構(gòu)，結(jié)構(gòu)為方便算法實(shí)現(xiàn)設(shè)計(jì)*/Page bM;/*內(nèi)存單元數(shù)*/int cMN;/*暫保存內(nèi)存當(dāng)前的狀態(tài)：緩沖區(qū) */int queue100;/*記錄調(diào)入隊(duì)列*/int K;/*調(diào)入隊(duì)列計(jì)數(shù)變量*/*初始化內(nèi)存單元、緩沖區(qū)*/void Init（Page *b,int cMN）int i,j;for(i=0;iN;i+) bi.num=-1;+ bi.time=N-i-1; for(i=0;iM;i+) for(j=0;jN;j+) cij=-1;/* 取

13、得在內(nèi)存中停留最久的頁(yè)面 ,默認(rèn)狀態(tài)下為最早調(diào)入的頁(yè)面 */ int GetMax(Page *b)int i;int max=-1;int tag=0; for(i=0;imax) max=bi.time; tag=i;return tag;/* 判斷頁(yè)面是否已在內(nèi)存中 */int Equation(int fold,Page *b)int i; for(i=0;i=0)bval.time=0;for(i=0;iM;i+)if (i!=val) bi.time+;elsequeue+K=fold;/* 記錄調(diào)入頁(yè)面 */ val=GetMax(b);bval.num=fold;bval.ti

14、me=0;for(i=0;iM;i+)if (i!=val) bi.time+;/*主程序 */void main()int aN=1,0,1,0,2,4,1,0,0,8,7,5,4,3,2,3,4;int i,j;start: K=-1;Init(b, c);for(i=0;iN;i+)Lru(ai,b);c0i=ai;/* 記錄當(dāng)前的內(nèi)存單元中的頁(yè)面 */ for(j=0;jM;j+)cji=bj.num;/* 結(jié)果輸出 */printf( 內(nèi)存狀態(tài)為： n);Myprintf;for(j=0;jN;j+)printf(|%2d ,aj);printf(|n);Myprintf;for(i

15、=0;iM;i+) for(j=0;jN;j+)if(cij=-1)printf(|%2c ,32);else printf(|%2d ,cij); printf(|n);Myprintf;printf(n 調(diào)入隊(duì)列為 :);for(i=0;iK+1;i+) printf(%3d,queuei);printf(n 缺頁(yè)次數(shù)為： %6dn 缺頁(yè)率： %16.6f,K+1,(float)(K+1)/N); printf(nAre you continuing!ty?);if(getche()=y)goto start;四、測(cè)試與評(píng)價(jià)1、程序運(yùn)行結(jié)果輸出內(nèi)存狀態(tài)為：| 1 | 0 | 1 | 0 |

16、 2 | 4 | 1 | 0 | 0 | 8 | 7 | 5 | 4 | 3 | 2 | 3 | 4 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 5 | 5 | 5 | 5 | 5 | 5 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 4 | 4 | 4 | 4 | 4 | | | | | 2 | 2 | 2 | 2 | 2 | 8 | 8 | 8 | 8 | 3 | 3 | 3 | 3 | | | | | | 4 | 4 | 4 | 4 | 4 | 7 | 7 | 7 | 7 | 2 | 2 | 2 |調(diào)入隊(duì)列為 :1 0 2 4 8 7 5 4 3 2缺頁(yè)次數(shù)為：10缺頁(yè)率：0.588235Are you continuing! y?2、程序執(zhí)行是穩(wěn)定的，高效的。在 LRU 算法中，要找出最近最久未使用的頁(yè)面的話，就必須設(shè)置有關(guān) 的訪問(wèn)記錄項(xiàng)，且每一次訪問(wèn)這些記錄