軟件學院綜合性、設計性實驗報告

專業：java年級/班級：2023級2023—2023學年第一學期

課程名稱計算機操作系統指導教師

學號-姓名-王宇菲

2023-12

實驗地點過街樓B區實驗時間

-23

項目名稱儲存管理實驗類型綜合性/設計性

一、實驗目的

通過請求頁式存儲管理中頁面置換算法模擬程序，了解虛擬存儲技術的特點，掌握

請求頁式存儲管理的頁面置換算法。

二、實驗儀器或設備

實驗機房Pc電腦

三、總體設計(設計原理、設計方案及流程等)

1.通過隨機數產生一個指令序列，共320條指令，指令的地址按下述原則生產：

50%的指令是順序執行的；

25%的指令是均勻分布在前地址部分；

25%的指令是均勻分布在后地址部分。

2.將指令序列變換成為頁地址流

設頁面大小為1K；用戶內存容量為4頁到32頁；用戶虛存容量為32K。

在用戶虛存中，按每K存放10條指令排列虛存地址，即320條指令在虛存中的存

放方式為:第0條至第9條指令為第0頁；第10條至19條指令為第1頁；…第310

條至319條指令為第31頁。

3.計算并輸出下述各種算法在不同內存容量下的命中率。

(1)先進先出算法(FIFO)

(2)最近最少使用算法(LRU)

(3)最佳使用算(OPT)

命中率=1一頁面失效次數/頁地址流長度

本實驗中，頁地址流長度為320,頁面失效次數為每次訪問相應指令時,該指令所相應

的頁不在內存的次數。

。關于隨機數的產生辦法。一方面要初始化設立隨機數，產生序列的開始點，例如，通

過下列語句實現：

srand(400)；

(1)計算隨機數，產生320條指令序列

m=160;

for(i=0;i<80；i++=

(

j=i*4；

a[j]=m;

a[j+l]=m+l;

a|j+2]=a[j]*1.0*rand()/32767；

a[j+3]=aEj+2]+l

m=a[j+3]+(319-a[j+3])*1.0*rand()/32767；

}

(2)將指令序列變換成為頁地址流

for(k=0；k<320;k++)

{pt=aEk]/10；

pd=a[k]%10；

)

(3)計算不同算法的命中率

rate=l-1.0*U/320；

其中U為缺頁中斷次數,320是頁地址流長度。

(4)輸出格式

kfifoIru

40.230.25

321.01.0

四、實驗環節(涉及重要環節、代碼分析等)

1.代碼如下

#include<conio.h>

#include<stdio.h>

ttinclude<stdlib.h>

#include<string.h>

#defineMyprintfprintf("|--+—+11++H+

-+—++++—+++|\n〃)/*表格控制*/

^definebsize4〃物理塊大小

#definepsize16〃進程大小

typedefstructpage

(

intnum；/*記錄頁面號*/

inttime;/*記錄調入內存時間*/

}Page;/*頁面邏輯結構，結構為方便算法實現設計*/

Pageb[bsize];/*內存單元數*/

intc[bsize][psize];/*暫保存內存當前的狀態：緩沖區*/

intqueue[100];/*記錄調入隊列*/

intK;/*調入隊列計數變量*/

intphb[bsize]={0}；//物理塊標號

intpro[psize]={0}；〃進程序列號

intflagEbsize]={0};//進程等待次數(存放最久未被使用的進程標志)

inti=0,j=0,k=0;//i表達進程序列號,j表達物理塊號

intm=-1,n=-1;〃物理塊空閑和進程是否相同判斷標志

intmax=-1,maxflag=0;//標記替換物理塊進程下標

intcount=0；//記錄頁面缺頁次數

!/****************火****火********************,/V**************

****〃

//**************************************************大*********

**〃隨機產生序列號函數

//********TV************************************************

*****

int*buiId()

(

printf(〃隨機產生一個進程序列號為：\n");

?inti=0;

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

(

pro[i]=10*rand()/(RAND_MAX+1)+1;

printfC%d",pro[i]);

}

printf;

return(pro);

)

//**********************************************************

****

〃查找空閑物理塊

|/*************************************************************

*

intsearchpb()

(

ofor(j=0;j<bsize;j++)

(

gif(phb[j]==0)

(

m=j;

3returnm;

break;

｝。

)

oreturn—1;

)

/,/*****************************************************

〃查找相同進程

//*********************************************************

*****

intsearchpro()

(

for(j=0;j<bsize;j++)

if(phb[j]==pro[i])

(

n=j;

。returnj;

)

)

?return-1;

)

//****************************************************

**********

〃初始化內存

//*************************************

不不不*不*****

voidempty()

(

ofor(i=0;i<bsize;i++)

ophb[i]=0;

count=0;//計數器置零

)

Z/*********************************火*********************

***

〃先進先出頁面置換算法

//***********************夫****************************

**********

voidFIF00

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

(

searchpb();

n=searchpro();

//找f1ag值最大的

for(j=0;j<bsize;j++)

(

if(f1ag[j]>maxf1ag)

maxflagflag[j]；

if(n==—1)〃不存在相同進程

if(m!=-1)//存在空閑物理塊

phb[m]=pro[i];//進程號填入該空閑物理塊

8count++;

flag[m]=0；

for(j=0；j<=m;j++)

(

flag[j]++;

}

m=-1；

else〃不存在空閑物理塊

phb[max]=pro[i];

flag[max]=0;

for(j=0;j<bsize;j++)

(

f1ag[j]++；

)

max=-1;

maxflag=0;

count++；

}

)

else//存在相同的進程

(

phb[n]=pro[i];

for(j=0;j<bsize;j++)

(

gflag[j]++;

)

n=-1;

)

for(j=0;j<bsize；j++)

printf(z/%d”,phb[j]);

printf("\n");

)

printf("缺頁次數為:％d\n",count)；

oprintfC\n");

}

/次初始化內存單元、緩沖區*/

voidInit(Page*b,intc[bsize][psize])

(

inti,j;

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

(

b[i].num=-l;

b[i],time=psize-i—1;

)

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

for(j=0；j<psize;j++)

c[i][j]=-1;

}

/*取得在內存中停留最久的頁面，默認狀態下為最早調入的頁面*/

intGetMax(Page*b)

(

inti;

intmax=-1；

inttag=0;

for(i=0;i<bsize；i++)

if(b[i].time>max)

max=b[i].time;

tag=i;

}

)

returntag；

}

/*判斷頁面是否已在內存中*/

intEquation(intfoId,Page*b)

(

inti；

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

I

if(fold==b[i].num)

returni；

)

return—1;

}

/*LRU核心部分*/

voidLruu(intfold,Page*b)

(

inti；

intval;

val=Equation(fold,b);

if(val>=0)

b[va1].time=0;

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

if(i!=val)

b[i].time++;

)

e1se

(

queue[++K]=foId;/*記錄調入頁面*/

val=GetMax(b)；

b[val].num=fold;

b[va1].time=0;

for(i=0;iVbsize;i++)

if(i!=va1)

b[i].time++;

)

)

voidLRU()

(

inti,j;

K=-l；

Init(b,c)；

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

(

Lruu(pro[i],b)；

c[0][i]=pro[i];

/*記錄當前的內存單元中的頁面*/

for(j=0；j<bsize;j++)

c[j][i]=b[j]?num;

)

/*結果輸出*/

printf(〃內存狀態為：\n〃)；

Myprintf;

for(j=0；j<psize;j++)

printfCI%2d"，pro[j]);

printfCI\n〃)；

Myprintf;

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

{for(j=0;j<psize;j++)

(

if(c[i][j]==-1)

printf(〃I%2c”，32);

else

printf(〃I%2d，z,c[i][j]);

)

printf(，zI\n〃)；

)

Myprintf;

printf(〃\n調入隊列為:〃)；

for(i=0;i<K+1;i++)

printfqueue[i])；

printf(〃\n缺頁次數為:%6d\n缺頁率：％16.6f〃,K+l,(f1oat)(K+l)/psi

Ze)；

}

//**********************************************************

****〃主函數

voidmain()

(

<>intse1

Eo{。

eprintf("\t\t\t\t

\t\t〃)；

叩rintf(n\t\t\t☆☆、八歡迎進入操作系統界面八-八☆☆\t\t\t〃)；

t\t\nH)；

Printf("7■讓☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\t\t\t〃)；

printfC\t\t\ti^虛擬內存☆\t\t

\t〃)；

gprintf("\t\t\t☆☆\t\t\t〃)；

叩rintf(〃\t\t\t☆1、產生隨機序列☆\t\t\t，z);

?printf("\t\t☆、t\t

\t〃)；

printf(z，\t\t\!☆2、最久未使用(LRU)☆\t\t

\t");

wprintf(〃\t\t\t^☆\t\t\t〃)；

printf(〃\t\t\t+3^先進先出(FIFO)☆\t\

t\t〃)；

rintf(〃\t\t\t☆☆\t\t\t");

oprintf("\t\t\!.☆4、最佳置換算法(。PT)☆\t\t\t〃)；

oprintf("\t\t\t☆☆

\t\t\t，z);

。printf(，z\t\t\t☆5、三種算法的比較()☆\t\t\t");

oprintf(〃\t\t\t^\t\

t”)；

oprintf(〃\t\t\t☆0、退出(Exit)☆\t

\t\t");

叩rintf(〃\t\t\t\t\t\nz/)；

叩rintf("請選擇所要執行的操作(0/1/2/3/4/5):”)；

scanf("%d"，&se1);

。switch(sei)

g{

bcase0:printf(〃\t\t\t八一人再見!人「\t\t\t\n*');system('*

pause〃);break；