第一篇：頁(yè)面替換算法實(shí)驗(yàn)報(bào)告

操作系統(tǒng)頁(yè)面替換算法實(shí)驗(yàn)報(bào)告

姓名： 沈慧 班級(jí)： 計(jì)091 學(xué)號(hào)： 0913022006

頁(yè)面替換算法

一．目的和要求

（一）目的

存儲(chǔ)管理的主要功能之一是合理地分配空間。請(qǐng)求頁(yè)式管理是一種常用的虛擬存儲(chǔ)管理技術(shù)。

本實(shí)驗(yàn)的目的是通過(guò)請(qǐng)求頁(yè)式管理中頁(yè)面置換算法的模擬設(shè)計(jì)，來(lái)了解虛擬存儲(chǔ)技術(shù)的特點(diǎn)，掌握請(qǐng)求頁(yè)式管理的頁(yè)面置換算法。

（二）要求

模擬頁(yè)式虛擬存儲(chǔ)管理中硬件的地址轉(zhuǎn)換和缺頁(yè)中斷，并用最佳頁(yè)面替換算法（OPT）、最近最少使用頁(yè)面替換算法（LRU）、先進(jìn)先出調(diào)度算法（FIFO）處理缺頁(yè)中斷。

二、算法描述

1．先進(jìn)先出(FIFO)置換算法的思路

該算法總是淘汰最先進(jìn)入內(nèi)存的頁(yè)面，即選擇在內(nèi)存中駐留時(shí)間最久的頁(yè)面予以淘汰。該算法實(shí)現(xiàn)簡(jiǎn)單，只需把一個(gè)進(jìn)程已調(diào)入內(nèi)存的頁(yè)面，按照先后次序連接成一個(gè)隊(duì)列，并設(shè)置一個(gè)替換指針，使它總指向最老的頁(yè)面。

2．最近久未使用(LRU)置換算法的思路

最近久未使用置換算法的替換規(guī)則，是根據(jù)頁(yè)面調(diào)入內(nèi)存后的使用情況來(lái)進(jìn)行決策的。該算法賦予每個(gè)頁(yè)面一個(gè)訪問(wèn)字段，用來(lái)記錄一個(gè)頁(yè)面自上次被訪問(wèn)以來(lái)所經(jīng)歷的時(shí)間，當(dāng)需淘汰一個(gè)頁(yè)面的時(shí)候選擇現(xiàn)有頁(yè)面中其時(shí)間值最大的進(jìn) 行淘汰。

3.最佳（OPT）置換算法的思路

其所選擇的被淘汰的頁(yè)面，獎(jiǎng)是以后不使用的，或者是在未來(lái)時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面，采用最佳算法，通常可保證獲得最低的缺頁(yè)率。

三、方案設(shè)計(jì)

1、數(shù)據(jù)結(jié)構(gòu) class RAMPAGE { protected: int *RAM;//內(nèi)存各塊，存放各頁(yè)

int ramcount;//內(nèi)存塊數(shù)

int *PAGE;//接收用戶要訪問(wèn)的各頁(yè)

int pagecount;//頁(yè)數(shù)

int *CHANGEPAGE;//存放淘汰的各頁(yè) int maxpage;//頁(yè)的最大頁(yè)號(hào)

int shortage;//缺頁(yè)的數(shù)量 public: RAMPAGE();//初始化

void input();//用戶輸入

void FIFO();//FIFO算法 void LRU();//LRU算法 void OPT();//OPT算法

~RAMPAGE();//釋放空間

};

三、測(cè)試與運(yùn)行

1、輸入要測(cè)試的數(shù)據(jù)

2、采用FIFO方法進(jìn)行頁(yè)面置換

3、采用LRU算法進(jìn)行頁(yè)面置換

4、采用OPT算法進(jìn)行頁(yè)面置換

源程序代碼：

#include #include #include using namespace std;class RAMPAGE { protected: int *RAM;//內(nèi)存各塊，存放各頁(yè) int ramcount;//內(nèi)存塊數(shù)

int *PAGE;//接收用戶要訪問(wèn)的各頁(yè)

int pagecount;//頁(yè)數(shù)

int *CHANGEPAGE;//存放淘汰的各頁(yè) int maxpage;//頁(yè)的最大頁(yè)號(hào)

int shortage;//缺頁(yè)的數(shù)量 public: RAMPAGE();//初始化

void input();//用戶輸入

void FIFO();//FIFO算法 void LRU();//LRU算法 void OPT();//OPT算法

~RAMPAGE();//釋放空間 };RAMPAGE::RAMPAGE(){ ramcount=0;//內(nèi)存塊數(shù)

pagecount=0;//頁(yè)數(shù)

maxpage=0;//頁(yè)的最大頁(yè)號(hào) } void RAMPAGE::input()//用戶輸入 { cout<<“請(qǐng)輸入內(nèi)存塊數(shù)：”;cin>>ramcount;//用戶輸入塊數(shù)

RAM=new int [ramcount];//內(nèi)存各塊，存放各頁(yè) cout<<“請(qǐng)輸入給定的頁(yè)面：以#結(jié)尾”<>page;//用戶輸入頁(yè)號(hào)

PAGE2[i]=page;//該頁(yè)進(jìn)入預(yù)分配空間

if(page>maxpage)maxpage=page;//找出最大頁(yè) i++;} pagecount=i;//記錄用戶輸入的頁(yè)數(shù) CHANGEPAGE=new int[pagecount];PAGE=new int[pagecount];//接收用戶要訪問(wèn)的各頁(yè)

for(i=0;i

} delete [] PAGE2;//釋放預(yù)申請(qǐng)空間 }

void RAMPAGE::FIFO(){ cout<<“使用FIFO算法：”<=maxpage||ramcount>=pagecount){ cout<<“缺頁(yè)次數(shù)：”<<0<int j=0,k=0,l=0;//j記錄內(nèi)存序號(hào)，k記錄淘汰頁(yè)空間序號(hào)，l記錄未被寫入的內(nèi)存塊號(hào)

cout<<“內(nèi)存各塊存儲(chǔ)變化：”<in=0;for(j=0;j

}

if(in==0)//頁(yè)不在內(nèi)存塊

{

shortage++;

if(RAM[ramcount-1]!=-1)//最后一個(gè)內(nèi)存塊標(biāo)記為-1，表示它未被寫入過(guò)頁(yè)號(hào)

{

CHANGEPAGE[k]=RAM[l];//!-1,則要進(jìn)行淘汰，記錄要被淘汰的頁(yè)號(hào)

k++;

}

RAM[l]=PAGE[i];//新頁(yè)寫入塊，將該塊初次寫入

l++;

if(l==ramcount)l=0;}

}

for(j=0;j

{cout<

cout<<“缺頁(yè)次數(shù)：”<

cout<

}

void RAMPAGE::LRU(){ cout<<“使用LRU算法：”<=maxpage||ramcount>=pagecount){ cout<<“缺頁(yè)次數(shù)：”<<0<

int i=0;for(i=0;icout<<“內(nèi)存各塊存儲(chǔ)變化：”<for(j=0;j

if(PAGE[i]==RAM[j])

{

in=1;

break;

}

}

if(in==0&&RAM[ramcount-1]!=-1){

shortage++;

for(j=0;j

RAM2[j]=0;

for(j=0;j

{

for(p=i-1;p>=0;p--)

{ RAM2[j]++;//RAM2[]存儲(chǔ)當(dāng)前內(nèi)存中各頁(yè)的權(quán)值（距該頁(yè)上次被訪問(wèn)待了多長(zhǎng)時(shí)間）

if(RAM[j]==PAGE[p])break;

}

}

int max=0;for(j=0;j

{

if(RAM2[j]>max)

max=RAM2[j];//max標(biāo)記最大的權(quán)值

}

for(j=0;j

{

if(max==RAM2[j])break;//定位max對(duì)應(yīng)的最大權(quán)值頁(yè)號(hào)的存儲(chǔ)塊號(hào)

}

CHANGEPAGE[k]=RAM[j];//將該塊中的頁(yè)號(hào)放入淘汰序列

RAM[j]=PAGE[i];//要訪問(wèn)的頁(yè)寫入內(nèi)存塊好

k++;// 淘汰數(shù)加1

}

if(in==0&&RAM[ramcount-1]==-1){

shortage++;

RAM[l]=PAGE[i];

l++;} }

for(j=0;j

cout<<“缺頁(yè)次數(shù)：”<

for(int m=0;m

void RAMPAGE::OPT(){ cout<<“使用OPT算法：”<=maxpage||ramcount>=pagecount){ cout<<“缺頁(yè)次數(shù)：”<<0<

int i=0;for(i=0;icout<<“內(nèi)存各塊存儲(chǔ)變化：”<for(j=0;j

in=0;for(j=0;j

if(PAGE[i]==RAM[j])

{

in=1;

break;

}

}

if(in==0&&RAM[ramcount-1]!=-1){

shortage++;

for(j=0;j

RAM2[j]=0;

for(j=0;j

{

for(p=i+1;p

{ RAM2[j]++;//RAM2[]存儲(chǔ)當(dāng)前內(nèi)存中各頁(yè)的權(quán)值（距該頁(yè)下次被訪問(wèn)要待多長(zhǎng)時(shí)間）

if(RAM[j]==PAGE[p])break;

}

}

int max=0;for(j=0;j

{

if(RAM2[j]>max)

max=RAM2[j];

}

for(j=0;j

{

if(max==RAM2[j])break;

}

CHANGEPAGE[k]=RAM[j];

RAM[j]=PAGE[i];

k++;

}

if(in==0&&RAM[ramcount-1]==-1){

shortage++;

RAM[l]=PAGE[i];

l++;} }

for(j=0;j

cout<<“缺頁(yè)次數(shù)：”<

for(int m=0;m

delete []PAGE;//釋放訪問(wèn)各頁(yè)空間

delete []CHANGEPAGE;//釋放淘汰頁(yè)空間 }

int main(){

率： RAMPAGE *task;

again: cout<<“說(shuō)明：”<input();cout<<“**************************************************************”<

cout<<“輸入 1 or 2 or 3選擇算法:”;int number;cin>>number;switch(number){ case 1: task->FIFO();break;case 2: task->LRU();break;case 3: task->OPT();break;default : cout<<“選擇出錯(cuò)!”<

cout<<“繼續(xù)其他算法(1 or 2 or 3)，0 跳過(guò)：”;cin>>number;switch(number){ case 1: task->FIFO();break;case 2: task->LRU();break;case 3: task->OPT();break;default : cout<<“跳過(guò)算法!”<

cout<<“***************************************************************”<

cout<<“繼續(xù)其他算法(1 or 2 or 3)，0 跳過(guò)：”;cin>>number;switch(number){ case 1: task->FIFO();break;case 2: task->LRU();break;case 3: task->OPT();break;

default : cout<<“跳過(guò)算法!”<

cout<<“***************************************************************”<

delete task;cout<<“結(jié)束程序/繼續(xù)新任務(wù)?(y / n): ”;char goon;cin>>goon;if(goon=='y'){ system(“CLS”);

goto again;} return 0;}

第二篇：頁(yè)面置換算法實(shí)驗(yàn)報(bào)告（精選）

《操作系統(tǒng)--頁(yè)面置換算法》

實(shí)驗(yàn)報(bào)告

姓

名： 范學(xué)升

學(xué)

號(hào)：1001050903

班

級(jí)：電科10-1班

專

業(yè)：電子信息科學(xué)與技術(shù)

一、實(shí)驗(yàn)?zāi)康?/p>

1．通過(guò)模擬實(shí)現(xiàn)幾種基本頁(yè)面置換的算法，了解虛擬存儲(chǔ)技術(shù)的特點(diǎn)。

2．掌握虛擬存儲(chǔ)請(qǐng)求頁(yè)式存儲(chǔ)管理中幾種基本頁(yè)面置換算法的基本思想，并至少用三種算法來(lái)模擬實(shí)現(xiàn)。

3．通過(guò)對(duì)幾種置換算法頁(yè)面的比較，來(lái)對(duì)比他們的優(yōu)缺點(diǎn)，并通過(guò)比較更換頻率來(lái)對(duì)比它們的效率。

二、實(shí)驗(yàn)內(nèi)容：

設(shè)計(jì)一個(gè)虛擬存儲(chǔ)區(qū)和內(nèi)存工作區(qū)，并使用下述算法來(lái)模擬實(shí)現(xiàn)頁(yè)面的置換： 1.先進(jìn)先出的算法（FIFO）2.最近最久未使用算法（LRU）3.最佳置換算法（OPT）

三、實(shí)驗(yàn)分析

在進(jìn)程運(yùn)行過(guò)程中，若其所訪問(wèn)的頁(yè)面不存在內(nèi)存而需要把它們調(diào)入內(nèi)存，但內(nèi)存已無(wú)空閑時(shí)，為了保證該進(jìn)程能夠正常運(yùn)行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁(yè)程序或數(shù)據(jù)送磁盤的對(duì)換區(qū)中。但應(yīng)調(diào)出哪個(gè)頁(yè)面，需根據(jù)一定的算法來(lái)確定，算法的好壞，直接影響到系統(tǒng)的性能。

一個(gè)好的頁(yè)面置換算法，應(yīng)該有較低的頁(yè)面更換頻率。

假設(shè)分給一作業(yè)的物理塊數(shù)為3，頁(yè)面數(shù)為20個(gè)。頁(yè)面號(hào)為(20個(gè))：

7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

1．先進(jìn)先出(FIFO)置換算法的思路

該算法總是淘汰最先進(jìn)入內(nèi)存的頁(yè)面，即選擇在內(nèi)存中駐留時(shí)間最久的頁(yè)面予以淘汰。該算法實(shí)現(xiàn)簡(jiǎn)單，只需把一個(gè)進(jìn)程已調(diào)入內(nèi)存的頁(yè)面，按照先后次序連接成一個(gè)隊(duì)列，并設(shè)置一個(gè)替換指針，使它總指向最老的頁(yè)面。

2．最近久未使用(LRU)置換算法的思路

最近久未使用置換算法的替換規(guī)則，是根據(jù)頁(yè)面調(diào)入內(nèi)存后的使用情況來(lái)進(jìn)行決策的。該算法賦予每個(gè)頁(yè)面一個(gè)訪問(wèn)字段，用來(lái)記錄一個(gè)頁(yè)面自上次被訪問(wèn)以來(lái)所經(jīng)歷的時(shí)間，當(dāng)需淘汰一個(gè)頁(yè)面的時(shí)候選擇現(xiàn)有頁(yè)面中其時(shí)間值最大的進(jìn) 行淘汰。

3.最佳（OPT）置換算法的思路

其所選擇的被淘汰的頁(yè)面，獎(jiǎng)是以后不使用的，或者是在未來(lái)時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面，采用最佳算法，通常可保證獲得最低的缺頁(yè)率。

4．?dāng)?shù)據(jù)結(jié)構(gòu)

struct pageInfor { int content;//頁(yè)面號(hào) int timer;//被訪問(wèn)標(biāo)記 };

class PRA { public:

PRA(void);int findSpace(void);//查找是否有空閑內(nèi)存

int findExist(int curpage);//查找內(nèi)存中是否有該頁(yè)面 int findReplace(void);//查找應(yīng)予置換的頁(yè)面 void display(void);//顯示 void FIFO(void);//FIFO算法 void LRU(void);//LRU算法

void BlockClear(void);//BLOCK清空，以便用另一種方法重新演示 pageInfor * block;//物理塊 pageInfor * page;//頁(yè)面號(hào)串 private: };

5．FIFO頁(yè)面置換算法

當(dāng)需要訪問(wèn)一個(gè)新的頁(yè)面時(shí)，首先調(diào)用findExist(i)函數(shù)來(lái)查看物理塊中是否就有這個(gè)頁(yè)面，若要查看的頁(yè)面物理塊中就有，則調(diào)用display函數(shù)直接顯示，不需要替換頁(yè)面；如果要查看的頁(yè)面物理塊中沒(méi)有，就需要尋找空閑物理塊放入，若存在有空閑物理塊，則將頁(yè)面放入；若沒(méi)有空閑物理塊，則調(diào)用findReplace函數(shù)替換頁(yè)面。并將物理塊中所有頁(yè)面timer++。

6．LRU頁(yè)面置換算法

當(dāng)需要訪問(wèn)一個(gè)新的頁(yè)面，首先調(diào)用findExist(i)函數(shù)查看物理塊中是否就有這個(gè)頁(yè)面。

7.OPT頁(yè)面置換算法

當(dāng)需要訪問(wèn)一個(gè)新的頁(yè)面，首先調(diào)用findExist(i)函數(shù)來(lái)查看物理塊中是否有這個(gè)頁(yè)面。

8．尋找置換頁(yè)面函數(shù)findReplace比較三個(gè)物理塊中的時(shí)間標(biāo)記timer，找到時(shí)間最久的。

四、源程序結(jié)構(gòu)分析

1． 程序結(jié)構(gòu)

程序共有以下九個(gè)部分：

int findSpace(void);//查找是否有空閑內(nèi)存

int findExist(int curpage);//查找內(nèi)存中是否有該頁(yè)面 int findReplace(void);//查找應(yīng)予置換的頁(yè)面 void display(void);//顯示 void FIFO(void);//FIFO算法 void LRU(void);//LRU算法 void OPT(void);//OPT算法；

void BlockClear(void);//BLOCK清空，以便用另一種方法重新演示 int main()

//主程序

五、實(shí)驗(yàn)結(jié)果

1運(yùn)行后的初始界面 opt算法

3.FIFO算法

4LRU算法

第三篇：頁(yè)面置換算法實(shí)驗(yàn)報(bào)告

計(jì)算機(jī)體系結(jié)構(gòu)

實(shí)驗(yàn)報(bào)告

班級(jí)：計(jì)科姓名：張華敏學(xué)號(hào)：

0902班

0909090814

FIFU算法

一，實(shí)驗(yàn)內(nèi)容：

編寫一段程序來(lái)模擬頁(yè)面置換算法中的FIFU算法的實(shí)現(xiàn) 二，算法設(shè)計(jì)：

設(shè)置一個(gè)產(chǎn)生隨機(jī)數(shù)的函數(shù)rand()產(chǎn)生隨機(jī)數(shù)來(lái)模擬程序所需訪問(wèn)的頁(yè)面的標(biāo)號(hào)，如果頁(yè)面需要被訪問(wèn)則把頁(yè)面中的一個(gè)標(biāo)志位設(shè)為in表示他已經(jīng)被調(diào)入內(nèi)存，如果再次需要訪問(wèn)此頁(yè)面是只需檢查此頁(yè)面的標(biāo)志位是否為in就可判斷它是否已經(jīng)存在在內(nèi)存中了，如果已經(jīng)存在則可直接使用，如果不存在則需調(diào)入，在調(diào)入新頁(yè)面是先檢查內(nèi)存空間是否已滿，如果未滿則直接調(diào)入，如果已經(jīng)滿了則需選擇一個(gè)頁(yè)面將其調(diào)出，調(diào)出時(shí)就把頁(yè)面的標(biāo)志位設(shè)為out。選擇頁(yè)面的規(guī)則是：將進(jìn)入內(nèi)存時(shí)間最久的頁(yè)面調(diào)出去，為了達(dá)到這一目的，在頁(yè)面中設(shè)置一個(gè)計(jì)數(shù)器，每當(dāng)有新頁(yè)面調(diào)入內(nèi)存時(shí)則將內(nèi)存中已經(jīng)存在的頁(yè)面計(jì)數(shù)器自動(dòng)加一，調(diào)出頁(yè)面時(shí)就選擇那個(gè)計(jì)數(shù)器最大值的頁(yè)面，調(diào)出后重新將計(jì)數(shù)器設(shè)為零。三，遇到的問(wèn)題及解決方案：

在做此實(shí)驗(yàn)時(shí)遇到了一些小問(wèn)題,如在C語(yǔ)言中函數(shù)名定義為export()則會(huì)報(bào)錯(cuò)。在調(diào)用有返回值的函數(shù)是如果直接int s=use(pag)則會(huì)運(yùn)行出錯(cuò),要先分開(kāi)寫如：int s,s=use(pag).四，源代碼 頭文件.cpp #include #include

int t;//全局變量，用來(lái)盛放rand()函數(shù)產(chǎn)生的隨機(jī)數(shù)

enum boolean{in,out};//定義一個(gè)枚舉類型 /////////如果把in，out換成 true,false則會(huì)處錯(cuò)誤

typedef struct { int num;//頁(yè)面編號(hào) char content;//頁(yè)面內(nèi)容

enum boolean flog;//判斷此頁(yè)面是否頁(yè)調(diào)入，調(diào)入為true,否則為false;int count;//頁(yè)面計(jì)數(shù)器

int usebit;//使用位，被使用過(guò)值為1，否則為0 }page;

FIFU.cpp #include #include #include #include“頭文件.cpp”

int capacity=3;//設(shè)置內(nèi)存最多可以容納的頁(yè)面數(shù)

void initialize(page p[])//初始化頁(yè)面函數(shù) { for(int i=0;i<5;i++)//初始化頁(yè)面，頁(yè)面內(nèi)容分別為小寫字母 abcde,計(jì)數(shù)器全部為0 {p[i].num=i;p[i].content=i+97;p[i].flog=out;p[i].count=0;} }

int use(page p[]){ t=rand()%5;//產(chǎn)生一個(gè)0-5的隨機(jī)數(shù)，if(p[t].flog==in){ printf(“tt%d頁(yè)面命中n”,t);//for(int i=0;i<5;i++)//調(diào)入此頁(yè)面后其他以在內(nèi)存中存在的頁(yè)面計(jì)數(shù)器加1 // { // if(p[i].flog==in)// p[i].count++;// } return(1);} else return(0);}

void import(page p[])//調(diào)入頁(yè)面的函數(shù) { /* int t=rand()%5;//產(chǎn)生一個(gè)0-5的隨機(jī)數(shù)，if(p[t].flog==in)printf(“tt%d頁(yè)面命中n”,t);*/ // if(p[t].flog==out)//如果此頁(yè)面未被調(diào)入內(nèi)存則立即調(diào)入 p[t].flog=in;capacity--;//調(diào)入后內(nèi)存空間減少一葉

for(int i=0;i<5;i++)//調(diào)入此頁(yè)面后其他以在內(nèi)存中存在的頁(yè)面計(jì)數(shù)器加1 { if(p[i].flog==in&&p[i].num!=t)p[i].count++;} printf(“頁(yè)面%d被調(diào)入內(nèi)存n”,t);}

void port(page p[])//調(diào)出頁(yè)面的函數(shù)，，，，，，，，，，，如果函數(shù)名定義為export則處錯(cuò)誤 { int x=0,y;//x用來(lái)暫時(shí)存放計(jì)數(shù)器 中的最大值，y存放此頁(yè)面的頁(yè)面號(hào) for(int i=0;i<5;i++)//尋找計(jì)數(shù)器值最大的 頁(yè)面 { if(p[i].count>x){ x=p[i].count;y=i;} }

p[y].flog=out;//修改調(diào)入符號(hào) p[y].count=0;capacity++;//調(diào)入后內(nèi)存空間增加一葉 printf(“ttt頁(yè)面%d被調(diào)出內(nèi)存n”,y);}

main(){ int s;long t3,t1,t2;page pag[5];//定義五個(gè)頁(yè)面，，，，，，，，，，，如果這個(gè)定義在子函數(shù)之前那么不用通過(guò)參數(shù) 子函數(shù)便可以直接訪問(wèn) t3=time(NULL);initialize(pag);do { t1=time(NULL);s=use(pag);//，，，，，，，，，，，，，，如果這里寫成int s=use(pag)則會(huì)運(yùn)行出錯(cuò)

//printf(“s=%d capacity=%dn”,s,capacity);if(capacity>0&&s==0)import(pag);else { if(capacity==0&&s==0){ port(pag);import(pag);} } t2=time(NULL);while(t2-t1<1){ t2=time(NULL);} }while(t2-t3<20);system(“pause”);}

五，測(cè)試結(jié)果：

LFU算法

一,實(shí)驗(yàn)內(nèi)容：

編寫一段程序來(lái)模擬頁(yè)面置換算法中的LFU算法的實(shí)現(xiàn) 二,算法設(shè)計(jì)：

設(shè)置一個(gè)產(chǎn)生隨機(jī)數(shù)的函數(shù)rand()產(chǎn)生隨機(jī)數(shù)來(lái)模擬程序所需訪問(wèn)的頁(yè)面的標(biāo)號(hào)，如果頁(yè)面需要被訪問(wèn)則把頁(yè)面中的一個(gè)標(biāo)志位設(shè)為in表示他已經(jīng)被調(diào)入內(nèi)存，如果再次需要訪問(wèn)此頁(yè)面是只需檢查此頁(yè)面的標(biāo)志位是否為in就可判斷它是否已經(jīng)存在在內(nèi)存中了，如果已經(jīng)存在則可直接使用，如果不存在則需調(diào)入，在調(diào)入新頁(yè)面是先檢查內(nèi)存空間是否已滿，如果未滿則直接調(diào)入，如果已經(jīng)滿了則需選擇一個(gè)頁(yè)面將其調(diào)出，調(diào)出時(shí)就把頁(yè)面的標(biāo)志位設(shè)為out。選擇頁(yè)面的規(guī)則是：將最近一段時(shí)間未被訪問(wèn)過(guò)的頁(yè)面調(diào)出。為了達(dá)到這一目的在頁(yè)面中設(shè)置一個(gè)標(biāo)志位，如果頁(yè)面在近期只要被訪問(wèn)過(guò)則將該標(biāo)志位設(shè)置為1（默認(rèn)為0），在選擇調(diào)出頁(yè)面時(shí)只需將標(biāo)志位為0的頁(yè)面調(diào)出即可。三,遇到的問(wèn)題及解決方案： 未遇到什么問(wèn)題

四,實(shí)驗(yàn)感悟：

遇到問(wèn)題后上網(wǎng)查資料和有效,及時(shí)查不到自己想要的但是也可從相關(guān)結(jié)果中獲得啟發(fā)給自己靈感來(lái)想到解決問(wèn)題的方法.四，源代碼

FLU.cpp #include #include #include #include“頭文件.cpp”

int capacity=3;

//設(shè)置內(nèi)存最多可以容納的頁(yè)面數(shù)

void initialize(page p[])

//初始化頁(yè)面函數(shù)

{

for(int i=0;i<5;i++)

//初始化頁(yè)面，頁(yè)面內(nèi)容分別為小寫字母 abcde,計(jì)數(shù)器全部為0

{p[i].num=i;

p[i].content=i+97;

p[i].flog=out;

p[i].count=0;

p[i].usebit=0;

}

}

int use(page p[]){

t=rand()%5;

//產(chǎn)生一個(gè)0-5的隨機(jī)數(shù)，if(p[t].flog==in)

{

printf(“tt%d頁(yè)面命中n”,t);

p[t].usebit=1;

//for(int i=0;i<5;i++)//調(diào)入此頁(yè)面后其他以在內(nèi)存中存在的頁(yè)面計(jì)數(shù)器加1

//

{

//

if(p[i].flog==in)

//

p[i].count++;

//

}

return(1);

}

else

return(0);

}

void import(page p[])//調(diào)入頁(yè)面的函數(shù)

{

int t=rand()%5;

//產(chǎn)生一個(gè)0-5的隨機(jī)數(shù)，//if(p[t].flog==in)

// {

//

printf(“tt%d頁(yè)面命中n”,t);

//

p[t].usebit=1;

// }

// if(p[t].flog==out)

//如果此頁(yè)面未被調(diào)入內(nèi)存則立即調(diào)入

p[t].flog=in;

capacity--;

//調(diào)入后內(nèi)存空間減少一葉

for(int i=0;i<5;i++)//調(diào)入此頁(yè)面后其他以在內(nèi)存中存在的頁(yè)面計(jì)數(shù)器加1

{

if(p[i].flog==in&&p[i].num!=t)

p[i].count++;

}

printf(“頁(yè)面%d被調(diào)入內(nèi)存n”,t);

}

void port(page p[])

//調(diào)出頁(yè)面的函數(shù)

////////////////////////////////如果函數(shù)名定義為export則處錯(cuò)誤

{

int x=0,y;//x用來(lái)暫時(shí)存放計(jì)數(shù)器 中的最大值，y存放此頁(yè)面的頁(yè)面號(hào)

int z=-1;

//用來(lái)判斷近期是否有未被訪問(wèn)過(guò)的頁(yè)面

int g=0;

for(int i=0;i<5;i++)//尋找計(jì)數(shù)器值最大的 頁(yè)面

{

if(p[i].count>x)

{

x=p[i].count;

y=i;

}

}

for(int i=0;i<5;i++)

{

if(p[i].flog==in&&p[i].usebit==0)

{

z=i;

g++;

}

}

if(z==-1||g==3)//如果所有頁(yè)面均為1則按照FIFO算法置換頁(yè)面 //如果g=3則表明頁(yè)面使用位全為零，此時(shí)也按照FIFO算法置換頁(yè)面

{

p[y].flog=out;//修改調(diào)入符號(hào)

p[y].count=0;

capacity++;

//調(diào)入后內(nèi)存空間增加一葉

p[y].usebit=0;

for(int i=0;i<5;i++)//將所有頁(yè)面置0

p[i].usebit=0;

printf(“ttt頁(yè)面%d被調(diào)出內(nèi)存n”,y);

}

else

//如果有頁(yè)面為0則將此頁(yè)面置換出來(lái)

{

p[z].flog=out;//修改調(diào)入符號(hào)

p[z].count=0;

capacity++;

//調(diào)入后內(nèi)存空間增加一葉

printf(“ttt頁(yè)面%d被調(diào)出內(nèi)存n”,z);

}

}

main(){

int s;

long t3,t1,t2;

page pag[5];//定義五個(gè)頁(yè)面

///////////////////如果這個(gè)定義在子函數(shù)之前那么不用通過(guò)參數(shù) 子函數(shù)便可以直接訪問(wèn)

t3=time(NULL);

initialize(pag);

do

{

t1=time(NULL);

s=use(pag);

if(capacity>0&&s==0)

import(pag);

else

{

if(capacity==0&&s==0)

{

port(pag);

import(pag);

}

}

t2=time(NULL);

while(t2-t1<1)

{

t2=time(NULL);

}

}while(t2-t3<20);

system(“pause”);}

六,實(shí)驗(yàn)結(jié)果

總結(jié)

通過(guò)本次試驗(yàn)我對(duì)各種頁(yè)面置換算法有了更深入的了解,也使得自己認(rèn)識(shí)到平常學(xué)習(xí)到某些東西覺(jué)得懂了會(huì)了可是一旦實(shí)際動(dòng)手操作起來(lái)就會(huì)發(fā)現(xiàn)總會(huì)存在這樣或者那樣的錯(cuò)誤，只有多動(dòng)手實(shí)際操作才會(huì)發(fā)現(xiàn)不足發(fā)現(xiàn)錯(cuò)誤并且改正。查漏補(bǔ)缺提高自己的實(shí)際動(dòng)手能力。

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

軟

件

學(xué)

院

上

機(jī)

實(shí)

驗(yàn)

報(bào)

告

課程名稱：

操作系統(tǒng)原理

實(shí)驗(yàn)項(xiàng)目：

虛擬內(nèi)存頁(yè)面置換算法

實(shí)

驗(yàn)

室：

地獄 018

姓

名 :

死神

學(xué)

號(hào)：

專業(yè)班級(jí) :

實(shí)驗(yàn)時(shí)間：

2015/12 ／ 13

實(shí)驗(yàn)成績(jī) 評(píng)閱教師

一、

實(shí)驗(yàn)?zāi)康眉耙?/p>

通過(guò)這次實(shí)驗(yàn)，加深對(duì)虛擬內(nèi)存頁(yè)面置換概念得理解,進(jìn)一步掌握先進(jìn)先出 FIFＯ、最佳置換ＯPI 與最近最久未使用ＬRU 頁(yè)面置換算法得實(shí)現(xiàn)方法。結(jié)合 Lｉｎux 得內(nèi)層得分析方法查瞧內(nèi)存得分配過(guò)程及 linuｘ keｒnel 得內(nèi)存管理機(jī)制 二、實(shí)驗(yàn)性質(zhì)

設(shè)計(jì)性 三、實(shí)驗(yàn)學(xué)時(shí)

學(xué)時(shí) 四、實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)環(huán)境１、實(shí)驗(yàn)環(huán)境：

C 與Ｃ++程序設(shè)計(jì)學(xué)習(xí)與實(shí)驗(yàn)系統(tǒng) 2、知識(shí)準(zhǔn)備:（１）使用 Linuｘ得基本命令；(2）了解 Liｎｕx vｍｓtat、freｅ、toｐ等命令查瞧ｌinuｘ系統(tǒng)得內(nèi)存分配情況；（3）

掌握虛擬內(nèi)存頁(yè)面置換算法 FＩＦO 等基本算法理論。

五、

實(shí)驗(yàn)內(nèi)容及步驟

假設(shè)有ｎ個(gè)進(jìn)程分別在 T1, … ,Ｔｎ時(shí)刻到達(dá)系統(tǒng)，它們需要得服務(wù)時(shí)間分別為S1，… ,Sｎ。分別采用先來(lái)先服務(wù) FCＦS 與短作業(yè)優(yōu)先 SJF 進(jìn)程調(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ǔ)。

１．輸入得形式

?inｔ

PagｅOrder［MａxNumbｅr]；//頁(yè)面序列 ｉｎt

ＰaｇeNｕm，LacｋNum=０,BlockNｕｍ;／／頁(yè)面?zhèn)€數(shù)，缺頁(yè)次數(shù),最小物理塊數(shù) 2、輸出得形式 doubｌe

LackPaｇｅRａt(yī)e／/缺頁(yè)率 缺頁(yè)個(gè)數(shù) 每次缺頁(yè)時(shí)物理塊中存儲(chǔ)

程序所能達(dá)到得功能 模擬先進(jìn)先出 FＩFO、最佳置換 OPＩ與最近最久未使用 LRＵ頁(yè)面置換算法得工作過(guò)程.假設(shè)內(nèi)存中分配給每個(gè)進(jìn)程得最小物理塊數(shù)為ｍ，在進(jìn)程運(yùn)行過(guò)程中要訪問(wèn)得頁(yè)面?zhèn)€數(shù)為 n，頁(yè)面訪問(wèn)序列為Ｐ1, …，Ｐn,分別利用不同得頁(yè)面置換算法調(diào)度進(jìn)程得頁(yè)面訪問(wèn)序列，給出頁(yè)面訪問(wèn)序列得置換過(guò)程，計(jì)算每種算法缺頁(yè)次數(shù)與缺頁(yè)率。測(cè)試數(shù)據(jù),包括正確得輸入及其輸出結(jié)果與含有錯(cuò)誤得輸入及其輸出結(jié)果。

程序中用到得所有抽象數(shù)據(jù)類型得定義、主程序得流程以及各程序模塊之間得層次（調(diào)用)關(guān)系.inｔ

PagｅOrdeｒ[MaxNumｂer］;//頁(yè)面序列 int

ＰａgeCoｕnt[MaxＮｕmｂer]={0｝；//計(jì)算內(nèi)存內(nèi)數(shù)據(jù)離下一次出現(xiàn)得距離 int

PａｇeNum,LackNuｍ＝0，ＢｌｏcｋNum;//頁(yè)面?zhèn)€數(shù),缺頁(yè)次數(shù),最小物理塊數(shù) douｂｌｅ

LaｃkPａｇeRaｔe＝0； bool ｆｏｕnd＝ｆａlsｅ;

六、實(shí)驗(yàn)數(shù)據(jù)及結(jié)果分析

運(yùn)行截圖：

圖６、1

圖６、2

圖６、3 七、實(shí)驗(yàn)總結(jié)

這次試驗(yàn),讓我加深了對(duì)虛擬內(nèi)存頁(yè)面置換算法得理解，進(jìn)一步掌握先進(jìn)先出 FIFO、最佳置換 OＰI 與最近最久未使用 LＲU 頁(yè)面置換算法得實(shí)現(xiàn)方法。熟悉 Linuｘ需要經(jīng)過(guò)大量得實(shí)驗(yàn)、改進(jìn)與思考，在編寫代碼得過(guò)程中遇到了一些問(wèn)題要積極面對(duì)并通過(guò)討論上網(wǎng)或者問(wèn)老師解決。通過(guò)這次試驗(yàn)我了解了虛擬內(nèi)存置換算法得一些知識(shí),就是我對(duì)于所學(xué)習(xí)得專業(yè)知識(shí)得到了更好得鞏固與提升。

附錄 源程序清單 ＃iｎclude ＜iｏｓｔｒeam> using namespace ｓｔｄ;#ｄｅｆinｅ ＭａxNumbｅr 100 void OＰI（int

PａgeOｒdｅｒ[MaxNuｍber］,iｎt

PａｇeCoｕnt［MａxＮumber]，?

int

PagｅＮｕm,ｉnｔ LackNum，int ＢlockNum，double

LacｋＰａgｅＲate,bｏol ｆound）

{

ｉnt moｄｕle［MaxNumber]；

iｎt sｕm＝0；

int i，j，k,ｍ;

fｏr(i=0;i

｛

moduｌe［ｉ］=ＰaｇeＯｒder[i］；

;＋＋ｍuｓ??)++ｊ；i＝

cｏuｔ<〈module[j］<〈”

＂;

；ldne<〈tｕoc?

｝

LackNuｍ=ＢｌoｃkNum；

foｒ(i=BlockNuｍ；i〈ＰageNum；i+＋）

｛

foｕnd=false;

fｏr（j=0;ｊ<ＢlockＮｕｍ；j＋+）//遍歷已存儲(chǔ),判斷就是否缺頁(yè)

｛

? ??

ｉf（module[ｊ]==ＰａgｅOrder［ｉ］)

{

??

foｕnd=true;

?

?

breaｋ;

?

｝

?? ｝

?

if（found==faｌse)//缺頁(yè),選擇替換

{

?

ｆor（j＝０；ｊ〈ＢlockＮｕm；j+＋）

/／計(jì)算內(nèi)存內(nèi)數(shù)據(jù)離下一次出現(xiàn)得距離

｛

PａgｅCｏｕnt［ｊ]=０;

ｆoｒ(k=i＋１；k

｛

??? ?

?

iｆ（module[j］!＝PageＯｒder[k])

??

PageCｏunt［j]++；

?

esle?

；kaｅrｂ?

｝

?

}

;］０[tｎuｏCegaP=xａm ｔnｉ?

iｎt kｉnｄ=0；

值大最出找/／）+＋j;muNkcolB〈j；0=j（rof?

{

?

if（PａｇeＣoｕｎｔ[j］>ｍax）

?

｛

??

；]j[tnuoＣｅgaP＝xam?? ?

?

kiｎｄ＝j(luò)；

?

｝

?

｝

module［kiｎd］=PａgｅOrder［i]；

?

LackNum++；）++ｍ;3

；”

”＜<］ｍ［elｕdom<〈tuoc??

?；lｄｎｅ＜

?

｝

LａｃkPａgeRate＝（LackＮuｍ＊1、0)／PageNum；

cｏut〈〈“該算法缺頁(yè)次數(shù)為：＂＜〈LackNum<＜eｎdｌ；

coｕt＜<”該算法缺頁(yè)率為：＂〈＜LackPａｇｅRａt(yī)e*100＜〈＇％”〈〈enｄl;｝ /＊＊＊＊＊＊*＊**＊＊***＊*＊＊**＊＊***＊***先進(jìn)先出置換算法＊＊*＊*＊*＊＊＊＊**＊*＊＊＊＊＊＊*＊＊＊＊**＊＊*＊＊*＊*＊/ vｏid FIFO(int

PagｅOrｄeｒ[MａxNｕmber],int

PａｇｅCounｔ［ＭaｘNuｍber］，egaPkｃaＬ

eｌbuod ,muNkcolB ｔni，mｕNｋcaL tni，muNｅｇａP

tni?Ｒate，booｌ ｆound)｛

int module[ＭａxNumber］;

iｎt sum=0；

int ｉ，j，ｍ;

for(ｉ=0;ｉ〈BlocｋＮum；ｉ+＋）//將內(nèi)存填滿

{

modｕlｅ［ｉ］＝PageOrｄeｒ［ｉ］；

；++mus??

PagｅCoｕnt[i]=３-i;）++j；ｉ=＜ｊ；0=ｊ（roｆ?

couｔ<<ｍｏdule[j]<<＂

“；

ｃout<＜enｄl;

}

LackNuｍ=BlockNum；

foｒ（i＝BlocｋNｕm；i〈PａgeＮuｍ;i++）

｛

fouｎｄ=fａlse；

ｆor（ｊ=0；j〈ＢlockNuｍ;j++)/／遍歷已存儲(chǔ)，判斷就是否缺頁(yè)

{

?

ｉf(module［j]==ＰａgeOrder[i］)

?

{

?

；eurt=dｎuof?? ?

breａk;

}

}

if（found==falｓｅ)//缺頁(yè)，選擇替換

｛

?

；]0［tnuoCｅgaＰ＝xam ｔｎi?

ｉnｔ ｋind=０；

值大最出找//）＋+ｊ;muNkcolB〈ｊ；０=j（rｏf?

｛

?

ｉf(PａgeCoｕnt［j]＞max）

｛

;］ｊ[tnuoCegａP=xａm?? ??

kiｎd=j；

｝

???

}

?

foｒ(inｔ k＝0;k＜BlocｋＮuｍ；ｋ++）／/不就是最大值，則要+1

?

{

?

?

ｉf（k！=kind)

PagｅCｏunt［k]++；

?

｝

?

moｄuｌe［kｉｎd］=PageOｒder［i］；

PageＣouｎt［kiｎd]=０；// 替換之后已經(jīng)查詢得次數(shù)改為0

LackNum++;

?

ｆor（m=０； m〈3；m++）

?

;”

”<〈］m[eludｏm〈

;ldne〈〈ｔuoc?? ｝

? ｝ ?

LａｃkPageＲate=（ＬackNｕm*１、0）/ＰagｅNuｍ；

cout〈〈“該算法缺頁(yè)次數(shù)為：”<＜LackNuｍ<

cｏuｔ＜<”該算法缺頁(yè)率為:＂<

PaｇeＯrdｅr[MaxＮumbｅｒ]，int

PａｇeCoｕnｔ［ＭaxNumｂｅr］，ｅｇaPｋcａL

elｂuod，muＮkｃｏlB tni,mｕNkcaL tni,muNegaＰ

tni??Ｒate,bool found){

int moｄuｌe[MａxNuｍｂer］；

inｔ sum＝0;

int i，j,m;

for（ｉ=0；i＜BｌockNum；i＋+)//將內(nèi)存填滿

{

moduｌe[ｉ]=PaｇeOｒdeｒ[i];

?

sｕm++；

ＰageCouｎt［i］=3—i；)＋+ｊ；i=＜j；0=j(roｆ?

cout〈〈mｏdule[j]〈〈”

”;

;ldne〈<ｔuoc??

｝

LａckＮum＝ＢｌockＮuｍ;

foｒ(ｉ=ＢlｏｃｋＮｕm；ｉ

｛

ｆouｎd=ｆaｌse;

fｏｒ（j=０；j＜BlockNum；j++)/／遍歷已存儲(chǔ),判斷就是否缺頁(yè)

{

?

if(module［j]==PageOｒder［i］）

??

｛

?

fｏund=truｅ；

ＰagｅCｏuｎt［ｊ]=０；//查詢后，更改次數(shù)

??

ｆor（iｎｔ k=0;k〈BlockＮuｍ；k++）

?

{

?? ??）j=！k（fi??

ＰａgeCｏuｎｔ[ｋ］+＋；

?

}

?

bｒｅａｋ;

?

｝

?

}

?

if(ｆounｄ＝=falsｅ）／／缺頁(yè),選擇替換

｛

?

；］０[tnuoCegａP=ｘam tni??

iｎt kind=0；

值大最出找／/）＋＋j；mｕNkcｏｌB

??)xaｍ〉]j［tnuoＣｅgaP（ｆｉ??

{

?

?;]j[tnuoCegａP=xam?

??

kiｎd=ｊ;

｝

? ｝

??

for（int k=0；k

｛

?

ｉf(k！=ｋind）

PagｅCounｔ［ｋ]+＋；

??

｝

?

mｏdule[kind]＝PageOrder［i］;

PageCoｕnt[ｋiｎｄ]＝0；// 替換之后未查詢得次數(shù)改為0

;++ｍｕNkcaL??

for（m＝0； ｍ<3;ｍ++）

?

coｕt〈

”；

?;ldne<〈ｔｕｏc? ｝

? } ?

LackPagｅRate=(LackＮｕm*1、0)/PaｇeNｕm;

ｃoｕｔ<〈“該算法缺頁(yè)次數(shù)為:＂＜

couｔ〈＜”該算法缺頁(yè)率為：”〈＜LackPａgeRate＊100〈＜“%’＜＜ｅｎdl;} int main（）

{

iｎt

PageＯｒｄer［MaｘNumｂer]；//頁(yè)面序列

inｔ

PaｇeCoｕnt[ＭａxＮumｂｅｒ]＝｛0｝;/／計(jì)算內(nèi)存內(nèi)數(shù)據(jù)離下一次出現(xiàn)得距離

inｔ

PagｅＮum，ＬackNuｍ＝0，BlocｋNum;//頁(yè)面?zhèn)€數(shù),缺頁(yè)次數(shù)，最小物理塊數(shù)

;0=etaＲegaPkcａL

eｌｂuoｄ? bool foｕｎd=false;

;3ecoｉhc,2eｃoihc,０=１ecoiｈc tni?

ｉnt i=０；）０==1ecoihc（eliｈｗ? ｛

；”:入輸新重:１,入輸不:0；據(jù)數(shù)入輸新重否是就“〈〈tｕoc? cｉｎ〉>chioｃe2；

if（ｃhｉoｃｅ2==１）

｛?

couｔ<＜”請(qǐng)輸入頁(yè)面?zhèn)€數(shù):”；

;muNegａＰ >>nic?;“數(shù)塊理物小最入輸請(qǐng)”〈〈tuoｃ? ；muNｋcolB>>niｃ? cｏut<〈”請(qǐng)輸入頁(yè)面序列：”<

for（i=０;ｉ〈ＰaｇｅNｕｍ；i++）

;]ｉ[ｒedrOegａP>〉nic? ｝?;”：ＵRL-3，IＰO—2，ＯFIF-1：法算擇選請(qǐng)＂<

iｆ（chiocｅ3==1)

ｃｏlB，muNkcaL,muNeｇaP，tnuoCｅgａP,reｄｒＯｅgaＰ(OＦIＦ?kNｕm，LackPageRａt(yī)e，founｄ);

eｌse

｛

ｉｆ（chioｃe3==2）

ｃｏｌB ,muNkcaＬ，muＮｅgａP,tnuｏＣｅｇaＰ，ｒedｒOegaP（IPO?ｋNum，LaｃkＰageRａｔe, fｏｕnd)；

esｌe?

，ｍｕNkcolB ,muＮｋcaL，mｕＮegaP，tｎuoCegａP,redrOｅgａP(UＲＬ?LackPaｇｅRａｔe，ｆound）;

｝ ＊＊＊***＊＊*＊*＊****＊＊****＊＊*＊＊＊*＊*＊＊＊**＊“〈＜tｕｏc?******＊*＊***＊＊***＊＊*＊＊*＊＊***”<＜endｌ；

;＂束結(jié)：１，續(xù)繼:0:束結(jié)是就還續(xù)繼擇選請(qǐng)"＜ｃhｉoｃe１;

｝ ｝

第五篇：頁(yè)面置換算法模擬,實(shí)驗(yàn)報(bào)告

中北大學(xué)軟件學(xué)院 實(shí) 驗(yàn) 報(bào) 告

專

業(yè)

軟件工程

課程名稱

計(jì)算機(jī)操作系統(tǒng)

學(xué)

號(hào)

姓

名

輔導(dǎo)教師

張

靜

成績(jī)

實(shí)驗(yàn)日期 2015、１1、20 實(shí)驗(yàn)時(shí)間實(shí)驗(yàn)名稱 :實(shí)驗(yàn)四

頁(yè)面置換算法模擬 ２、實(shí)驗(yàn)?zāi)康?１）了解內(nèi)存分頁(yè)管理策略（2）掌握調(diào)頁(yè)策略(3）掌握一般常用得調(diào)度算法（4）學(xué)會(huì)各種存儲(chǔ)分配算法得實(shí)現(xiàn)方法。

（5）了解頁(yè)面大小與內(nèi)存實(shí)際容量對(duì)命中率得影響。

3、實(shí)驗(yàn)要求 編程實(shí)現(xiàn)頁(yè)面置換算法，最少實(shí)現(xiàn)兩種算法，比較算法得優(yōu)劣,并將調(diào)試結(jié)果顯示在計(jì)算機(jī)屏幕上，并檢測(cè)機(jī)算與筆算得一致性。

（1）采用頁(yè)式分配存儲(chǔ)方案，通過(guò)分別計(jì)算不同算法得命中率來(lái)比較算法得優(yōu)劣，同時(shí)也考慮頁(yè)面大小及內(nèi)存實(shí)際容量對(duì)命中率得影響;（2）實(shí)現(xiàn) OＰT 算法(最優(yōu)置換算法)、ＬRU 算法(Lｅast Recｅｎtly）、FIFO 算法（Fｉrst IN Firｓｔ Out）得模擬;（3)使用某種編程語(yǔ)言模擬頁(yè)面置換算法.4、實(shí)驗(yàn)算法描述 （1）ＦIFO（先進(jìn)先出）

Y

Ｎ

N

Y

開(kāi)始 頁(yè)面走向存入數(shù)組 p[]中,內(nèi)存塊用page[]表示初始化為 0 當(dāng)前p[]中第i個(gè)元素就是否已在內(nèi)Page[]就是否有空把 page[]中最先裝入得頁(yè)面置換出去、i++ 把 p[i]得內(nèi)容直接裝入最上面一個(gè)空內(nèi)存塊,i++ 輸出當(dāng)前內(nèi)存塊狀態(tài) i++

圖 4－1FIFＯ算法流程圖

結(jié)束

(2）

LＲU（最近最久未使用）

Y

N

Y

Ｎ

圖 4—2

LＲU 算法流程圖

開(kāi)始 頁(yè)面走向存入數(shù)組 p[]中,內(nèi)存塊用 page[]表示初始化為 0 當(dāng)前 p[]中第 i 個(gè)元素就是否已在內(nèi)存 Page[]就是否有空把 page[]中最近最久未使用得頁(yè)面置換出去、i++ 把 p[i]得內(nèi)容直接裝入最上面一個(gè)空內(nèi)存塊,i++ 輸出當(dāng)前內(nèi)存塊狀態(tài)

結(jié)束 i++

(3）OＰＴ（最佳置換算法）

Y

N

Y

Ｎ

圖４－3 ＯPT 流程圖

開(kāi)始 頁(yè)面走向存入數(shù)組 p[]中,內(nèi)存塊用 page[]表示初始化為 0 當(dāng)前 p[]中第 i 個(gè)元素就是否已在內(nèi)存 Page[]就是否有空把 page[]中以后一段時(shí)間都不使用或就是使用時(shí)間離現(xiàn)在最遠(yuǎn)得換出、i++ 把 p[i]得內(nèi)容直接裝入最上面一個(gè)空內(nèi)存塊,i++ 輸出當(dāng)前內(nèi)存塊狀態(tài)

結(jié)束 i++

6、實(shí)驗(yàn)代碼 ＃iｎcｌuｄe ＜iostreａm〉 usiｎｇ ｎａmespace sｔｄ;#defiｎe Bｓｉzｅ ３ #dｅfine Psｉｚe 20 ｓｔruct ｐaｇｅInｆor ｛

號(hào)面頁(yè)//

;ｔneｔｎoc tni? int tｉmer;

//被訪問(wèn)標(biāo)記 ｝;ｃlasｓ ＰＲA{ ｐuｂｌiｃ：

PRA(ｖoid）；

存內(nèi)閑空有否是就找查/／

;)diov（eｃaｐSdnif tni? iｎt ｆindExist（int curpage）;

／／查找內(nèi)存中就是否有該頁(yè)面

int findReplacｅ（vｏid）;

//查找應(yīng)予置換得頁(yè)面

void ｄisplay(void）;

//顯示

法算 OＦIF//;）dioｖ（OFIＦ ｄiov? 法算 UＲL／/；)dｉov(URL diov? vｏid Ｏptimａl(ｖoid);／／ＯPTIＭAL 算法

ｖoｉd BlockＣlear（voiｄ)；/／ＢLOCK 恢復(fù)

pageＩｎfor ＊ ｂlｏck；//物理塊

pageInfoｒ ＊ page；／／頁(yè)面號(hào)串 privaｔe: };PＲA：：PＲＡ(vｏid）{

ｉnt QStriｎg［２0］=｛7，0，1，２,0，3,0，4,２，3,0,3,２,1，2，0，1,7,0,１};

block = ｎew paｇeIｎfor[Bｓizｅ］;)++i;ｅzisB＜ｉ;0＝i ｔnｉ(rof? {

;1— = tnｅtnｏc、］ｉ［ｋcolb? ；0 ＝ remｉt、]ｉ［kcolb?? }

page = ｎew pageInfｏｒ［Psｉze];）＋+ｉ;eｚiｓP〈i ；０=i（ｒof? {

；]i[gｎiｒtSQ = tｎetnoｃ、］i[egａp?;0 = rｅmit、]i[eｇａｐ?? }?} iｎt ＰRA：：fｉndSpace（voiｄ）

{

for（iｎt i=0； i

if(bｌocｋ[i]、cｏntent =＝ －1）

置位中 KＣOLＢ回返，存內(nèi)閑空到找//;i nrutｅｒ?;1— ｎruteｒ?｝ inｔ ＰRA：：fiｎｄExisｔ（iｎt cｕrpage）

{

ｆor（int i=0;ｉ<Ｂsizｅ； i++））tｎetnｏc、]egapruc［ｅgａp =＝ tneｔｎoc、］ｉ［kｃoｌb(fi??

置位中 KCOＬB 回返,面頁(yè)該有中存內(nèi)到找//;i nrｕter? ；1— nruter?｝ iｎt PRA：：findReplａce(void）

{

;0 ＝ sop tｎi? foｒ（iｎt i=0;i<Ｂsｉzｅ； ｉ+＋）)rｅmit、］soｐ[ｋcｏlb =＞ rｅmit、］i［kcｏlb（fi??

? pos = i;//找到應(yīng)予置換頁(yè)面,返回 BLOCＫ中位置

ｒeturn pos； } voｉd ＰRＡ：:display（voiｄ）

{

for（inｔ i=0;i＜Ｂsiｚe； ｉ++）

ｉｆ(bｌock［ｉ］、coｎteｎｔ!＝-１）

?；” ”<〈ｔnetnoc、］i[kcｏlb〈〈tuoc? ；ldｎe＜＜tuoc?｝ void PRA：：Optimａｌ（ｖoid)｛

； noｉtisop,ecapｓ，tsiｘe tｎi? fｏr（ｉnt i=0； i

｛?;)i（tsixEdｎif = tｓｉxe??）1-=！

ｔsixe（fｉ?

{?

;ｌdnｅ〈〈”頁(yè)缺不“<<ｔｕoｃ? ｝??

esｌｅ?

{?? ?? spａｃe = findSpacｅ（）；

?）1— ＝！

eｃaｐs（fi? ?

{? ?

；]i［egaｐ = ］eｃapｓ［kcolｂ?

?

;）（yalpsid??

? }

?

ｅslｅ?

{?? ?)+＋k ；ezisB<ｋ ；0＝k tｎｉ（roｆ?

? for（iｎｔ j＝i； j＜Psize； ｊ+＋)

?

{???

??)ｔnetnoc、]ｊ［ｅgaｐ =!ｔnｅtnoc、］k[ｋcolb（ｆi?

｛ 為 RＥMＩT 置設(shè)，用會(huì)不來(lái)將//};00０1 = ｒemiｔ、］k［kcoｌb??一個(gè)很大數(shù)

??

esle?

??

｛

??

?

? bloｃk［k]、ｔｉmeｒ = j;

?

?? ｂreaｋ；

｝ ??? }?????

? ｐoｓition ＝ fiｎdReｐｌａce（）；

?

；］i［ｅｇap ＝ ]ｎｏiｔｉｓｏｐ[ｋcolｂ?

；）(yalｐsｉｄ??

｝?? ? }

}?｝ voiｄ PRA:：LRU（ｖoid){

int ｅxｉsｔ,ｓpace，ｐositioｎ ；

for(int ｉ ＝ 0； i < Psizｅ;ｉ++）

｛? ? ｅxist = fｉndEｘｉst(i);)1－ =！

tsｉxｅ(ｆi?

{

?? cout＜<”不缺頁(yè)”＜

?

blｏck［eｘisｔ］、tiｍｅｒ = —1；//恢復(fù)存在得并剛訪問(wèn)過(guò)得ＢLOCK 中頁(yè)面 TＩMＥR 為－1

? }

? else

｛? ?? sｐace = fｉｎdSpace();?）１-=!ecaｐs（fi? ?

{?;]i[ｅgａp = ］ecaｐs［ｋｃolｂ?? ?

；)（ｙalpｓid? ?? ｝

?

eｓle?

｛??

；）（eｃａｌｐeRｄｎif = noｉtiｓop??

?

bｌoｃk[positiｏn］ = ｐagｅ［i］；

?

;）(yａlｐsid?

｝??

｝?

for(int ｊ=0;j〈Ｂsizｅ;j++)

;+＋rｅmit、］j[kcolb?? ｝?｝ ｖoｉd PRA:：ＦIFO（ｖoid）

{

int exｉｓt,ｓpace,position ；

for（iｎt i=0;i

｛?

exｉｓt ＝ findExist(ｉ）；

? ｉf（eｘist!＝-１）

{cout＜<＂不缺頁(yè)＂＜

esle?

｛

sｐａce = findSｐａｃe（）；

?)1-=！

ecaｐs（ｆi? ?? ｛

?

block［spaｃｅ］ = paｇe[ｉ]；

?

? displaｙ();

｝??

ｅsｌe?? ?

｛

??

pｏsition = findReplaｃe（）；

??

block［pｏsitioｎ] ＝ paｇe[i］；

;)（yａlｐsｉd?? ?? ｝

}?）＋+j;ezｉsB

ｂlock[j］、tｉmｅr+＋；//BLOCK 中所有頁(yè)面ＴIMER+＋

｝?｝ void ＰＲA：：BlockＣleａr（vｏiｄ)｛

for(inｔ ｉ=０;i

{?

blocｋ[i］、contｅnt =-1；

? ｂｌｏcｋ[i]、timeｒ = ０;

｝

} ｖoid mａｉn(vｏiｄ)｛

;lｄne<〈”:法 算 換 置 面 頁(yè)“＜＜tuｏc? ｃｏｕｔ〈〈”頁(yè)面號(hào)引用串：7,０,1,2，0,3,0，4,2，３，0，３,2,1,2，0，1，7，０,1＂<〈ｅndｌ；

cout〈〈”選擇<１＞應(yīng)用 LＲU 算法”〈＜eｎdl；

coｕt<＜”選擇<２〉應(yīng)用 FIFO 算法”〈

ｃout<<”選擇＜3>應(yīng)用 Optｉmａl 算法“<〈ｅndl;

；ldne<<＂出退>0〈擇選”〈＜ｔuoc? int select；

ＰRA tesｔ;? whｉle(seleｃｔ)

｛

? cｉｎ〉>select;）tcｅｌｅs（ｈctｉws?

｛?

:0 esac??;ｋaerb? :1 esａc???;ｌdnｅ＜<“：下如果結(jié)法算ＵRL”＜〈tuoc?

;）（URL、tset??

；)(raelCkｃｏｌB、tｓeｔ??;ldne＜<”－－-—-—－-—-—--—-—－—－———“<

? break；

：2 esac?

cｏut<〈”FIFO 算法結(jié)果如下:“<＜endl；

tesｔ、FIFO();?；）（raelCｋcoｌＢ、ｔset?

? cｏuｔ<〈”-——-－－－－－-—－—－－---－—－-”＜〈eｎdl;

?

ｂreak；

caｓe 3:

；ｌdnｅ〈＜”：下如果結(jié)法算 lａmiｔｐＯ”<

test、Optimal（）;

?

；)（rａeｌCkｃolB、tｓet??；ldｎe＜<＂－-－-—－－--－-——-－————－－－＂〈〈tuoc??;ｋaeｒb?

defaulｔ：

?

；ldｎe〈＜”號(hào)能功確正入輸請(qǐng)“＜＜tuoｃ?

;ｋaerb?? }?? } ｝

6、實(shí)驗(yàn)結(jié)果

7、實(shí)驗(yàn)心得 加深了對(duì)操作系統(tǒng)得認(rèn)識(shí),了解了操作系統(tǒng)中各種資源分配算法得實(shí)現(xiàn)，特別就是對(duì)虛擬存儲(chǔ)，頁(yè)面置換有了深入得了解，并能夠用高級(jí)語(yǔ)言進(jìn)行模擬演示。在這短短得兩周時(shí)間里，通過(guò)瀏覽、閱讀有關(guān)得資料，學(xué)到了很多東西,同時(shí)也發(fā)現(xiàn)僅僅書本得知識(shí)就是遠(yuǎn)遠(yuǎn)不夠得,需要把知識(shí)運(yùn)用到實(shí)踐中去,能力才能得到提高。

使用 MFＣ可視化編程極大得減少了編寫得代碼量，直觀得界面設(shè)計(jì)，不但便于修改，而且簡(jiǎn)化了界面程序代碼得編寫 兩種頁(yè)面置換算法 FIＦO 與ＬRＵ理解起來(lái)相當(dāng)容易，但在實(shí)際編程實(shí)現(xiàn)得時(shí)候需要注意各種細(xì)節(jié),需要耐心細(xì)致,實(shí)際編程中遇到一些細(xì)節(jié)上得小問(wèn)題確實(shí)需要仔細(xì)考慮才行.