【正文】 { i=i。 break。 } if (i==5) cout\n您輸入的進(jìn)程名有誤！請重新輸入。 else f=false。 } cout請輸入申請各類資源數(shù)量：\n。 for(j=0。jM。j++) cinRequest[j]。 for(j=0。jM。j++) { check[j]=Request[j]+iAllocation[i][j]。 } for(j=0。jM。j++) { if((iMax[i][j]check[j])0) { cout\n資源申請超過最大需求量?。?！\n。 return false。 } } for(j=0。jM。j++) { if((iAvailable[j]Request[j])0) { cout\n不能滿足進(jìn)程?。。n。 return false。 } } for(j=0。jM。j++) { iAvailable[j]=Request[j]。 iAllocation[i][j]+=Request[j]。 iNeed[i][j]=Request[j]。 } safety(iAllocation,iNeed,iAvailable,cName)。 return true。}運(yùn)行結(jié)果界面：實(shí)驗(yàn)五 頁面置換算法模擬【開發(fā)語言及實(shí)現(xiàn)平臺(tái)或?qū)嶒?yàn)環(huán)境】C++/CMicrosoft Visual Studio 【實(shí)驗(yàn)?zāi)康摹浚?）進(jìn)一步理解利用頁面調(diào)度算法實(shí)現(xiàn)虛擬內(nèi)存的問題；（2）通過模擬實(shí)現(xiàn)請求頁式存儲(chǔ)管理的幾種基本頁面置換算法，了解虛擬存儲(chǔ)技術(shù)的特點(diǎn)。（3）掌握虛擬存儲(chǔ)請求頁式存儲(chǔ)管理中幾種基本頁面置換算法的基本思想和實(shí)現(xiàn)過程，并比較它們的效率。（4）了解頁面大小和內(nèi)存實(shí)際容量對(duì)命中率的影響?！緦?shí)驗(yàn)內(nèi)容】（1）在了解和掌握頁面調(diào)度算法的基礎(chǔ)上，編制先進(jìn)先出的算法（FIFO）、最近最少使用算法（LRU）、最佳淘汰算法（OPT）等各種頁面置換算法。將調(diào)試結(jié)果顯示在計(jì)算機(jī)屏幕上，再檢測和筆算的一致性。（2）理解和掌握命中率的問題（3）會(huì)使用某種編程語言?！緦?shí)驗(yàn)原理】分頁存儲(chǔ)管理將一個(gè)進(jìn)程的邏輯地址空間分成若干大小相等的片，稱為頁面或頁。在進(jìn)程運(yùn)行過程中，若其所要訪問的頁面不在內(nèi)存而需把它們調(diào)入內(nèi)存，但內(nèi)存已無空閑空間時(shí)，為了保證該進(jìn)程能正常運(yùn)行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁程序或數(shù)據(jù)，送磁盤的對(duì)換區(qū)中。但應(yīng)將哪 個(gè)頁面調(diào)出，須根據(jù)一定的算法來確定。通常，把選擇換出頁面的算法稱為頁面置換算法(Page_Replacement Algorithms)。 一個(gè)好的頁面置換算法，應(yīng)具有較低的頁面更換頻率。從理論上講，應(yīng)將那些以后不再會(huì)訪問的頁面換出，或?qū)⒛切┰谳^長時(shí)間內(nèi)不會(huì)再訪問的頁面調(diào)出。一、最佳置換算法OPT(Optimal)它是由Belady于1966年提出的一種理論上的算法。其所選擇的被淘汰頁面，將是以后永不使用的或許是在最長(未來)時(shí)間內(nèi)不再被訪問的頁面。采用最佳置換算法，通常可保證獲得最低的缺頁率。但由于人目前還無法預(yù)知一個(gè)進(jìn)程在內(nèi)存的若干個(gè)頁面中，哪一個(gè)頁面是未來最長時(shí)間內(nèi)不再被訪問的，因而該算法是無法實(shí)現(xiàn)的，便可以利用此算法來評(píng)價(jià)其它算法。 二、先進(jìn)先出(FIFO)頁面置換算法 這是最早出現(xiàn)的置換算法。該算法總是淘汰最先進(jìn)入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時(shí)間最久的頁面予以淘汰。該算法實(shí)現(xiàn)簡單只需把一個(gè)進(jìn)程已調(diào)入內(nèi)存的頁面，按先后次序鏈接成一個(gè)隊(duì)列，并設(shè)置一個(gè)指針，稱為替換指針，使它總是指向最老的頁面。三、最近最久未使用置換算法 LRU(Least Recently Used)置換算法的描述FIFO置換算法性能之所以較差，是因?yàn)樗罁?jù)的條件是各個(gè)頁面調(diào)入內(nèi)存的時(shí)間，而頁面調(diào)入的先后并不能反映頁面的使用情況。最近最久未使用（LRU）置換算法，是根據(jù)頁面調(diào)入內(nèi)存后的使用情況進(jìn)行決策的。由于無法預(yù)測各頁面將來的使用情況，只能利用“最近的過去”作為“最近的將來”的近似，因此，LRU置換算法是選擇最近最久未使用的頁面予以淘汰。該算法賦予每個(gè)頁面一個(gè)訪問字段，用來記錄一個(gè)頁面自上次被訪問以來所經(jīng)歷的時(shí)間t,，當(dāng)須淘汰一個(gè)頁面時(shí)，選擇現(xiàn)有頁面中其t值最大的，即最近最久未使用的頁面予以淘汰。 LRU置換算法的硬件支持 　 LRU置換算法雖然是一種比較好的算法，但要求系統(tǒng)有較多的支持硬件。為了了解一個(gè)進(jìn)程在內(nèi)存中的各個(gè)頁面各有多少時(shí)間未被進(jìn)程訪問，以及如何快速地知道哪一頁是最近最久未使用的頁面，須有以下兩類硬件之一的支持： 1）寄存器 為了記錄某個(gè)進(jìn)程在內(nèi)存中各頁的使用情況，須為每個(gè)在內(nèi)存中的頁面配置一個(gè)移位寄存器，可表示為 R=Rn1Rn2Rn3……R2R1R0 當(dāng)進(jìn)程訪問某物理塊時(shí)，要將相應(yīng)寄存器的Rn1位置成1。此時(shí)，定時(shí)信號(hào)將每隔一定時(shí)間(例如100ms)將寄存器右移一位。如果我們把n位寄存器的數(shù)看作是一個(gè)整數(shù)，那么具有最小數(shù)值的寄存器所對(duì)應(yīng)的頁面，就是最近最久未使用的頁面。如圖1示出了某進(jìn)程在內(nèi)存中具有8個(gè)頁面，為每個(gè)內(nèi)存頁面配置一個(gè)8位寄存器時(shí)的LRU訪問情況。這里，把8個(gè)內(nèi)存頁面的序號(hào)分別定為1??8。由圖可以看出，第7個(gè)內(nèi)存頁面的R值最小，當(dāng)發(fā)生缺頁時(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 2)棧 可利用一個(gè)特殊的棧來保存當(dāng)前使用的各個(gè)頁面的頁面號(hào)。每當(dāng)進(jìn)程訪問某頁面時(shí)，便將頁面的頁面號(hào)從棧中移出，將它壓入棧頂。因此，棧頂始終是最新被訪問頁面的編號(hào)民，而棧底則是最近最久未使用的頁面的頁面號(hào)?！緦?shí)驗(yàn)步驟】 參考實(shí)驗(yàn)步驟如下：（1）現(xiàn)定義數(shù)據(jù)結(jié)構(gòu)和全局變量。include include define M 4 define N 17 define Myprintf printf(|++++++++++++++++|\n) /*表格控制*/ typedef struct page { int num。 /*記錄頁面號(hào)*/ int time。 /*記錄調(diào)入內(nèi)存時(shí)間*/ }Page。 /* 頁面邏輯結(jié)構(gòu)，結(jié)構(gòu)為方便算法實(shí)現(xiàn)設(shè)計(jì)*/ Page b[M]。 /*內(nèi)存單元數(shù)*/ int c[M][N]。 /*暫保存內(nèi)存當(dāng)前的狀態(tài)：緩沖區(qū)*/ int queue[100]。 /*記錄調(diào)入隊(duì)列*/ int K。 /*調(diào)入隊(duì)列計(jì)數(shù)變量*/ （2）初始化內(nèi)存單元、緩沖區(qū) void Init(Page *b,int c[M][N]) { int i,j。 for(i=0。iN。i++) { b[i].num=1。 b[i].time=Ni1。 } for(i=0。iM。i++) for(j=0。jN。j++) c[i][j]=1。 } （3）取得在內(nèi)存中停留最久的頁面,默認(rèn)狀態(tài)下為最早調(diào)入的頁面*/ int GetMax(Page *b) { int i。 int max=1。 int tag=0。 for(i=0。iM。i++) { if(b[i].timemax) { max=b[i].time。 tag=i。 } } return tag。 } （4）判斷頁面是否已在內(nèi)存中*/ int Equation(int fold,Page *b) { int i。 for(i=0。iM。i++) if (fold= =b[i].num) return i。 return 1。 }（5）LRU算法void Lru(int fold,Page *b) { int i。 int val。 val=Equation(fold,b)。 if (val=0) { b[val].time=0。 for(i=0。iM。i++) if (i!=val) b[i].time++。 } else { queue[++K]=fold。/*記錄調(diào)入頁面*/ val=GetMax(b)。 b[val].num=fold。 b[val].time=0。 for(i=0。iM。i++) if (i!=val) b[i].time++。 } }FIFO與OPT的算法描述省略。（6）主程序 void main() { int a[N]={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(a[i],b)。 c[0][i]=a[i]。 /*記錄當(dāng)前的內(nèi)存單元中的頁面*/ for(j=0。jM。j++) c[j][i]=b[j].num。 } /*結(jié)果輸出*/ printf(內(nèi)存狀態(tài)為：\n)。 Myprintf。 for(j=0。jN。j++) printf(|%2d ,a[j])。 printf(|\n)。 Myprintf。 for(i=0。iM。i++) { for(j=0。jN。j++) if(c[i][j]==1) printf(|%2c ,32)。 else printf(|%2d ,c[i][j])。 printf(|\n)。 } Myprintf。 printf(\n調(diào)入隊(duì)列為:)。 for(i=0。iK+1。i++) printf(%3d,queue[i])。 printf(\n缺頁次數(shù)為：%6d\n缺頁率：%,K+1,(float)(K+1)/N)。 printf(\nAre you continuing!\ty?)。 if(getche()==39。y39。) goto start。 }【思考題】（1）為什么在實(shí)際的系統(tǒng)中不用LRU置換算法，而用它的近似算法？找出最久未被訪問的塊最簡單的方法是逐個(gè)查找塊的最近訪問時(shí)刻，然后取出時(shí)間最久的，時(shí)間復(fù)雜度為O（N）,顯然當(dāng)N很大，換句話說，內(nèi)存中緩存塊的數(shù)量很多時(shí)，查找的效率很低（2）OPT算法為什么難以實(shí)現(xiàn)？OPT算法本身實(shí)現(xiàn)就不現(xiàn)實(shí)，它只是一種理想算法，它是假設(shè)將來主存中的頁面調(diào)度情況與過去一段時(shí)間內(nèi)主存中的調(diào)度情況是相同的，這種假設(shè)并不總是正確的，因此在執(zhí)行過程中會(huì)出現(xiàn)錯(cuò)誤。（3）在編程中遇到了哪些問題？你是如何解決的？ 遇到了一些錯(cuò)誤，采用了單步調(diào)試，最后修改了錯(cuò)誤。39