虛擬內(nèi)存頁(yè)面置換算法實(shí)驗(yàn)報(bào)告

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

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

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

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

5、 結(jié)據(jù):墳，受X入套匚_' 3圖6.3七、實(shí)驗(yàn)總結(jié)這次試驗(yàn)，讓我加深了對(duì)虛擬內(nèi)存頁(yè)面置換算法的理解， 進(jìn)一步掌握先進(jìn)先出FIFO 最佳置換OPI和最近最久未使用LRU頁(yè)面置換算法的實(shí)現(xiàn)方法。熟悉 Linux需要經(jīng)過(guò)大 量的實(shí)驗(yàn)、改進(jìn)與思考，在編寫(xiě)代碼的過(guò)程中遇到了一些問(wèn)題要積極面對(duì)并通過(guò)討論上 網(wǎng)或者問(wèn)老師解決。通過(guò)這次試驗(yàn)我了解了虛擬內(nèi)存置換算法的一些知識(shí)，是我對(duì)于所 學(xué)習(xí)的專(zhuān)業(yè)知識(shí)得到了更好的鞏固和提升。附錄源程序清單#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+ )/遍歷已存儲(chǔ)，判斷是否缺頁(yè)if(modulej=PageOrderi)found=true;break;if(found=false)/缺頁(yè)，選擇替換for(j=0;j<BlockNum;j+) /計(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<<”該算法缺頁(yè)次數(shù)為："<<LackNum<<endl;cout<<”該算法缺頁(yè)率為："<&

9、lt;LackPageRate*100<<'%'<<endl;先進(jìn)先出置換算法*/*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+ )/遍歷已存儲(chǔ)，判斷是否缺頁(yè)if(modulej=PageOrderi)found=true;break;if(found=false)/缺頁(yè)，選擇替換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<<”該算法缺頁(yè)次數(shù)為："

12、<<LackNum<<endl;cout<<”該算法缺頁(yè)率為："<<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+)遍歷已存儲(chǔ)，判斷是否缺頁(yè)if(modulej=PageOrderi)found=true;PageCountj=0;/查詢后，更改次數(shù)for(int k=0;k<BlockNum;k+) if

14、(k!=j)PageCountk+; break;if(found=false)/缺頁(yè)，選擇替換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<<”該算法缺頁(yè)次數(shù)為："<<LackNum<<endl;cout<<”該算法缺頁(yè)率為："<<LackPageRate*100<<'%'<<endl;int main ()int PageOrderMaxNumber;/頁(yè)面序歹!Jint PageCountMaxNumber=0;/計(jì)算內(nèi)存內(nèi)數(shù)據(jù)離下一次出現(xiàn)的距離int

16、 PageNum,LackNum=0,BlockNum;須面?zhèn)€數(shù)，缺頁(yè)次數(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<<"請(qǐng)輸入頁(yè)面?zhèn)€數(shù)："cin>> PageNum;cout<<"請(qǐng)輸入最小物理塊數(shù)"cin>>BlockNum;cout<<"請(qǐng)輸入頁(yè)面序列："<<endl;for(i=0;i<PageNum;i+)cin>>PageOrderi;整理范本cout<<"請(qǐng)選擇算法：1-FIFQ 2-OPI, 3-LRU:"cin>>chioce3;if(chioce3=1)FIFO(PageOrder,PageCount,PageNum,LackNum, BlockNum, LackPageRate,整理范本found);elsei