lru頁面置換算法模擬最近最久未使用置換算法課程設(shè)計

1、文檔來源為:從網(wǎng)絡(luò)收集整理.word 版本可編輯.歡迎下載支持.LRU頁面置換算法模擬-最近最久未使用置換算法-課程設(shè)計LRU 頁面置換算法模擬 - 最近最久未使用置換算法| 課程設(shè)計 | 計算機(jī)數(shù)據(jù)庫課程設(shè)計一、設(shè)計目的1、用C語言實(shí)現(xiàn)最近最久未使用（LRU置換算法。2、了解內(nèi)存分頁管理策略3、掌握調(diào)頁策略4、掌握一般常用的調(diào)度算法5、選取調(diào)度算法中的典型算法，模擬實(shí)現(xiàn)二、設(shè)計任務(wù)在Window98/2000系統(tǒng)的TC2.0環(huán)境下運(yùn)行程序；通過從一般常用的調(diào)頁算法中選取典型算法LRU 了解頁面管理的相關(guān)細(xì)節(jié)，并用程序設(shè)計實(shí)現(xiàn)LRU三、設(shè)計內(nèi)容與步驟分頁存儲管理將一個進(jìn)程的邏輯地址空間分成若干

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

3、確定調(diào)入的頁，是一定會被訪問的，再加之請求調(diào)頁策略比較易于實(shí)現(xiàn)，故在目前的虛擬存儲器中，大多采用此策略。但這種策略每次僅調(diào)入一頁，故須花費(fèi)較大的系統(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)頁速度。為此，在進(jìn)程運(yùn)行前，便須將與該進(jìn)程有關(guān)的文件，從文件區(qū)拷

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

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

6、間時，為了保證該進(jìn)程能正常運(yù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)出。 常見置換算法 最佳置換算法(Optimal) ：它是由 Belady 于 1966年提出的一種理論上的算法。其所選擇的被淘汰頁面，將是以后永不使用的或許是在最長( 未來 ) 時間內(nèi)不再被訪問的頁面。采用最佳置換算法，通?？杀ＷC

7、獲得最低的缺頁率。但由于人目前還無法預(yù)知一個進(jìn)程在內(nèi)存的若干個頁面中，哪一個頁面是未來最長時間內(nèi)不再被訪問的，因而該算法是無法實(shí)現(xiàn)的，便可以利用此算法來評價其它算法。 先進(jìn)先出 (FIFO) 頁面置換算法： 這是最早出現(xiàn)的置換算法。該算法總是淘汰最先進(jìn)入內(nèi)存的頁面，即選擇在內(nèi) 存中駐留時間最久的頁面予以淘汰。該算法實(shí)現(xiàn)簡單只需把一個進(jìn)程已調(diào)入內(nèi) 存的頁面，按先后次序鏈接成一個隊(duì)列，并設(shè)置一個指針，稱為替換指針，使 它總是指向最老的頁面。 LRU 置換算法：這是本次設(shè)計的重點(diǎn)。 CLOCK置換算法：a,簡單CLOCIfi換算法；b,改進(jìn)型CLOC算法。LRU 算法是較好的一種算法，而由于 LRU

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

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

10、之一的支持：1) 寄存器5文檔來源為:從網(wǎng)絡(luò)收集整理.word 版本可編輯.歡迎下載支持.為了記錄某個進(jìn)程在內(nèi)存中各頁的使用情況，須為每個在內(nèi)存中的頁面 配置一個移位寄存器，可表示為R=Rn-1Rn-2Rn-3 R2R1R0當(dāng)進(jìn)程訪問某物理塊時，要將相應(yīng)寄存器 的Rn-1位置成1。此時，定時信號將每隔一定時間（例如100msX寄存器右移 一位。如果我們把n位寄存器的數(shù)看作是一個整數(shù)，那么具有最小數(shù)值的寄存 器所對應(yīng)的頁面，就是最近最久未使用的頁面。如圖 1示出了某進(jìn)程在內(nèi)存中 具有8個頁面，為每個內(nèi)存頁面配置一個 8位寄存器時的LRU訪問情況。這 里，把8個內(nèi)存頁面的序號分別定為1?8。由圖可

11、以看出，第7個內(nèi)存頁面的 R值最小，當(dāng)發(fā)生缺頁時首先將它置換出去。R 實(shí) 頁R7R6R5R4R3R2R1R0101010010210110110030000010040110101151 -10101106001010117000001118011011012)棧可利用一個特殊的棧來保存當(dāng)前使用的各個頁面的頁面號。每當(dāng)進(jìn)程訪 問某頁面時，便將頁面的頁面號從棧中移出，將它壓入棧頂。因此，棧頂始終 是最新被訪問頁面的編號民,而棧底則是最近最久未使用的頁面的頁面號。（三）、程序設(shè)計流程圖（四）LRU算法實(shí)現(xiàn)。#include<stdio.h>#include<conio.h>

12、#define M 4#define N 17#define Myprintf printf("|+|n")/*表 控制*/typedef struct pageint num; /*記錄頁面號*/int time; /*記錄調(diào)入內(nèi)存時間*/Page;/*頁面邏輯結(jié)構(gòu)，結(jié)構(gòu)為方便算法實(shí)現(xiàn)設(shè)計*/Page bM;/* 內(nèi)存單元數(shù)*/int cMN; /* 暫保存內(nèi)存當(dāng)前的狀態(tài)：緩沖區(qū)*/int queue100;/* 記錄調(diào)入隊(duì)列 */int K; /* 調(diào)入隊(duì)列計數(shù)變量*/* 初始化內(nèi)存單元、緩沖區(qū)*/void Init(Page *b,int cMN)int i,j;fo

13、r(i=0;i<N;i+)bi.num=-1;+bi.time=N-i-1;for(i=0;i<M;i+)for(j=0;j<N;j+)cij=-1;/* 取得在內(nèi)存中停留最久的頁面, 默認(rèn)狀態(tài)下為最早調(diào)入的頁面*/int GetMax(Page *b)int i;int max=-1;int tag=0;for(i=0;i<M;i+)if(bi.time>max)max=bi.time;tag=i;return tag;/* 判斷頁面是否已在內(nèi)存中 */int Equation(int fold,Page *b)int i;for(i=0;i<M;i+)i

14、f (fold=bi.num)return i;return -1;/*LRU 核心部分 */void Lru(int fold,Page *b) int i;int val;val=Equation(fold,b);if (val>=0)bval.time=0;for(i=0;i<M;i+)if (i!=val) bi.time+; elsequeue+K=fold;/*記錄調(diào)入頁面*/val=GetMax(b);bval.num=fold;bval.time=0;for(i=0;i<M;i+)if (i!=val) bi.time+;/* 主程序 */void main(

15、)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;i<N;i+)Lru(ai,b);c0i=ai;/* 記錄當(dāng)前的內(nèi)存單元中的頁面*/for(j=0;j<M;j+)cji=bj.num;/*結(jié)果輸出 */printf(" 內(nèi)存狀態(tài)為： n");Myprintf;for(j=0;j<N;j+)printf("|%2d ",aj);printf("|n");Myprintf;for(i=0;i<M;i+)

16、 for(j=0;j<N;j+)if(cij=-1)printf("|%2c ",32);elseprintf("|%2d ",cij);printf("|n");Myprintf;printf("n 調(diào)入隊(duì)列為 :");for(i=0;i<K+1;i+)printf("%3d",queuei);printf("n缺頁次數(shù)為：6dn缺頁率： %16.6f",K+1,(float)(K+1)/N);printf("nAre you continuing!t

17、y?");if(getche()='y')goto start;四、測試與評價1、程序運(yùn)行結(jié)果輸出內(nèi)存狀態(tài)為：|-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-| 1 | 0 | 1 | 0 | 2 | 4 | 1 | 0 | 0 | 8 | 7 | 5 | 4 | 3 | 2 | 3 | 4 |9文檔來源為:從網(wǎng)絡(luò)收集整理.word 版本可編輯.歡迎下載支持.|+| 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缺頁次數(shù)為：10缺頁率： 0.588235Are you continuing! y?2、程序執(zhí)行是穩(wěn)定的，高效的。在 LRU算法中，要找出最近最久未使用的頁面的