页面置换算法实验报告.docx

页面置换算法实验报告.docx

《页面置换算法实验报告.docx》由会员分享，可在线阅读，更多相关《页面置换算法实验报告.docx（32页珍藏版）》请在冰点文库上搜索。

页面置换算法实验报告

操作系统课程设计报告

课程名称：

操作系统课程设计

课程设计题目：

页面置换算法

学院：

计算机科学与技术学院

专业：

科技

小组成员:

庞思慧E01114081

王蒙E01114161

姚慧乔E01114349

朱潮潮E01114408

指导老师：

邱剑锋

1实验目的3

2实验要求3

3实验内容与步骤3

4算法思想4

5模块设计4

6程序设计5

7测试结果7

8结果分析9

9程序代码9

10课程设计小结24

页面置换算法模拟设计

1.实验目的

（1）通过模拟实现几种基本页面置换的算法，了解虚拟存储技术的特点。

（2）掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想，并至少用三种算法来模拟实现。

（3）通过对几种置换算法命中率的比较，来对比他们的优缺点。

2.实验要求

 计算并输出下述各种算法在不同内存容量下的命中率。

A先进先出的算法（FIFO）

B最近最少使用算法（LRU）

C最佳淘汰算法（OPT）

3.实验内容与步骤

（1）通过随机数产生一个指令序列，共320条指令，具体的实施方法是：

A．[0，319]的指令地址之间随机选取一起点M;

B．顺序执行一条指令，即执行地址为M+1的指令；

C．在前地址[0，M+1]中随机选取一条指令并执行，该指令的地址为M’;

D．顺序执行一条指令，其地址为M’+1；

E．在后地址[M’+2，319]中随机选取一条指令并执行；

F．重复A—E，直到执行320次指令。

（2）指令序列变换成页地址流

A.页面大小为1K；

B.用户内存容量为4页到32页；

C.用户虚存容量为32K。

在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：

第0条—第9条指令为第0页（对应虚存地址为[0，9]）；

第10条—第19条指令为第1页（对应虚存地址为[10，19]）；

。

。

。

。

。

。

。

。

。

。

。

。

。

。

。

。

。

。

。

。

。

第310条—第319条指令为第31页（对应虚存地址为[310，319]）；

（3）计算并输出上述各种算法在不同内存容量下的命中率。

命中率=1-缺页次数/页地址流长度

4.算法思想

在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。

但应将哪 个页面调出，须根据一定的算法来确定。

通常，把选择换出页面的算法称为页面置换算法。

一个好的页面置换算法，应具有较低的页面更换频率。

从理论上讲，应将那些以后不再会访问的页面换出，或将那些在较长时间内不会再访问的页面调出。

1.先进先出算法FIFO：

这是最早出现的置换算法。

该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。

该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。

2.最近最久未使用算法LRU（least recently used）：

算法的基本思想：

当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。

该算法的主要出发点是，如果某页被访问了，则它可能马上还被访问。

或者反过来说，如果某页很长时间未被访问，则它在最近一段时间不会被访问。

3.最佳淘汰算法OPT

其所选择的被淘汰的页面将是以后永不使用，或许是未来最长时间内不使用的页面，该算法可保证获得最低的淘汰率，但在实际运用中无法实现，可用来评价其他算法的命中率。

5.模块设计

总模块图

主程序图

6.程序设计

structPro//内存页的结构体

{

intnum；//记录页面号

inttime；//页面从未被利用的时间

};

#defineM320//定义指令条数

ProP[M];//产生的随机指令数组

voidInput（）//产生随机数

{

ints;//随机数

inti;

srand（time（0））;

s=rand（）%M;

//cout<<"\n------------随机产生指令流------------\n";

for（i=0;i

{

p[i].num=s;//任选一指令访问点m

p[i+1].num=p[i].num+1;//顺序执行一条指令

p[i+2].num=（int）（（float）p[i].num*（rand（）/（RAND_MAX+1.0）））;//执行前地址指令m'

p[i+3].num=p[i+2].num+1;//顺序执行一条指令

s=（int）（（float）（319-p[i+2].num）*（rand（）/（RAND_MAX+1.0）））+p[i+2].num;

}

for（i=0;i

{

p[i].time=0;

}

}

intSearch（inte,Pro*page1,intN）//查找内存中是否存在要调入的页面

{

intt;

Pro*page=newPro[N];

page=page1;

for（inti=0;i

{

t=e/10;

if（t==page[i].num）

returni;

}

return-1;

}

intMax（Pro*page1,intN）//查找最久最久未被使用的页面

{

Pro*page=newPro[N];

page=page1;

inte=page[0].time,i=0;

while（i

{

if（e

i++;

}

for（i=0;i

if（e==page[i].time）returni;//找最长时间的下标return-1;

}

intCompfu（Pro*page1,inti,intt,Prop[M]）//找到最久不使用的页面

{

Pro*page=newPro[N];

page=page1;

intcount=0;

for（intj=i;j

{

if（page[t].num==p[j].num/10）break;//当前页面开始往后查找是否命中内存中的页号

else++count;//内存中的页面下次出现经过的页面数

}

returncount;

}

7.测试结果

选中算法，输入内存数点击计算

点击命中率按钮

点击退出按钮

8.结果分析

理论上，四种替换算法的命中率由高到底排列应该是OPT>LRU>CLOCK>FIFO。

实际上，在内存页面数较少（4~5页面）时，3种算法的命中率差别不大，可是50%左右。

在内存页面为7~25个页面之间时，3种算法的访内命中率大致在52%至87%之间变化。

在内存页面为25~32个页面时，由于用户进程的所有指令基本上都已装入内存，从而命中率已较大。

从而算法之间的差别不大。

9.程序代码

//页面置换算法模拟设计Dlg.cpp:

implementationfile

#include"stdafx.h"

#include"页面置换算法模拟设计.h"

#include"页面置换算法模拟设计Dlg.h"

#ifdef_DEBUG

#definenewDEBUG_NEW

#undefTHIS_FILE

staticcharTHIS_FILE[]=__FILE__;

#endif

/////////////////////////////////////////////////////////////////////////////

//CMyDlgdialog

CMyDlg:

:

CMyDlg（CWnd*pParent/*=NULL*/）

:

CDialog（CMyDlg:

:

IDD,pParent）

{

//{{AFX_DATA_INIT（CMyDlg）

m_iFifo=0;

N=0;

MZL=0.0;

//}}AFX_DATA_INIT

//NotethatLoadIcondoesnotrequireasubsequentDestroyIconinWin32

m_hIcon=AfxGetApp（）->LoadIcon（IDR_MAINFRAME）;

}

voidCMyDlg:

:

DoDataExchange（CDataExchange*pDX）

{

CDialog:

:

DoDataExchange（pDX）;

//{{AFX_DATA_MAP（CMyDlg）

DDX_Control（pDX,IDC_EDIT4,m_suiji2）;

DDX_Control（pDX,IDC_EDIT5,m_yemian）;

DDX_Control（pDX,IDC_EDIT3,m_suiji）;

DDX_Radio（pDX,IDC_RADIO1,m_iFifo）;

DDX_Text（pDX,IDC_EDIT1,N）;

DDX_Text（pDX,IDC_EDIT2,MZL）;

//}}AFX_DATA_MAP

}

BEGIN_MESSAGE_MAP（CMyDlg,CDialog）

//{{AFX_MSG_MAP（CMyDlg）

ON_WM_PAINT（）

ON_WM_QUERYDRAGICON（）

ON_BN_CLICKED（IDC_BUTTON1,OnButton1）

ON_BN_CLICKED（IDC_RADIO1,OnRadio1）

ON_BN_CLICKED（IDC_RADIO2,OnRadio2）

ON_BN_CLICKED（IDC_RADIO3,OnRadio3）

ON_EN_CHANGE（IDC_EDIT2,OnChangeEdit2）

ON_BN_CLICKED（IDC_BUTTON2,OnButton2）

ON_BN_CLICKED（IDC_BUTTON3,OnButton3）

//}}AFX_MSG_MAP

END_MESSAGE_MAP（）

/////////////////////////////////////////////////////////////////////////////

//CMyDlgmessagehandlers

BOOLCMyDlg:

:

OnInitDialog（）

{

CDialog:

:

OnInitDialog（）;

//Settheiconforthisdialog.Theframeworkdoesthisautomatically

//whentheapplication'smainwindowisnotadialog

SetIcon（m_hIcon,TRUE）;//Setbigicon

SetIcon（m_hIcon,FALSE）;//Setsmallicon

//TODO:

Addextrainitializationhere

returnTRUE;//returnTRUEunlessyousetthefocustoacontrol

}

//Ifyouaddaminimizebuttontoyourdialog,youwillneedthecodebelow

//todrawtheicon.ForMFCapplicationsusingthedocument/viewmodel,

//thisisautomaticallydoneforyoubytheframework.

voidCMyDlg:

:

OnPaint（）

{

if（IsIconic（））

{

CPaintDCdc（this）;//devicecontextforpainting

SendMessage（WM_ICONERASEBKGND,（WPARAM）dc.GetSafeHdc（）,0）;

//Centericoninclientrectangle

intcxIcon=GetSystemMetrics（SM_CXICON）;

intcyIcon=GetSystemMetrics（SM_CYICON）;

CRectrect;

GetClientRect（&rect）;

intx=（rect.Width（）-cxIcon+1）/2;

inty=（rect.Height（）-cyIcon+1）/2;

//Drawtheicon

dc.DrawIcon（x,y,m_hIcon）;

}

else

{

CDialog:

:

OnPaint（）;

}

}

//Thesystemcallsthistoobtainthecursortodisplaywhiletheuserdrags

//theminimizedwindow.

HCURSORCMyDlg:

:

OnQueryDragIcon（）

{

return（HCURSOR）m_hIcon;

}

#include

#include

#include

#defineM320

intN;

structPro//内存页的结构体

{

intnum,time;

};

Prop[M];

voidInput（）//输入函数，输入实际页号和实际页数

{

ints;//随机数

inti;

srand（time（0））;//每次运行时进程号不同，用来作为初始化随机数队列的种子

s=rand（）%M;

//cout<<"\n------------随机产生指令流------------\n";

for（i=0;i

{

p[i].num=s;//任选一指令访问点m

p[i+1].num=p[i].num+1;//顺序执行一条指令

p[i+2].num=（int）（（float）p[i].num*（rand（）/（RAND_MAX+1.0）））;//执行前地址指令m'

p[i+3].num=p[i+2].num+1;//顺序执行一条指令

s=（int）（（float）（319-p[i+2].num）*（rand（）/（RAND_MAX+1.0）））+p[i+2].num;

}

for（i=0;i

{

p[i].time=0;

}

/*p[0].num=10;p[1].num=22;p[2].num=33;p[3].num=44;p[4].num=50;

p[5].num=13;p[6].num=32;p[7].num=22;///测试数据1,2,3,4,5,1,3,2fifo5,1,2,4LRU5,1,3,2opt置换1,2,3,5

*/

}

intSearch（inte,Pro*page1,intN）//查找内存中是否存在要调入的页面

{

intt;

Pro*page=newPro[N];

page=page1;

for（inti=0;i

{

t=e/10;

if（t==page[i].num）

returni;

}

return-1;

}

intMax（Pro*page1,intN）//找出离现在时间最长的页面

{

Pro*page=newPro[N];

page=page1;

inte=page[0].time,i=0;

while（i

{

if（e

i++;

}

for（i=0;i

if（e==page[i].time）returni;//找最长时间的下标

return-1;

}

intCompfu（Pro*page1,inti,intt,Prop[M]）//找到最久不使用的页面

{

Pro*page=newPro[N];

page=page1;

intcount=0;

for（intj=i;j

{

if（page[t].num==p[j].num/10）break;//当前页面开始往后查找在内存中的页帧号

else++count;

}

returncount;

}

voidCMyDlg:

:

OnButton1（）

{

//TODO:

Addyourcontrolnotificationhandlercodehere

UpdateData（true）;

Input（）;

//————————地址流————————

CStringstr1,tmp1;

tmp1=str1="";

intk=0,t=0,i=0;

for（i=0;i

{

tmp1.Format（"%-4d",p[i].num）;

str1+=tmp1;

k++;

if（k%16==0）

{

str1+="\n\r\n\r\n\r";

}

}

m_suiji.SetWindowText（_T（str1））;

//————————页面流————————

CStringstr2,tmp2;

tmp2=str2="";

for（i=0;i

{

tmp2.Format（"%-4d",p[i].num/10）;

str2+=tmp2;

k++;

if（k%16==0）

{

str2+="\n\r\n\r\n\r";

}

}

m_suiji2.SetWindowText（_T（str2））;

Pro*page=newPro[N];

for（intj=0;j

{

page[j].num=-1;

page[j].time=j;

}

if（m_iFifo==0）//FIFO页面置换

{

floatn=0;//记录缺页数

inti=0;

CStringstr3,tmp3;

str3="";

m_yemian.SetWindowText（_T（str3））;

while（i

{

if（Search（p[i].num,page,N）>=0）++i;//找到相同的页面

else

{

n++;

page[t].num=p[i].num/10;//如果没有找到相同的页，则进行页面替换，缺页数加一

//——————————

tmp3="";

m_yemian.GetWindowText（_T（str3））;

for（inti=0;i

if（page[i].num==-1）

{

tmp3.Format（"%s",""）;

str3+=tmp3;

}

else

{

tmp3.Format（"%-4d",page[i].num）;

str3+=tmp3;

}

str3+="\n\r\n\r\n\r";

m_yemian.SetWindowText（_T（str3））;

//——————————

t=（++t）%N;

}

}

MZL=1-n/M;

}

if（m_iFifo==1）//LRU页面置换

{

intp2;

floatn=0;//记录缺页数

inti=0;

intt1=t=0;

CStringstr3,tmp3;

str3="";

m_yemian.SetWindowText（_T（str3））;

while（i

{

intk;

k=Search（p[i].num,page,N）;

if（k>=0）

{

page[k].time=0;

for（p2=0;p2

{

if（p2!

=k）

page[p2].time++;

}

}

else

{

if（t1

{n++;

page[t].num=p[i].num/10;//如果没有找到相同的页，则进行页面替换，缺页数加一

++t1;

t++;

page[t].time=0;

//——————————

tmp3="";

m_yemian.GetWindowText（_T（str3））;

for（inti=0;i

if（page[i].num==-1）

{

tmp3.Format（"%s",""）;

str3+=tmp3;

}

else

{

tmp3.Format（"%