1、實(shí)驗(yàn)報(bào)告三 虛擬內(nèi)存頁面置換算法班級 學(xué)號 姓名 一、 實(shí)驗(yàn)?zāi)康耐ㄟ^這次實(shí)驗(yàn)，加深對虛擬內(nèi)存頁面置換概念的理解，進(jìn)一步掌握先進(jìn)先出FIFO，最佳置換OPI和最近最久未使用LRU頁面置換算法的實(shí)現(xiàn)方法。二、實(shí)驗(yàn)的開發(fā)環(huán)境1. 硬件設(shè)備：PC機(jī)一臺2. 軟件環(huán)境：安裝Windows操作系統(tǒng)或者Linux操作系統(tǒng)，并安裝相關(guān)的程序開發(fā)環(huán)境，如C C+Java 等編程語言環(huán)境。三、實(shí)驗(yàn)設(shè)計(jì)思路 問題描述：設(shè)計(jì)程序模擬先進(jìn)先出FIFO，最佳置換OPI和最近最久未使用LRU頁面置換算法的工作過程。假設(shè)內(nèi)存中分配給每個(gè)進(jìn)程的最小物理塊數(shù)為m，在進(jìn)程運(yùn)行過程中要訪問的頁面?zhèn)€數(shù)為n，頁面訪問序列為P1, ,Pn

2、，分別利用不同的頁面置換算法調(diào)度進(jìn)程的頁面訪問序列，給出頁面訪問序列的置換過程，計(jì)算每種算法缺頁次數(shù)和缺頁率。四、實(shí)驗(yàn)內(nèi)容及結(jié)果程序要求如下：1）利用先進(jìn)先出FIFO，最佳置換OPI和最近最久未使用LRU三種頁面置換算法模擬頁面訪問過程。2）模擬三種算法的頁面置換過程，給出每個(gè)頁面訪問時(shí)的內(nèi)存分配情況。3）輸入：最小物理塊數(shù)m，頁面?zhèn)€數(shù)n，頁面訪問序列P1, ,Pn，算法選擇1-FIFO，2-OPI，3-LRU。4）輸出：每種算法的缺頁次數(shù)和缺頁率。程序源碼如下：#include "iostream.h"const int DataMax=100;const int Blo

3、ckNum = 10;int DataShowBlockNumDataMax; / 用于存儲要顯示的數(shù)組bool DataShowEnableBlockNumDataMax; / 用于存儲數(shù)組中的數(shù)據(jù)是否需要顯示/int DataDataMax=4,3,2,1,4,3,5,4,3,2,1,5,6,2,3,7,1,2,6,1; / 測試數(shù)據(jù)/int N = 20; / 輸入頁面?zhèn)€數(shù)int DataDataMax; / 保存數(shù)據(jù)int BlockBlockNum; / 物理塊int countBlockNum; / 計(jì)數(shù)器int N ; / 頁面?zhèn)€數(shù)int M;/最小物理塊數(shù)int ChangeT

4、imes;void DataInput(); / 輸入數(shù)據(jù)的函數(shù)void DataOutput();void FIFO(); / FIFO 函數(shù)void Optimal(); / Optimal函數(shù)void LRU(); / LRU函數(shù)1 / 8/*int main(int argc, char* argv) DataInput();/ DataInput(); / FIFO(); / Optimal(); / LRU(); / return 0; int menu; while(true) cout<<endl; cout<<"* 菜單選擇 *"&

5、lt;<endl; cout<<"*"<<endl; cout<<"* 1-FIFO *"<<endl; cout<<"* 2-Optimal *"<<endl; cout<<"* 3-LRU *"<<endl; cout<<"* 0-EXIT *"<<endl; cout<<"*"<<endl; cin>>menu

6、; switch(menu) case 1: FIFO();break; case 2: Optimal();break; case 3: LRU();break; default: break; if(menu!=1&&menu!=2&&menu!=3) break; /*/void DataInput() cout<<"請輸入最小物理塊數(shù)：" cin>>M; while(M > BlockNum) / 大于數(shù)據(jù)個(gè)數(shù) cout<<"物理塊數(shù)超過預(yù)定值，請重新輸入：" cin>

7、;>M; cout<<"請輸入頁面的個(gè)數(shù)：" cin>>N; while(N > DataMax) / 大于數(shù)據(jù)個(gè)數(shù) cout<<"頁面?zhèn)€數(shù)超過預(yù)定值，請重新輸入：" cin>>N; cout<<"請輸入頁面訪問序列："<<endl; for(int i=0;i<N;i+) cin>>Datai;void DataOutput() int i,j; for(i=0;i<N;i+) / 對所有數(shù)據(jù)操作 cout<<Da

8、tai<<" " cout<<endl; for(j=0;j<M;j+) cout<<" " for(i=0;i<N;i+) / 對所有數(shù)據(jù)操作 if( DataShowEnableji ) cout<<DataShowji<<" " else cout<<" " cout<<endl; cout<<"缺頁次數(shù): "<<ChangeTimes<<endl; cout

9、<<"缺頁率: "<<ChangeTimes*100/N<<"%"<<endl;void FIFO() int i,j; bool find; int point; int temp; / 臨時(shí)變量 ChangeTimes = 0; for(j=0;j<M;j+) for(i=0;i<N;i+) DataShowEnableji = false; / 初始化為false，表示沒有要顯示的數(shù)據(jù) for(i=0;i<M;i+) counti = 0; / 大于等于BlockNum，表示塊中沒有

10、數(shù)據(jù)，或需被替換掉 / 所以經(jīng)這樣初始化（3 2 1），每次替換>=3的塊，替換后計(jì)數(shù)值置1， / 同時(shí)其它的塊計(jì)數(shù)值加1 ，成了（1 3 2 ），見下面先進(jìn)先出程序段 for(i=0;i<N;i+) / 對有所數(shù)據(jù)操作 / 增加count for(j=0;j<M;j+) countj+; find = false; / 表示塊中有沒有該數(shù)據(jù) for(j=0;j<M;j+) if( Blockj = Datai ) find = true; if( find ) continue; / 塊中有該數(shù)據(jù)，判斷下一個(gè)數(shù)據(jù) / 塊中沒有該數(shù)據(jù) ChangeTimes+; / 缺

11、頁次數(shù)+ if( (i+1) > M ) / 因?yàn)閕是從0開始記，而M指的是個(gè)數(shù)，從1開始，所以i+1 /獲得要替換的塊指針 temp = 0; for(j=0;j<M;j+) if( temp < countj ) temp = countj; point = j; / 獲得離的最遠(yuǎn)的指針 else point = i; / 替換 Blockpoint = Datai; countpoint = 0; / 更新計(jì)數(shù)值 / 保存要顯示的數(shù)據(jù) for(j=0;j<M;j+) DataShowji = Blockj; DataShowEnablei<M?(j<=

12、i?j:i):ji = true; / 設(shè)置顯示數(shù)據(jù) / 輸出信息 cout<< endl; cout<<"FIFO => "<< endl; DataOutput();void Optimal() int i,j,k; bool find; int point; int temp; / 臨時(shí)變量，比較離的最遠(yuǎn)的時(shí)候用 ChangeTimes = 0; for(j=0;j<M;j+) for(i=0;i<N;i+) DataShowEnableji = false; / 初始化為false，表示沒有要顯示的數(shù)據(jù)/ for

13、(i=0;i<M;i+)/ / counti = 0 ; / / for(i=0;i<N;i+) / 對有所數(shù)據(jù)操作 find = false; / 表示塊中有沒有該數(shù)據(jù) for(j=0;j<M;j+) if( Blockj = Datai ) find = true; if( find ) continue; / 塊中有該數(shù)據(jù)，判斷下一個(gè)數(shù)據(jù) / 塊中沒有該數(shù)據(jù)，最優(yōu)算法 ChangeTimes+; / 缺頁次數(shù)+ for(j=0;j<M;j+) / 找到下一個(gè)值的位置 find = false; for( k =i;k<N;k+) if( Blockj = D

14、atak ) find = true; countj = k; break; if( !find ) countj = N; if( (i+1) > M ) / 因?yàn)閕是從0開始記，而BlockNum指的是個(gè)數(shù)，從1開始，所以i+1 /獲得要替換的塊指針 temp = 0; for(j=0;j<M;j+) if( temp < countj ) temp = countj; point = j; / 獲得離的最遠(yuǎn)的指針 else point = i; / 替換 Blockpoint = Datai; / 保存要顯示的數(shù)據(jù) for(j=0;j<M;j+) DataShow

15、ji = Blockj; DataShowEnablei<M?(j<=i?j:i):ji = true; / 設(shè)置顯示數(shù)據(jù) / 輸出信息 cout<< endl; cout<<"Optimal => "<< endl; DataOutput();void LRU() int i,j; bool find; int point; int temp; / 臨時(shí)變量 ChangeTimes = 0; for(j=0;j<M;j+) for(i=0;i<N;i+) DataShowEnableji = false;

16、/ 初始化為false，表示沒有要顯示的數(shù)據(jù) for(i=0;i<M;i+) counti = 0 ; for(i=0;i<N;i+) / 對有所數(shù)據(jù)操作 / 增加count for(j=0;j<M;j+) countj+; find = false; / 表示塊中有沒有該數(shù)據(jù) for(j=0;j<M;j+) if( Blockj = Datai ) countj = 0; find = true; if( find ) continue; / 塊中有該數(shù)據(jù)，判斷下一個(gè)數(shù)據(jù) / 塊中沒有該數(shù)據(jù) ChangeTimes+; / 缺頁次數(shù)+ if( (i+1) > M

17、 ) / 因?yàn)閕是從0開始記，而BlockNum指的是個(gè)數(shù)，從1開始，所以i+1 /獲得要替換的塊指針 temp = 0; for(j=0;j<M;j+) if( temp < countj ) temp = countj; point = j; / 獲得離的最遠(yuǎn)的指針 else point = i; / 替換 Blockpoint = Datai; countpoint = 0; / 保存要顯示的數(shù)據(jù) for(j=0;j<M;j+) DataShowji = Blockj; DataShowEnablei<M?(j<=i?j:i):ji = true; / 設(shè)置顯示數(shù)據(jù) / 輸出信息 cout<< endl; cout<<"LRU => "<< endl; DataOutput();五、實(shí)驗(yàn)效果六、實(shí)驗(yàn)總結(jié)通過這次實(shí)驗(yàn)我對先進(jìn)先出FIFO，最佳置換OPI和最近最久未使用LRU頁面置換算法的實(shí)現(xiàn)方法。有了更多的了解。在編程過程中我也通過查閱書籍和復(fù)習(xí)以前