【正文】 { 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。}運行結(jié)果界面：實驗五 頁面置換算法模擬【開發(fā)語言及實現(xiàn)平臺或?qū)嶒灜h(huán)境】C++/CMicrosoft Visual Studio 【實驗?zāi)康摹浚?）進(jìn)一步理解利用頁面調(diào)度算法實現(xiàn)虛擬內(nèi)存的問題；（2）通過模擬實現(xiàn)請求頁式存儲管理的幾種基本頁面置換算法，了解虛擬存儲技術(shù)的特點。（3）掌握虛擬存儲請求頁式存儲管理中幾種基本頁面置換算法的基本思想和實現(xiàn)過程，并比較它們的效率。（4）了解頁面大小和內(nèi)存實際容量對命中率的影響?！緦嶒瀮?nèi)容】（1）在了解和掌握頁面調(diào)度算法的基礎(chǔ)上，編制先進(jìn)先出的算法（FIFO）、最近最少使用算法（LRU）、最佳淘汰算法（OPT）等各種頁面置換算法。將調(diào)試結(jié)果顯示在計算機(jī)屏幕上，再檢測和筆算的一致性。（2）理解和掌握命中率的問題（3）會使用某種編程語言?！緦嶒炘怼糠猪摯鎯芾韺⒁粋€進(jìn)程的邏輯地址空間分成若干大小相等的片，稱為頁面或頁。在進(jìn)程運行過程中，若其所要訪問的頁面不在內(nèi)存而需把它們調(diào)入內(nèi)存，但內(nèi)存已無空閑空間時，為了保證該進(jì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)出。一、最佳置換算法OPT(Optimal)它是由Belady于1966年提出的一種理論上的算法。其所選擇的被淘汰頁面，將是以后永不使用的或許是在最長(未來)時間內(nèi)不再被訪問的頁面。采用最佳置換算法，通常可保證獲得最低的缺頁率。但由于人目前還無法預(yù)知一個進(jìn)程在內(nèi)存的若干個頁面中，哪一個頁面是未來最長時間內(nèi)不再被訪問的，因而該算法是無法實現(xiàn)的，便可以利用此算法來評價其它算法。 二、先進(jìn)先出(FIFO)頁面置換算法 這是最早出現(xiàn)的置換算法。該算法總是淘汰最先進(jìn)入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時間最久的頁面予以淘汰。該算法實現(xiàn)簡單只需把一個進(jìn)程已調(diào)入內(nèi)存的頁面，按先后次序鏈接成一個隊列，并設(shè)置一個指針，稱為替換指針，使它總是指向最老的頁面。三、最近最久未使用置換算法 LRU(Least Recently Used)置換算法的描述FIFO置換算法性能之所以較差，是因為它所依據(jù)的條件是各個頁面調(diào)入內(nèi)存的時間，而頁面調(diào)入的先后并不能反映頁面的使用情況。最近最久未使用（LRU）置換算法，是根據(jù)頁面調(diào)入內(nèi)存后的使用情況進(jìn)行決策的。由于無法預(yù)測各頁面將來的使用情況，只能利用“最近的過去”作為“最近的將來”的近似，因此，LRU置換算法是選擇最近最久未使用的頁面予以淘汰。該算法賦予每個頁面一個訪問字段，用來記錄一個頁面自上次被訪問以來所經(jīng)歷的時間t,，當(dāng)須淘汰一個頁面時，選擇現(xiàn)有頁面中其t值最大的，即最近最久未使用的頁面予以淘汰。 LRU置換算法的硬件支持 　 LRU置換算法雖然是一種比較好的算法，但要求系統(tǒng)有較多的支持硬件。為了了解一個進(jìn)程在內(nèi)存中的各個頁面各有多少時間未被進(jìn)程訪問，以及如何快速地知道哪一頁是最近最久未使用的頁面，須有以下兩類硬件之一的支持： 1）寄存器 為了記錄某個進(jìn)程在內(nèi)存中各頁的使用情況，須為每個在內(nèi)存中的頁面配置一個移位寄存器，可表示為 R=Rn1Rn2Rn3……R2R1R0 當(dāng)進(jìn)程訪問某物理塊時，要將相應(yīng)寄存器的Rn1位置成1。此時，定時信號將每隔一定時間(例如100ms)將寄存器右移一位。如果我們把n位寄存器的數(shù)看作是一個整數(shù)，那么具有最小數(shù)值的寄存器所對應(yīng)的頁面，就是最近最久未使用的頁面。如圖1示出了某進(jìn)程在內(nèi)存中具有8個頁面，為每個內(nèi)存頁面配置一個8位寄存器時的LRU訪問情況。這里，把8個內(nèi)存頁面的序號分別定為1??8。由圖可以看出，第7個內(nèi)存頁面的R值最小，當(dāng)發(fā)生缺頁時首先將它置換出去。 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)棧 可利用一個特殊的棧來保存當(dāng)前使用的各個頁面的頁面號。每當(dāng)進(jìn)程訪問某頁面時，便將頁面的頁面號從棧中移出，將它壓入棧頂。因此，棧頂始終是最新被訪問頁面的編號民，而棧底則是最近最久未使用的頁面的頁面號?！緦嶒灢襟E】 參考實驗步驟如下：（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。 /*記錄頁面號*/ int time。 /*記錄調(diào)入內(nèi)存時間*/ }Page。 /* 頁面邏輯結(jié)構(gòu)，結(jié)構(gòu)為方便算法實現(xiàn)設(shè)計*/ Page b[M]。 /*內(nèi)存單元數(shù)*/ int c[M][N]。 /*暫保存內(nèi)存當(dāng)前的狀態(tài)：緩沖區(qū)*/ int queue[100]。 /*記錄調(diào)入隊列*/ int K。 /*調(diào)入隊列計數(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)入隊列為:)。 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）為什么在實際的系統(tǒng)中不用LRU置換算法，而用它的近似算法？找出最久未被訪問的塊最簡單的方法是逐個查找塊的最近訪問時刻，然后取出時間最久的，時間復(fù)雜度為O（N）,顯然當(dāng)N很大，換句話說，內(nèi)存中緩存塊的數(shù)量很多時，查找的效率很低（2）OPT算法為什么難以實現(xiàn)？OPT算法本身實現(xiàn)就不現(xiàn)實，它只是一種理想算法，它是假設(shè)將來主存中的頁面調(diào)度情況與過去一段時間內(nèi)主存中的調(diào)度情況是相同的，這種假設(shè)并不總是正確的，因此在執(zhí)行過程中會出現(xiàn)錯誤。（3）在編程中遇到了哪些問題？你是如何解決的？ 遇到了一些錯誤，采用了單步調(diào)試，最后修改了錯誤。39