力U4H2總

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

（2023/2023學(xué)年第1學(xué)期）

課程名稱操作系統(tǒng)原理

實(shí)驗(yàn)名稱實(shí)驗(yàn)6：頁面置換算法模擬

實(shí)驗(yàn)時(shí)間2023年12月10日

指導(dǎo)單位軟件工程系

指導(dǎo)教師楊健

學(xué)生姓名班級(jí)學(xué)號(hào)

學(xué)院（系）軟件工程系專

計(jì)算機(jī)軟件與服務(wù)外包

業(yè)

實(shí)驗(yàn)名稱實(shí)驗(yàn)l：Linux操作、使用、編程與進(jìn)程創(chuàng)建指導(dǎo)教師楊健

實(shí)驗(yàn)類型實(shí)驗(yàn)實(shí)驗(yàn)學(xué)時(shí)2實(shí)驗(yàn)時(shí)間2023.12.10

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

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

2.掌握虛擬存儲(chǔ)請(qǐng)求頁式存儲(chǔ)管理中幾種基本頁面置換算法的基本思想，

并至少用三種算法來模擬實(shí)現(xiàn)。

3.通過對(duì)幾種置換算法頁面的比較，來對(duì)比他們的優(yōu)缺陷，并通過比較更

換頻率來對(duì)比它們的效率。

二、實(shí)驗(yàn)環(huán)境（實(shí)驗(yàn)設(shè)備）

Windows2023

Visua1Studio

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

設(shè)計(jì)一個(gè)虛擬存儲(chǔ)區(qū)和內(nèi)存工作區(qū)，并使用下述算法來模擬實(shí)現(xiàn)頁面的置

換：

1.先進(jìn)先出的算法（FIFO）

2.最近最久未使用算法（LRU）

3.最佳置換算法（OPT）

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

在進(jìn)程運(yùn)營過程中，若其所訪問的頁面不存在內(nèi)存而需要把它們調(diào)入內(nèi)

存，但內(nèi)存已無空閑時(shí)，為了保證該進(jìn)程可以正常運(yùn)營，系統(tǒng)必須從內(nèi)存中

調(diào)出一頁程序或數(shù)據(jù)送磁盤的對(duì)換區(qū)中。但應(yīng)調(diào)出哪個(gè)頁面，需根據(jù)一定

的算法來擬定，算法的好壞,直接影響到系統(tǒng)的性能。

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

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

頁面號(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)存的頁面，即選擇在內(nèi)存中駐留時(shí)間最久的

頁面予以淘汰。該算法實(shí)現(xiàn)簡樸，只需把一個(gè)進(jìn)程已調(diào)入內(nèi)存的頁面，按照

先后順序連接成一個(gè)隊(duì)列，并設(shè)立一個(gè)替換指針，使它總指向最老的頁面。

2.最近久未使用（LRU）置換算法的思緒

最近久未使用置換算法的替換規(guī)則，是根據(jù)頁面調(diào)入內(nèi)存后的使用情況

來進(jìn)行決策的。該算法賦予每個(gè)頁面一個(gè)訪問字段,用來記錄一個(gè)頁面自上

次被訪問以來所經(jīng)歷的時(shí)間，當(dāng)需淘汰一個(gè)頁面的時(shí)候選擇現(xiàn)有頁面中其

時(shí)間值最大的進(jìn)

行淘汰。

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

其所選擇的被淘汰的頁面,獎(jiǎng)是以后不使用的，或者是在未來時(shí)間內(nèi)不

再被訪問的頁面,采用最佳算法，通常可保證獲得最低的缺頁率。

4.FIFO頁面置換算法

當(dāng)需要訪問一個(gè)新的頁面時(shí)，一方面調(diào)用findExist（i）函數(shù)來查看

物理塊中是否就有這個(gè)頁面，若要查看的頁面物理塊中就有，則調(diào)用displ

ay函數(shù)直接顯示,不需要替換頁面;假如要查看的頁面物理塊中沒有,就需

要尋找空閑物理塊放入，若存在有空閑物理塊，則將頁面放入；若沒有空閑

物理塊，則調(diào)用findRep1ace函數(shù)替換頁面。并將物理塊中所有頁面tim

er++o

5.LRU頁面置換算法

當(dāng)需要訪問一個(gè)新的頁面，一方面調(diào)用findExist(i)函數(shù)查看物理塊中

是否就有這個(gè)頁面。

6.OPT頁面置換算法

當(dāng)需要訪問一個(gè)新的頁面，一方面調(diào)用findExist(i)函數(shù)來查看物

理塊中是否有這個(gè)頁面。

7.尋找置換頁面函數(shù)findReplace比較三個(gè)物理塊中的時(shí)間標(biāo)記tim

er,找屆時(shí)間最久的。

代碼

ttinclude<stdio.h>

#include<std1ib.h>

#include<time.h>

#defineBLOCKJIAX_SIZE20〃最?大洙?物?理;t?塊d大洙？小？

enum{FIFO=1,LRU,OPT);

structnode_page{

intaddress；〃指?令?地?址?

intpage_num;//頁？面?號(hào)？

intnext_order;//T?一？次?訪？問6的？次?序b

}*Page;

//物？理;I?塊6定“義？

typedefstructBlockNode{

intpage_index;〃page數(shù)筋組哩？的？下？標(biāo)括？

struetBiockNode*next;

}B1ockNode;

struct{

int1ength;〃當(dāng)獺？前。物?理;t?塊。長Q度。

intmiss_flag;//缺d?頁？標(biāo)括？志？,?若?為al,?則。缺d?頁?

intmiss_count;//缺d?頁？次?數(shù)筋

BlockNode*front;

BlockNode*rear;

(Block;

〃本?程i序。中D全？局?變?量？名？均U由？兩？個(gè)?單蹋？詞洙?組哩？成a?且。開a頭？字?母?大洙?寫'

intBlocksize=5;//物?理;t?塊6大洙？小？

intPageCount=200;〃頁？面？總哩？數(shù)筋

intPageSize=1024;〃頁?面?大洙？小？

intAddrRange=8*1024;//訪？問6地？址-范？圍§

intget_num(intdown,intup)〃得?到?一?個(gè)?down?up之?間？的?整?數(shù)籥

(

intnum;

charstr[ill]；

while(l){

fgets(str,111*sizeof(int),stdin);

num=atoi(str);//把？字?符？串？中D的？數(shù)觴字?轉(zhuǎn)墻換?為a整？數(shù)觴

if(num>=down&&num<=up)

break；

print"”輸？入?范？圍§有鼠誤6,請(qǐng)?重?新？輸?入?:〃)；

}//while

returnnum;

I

voidinit_b1ock()//構(gòu)1造i一？個(gè)？空？的？物？理;t?塊。隊(duì)6歹ij

(

B1ock.rear=Block.front=(B1ockNode*)ma11oc(sizeof(BlockNode))；

if(IBiock.front){

printf("內(nèi)U存?分?配?失骸?敗悒？\n〃)；

exit(0);

)

B1ock.1ength=0;

Block.miss_count=0;

Block,rear->next=NULL;

)

voidenqueue(intpage_index)〃入？隊(duì)6

B1ockNode*nodc=(BlockNode*)mal1oc(sizeof(BlockNode))；

if(!node){

printf(?'內(nèi)口存?分?配?失骸？敗悒？\n〃);

exit(0);

}

node->page_index=page_index;

node->next=NULL;

Block.length++;

Block,rear->next=node;

Biock.rear=node;

I

voiddequeue()//出？隊(duì)6

(

BiockNode*node；

node=Block.front—>next;

Biock.front->next=node->next;

if(node==B1ock.rear)

B1ock.rear=Block,front;

free(node);

Block,length一一；

voidclear_block()〃清？空?物？理;l?塊6

{

while(Block,rear=Block.front->next){

Block.front->next=Block.rear—>next;

free(B1ock.rear)；

B1ock.1ength—;

}

B1ock.rear=Block.front；

B1ock.length=0；

Block,miss_count=0；

}

voiddestroy_block()//銷口毀Ci物?理;i?塊6

{

while(Block.rear=B1ock.front){

Block.fron『Block.front->next;

free(Block,rear);

)

free(page);

)

voidinit_page()//初？始？化~頁？面？系U列

inti,j；

srand(time(NULL))；//用？當(dāng)獺?前。系U統(tǒng)?時(shí)骸？間？來"初？始?化-隨？機(jī)。種?子哩？

page=(structnode_page*)malloc(PageCount*sizeof(structnode_page));

for(i=0;i<PageCount;i++){

page[i].address=rand()%AddrRange；

page[i].page_num=page[i].address/PageSize;

)

for(i=0;i<PageCount;i++){

for(j=i+1;j<PageCount;j++){

if(page[i].page_num==page[j].page_num){

page[i].nextorder=j;

break;

}//if

}//for

if(j==PageCount)〃說口明+page[i]以?后。都?不？會(huì)d再(i訪？問6

page[i].next_order=PageCount;

}//for

)

voidprint_page()〃打洙？印？頁？面？系H歹U

(

inti;

pr1ntf(??????????\n)；

printf(〃頁？面？系u列為a：毗\n");

for(i=0;i<PageCount；i++){

printfC/[%—2d,%-4d]*,Page[i].page_num,page[i].address%PageSize);

if((i+1)%5==0){

printf('\n");

}//if

)

printf(〃\n〃)；

!

voidFIFO_Replace(intpage_index)〃FIFO置？換？

(

BlockNode*node;

if(!B1ock.length){

enqueue(page_index);

B1ock.miss_flag=0;

return;

}

node=Block.front;

while(node=node->next){

if(page[node—>pageindex],pagenum二二page[page_index].pagenum){

Block.miss_flag=0；

return;

)

)

if(Block.Iength<BlockSize){

enqueue(page_index)；

Block.miss_f1ag=0;

return;

}

dequeue()；

enqueue(page_index);

Biock.missf1ag=1;

B1ock.miss_count++;

)

voidLRU_Replace(intpage_index)//LRU置?換？

(

BiockNode*node,*last_node;

if(IBlock.length){

enqueue(page_index);

Biock,miss_f1ag=0;

return;

}

last_node=node=Block.front；

while(node=node->next){

if(page[node->page_index],page_num==page[page_index].page_num){

last_node->next=node->next;

B1ock.length;

if(node==B1ock.rear)

Block.rear=lastnode；

enqueue(node->page_index);

free(node)；

BIock.miss_f1ag=0；

return;

}

last_node=node;

}

if(Block.length<BiockSize){

enqueue(page_index);

B1ock.miss_flag=0；

return；

(

dequeue();

enqueue(page_index);

Block,miss_flag=1；

Block,misscount++;

)

voidOPT_Replace(intpage_index)//0PT置？換？

(

BlockNode*node;

B1ockNode*max_node,*max_node_1ast;

if(!Block.length){

enqueue(pageindex)；

B1ock.miss_flag=0;

return;

}

node=Block.front;

while(node=node—>next){

if(page[node->page_index],page_num==page[page_index].page_num){

node->page_index=page_index;

Block,miss_flag=0;

return;

I

)

if(Block.1ength<BlockSize)(

enqueue(pageindex)；

Block.miss_f1ag=0;

return;

)

node=Block,front；

max_node=node->next;

while(node二node->next){//尋°找6Block中Dnextorder值u最？大洙？的？節(jié)口點(diǎn)？

if(page[max_node->page_index].next_order<page[node->page_index].next_order)

max_node=node;

I

node=Block.front;

max_node_last=node;

while(node=node->next){〃尋°找。B1ock中Dnext_order值H最?大洙？的?節(jié)U點(diǎn)？的?上？一？個(gè)?節(jié)U

點(diǎn)？

if(node=max_node)

break;

max_node_1ast=node；

)

maxnodelast->next=maxnode->next;

B1ock.1ength—;

if(max_node==Biock.rear)

B1ock.rear=max_node_last；

free(maxnode);

enqueue(page_index);

Block,miss_f1ag=1;

B1ock.miss_count++;

)

voidpage_replace(intnum)

{

inti,j;

BiockNode*node;

charstr[3][5]={"FIFO",〃LRU”，MOPT”);

printf("======================%s=========================\n^,str[num-1]);

printf("頁?面?號(hào)?*〃)；

for(i=0；i<BlockSize：i++)

printf("〃)；

printfC*是？否？缺d?頁?*\n");

for(i=0；i<PageCount;i++){

printf("%-4d*〃，page[i].page_num);

if(num==FIFO)

FIFORep1ace(i);

elseif(num==LRU)

LRU_Replace(i);

e1seif(num==OPT)

OPTReplace(i);

node=Block,front;

whi1e(node=node—>next)

printf(0%-2d“、page[node—>page_index].page_num);

for(j=Block.1ength;j<B1ockSize；j++)

printf(*'");

printfC*%s*\n\nH,(Biock.miss_flag-l?"Yes":"No"));

)

prjntf(〃\n~-\n〃)*

printf("缺d?頁？數(shù)第：%d，缺d?頁？率6:%%%.2f\n\nz/,Block,miss_count,(float)Block.miss_cou

nt/PageCount*100);

printf(〃按恪？回？車u鍵ti繼i續(xù)？！\n\n");

getchar();

)

voidconfige()〃程i序6設(shè)??置？

(

intnum;

while(l){

printf("\n***************************************************\口")；

printf(zz*程i序6設(shè)??置？*\n〃);

ppintf("***************************************************\n");

printfC*1,設(shè)@?置?物?理之？塊6大洙?小？(默?認(rèn)？5)*\n〃)；

printf(〃*2,設(shè)??置？訪？問6地?址?范？圍§(默?認(rèn)?8K)*\n〃)；

printf(〃*3,設(shè)??置?頁？面？大洙？小？(默?認(rèn)？1K)*\n〃)；

printfC*4,設(shè)@?置？頁？面？總哩？數(shù)筋(默？認(rèn)?200)*\n");

printf(〃*5,顯?示？各小項(xiàng)?設(shè)@?置？值u*\n");

printf("*6,返5?回？*\n");

printf("***************************************************\n〃)；

printf("請(qǐng)?輸？入?您U的?選?擇？:〃)；

num=get_num(l,6);

if(num==6)

break;

if(num==1){

printf("請(qǐng)?輸?入?物?理;t?塊6大洙?小？(l,%d):〃，BL0CK_MAX_SIZE);

BlockSize=get_num(l,BL0CK_MAX_SIZE);

printf("設(shè)@?置?成6功|!\n\n”);

)//if

elseif(num=二2){

printf(〃請(qǐng)？輸？入?訪？問6地?址?范？圍§(r%d)K:\999);

AddrRange=get_num(1,999)*1024;

printf("設(shè)??置?成6功|!\n\n〃);

}//elseif

elseif(num==3){

printf(〃請(qǐng)?輸?入？頁？面？大洙?小？(1?%d)K：”，AddrRange/1024)；

PageSize=getnum(l,AddrRange/1024)*1024;

printf("設(shè)@?置？成6功I!\n\n");

}//eIseif

elseif(num=4){

printf(〃請(qǐng)？輸?入?頁?面?總哩?數(shù)jg(l1%d):〃，32767);

PageCount=get_num(l,32767);

printf("設(shè)??置？成6功！\n\n*');

}//else!f

elseif(num==5){

printfC\n〃)；

printf(〃*當(dāng)獺？前。物?理;t?塊6大洙？小？：%d\n\BlockSize);

printf(〃*當(dāng)獺？前。訪？問6地?址?范？圍§:%dK\n*,AddrRange/1024)；

printf(〃*當(dāng)獺？前。頁?面?大洙?小？:%dK\nH,PageSize/1024)；

printf(〃*當(dāng)獺?前。頁？面?總哩?數(shù))B%d\n",PageCount);

priniI\\n),

)

)

free(page);

init_page();

)

voidbegin()

intnum;

printpage()；

whi1e(l){

printf(〃\n***************************************************\n")；

printf(H*頁？面?置？換？算？法?*\n〃)；

printf(〃***************************************************\n");

printff*1,先省進(jìn)？先◎出？置？換？算？法而？FIFO)*\n〃)；

printf(〃*2,最?近(1最？久？未'使？用？置?換？算?法"LRU)*\n〃)；

printf(〃*3,最？佳？置?換？算?法力？OPT)*\n〃)；

printf("*4,返5?回？*\n");

printf("***************************************************\n11)；

Printf(〃請(qǐng)?輸？入？您U的？選?擇？：");

num=get_num(1,4);

if(num==4)

break；

page_rep1ace(num)；

clearblock();

I

free(page);

init_page();

)

intmain()

intnum;

init_b1ock();

init_page();

while(1){

printf("\n***************************************************\n")；

printf("*存?儲(chǔ)沮?器+管U理;t?模￡擬2系口統(tǒng)?*\n”)；

printf("***************************************************\n〃)；

printfC*1,進(jìn)?入?頁？面?置?換?算?法

printfC*2,進(jìn)?入?程i序6設(shè)??置？*\n”)；

printfC*3,退？出？*\n");

printf(〃***************************************************\n");

printf(〃請(qǐng)?輸?入?您U的？選?擇?:");

num=get_num(1,3)；

if(num-3)

break;

if(num-1)

begin0;

elseif(num==2)

confige();

)

destroyb1ock();

return0；

i

j

截圖

[1,96H3,1005][4,222][2,627][4,748]

[6,648H7,654H2,24H6,20][6,5151

[5,899][2,591][4,114][0,289][2,443]

[5,39H2,934][5,660H0,121][1,492J

[0,667][0,552][3,163H4,1019][0,780]

[6,575][3,104][7,980][5,70][1,381]

[5,549][1,881][6,303][1,196][2,6501

[7,727][4,903JC6,355][4,505][1,1002]

[3,110][6,906][2,302][?,133][1,550]

[5,258][0,293H7,714H6,795][5,261

[5,568][0,951JC3,544][2,741][0,649]

[2,1018][3,1020][3,674][3,927][7,775]

[7,549][2,892H2,852][?,103][7,715]

[0，116][0,1006][5,851][?,536][5,923]

*頁面置換算法*

進(jìn)

置

1先出

?SW-

近

未翻翻墨嬴,

2久

薯

?覆

佳

算

3換

■法〈

回OPT)*

4*

，

1*57421*No*

6*74216*Ves*

0*42160*Ves*

0*42160*No*

0*42160*No*

7*21607*Ves*

6*21076*No*

2*10762*No*

7*10627*No*

缺頁數(shù)：70,缺頁率:Z35.00

按回車鍵繼續(xù)？

1*07241工No*

6*07216*Ves*

0*07216*No*

0*07216*No*

0*07216*No*

7*07216*No*

6*07216*No*

2*07216*No*

7*07216*No*

24\r<xr~~/xr<\MMW?VMX/wxNvrf\rtfxr?\rtf\r~?w\nxrtfw\r~?\r<xMXNxr?vr?vw>~~~tfsr?Mi~fvw*\M\rifxrrw\r?xrtfw\r~~

缺頁數(shù)：3i,缺頁率:Z15.50

按回車鍵繼續(xù)？

存儲(chǔ)器管理模擬系統(tǒng)*

1，進(jìn)入頁面置擅算法*

2,進(jìn)入程序設(shè)置*

3,退出*

請(qǐng)輸入您的選擇：2

程序設(shè)置*

卷

大

置

設(shè)

1理?M

人

置

：

設(shè)

2間

大8v8K>*

置

火

設(shè)

面

3頁)

總*

置

設(shè)

面1K0

4頁

警