計(jì)算機(jī)工程學(xué)院

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

課程名：《

操作系統(tǒng)原理A

》

題

目：

虛擬存儲器管理

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

班

級：

學(xué)

號：

姓

名：

評語：

成績：

指導(dǎo)教師：

批閱時間：

****年**月**日

一、實(shí)驗(yàn)?zāi)康呐c要求

1.目的：

請求頁式虛存管理是常用的虛擬存儲管理方案之一。通過請求頁式虛存管理中對頁面置換算法的模擬，有助于理解虛擬存儲技術(shù)的特點(diǎn)，并加深對請求頁式虛存管理的頁面調(diào)度算法的理解。

2.要求：

本實(shí)驗(yàn)要求使用C語言編程模擬一個擁有若干個虛頁的進(jìn)程在給定的若干個實(shí)頁中運(yùn)行、并在缺頁中斷發(fā)生時分別使用FIFO和LRU算法進(jìn)行頁面置換的情形。其中虛頁的個數(shù)可以事先給定（例如10個），對這些虛頁訪問的頁地址流（其長度可以事先給定，例如20次虛頁訪問）可以由程序隨機(jī)產(chǎn)生，也可以事先保存在文件中。要求程序運(yùn)行時屏幕能顯示出置換過程中的狀態(tài)信息并輸出訪問結(jié)束時的頁面命中率。程序應(yīng)允許通過為該進(jìn)程分配不同的實(shí)頁數(shù)，來比較兩種置換算法的穩(wěn)定性。

二、實(shí)驗(yàn)說明

1．設(shè)計(jì)中虛頁和實(shí)頁的表示

本設(shè)計(jì)利用C語言的結(jié)構(gòu)體來描述虛頁和實(shí)頁的結(jié)構(gòu)。

pn

pfn

time

pn

pfn

next

虛頁結(jié)構(gòu)

實(shí)頁結(jié)構(gòu)

在虛頁結(jié)構(gòu)中，pn代表虛頁號，因?yàn)楣?0個虛頁，所以pn的取值范圍是0—9。pfn代表實(shí)頁號，當(dāng)一虛頁未裝入實(shí)頁時，此項(xiàng)值為-1；當(dāng)該虛頁已裝入某一實(shí)頁時，此項(xiàng)值為所裝入的實(shí)頁的實(shí)頁號pfn。time項(xiàng)在FIFO算法中不使用，在LRU中用來存放對該虛頁的最近訪問時間。

在實(shí)頁結(jié)構(gòu)中中，pn代表虛頁號，表示pn所代表的虛頁目前正放在此實(shí)頁中。pfn代表實(shí)頁號，取值范圍（0—n-1）由動態(tài)指派的實(shí)頁數(shù)n所決定。next是一個指向?qū)嶍摻Y(jié)構(gòu)體的指針，用于多個實(shí)頁以鏈表形式組織起來，關(guān)于實(shí)頁鏈表的組織詳見下面第4點(diǎn)。

2．關(guān)于缺頁次數(shù)的統(tǒng)計(jì)

為計(jì)算命中率，需要統(tǒng)計(jì)在20次的虛頁訪問中命中的次數(shù)。為此，程序應(yīng)設(shè)置一個計(jì)數(shù)器count，來統(tǒng)計(jì)虛頁命中發(fā)生的次數(shù)。每當(dāng)所訪問的虛頁的pfn項(xiàng)值不為-1，表示此虛頁已被裝入某實(shí)頁內(nèi)，此虛頁被命中，count加1。最終命中率=count/20*100%。

3．LRU算法中“最近最久未用”頁面的確定

為了能找到“最近最久未用”的虛頁面，程序中可引入一個時間計(jì)數(shù)器countime，每當(dāng)要訪問一個虛頁面時，countime的值加1，然后將所要訪問的虛頁的time項(xiàng)值設(shè)置為增值后的當(dāng)前countime值，表示該虛頁的最后一次被訪問時間。當(dāng)LRU算法需要置換時，從所有已分配實(shí)頁的虛頁中找出time值為最小的虛頁就是“最近最久未用”的虛頁面，應(yīng)該將它置換出去。

4．算法中實(shí)頁的組織

因?yàn)槟芊峙涞膶?shí)頁數(shù)n是在程序運(yùn)行時由用戶動態(tài)指派的，所以應(yīng)使用鏈表組織動態(tài)產(chǎn)生的多個實(shí)頁。為了調(diào)度算法實(shí)現(xiàn)的方便，可以考慮引入free和busy兩個鏈表：free鏈表用于組織未分配出去的實(shí)頁，首指針為free_head，初始時n個實(shí)頁都處于free鏈表中；busy鏈表用于組織已分配出去的實(shí)頁，首指針為busy_head，尾指針為busy_tail，初始值都為null。當(dāng)所要訪問的一個虛頁不在實(shí)頁中時，將產(chǎn)生缺頁中斷。此時若free鏈表不為空，就取下鏈表首指針?biāo)傅膶?shí)頁，并分配給該虛頁。若free鏈表為空，則說明n個實(shí)頁已全部分配出去，此時應(yīng)進(jìn)行頁面置換：對于FIFO算法要將busy_head

所指的實(shí)頁從busy鏈表中取下，分配給該虛頁，然后再將該實(shí)頁插入到busy鏈表尾部；對于LRU算法則要從所有已分配實(shí)頁的虛頁中找出time值為最小的虛頁，將該虛頁從裝載它的那個實(shí)頁中置換出去，并在該實(shí)頁中裝入當(dāng)前正要訪問的虛頁。

三、程序流程圖

四、主要程序清單

#include

#include

/*全局變量*/

int

mSIZE;

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

int

pSIZE;

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

static

int

memery[10]={0};

/*物理塊中的頁號*/

static

int

page[100]={0};

/*頁面號引用串*/

static

int

temp[100][10]={0};

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

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

void

FIFO();

void

LRU();

void

OPT();

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

void

print(unsigned

int

t);

void

designBy();

void

download();

void

mDelay(unsigned

int

Delay);

/*主函數(shù)*/

void

main()

{

int

i,k,code;

printf(“請輸入物理塊的個數(shù)(M<=10)：“);

scanf(“%d“,&mSIZE);

printf(“請輸入頁面號引用串的個數(shù)(P<=100)：“);

scanf(“%d“,&pSIZE);

puts(“請依次輸入頁面號引用串(連續(xù)輸入，無需隔開)：“);

for(i=0;i

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

download();

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.先進(jìn)先出(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:

OPT();

break;

case

4:

system(“cls“);

//system(“color

0A“);

exit(0);

default:

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

}

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

getchar();

}

while

(code!=4);

getchar();

}

/*載入數(shù)據(jù)*/

void

download()

{

printf(“＼nFinish.＼n載入成功!“);

}

/*設(shè)置延遲*/

void

mDelay(unsigned

int

Delay)

{

unsigned

int

i;

for(;Delay>0;Delay--)

{

for(i=0;i<124;i++)

{

printf(“

＼b“);

}

}

}

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

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“);

}

/*計(jì)算過程延遲*/

void

compute()

{

int

i;

printf(“正在進(jìn)行相關(guān)計(jì)算，請稍候“);

for(i=0;i++<30;printf(“＼b“));

for(i=0;i++<30;printf(“

“));

for(i=0;i++<30;printf(“＼b“));

}

/*先進(jìn)先出頁面置換算法*/

void

FIFO()

{

int

memery[10]={0};

int

time[10]={0};

/*記錄進(jìn)入物理塊的時間*/

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++;

/*計(jì)算換出頁*/

max=time[0]

for(m=2;m

if(time[m]

max=m;

memery[max]=page[i];

time[max]=i;

/*記錄該頁進(jìn)入物理塊的時間*/

for(j=0;j

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

}

else

{

for(j=0;j

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

}

}

compute();

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++;

/*計(jì)算換出頁*/

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

}

/*最佳置換算法*/

void

OPT()

{

int

memery[10]={0};

int

next[10]={0};

/*記錄下一次訪問時間*/

int

i,j,k,l,m;

int

max;

/*記錄換出頁*/

int

count=0;

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

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

for(i=0;i

{

memery[i]=page[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++;

/*得到物理快中各頁下一次訪問時間*/

for(m=0;m

{

for(l=i+1;l

if(memery[m]==page[l])

break;

next[m]=l;

}

/*計(jì)算換出頁*/

max=next[0]>=next[1]?0:1;

for(m=2;m

if(next[m]>next[max])

max=m;

/*下一次訪問時間都為pSIZE,則置換物理塊中第一個*/

memery[max]=page[i];

for(j=0;j

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

}

}

if(k==mSIZE)

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

{

count++;

/*得到物理快中各頁下一次訪問時間*/

for(m=0;m

{

for(l=i+1;l

if(memery[m]==page[l])

break;

next[m]=l;

}

/*計(jì)算換出頁*/

max=next[0]>=next[1]?0:1;

for(m=2;m

if(next[m]>next[max])

max=m;

/*下一次訪問時間都為pSIZE,則置換物理塊中第一個*/

memery[max]=page[i];

for(j=0;j

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

}

}

五、程序運(yùn)行結(jié)果

①FIFO

②LRU

六、實(shí)驗(yàn)體會

在做該次作業(yè)的時候，通過對課本相關(guān)內(nèi)容的溫習(xí)，以及對自己在網(wǎng)絡(luò)上找到的一些資源的了解。我對操作系統(tǒng)中頁面調(diào)度的算法有了很大程度的了解，加深了對課程上知識的理解，也懂得了如何在程序中將這些算法實(shí)現(xiàn)，在程序中基本上實(shí)現(xiàn)了所要求的算法以及相關(guān)的性能分析，基本上實(shí)現(xiàn)了課程的要求。

這次作業(yè)也暴露了自己在某些方面的不足之處，自己的語言功底有一定的不足，以及一開始對某個算法不夠熟悉，將算法實(shí)現(xiàn)設(shè)計(jì)的比較復(fù)雜，此次自己的程序存在一些思想上的漏洞，反映出此次程序設(shè)計(jì)的要求有了一定的限制。