實(shí)驗(yàn)5存儲(chǔ)管理

1、實(shí)驗(yàn)5 存儲(chǔ)管理【開(kāi)發(fā)語(yǔ)言及實(shí)現(xiàn)平臺(tái)或?qū)嶒?yàn)環(huán)境】C+/C#Microsoft Visual Studio 6.0/ Microsoft Visual Studio .NET 2003【實(shí)驗(yàn)?zāi)康摹浚?）了解內(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)要求】（1）采用頁(yè)式分配存儲(chǔ)方案，通過(guò)分別計(jì)算不同算法的命中率來(lái)比較算法的優(yōu)劣，同時(shí)也考慮頁(yè)面大小及內(nèi)存實(shí)際容量對(duì)命中率的影響；（2）實(shí)現(xiàn)OPT 算法 (最優(yōu)置換算法) 、LRU 算法 (Least Recently) 、

2、 FIFO 算法 (First IN First Out)的模擬；（3）會(huì)使用某種編程語(yǔ)言。【實(shí)驗(yàn)原理】分頁(yè)存儲(chǔ)管理將一個(gè)進(jìn)程的邏輯地址空間分成若干大小相等的片，稱(chēng)為頁(yè)面或頁(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è)程序或數(shù)據(jù)，送磁盤(pán)的對(duì)換區(qū)中。但應(yīng)將哪 個(gè)頁(yè)面調(diào)出，須根據(jù)一定的算法來(lái)確定。通常，把選擇換出頁(yè)面的算法稱(chēng)為頁(yè)面置換算法(Page_Replacement Algorithms)。 一個(gè)好的頁(yè)面置換算法，應(yīng)具有較低的頁(yè)面更換頻率。從理論上講，應(yīng)將那些以后不再會(huì)訪問(wèn)的頁(yè)面換出，或?qū)⒛切┰谳^長(zhǎng)

3、時(shí)間內(nèi)不會(huì)再訪問(wèn)的頁(yè)面調(diào)出。一、最佳置換算法OPT(Optimal)它是由Belady于1966年提出的一種理論上的算法。其所選擇的被淘汰頁(yè)面，將是以后永不使用的或許是在最長(zhǎng)(未來(lái))時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面。采用最佳置換算法，通?？杀ＷC獲得最低的缺頁(yè)率。但由于人目前還無(wú)法預(yù)知一個(gè)進(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è)面，按先后次序鏈接

4、成一個(gè)隊(duì)列，并設(shè)置一個(gè)指針，稱(chēng)為替換指針，使它總是指向最老的頁(yè)面。三、最近最久未使用置換算法 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)行決策的。由于無(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í)，選擇

5、現(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)存中各頁(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ù)，那

6、么具有最小數(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)分別定為18。由圖可以看出，第3個(gè)內(nèi)存頁(yè)面的R值最小，當(dāng)發(fā)生缺頁(yè)時(shí)首先將它置換出去。 R7 R6 R5 R4 R3 R2 R1 R0 1 0 1 0 1 0 0 1 0 2 1 0 1 0 1 1 0 0 3 0 0 0 0 0 1 0 0 4 0 1 1 0 1 0 1 1 5 1 1 0 1 0 1 1 0 6 0 0 1 0 1 0 1 1 7 0 0 0 0 0 1 1 1 8 0 1 1 0 1 1 0 1

7、 2)棧 可利用一個(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)。假定現(xiàn)有一進(jìn)程所訪問(wèn)的頁(yè)面的頁(yè)面號(hào)序列為：4,7,0,7,1,0,1,2,1,2,6隨著進(jìn)程的訪問(wèn)，棧中頁(yè)面號(hào)的變化情況如下圖所示。在訪問(wèn)頁(yè)面6是發(fā)生了缺頁(yè)，此時(shí)頁(yè)面4是最近最久未被訪問(wèn)的頁(yè)，應(yīng)將它置換出去。4707101212621261011212077100001770077777044444444447【實(shí)驗(yàn)步驟】參考實(shí)驗(yàn)步驟如下：（1）現(xiàn)定義數(shù)據(jù)結(jié)構(gòu)和全局變量。#include&l

8、t;stdio.h> #include<conio.h> #define M 4 #define N 17 #define Myprintf printf("|-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-|n")/*表格控制*/ typedef struct page int 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;/

9、*記錄調(diào)入隊(duì)列*/ int K;/*調(diào)入隊(duì)列計(jì)數(shù)變量*/   （2）初始化內(nèi)存單元、緩沖區(qū) void Init(Page *b,int cMN) int i,j; for(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; （3）取得在內(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;i<M;i+) if(bi.time>max) m

10、ax=bi.time; tag=i; return tag; （4）判斷頁(yè)面是否已在內(nèi)存中*/ intEquation(int fold,Page *b) int i; for(i=0;i<M;i+) if (fold= =bi.num) return i; return -1; （5）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+; else queue+K=f

11、old;/*記錄調(diào)入頁(yè)面*/ val=GetMax(b); bval.num=fold; bval.time=0; for(i=0;i<M;i+) if (i!=val) bi.time+; （6）主程序 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;i<N;i+) Lru(ai,b); c0i=ai; /*記錄當(dāng)前的內(nèi)存單元中的頁(yè)面*/ for(j=0;j<M;j+) cji=bj.num; /*結(jié)果輸出*/ pri

12、ntf("內(nèi)存狀態(tài)為：n"); Myprintf; for(j=0;j<N;j+) printf("|%2d ",aj); printf("|n"); Myprintf; for(i=0;i<M;i+) for(j=0;j<N;j+) if(cij=-1) printf("|%2c ",32); else printf("|%2d ",cij); printf("|n"); Myprintf; printf("n調(diào)入隊(duì)列為:"); for(i=0;