LRU頁面置換算法模擬

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

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

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

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

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

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

7、進程在內(nèi)存的若干個頁面中，哪一個頁面是未來最長時間內(nèi)不再被訪問的，因而該算法 是無法實現(xiàn)的，便可以利用此算法來評價其它算法。 先進先出 (FIFO) 頁面置換算法：這是最早出現(xiàn)的置換算法。該算法總是淘汰最先進入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時間最久的頁面予 以淘汰。該算法實現(xiàn)簡單只需把一個進程已調(diào)入內(nèi)存的頁面，按先后次序鏈接成一個隊列，并設(shè)置一個指 針，稱為替換指針，使它總是指向最老的頁面。 LRU置換算法：這是本次設(shè)計的重點 CLOCK置換算法：a,簡單CLOCK置換算法；b,改進型CLOCK算法。LRU算法是較好的一種算法， 而由于LRU在硬件上要求較多，在實際應(yīng)用中多采用 LRU的近似算

8、法。CLOCK算法就是用得較多的一種 LRU近似算法。 最少使用(LFU:Least Frequently Used置換算法：在采用該算法時，應(yīng)為在內(nèi)存中的每個頁面設(shè)置一 個移位寄存器骼來記錄該頁面被訪問的頻率。該置換算法選擇在最近時期使用最少的頁面為淘汰頁。 頁面緩沖算法(PBA : Page Buffering Algorithm)、最近最久未使用置換算法LRU(Least Recently Used)置換算法的描述FIFO置換算法性能之所以較差， 是因為它所依據(jù)的條件是各個頁面調(diào)入內(nèi)存的時間，而頁面調(diào)入的先后并不能反映頁面的使用情況。最近最久未使用( LRU )置換算法，是根據(jù)頁面調(diào)入內(nèi)

9、存后的使用情況進 行決策的。由于無法預(yù)測各頁面將來的使用情況，只能利用最近的過去”作為 最近的將來”的近似，因此，LRU置換算法是選擇最近最久未使用的頁面予以淘汰。該算法賦予每個頁面一個訪問字段，用來記錄一個 頁面自上次被訪問以來所經(jīng)歷的時間t,，當(dāng)須淘汰一個頁面時， 選擇現(xiàn)有頁面中其t值最大的，即最近最久未使用的頁面予以淘汰。2、LRU置換算法的硬件支持LRU置換算法雖然是一種比較好的算法，但要求系統(tǒng)有較多的支持硬件。為了了解一個進程在內(nèi)存中的各個頁面各有多少時間未被進程訪問，以及如何快速地知道哪一頁是最近最久未使用的頁面，須有以下 兩類硬件之一的支持：1) 寄存器為了記錄某個進程在內(nèi)存中各

10、頁的使用情況，須為每個在內(nèi)存中的頁面配置一個移位寄存器，可表示 為R=Rn-1Rn-2Rn-3R2R1R0當(dāng)進程訪問某物理塊時，要將相應(yīng)寄存器的 Rn-1位置成1。此時，定時 信號將每隔一定時間(例如100ms)將寄存器右移一位。如果我們把n位寄存器的數(shù)看作是一個整數(shù)，那么具 有最小數(shù)值的寄存器所對應(yīng)的頁面，就是最近最久未使用的頁面。如圖1示出了某進程在內(nèi)存中具有 8個頁面，為每個內(nèi)存頁面配置一個 8位寄存器時的LRU訪問情況。這里，把 8個內(nèi)存頁面的序號分別定為 1 ?8由圖可以看岀，第 7個內(nèi)存頁面的R值最小，當(dāng)發(fā)生缺頁時首先將它置換岀去。R實頁R7R6R5R4R3R2R1R0101010

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

12、pedef struct pageint num; /*記錄頁面號*/int time; /*記錄調(diào)入內(nèi)存時間*/Page;/*頁面邏輯結(jié)構(gòu)，結(jié)構(gòu)為方便算法實現(xiàn)設(shè)計*/Page bM;/*內(nèi)存單元數(shù)*/int cMN;/*暫保存內(nèi)存當(dāng)前的狀態(tài)：緩沖區(qū) */int queue100;/*記錄調(diào)入隊列*/int K;/*調(diào)入隊列計數(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)存中停留最久的頁面 ,默認(rèn)狀態(tài)下為最早調(diào)入的頁面 */ int GetMax(Page *b)int i;int max=-1;int tag=0; for(i=0;imax) max=bi.time; tag=i;return tag;/* 判斷頁面是否已在內(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)入頁面 */ 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)存單元中的頁面 */ 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)入隊列為 :);for(i=0;iK+1;i+) printf(%3d,queuei);printf(n 缺頁次數(shù)為： %6dn 缺頁率： %16.6f,K+1,(float)(K+1)/N); printf(nAre you continuing!ty?);if(getche()=y)goto start;四、測試與評價1、程序運行結(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)入隊列為 :1 0 2 4 8 7 5 4 3 2缺頁次數(shù)為：10缺頁率：0.588235Are you continuing! y?2、程序執(zhí)行是穩(wěn)定的，高效的。在 LRU 算法中，要找出最近最久未使用的頁面的話，就必須設(shè)置有關(guān) 的訪問記錄項，且每一次訪問這些記錄