虛擬內(nèi)存頁面置換算法實驗報告

1、軟件學(xué)院上機實 驗報告課程名稱：操作系統(tǒng)原理實驗項目：虛擬內(nèi)存頁面置換算法實驗室：地獄018姓 名： 死神 學(xué) 號：專業(yè)班級： 實驗時間：2015/12/13實驗成績評閱教師實驗?zāi)康募耙笸ㄟ^這次實驗，加深對虛擬內(nèi)存頁面置換概念的理解， 進一步掌握先進先出FIFO 最佳置換OPI和最近最久未使用LRU頁面置換算法的實現(xiàn)方法。結(jié)合 Linux的內(nèi)層的分 析方法查看內(nèi)存的分配過程及l(fā)inux kernel的內(nèi)存管理機制二、實驗性質(zhì)設(shè)計性三、實驗學(xué)時4學(xué)時四、實驗環(huán)境實驗環(huán)境1.實驗環(huán)境：C與C+®序設(shè)計學(xué)習(xí)與實驗系統(tǒng)2.知識準(zhǔn)備：(1)使用Linux的基本命令；(2) 了解Linux v

2、mstat、free、top等命令查看linux系統(tǒng)的內(nèi)存分配 情況；(3)掌握虛擬內(nèi)存頁面置換算法 FIFO等基本算法理論。五、實驗內(nèi)容及步驟假設(shè)有n個進程分別在 T1,，Tn時刻到達系統(tǒng)，它們需要的服務(wù)時間分別為 S1,Sn=分別采用先來先服務(wù)FCF辭口短作業(yè)優(yōu)先SJF51程調(diào)度算法進行調(diào)度，計算每 個進程的完成時間、周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間，并且統(tǒng)計n個進程的平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。步驟通過已知最小物理塊數(shù)、頁面?zhèn)€數(shù)、頁面訪問序列、及采用置換方式可以得出頁面 置換的缺頁次數(shù)和缺頁率，及每次缺頁時物理塊中存儲。1 .輸入的形式int PageOrderMaxNumber;/頁面序歹!

3、Jint PageNum,LackNum=0,BlockNum;/頁面?zhèn)€數(shù)，缺頁次數(shù),最小物理塊數(shù)2 .輸出的形式double LackPageRate/缺頁率缺頁個數(shù)每次缺頁時物理塊中存儲程序所能達到的功能模擬先進先出FIF。最佳置換OPI和最近最久未使用LRU頁面置換算法的工作過程。 假設(shè)內(nèi)存中分配給每個進程的最小物理塊數(shù)為m,在進程運行過程中要訪問的頁面?zhèn)€數(shù)為n,頁面訪問序列為P1,Pn,分別利用不同的頁面置換算法調(diào)度進程的頁面訪問序 列，給出頁面訪問序列的置換過程，計算每種算法缺頁次數(shù)和缺頁率。測試數(shù)據(jù)，包括 正確的輸入及其輸出結(jié)果和含有錯誤的輸入及其輸出結(jié)果。程序中用到的所有抽象數(shù)據(jù)

4、類型的定義、主程序的流程以及各程序模塊之間的層次 （調(diào)用）關(guān)系。int PageOrderMaxNumber;/頁面序歹!Jint PageCountMaxNumber=0;/計算內(nèi)存內(nèi)數(shù)據(jù)離下一次出現(xiàn)的距離int PageNum,LackNum=0,BlockNum;/頁面?zhèn)€數(shù)，缺頁次數(shù),最小物理塊數(shù) double LackPageRate=0;bool found=false;整理范本頭文件流程圖六、實驗數(shù)據(jù)及結(jié)果分析運行截圖:圖6.1 XC: UlSOFrCTursnt>inm e»p. eze圖6.2明不續(xù)粕面八面4注1尊一是數(shù)數(shù)埋列 tiR個物序I 0 3 市；20救

5、 結(jié)據(jù):墳，受X入套匚_' 3圖6.3七、實驗總結(jié)這次試驗，讓我加深了對虛擬內(nèi)存頁面置換算法的理解， 進一步掌握先進先出FIFO 最佳置換OPI和最近最久未使用LRU頁面置換算法的實現(xiàn)方法。熟悉 Linux需要經(jīng)過大 量的實驗、改進與思考，在編寫代碼的過程中遇到了一些問題要積極面對并通過討論上 網(wǎng)或者問老師解決。通過這次試驗我了解了虛擬內(nèi)存置換算法的一些知識，是我對于所 學(xué)習(xí)的專業(yè)知識得到了更好的鞏固和提升。附錄源程序清單#include <iostream>using namespace std;#define MaxNumber 100void OPI(int Page

6、OrderMaxNumber,int PageCountMaxNumber, int PageNum,int LackNum,int BlockNum, double LackPageRate,boo found)int moduleMaxNumber;int sum=0;int i,j,k,m;for(i=0;i<BlockNum;i+)/將內(nèi)存填滿 modulei=PageOrderi;sum+;for(j=0;j<=i;j+)cout<<modulej<<""cout<<endl;LackNum=BlockNum;for

7、(i=BlockNum;i<PageNum;i+)found=false;for(j=0;j<BlockNum;j+ )/遍歷已存儲，判斷是否缺頁if(modulej=PageOrderi)found=true;break;if(found=false)/缺頁，選擇替換for(j=0;j<BlockNum;j+) /計算內(nèi)存內(nèi)數(shù)據(jù)離下次出現(xiàn)的距離 PageCountj=0;for(k=i+1;k<PageNum;k+)if(modulej!=PageOrderk)PageCountj+;elsebreak;int max=PageCount0;int kind=0;fo

8、r(j=0;j<BlockNum;j+)找出最大值if(PageCountj>max)max=PageCountj;kind=j;modulekind=PageOrderi;LackNum+;for(m=0; m<3;m+)cout<<modulem<<""cout<<endl;LackPageRate=(LackNum*1.0)/PageNum;cout<<”該算法缺頁次數(shù)為："<<LackNum<<endl;cout<<”該算法缺頁率為："<&

9、lt;LackPageRate*100<<'%'<<endl;先進先出置換算法*/*void FIFO(int PageOrderMaxNumber,int PageCountMaxNumber, int PageNum,int LackNum,int BlockNum, double LackPageRate,boo found)int moduleMaxNumber;int sum=0;int i,j,m；for(i=0;i<BlockNum;i+)/將內(nèi)存填滿modulei=PageOrderi;sum+;PageCounti=3-i;for

10、(j=0;j<=i;j+)cout<<modulej<<""cout<<endl;LackNum=BlockNum;for(i=BlockNum;i<PageNum;i+)found=false;for(j=0;j<BlockNum;j+ )/遍歷已存儲，判斷是否缺頁if(modulej=PageOrderi)found=true;break;if(found=false)/缺頁，選擇替換int max=PageCount0;int kind=0;for(j=0;j<BlockNum;j+)找出最大值if(Page

11、Countj>max)max=PageCountj;kind=j;for(int k=0;k<BlockNum;k+)/不是最大值，貝慳 +1if(k!=kind)PageCountk+;modulekind=PageOrderi;PageCountkind=0;/替換之后已經(jīng)查詢的次數(shù)改為 LackNum+;for(m=0; m<3;m+)cout<<modulem<<""cout<<endl;LackPageRate=(LackNum*1.0)/PageNum;cout<<”該算法缺頁次數(shù)為："

12、<<LackNum<<endl;cout<<”該算法缺頁率為："<<LackPageRate*100<<'%'<<endl;最近最久未使用置換算法*/*void LRU(int PageOrderMaxNumber,int PageCountMaxNumber,int PageNum,int LackNum,int BlockNum, doublefound)int moduleMaxNumber;int sum=0;int i,j,m;for(i=0;i<BlockNum;i+)/將內(nèi)存填

13、滿modulei=PageOrderi;sum+;PageCounti=3-i;for(j=0;j<=i;j+) cout<<modulej<<""cout<<endl;LackNum=BlockNum;for(i=BlockNum;i<PageNum;i+)found=false;for(j=0;j<BlockNum;j+)遍歷已存儲，判斷是否缺頁if(modulej=PageOrderi)found=true;PageCountj=0;/查詢后，更改次數(shù)for(int k=0;k<BlockNum;k+) if

14、(k!=j)PageCountk+; break;if(found=false)/缺頁，選擇替換int max=PageCount0;int kind=0;for(j=0;j<BlockNum;j+)找出最大值if(PageCountj>max)max=PageCountj;kind=j;for(int k=0;k<BlockNum;k+)if(k!=kind)PageCountk+;modulekind=PageOrderi;PageCountkind=0;/替換之后未查詢的次數(shù)改為 0LackNum+;for(m=0; m<3;m+)cout<<modu

15、lem<<""cout<<endl;LackPageRate=(LackNum*1.0)/PageNum;cout<<”該算法缺頁次數(shù)為："<<LackNum<<endl;cout<<”該算法缺頁率為："<<LackPageRate*100<<'%'<<endl;int main ()int PageOrderMaxNumber;/頁面序歹!Jint PageCountMaxNumber=0;/計算內(nèi)存內(nèi)數(shù)據(jù)離下一次出現(xiàn)的距離int

16、 PageNum,LackNum=0,BlockNum;須面?zhèn)€數(shù)，缺頁次數(shù),最小物理塊數(shù) double LackPageRate=0;bool found=false;int chioce1=0,chioce2,chioce3;int i=0;while(chioce1=0)cout<<”是否重新輸入數(shù)據(jù)；0:不輸入，1：重新輸入："cin>>chioce2;if(chioce2=1)cout<<"請輸入頁面?zhèn)€數(shù)："cin>> PageNum;cout<<"請輸入最小物理塊數(shù)"cin>>BlockNum;cout<<"請輸入頁面序列："<<endl;for(i=0;i<PageNum;i+)cin>>PageOrderi;整理范本cout<<"請選擇算法：1-FIFQ 2-OPI, 3-LRU:"cin>>chioce3;if(chioce3=1)FIFO(PageOrder,PageCount,PageNum,LackNum, BlockNum, LackPageRate,整理范本found);elsei