第一篇：頁面置換算法模擬,實驗報告

中北大學(xué)軟件學(xué)院 實 驗 報 告

專

業(yè)

軟件工程

課程名稱

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

學(xué)

號

姓

名

輔導(dǎo)教師

張

靜

成績

實驗日期 2015、１1、20 實驗時間實驗名稱 :實驗四

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

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

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

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

Y

Ｎ

N

Y

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

圖 4－1FIFＯ算法流程圖

結(jié)束

(2）

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

Y

N

Y

Ｎ

圖 4—2

LＲU 算法流程圖

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

結(jié)束 i++

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

Y

N

Y

Ｎ

圖４－3 ＯPT 流程圖

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

結(jié)束 i++

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

號面頁//

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

//被訪問標記 ｝;ｃlasｓ ＰＲA{ ｐuｂｌiｃ：

PRA(ｖoid）；

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

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

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

int findReplacｅ（vｏid）;

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

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；／／頁面號串 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 回返,面頁該有中存內(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)予置換頁面,返回 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ｅ〈〈”頁缺不“<<ｔｕ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è)，用會不來將//};00０1 = ｒemiｔ、］k［kcoｌb??一個很大數(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＜<”不缺頁”＜

?

blｏck［eｘisｔ］、tiｍｅｒ = —1；//恢復(fù)存在得并剛訪問過得ＢLOCK 中頁面 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＜<＂不缺頁＂＜

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 中所有頁面Ｔ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<〈”:法 算 換 置 面 頁“＜＜tuｏc? ｃｏｕｔ〈〈”頁面號引用串：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〈＜”號能功確正入輸請“＜＜tuoｃ?

;ｋaerb?? }?? } ｝

6、實驗結(jié)果

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

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

第二篇：頁面置換算法模擬

“計算機操作系統(tǒng)”課程設(shè)計大作業(yè)

一、題目: 頁面置換算法模擬實驗

二、目的

分別采用最佳(Optimal)置換算法、先進先出(FIFO)頁面置換算法和最近最少使用(LRU)置換算法對用戶輸入的頁面號請求序列進行淘汰和置換，從而加深對頁面置換算法的理解。

三、內(nèi)容和要求

請用C/C++語言編一個頁面置換算法模擬程序。用戶通過鍵盤輸入分配的物理內(nèi)存總塊數(shù)，再輸入用戶邏輯頁面號請求序列，然后分別采用最佳(Optimal)置換算法、先進先出(FIFO)頁面置換算法和最近最少使用(LRU)置換算法三種算法對頁面請求序列進行轉(zhuǎn)換，最后按照課本P150頁圖4-26的置換圖格式輸出每次頁面請求后各物理塊內(nèi)存放的虛頁號，并算出每種算法的缺頁次數(shù)。最后評價三種頁面置換算法的優(yōu)缺點。

三種頁面置換算法的思想可參考教材P149-P152頁。

假設(shè)頁面號請求序列為4、3、2、1、4、3、5、4、3、2、1、5，當分配給某進程的物理塊數(shù)分別為3塊和4塊時，試用自己編寫的模擬程序進行頁面轉(zhuǎn)換并輸出置換圖和缺頁次數(shù)。

四、提交內(nèi)容 本大作業(yè)每個人必須單獨完成，大作業(yè)以WORD附件形式提交。最后需提交的內(nèi)容包括：算法算法思路及流程圖、數(shù)據(jù)結(jié)構(gòu)說明、源程序（關(guān)鍵代碼需要注釋說明）、運行結(jié)果截圖、心得體會及總結(jié)。

大作業(yè)嚴禁抄襲。發(fā)現(xiàn)抄襲一律以不及格論。

請大家嚴格按照大作業(yè)題目來編寫程序，不要上交以前布置的大作業(yè)。如果提交的大作業(yè)題目與本文檔要求不符，成績一律為不及格。

請大家按時在網(wǎng)院網(wǎng)上系統(tǒng)里提交大作業(yè)，過了規(guī)定時間將無法再補交大作業(yè)。

頁面置換算法模擬實驗

算法算法思路

模擬FIFOOPTLRU這3種頁面置換算法，先分配所需的內(nèi)存空間，在根據(jù)已知的序列，分別根據(jù)不同的頁面算法去訪問已知序列，得出不同內(nèi)存空間的置換算法的缺頁數(shù)量?？傮w流程圖

開始輸入內(nèi)存數(shù)執(zhí)行頁面置換FIFOLRUOPT顯示結(jié)果結(jié)束

數(shù)據(jù)結(jié)構(gòu)說明

源程序（關(guān)鍵代碼需要注釋說明）FIFO關(guān)鍵源碼

LRU關(guān)鍵源碼

OPT關(guān)鍵源碼

程序源碼

#include using namespace std;#define N 12 //默認序列12 #define M 4 // 默認開辟4 內(nèi)存空間 struct page{ int pno;// 定義頁號

int bno;//定義塊號

int time;// 定義最近使用

int status;//定義命中狀態(tài)

int order;//定義優(yōu)先級 };

int list[12]={4,3,2,1,4,2,5,2,3,2,1,5};// 已知序列

// 輸出方法

void output(int *a ,int n){ for(int i=0;i

cout<<*a<<'t';

a++;} cout<<'n';}

void fifo(int *list,int mem_num){

page p[N];// 定義記錄數(shù)組

int flag;int mem[M];// 定義內(nèi)存

int index =0;// 默認下標

int lack=0;// 初始化內(nèi)存

for(int i=0;i

mem[i]=0;} // 遍歷序列

for(i=0;i

flag=0;// 設(shè)置默認命中 0

for(int j=0;j

if(list[i]==mem[j]){ // 檢測序列與已知內(nèi)存值，命中返回flag

flag=1;

break;

}

}

if(flag==1){ // 判斷是否命中，則對 p 賦值

p[i].bno = j+1;

p[i].pno = list[i];

p[i].status =1;

}else{

p[i].pno = list[i];

p[i].status = 0;

mem[index] = list[i];

p[i].bno = index+1;// 賦予 頁號

index =(index+1)%mem_num;// 每次取余

lack++;

} }

cout<<“FIFO算法：n”;cout<<“---**n”;cout<<“缺頁次數(shù)：”<<'t'<

cout<<“-----**n”;cout<<“序列號n”;

cout<<“-----**n”;for(i=0;i

cout<<“-----**n”;} for(i=mem_num;icout<<“-----**n”;}

}

struct mem{ int order;//內(nèi)存優(yōu)先級 主要用于識別是否不常用

int pno;// 內(nèi)存頁號

int time;// 記錄是否最近使用 };

void lru(int *list,int mem_num){ page p[N];// 定義記錄數(shù)組

int flag;mem m[M];// 定義內(nèi)存

int index =0;// 默認下標

int lack=0;int temp;int max=0;// 內(nèi)存賦值

for(int i=0;i

m[i].pno=0;

//默認初始優(yōu)先級 0

m[i].order = 0;} for(i=0;i

flag=0;

for(int j=0;j

if(list[i]==m[j].pno){

flag=1;

index=j;

//m[j].order++;

p[i].order =m[j].order;

break;

}

}

if(flag==1){ //命中后，p[i].bno = index+1;

p[i].pno = list[i];

p[i].status = 1;

p[i].order--;

temp = p[i].order;

for(j=0;j

if(p[j].order

temp=p[j].order;

index = p[j].bno;

}

}

}else{

p[i].status=0;

p[i].pno = list[i];

m[index].pno = list[i];

m[index].order = p[i].order;

p[i].bno = index+1;

for(j=0;j

if(m[j].order>max){

index = j;

}

}

index =(index+1)%mem_num;// 每次取余有效的下標

//max++;

lack++;

} } cout<<“LRU算法：n”;cout<<“---**n”;cout<<“缺頁次數(shù)：”<<'t'<

cout<<“-----**n”;cout<<“序列號n”;

cout<<“-----**n”;for(i=0;i

cout<<“-----**n”;} for(i=mem_num;ivoid opt(int *list,int mem_num){ page p[N];//定義頁面

mem m[M];int flag=0;int index = 0;//下標

int max = N;int lack=0;for(int i=0;i

m[i].pno=0;

m[i].time = 0;//設(shè)置內(nèi)存使用頻率

}

for(i=0;i

flag=0;

for(int j=0;j

if(list[i]==m[j].pno){

flag=1;

index = j;

break;

}

}

if(flag==1){

p[i].status =1;

p[i].bno = index+1;

p[i].pno = list[i];

for(j=0;j

for(int g=i;g

if(m[j].pno==list[g]){

m[j].time = N-g;//獲取到 最近使用

p[i].time = m[j].time;

index = j;

}

}

}

}else{

p[i].status =0;

p[i].pno = list[i];

m[index].pno = list[i];

m[index].time = N;//設(shè)置默認不使用

p[i].bno =index+1;

for(j=0;j

if(m[j].time>max){

index = j;

}

}

index =(index+1)%mem_num;

lack++;

}

} cout<<“OPT算法：n”;cout<<“---**n”;cout<<“缺頁次數(shù)：”<<'t'<

cout<<“-----**n”;cout<<“序列號n”;

cout<<“-----**n”;for(i=0;i

cout<<“-----**n”;} for(i=mem_num;icout<<“-----**n”;} }

void main(){ int m;cout << “===========================n”;cout << “請輸入內(nèi)存大小（3/4）n”;cin >> m;cout << “===========================n”;opt(list,m);fifo(list,m);lru(list,m);

}

運行結(jié)果截圖

FIFO、LRU、OPT運行截圖（開辟3個內(nèi)存空間）：

FIFO、LRU、OPT運行截圖（開辟4個內(nèi)存空間）：

心得體會及總結(jié)：

在開始做題目的時候，需要了解什么是FIOFOLRUOPT這3個頁面置換的知識點，同時參考了網(wǎng)絡(luò)上許多實現(xiàn)過程技巧，并在在紙上面簡單畫出頁面如何記錄如何與內(nèi)存置換，這樣子比較方便寫出算法。由于這次設(shè)計的時間比較倉促，其中不免會有些紕漏，比如在程序的實現(xiàn)上還不夠嚴謹，出錯處理不夠完善等多方面問題，這些都有進一步改善。同時，在這次編寫3個頁面算法的過程中，我學(xué)到了很多東西，無論在理論上還是實踐中，都得到不少的提高，這對以后的工作中會有一定的幫助。

第三篇：頁面置換算法實驗報告（精選）

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

實驗報告

姓

名： 范學(xué)升

學(xué)

號：1001050903

班

級：電科10-1班

專

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

一、實驗?zāi)康?/p>

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

2．掌握虛擬存儲請求頁式存儲管理中幾種基本頁面置換算法的基本思想，并至少用三種算法來模擬實現(xiàn)。

3．通過對幾種置換算法頁面的比較，來對比他們的優(yōu)缺點，并通過比較更換頻率來對比它們的效率。

二、實驗內(nèi)容：

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

三、實驗分析

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

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

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

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

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

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

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

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

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

其所選擇的被淘汰的頁面，獎是以后不使用的，或者是在未來時間內(nèi)不再被訪問的頁面，采用最佳算法，通?？杀ＷC獲得最低的缺頁率。

4．數(shù)據(jù)結(jié)構(gòu)

struct pageInfor { int content;//頁面號 int timer;//被訪問標記 };

class PRA { public:

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

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

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

5．FIFO頁面置換算法

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

6．LRU頁面置換算法

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

7.OPT頁面置換算法

當需要訪問一個新的頁面，首先調(diào)用findExist(i)函數(shù)來查看物理塊中是否有這個頁面。

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

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

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

程序共有以下九個部分：

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

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

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

//主程序

五、實驗結(jié)果

1運行后的初始界面 opt算法

3.FIFO算法

4LRU算法

第四篇：頁面置換算法實驗報告

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

實驗報告

班級：計科姓名：張華敏學(xué)號：

0902班

0909090814

FIFU算法

一，實驗內(nèi)容：

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

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

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

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

enum boolean{in,out};//定義一個枚舉類型 /////////如果把in，out換成 true,false則會處錯誤

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

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

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

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

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

void initialize(page p[])//初始化頁面函數(shù) { for(int i=0;i<5;i++)//初始化頁面，頁面內(nèi)容分別為小寫字母 abcde,計數(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)生一個0-5的隨機數(shù)，if(p[t].flog==in){ printf(“tt%d頁面命中n”,t);//for(int i=0;i<5;i++)//調(diào)入此頁面后其他以在內(nèi)存中存在的頁面計數(shù)器加1 // { // if(p[i].flog==in)// p[i].count++;// } return(1);} else return(0);}

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

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

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

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

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

//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”);}

五，測試結(jié)果：

LFU算法

一,實驗內(nèi)容：

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

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

四,實驗感悟：

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

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

int capacity=3;

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

void initialize(page p[])

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

{

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

//初始化頁面，頁面內(nèi)容分別為小寫字母 abcde,計數(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)生一個0-5的隨機數(shù)，if(p[t].flog==in)

{

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

p[t].usebit=1;

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

//

{

//

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

//

p[i].count++;

//

}

return(1);

}

else

return(0);

}

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

{

int t=rand()%5;

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

// {

//

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

//

p[t].usebit=1;

// }

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

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

p[t].flog=in;

capacity--;

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

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

{

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

p[i].count++;

}

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

}

void port(page p[])

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

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

{

int x=0,y;//x用來暫時存放計數(shù)器 中的最大值，y存放此頁面的頁面號

int z=-1;

//用來判斷近期是否有未被訪問過的頁面

int g=0;

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

{

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)//如果所有頁面均為1則按照FIFO算法置換頁面 //如果g=3則表明頁面使用位全為零，此時也按照FIFO算法置換頁面

{

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

p[y].count=0;

capacity++;

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

p[y].usebit=0;

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

p[i].usebit=0;

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

}

else

//如果有頁面為0則將此頁面置換出來

{

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

p[z].count=0;

capacity++;

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

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

}

}

main(){

int s;

long t3,t1,t2;

page pag[5];//定義五個頁面

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

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”);}

六,實驗結(jié)果

總結(jié)

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

第五篇：操作系統(tǒng) 七次實驗報告 常用頁面置換算法模擬實驗

操作系統(tǒng)課程第七次實驗報告

姓名

學(xué)號

系

計算機

任課教師

指導(dǎo)教師

評閱教師

實驗地點

綜合樓B102

實驗時間

2012-9-26

實驗課表現(xiàn)

出勤和個人表現(xiàn)Q1(15+15（組長評分）=30分)

得分：

實驗

總分

(Q1+Q2+Q3+Q4)

實驗完成情況Q2(45分(組長與教師評分的加權(quán)平均))

得分：

實驗編號與實驗名稱：

實驗七、常用頁面置換算法模擬實驗

實驗?zāi)康模?/p>

通過模擬實現(xiàn)請求頁式存儲管理的幾種基本頁面置換算法，了解虛擬存儲技術(shù)的特點，掌握虛擬存儲請求頁式存儲管理中幾種基本頁面置換算法的基本思想和實現(xiàn)過程，并比較它們的效率。

實驗內(nèi)容及要求（詳見實驗講義與實驗指導(dǎo)書）：

要求：

1）要求用你熟悉的程序設(shè)計語言編寫和調(diào)試一個頁面置換模擬程序；要求在主函數(shù)中測試。

2）實驗報告中必須包括：設(shè)計思想、數(shù)據(jù)定義（包括詳細說明）、處理流程（詳細算法描述和算法流程圖）、源代碼、運行結(jié)果、體會等部分。

3）必須模擬本實驗內(nèi)容中提到的算法中的至少2種頁面置換算法。

4）

比較不同頁面置換算法的效率

內(nèi)容：編寫一個程序，使用以下頁面置換算法中的某2種分別模擬一個分頁系統(tǒng)，并統(tǒng)計同一個頁面訪問序列情況下不同頁面置換算法引發(fā)的缺頁中斷次數(shù)。

1、第二次機會算法（Second

Chance）

2、最近最少使用算法（Least

Recently

Used，LRU）

3、最不常用算法（Not

Frequently

Used，NFU）

4、最近未使用算法（Not

Recently

Used，NRU）

5、時鐘頁面置換算法

6、老化算法（aging）

頁框的數(shù)量固定為4，虛擬頁面數(shù)為8。實驗輸入為訪問頁面序列，比如0，1，3，2，7，1

實驗用到的軟件（：）

DevC++,Visio

實驗內(nèi)容及關(guān)鍵步驟（代碼）Q3（15分）

得分：

流程圖：輸入頁面訪問序列

取訪問的頁號

查頁表

是否缺頁？

是

置缺頁標志flag為’*’

按算法不同淘汰一頁面

調(diào)入所訪問的頁面

否

FIFO算法流程圖

LRU算法流程圖：

函數(shù)關(guān)系解釋圖：

實現(xiàn)結(jié)果：

圖1

圖2

代碼：

#include

#include

#define

MEMORY_SIZE

/*物理塊數(shù)*/

#define

PROESS_SIZE

/*頁面號引用串個數(shù)*/#include

#include

/*全局變量*/

int

mSIZE=4;

int

pSIZE=8;

static

int

memery[4]={0};

/*物理塊中的頁號*/

static

int

page[8]={0};

/*頁面號引用串*/

static

int

temp[8][4]={0};

/*輔助數(shù)組*/

/*置換算法函數(shù)*/

void

FIFO();

void

LRU();

void

OPT();

void

designBy();

/*輔助函數(shù)*/

void

print(unsigned

int

t);

/*主函數(shù)*/

int

main()

{

int

i,k,code;

designBy();

system(“color

0A“);

puts(“請依次輸入頁面號(8個)：“);

for(i=0;i

scanf(“%1d“,&page[i]);

system(“cls“);

system(“color

0E“);

do{

puts(“輸入的頁面號引用串為：“);

for(k=0;k<=(pSIZE-1)/20;k++)

{

for(i=20*k;(i

{

if(((i+1)%20==0)||(((i+1)%20)&&(i==pSIZE-1)))

printf(“%d＼n“,page[i]);

else

printf(“%d

“,page[i]);

}

}

printf(“*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*＼n“);

printf(“*

請選擇頁面置換算法：＼t＼t＼t

*＼n“);

printf(“*

-----------------------------------------

*＼n“);

printf(“*

1.先進先出(FIFO)

2.最近最久未使用(LRU)

*＼n“);

printf(“*

3.退出

*＼n“);

printf(“*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*＼n“);

printf(“請選擇操作：[

]＼b＼b“);

scanf(“%d“,&code);

switch(code)

{

case

1:

FIFO();

break;

case

2:

LRU();

break;

case

3:

system(“cls“);

system(“color

0A“);

exit(0);

default:

printf(“輸入錯誤，請重新輸入：“);

}

printf(“按任意鍵重新選擇置換算法：>>>“);

getch();

system(“cls“);

}while

(code!=3);

getch();

}

void

print(unsigned

int

t)

{

int

i,j,k,l;

int

flag;

for(k=0;k<=(pSIZE-1)/20;k++)

{

for(i=20*k;(i

{

if(((i+1)%20==0)||(((i+1)%20)&&(i==pSIZE-1)))

printf(“%d＼n“,page[i]);

else

printf(“%d

“,page[i]);

}

for(j=0;j

{

for(i=20*k;(i{

if(i>=j)

printf(“

|%d|“,temp[i][j]);

else

printf(“

|

|“);

}

for(i=mSIZE+20*k;(i

{

for(flag=0,l=0;l

if(temp[i][l]==temp[i-1][l])

flag++;

if(flag==mSIZE)/*頁面在物理塊中*/

printf(“

“);

else

printf(“

|%d|“,temp[i][j]);

}

/*每行顯示20個*/

if(i%20==0)

continue;

printf(“＼n“);

}

}

printf(“----------------------------------------＼n“);

printf(“缺頁次數(shù)：%d＼t＼t“,t+mSIZE);

printf(“缺頁率：%d/%d＼n“,t+mSIZE,pSIZE);

printf(“置換次數(shù)：%d＼t＼t“,t);

printf(“訪問命中率：%d%%＼n“,(pSIZE-(t+mSIZE))*100/pSIZE);

printf(“----------------------------------------＼n“);

}

/*先進先出頁面置換算法*/

void

FIFO()

{

int

memery[10]={0};

int

time[10]={0};

/*記錄進入物理塊的時間*/

int

i,j,k,m;

int

max=0;

/*記錄換出頁*/

int

count=0;

/*記錄置換次數(shù)*/

/*前mSIZE個數(shù)直接放入*/

for(i=0;i

{

memery[i]=page[i];

time[i]=i;

for(j=0;j

temp[i][j]=memery[j];

}

for(i=mSIZE;i

{

/*判斷新頁面號是否在物理塊中*/

for(j=0,k=0;j

{

if(memery[j]!=page[i])

k++;

}

if(k==mSIZE)

/*如果不在物理塊中*/

{

count++;

/*計算換出頁*/

max=time[0]

for(m=2;m

if(time[m]

max=m;

memery[max]=page[i];

time[max]=i;

/*記錄該頁進入物理塊的時間*/

for(j=0;j

temp[i][j]=memery[j];

}

else

{

for(j=0;j

temp[i][j]=memery[j];

}

}

print(count);

}

/*最近最久未使用置換算法*/

void

LRU()

{

int

memery[10]={0};

int

flag[10]={0};

/*記錄頁面的訪問時間*/

int

i,j,k,m;

int

max=0;

/*記錄換出頁*/

int

count=0;

/*記錄置換次數(shù)*/

/*前mSIZE個數(shù)直接放入*/

for(i=0;i

{

memery[i]=page[i];

flag[i]=i;

for(j=0;j

temp[i][j]=memery[j];

}

for(i=mSIZE;i

{

/*判斷新頁面號是否在物理塊中*/

for(j=0,k=0;j

{

if(memery[j]!=page[i])

k++;

else

flag[j]=i;

/*刷新該頁的訪問時間*/

}

if(k==mSIZE)

/*如果不在物理塊中*/

{

count++;

/*計算換出頁*/

max=flag[0]

for(m=2;m

if(flag[m]

max=m;

memery[max]=page[i];

flag[max]=i;

/*記錄該頁的訪問時間*/

for(j=0;j

temp[i][j]=memery[j];

}

else

{

for(j=0;j

temp[i][j]=memery[j];

}

}

//

compute();

print(count);

}

/*顯示設(shè)計者信息*/

void

designBy()

{

printf(“┏━━━━━━━━━━━━━━━━━━━━━━━━━┓＼n“);

printf(“┃㊣

實驗七：頁面置換算法

㊣┃＼n“);

printf(“┃

學(xué)號：1001010042

┃＼n“);

printf(“┃

姓名：黃浩全

4.9.9.0>┃＼n“);

printf(“┣━━━━━━━━━━━━━━━━━━━━━━━━━┫＼n“);

}

實驗過程中遇到的問題解決辦法與實驗體會Q4（需手寫，10分）

得分：

1、在FIFO算法可以很容易用數(shù)組實現(xiàn)，而LRU算法可以用數(shù)組實現(xiàn)，不過用結(jié)構(gòu)體會更明顯簡單。結(jié)構(gòu)體成員變量可以記錄頁號進入的時間，和最近使用的記錄。相對比數(shù)組更容易理解和實現(xiàn)。

2:首先，F(xiàn)IFO（先進先出）算法和LRU（最近未使用算法）兩者之間，F(xiàn)IFO算法明顯會比LRU容易理解，而且比LRU算法較容易實現(xiàn)，但在性能方面，LRU的確在優(yōu)化方面做的比較理想。再且在考慮頁框和頁表號之間的問題用代碼可以容易模擬，但是真是在物理內(nèi)存塊中是如何實現(xiàn)，那確實是很難以理解，需要真正理解到內(nèi)存內(nèi)部的知識才知道這兩個算法是怎么實現(xiàn)的。

評閱教師特殊評語：

評閱教師：

日

期：