页面置换算法实验报告

《操作系统--页面置换算法》

实验报告

姓 名： 范学升

学 号：1001050903

班 级：电科10-1班

专 业：电子信息科学与技术

一、实验目的

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

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

3．通过对几种置换算法页面的比较，来对比他们的优缺点，并通过比较更换频率来对比它们的效率。

二、实验内容：

设计一个虚拟存储区和内存工作区，并使用下述算法来模拟实现页面的置换：

1. 先进先出的算法（FIFO）

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

3. 最佳置换算法（OPT）

三、实验分析

在进程运行过程中，若其所访问的页面不存在内存而需要把它们调入内存，但内存已无空闲时，为了保证该进程能够正常运行，系统必须从内存中调出一页程序或数据送磁盘的对换区中。但应调出哪个页面，需根据一定的算法来确定，算法的好坏，直接影响到系统的性能。

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

假设分给一作业的物理块数为3 ，页面数为20个。

页面号为(20个)：

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

1．先进先出(FIFO)置换算法的思路

该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面，按照先后次序连接成一个队列，并设置一个替换指针，使它总指向最老的页面。

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

最近久未使用置换算法的替换规则，是根据页面调入内存后的使用情况来进行决策的。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间，当需淘汰一个页面的时候选择现有页面中其时间值最大的进

行淘汰。

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

其所选择的被淘汰的页面，奖是以后不使用的，或者是在未来时间内不再被访问的页面，采用最佳算法，通常可保证获得最低的缺页率。

4．数据结构

struct pageInfor

{

int content;//页面号

int timer;//被访问标记

};

class PRA

{

public:

PRA(void);

int findSpace(void); //查找是否有空闲内存

int findExist(int curpage); //查找内存中是否有该页面

int findReplace(void); //查找应予置换的页面

void display(void); //显示

void FIFO(void); //FIFO算法

void LRU(void); //LRU算法

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

pageInfor * block; //物理块

pageInfor * page; //页面号串

private:

};

5．FIFO页面置换算法

当需要访问一个新的页面时，首先调用findExist(i)函数来查看物理块中是否就有这个页面，若要查看的页面物理块中就有，则调用display函数直接显示，不需要替换页面；如果要查看的页面物理块中没有，就需要寻找空闲物理块放入，若存在有空闲物理块，则将页面放入；若没有空闲物理块，则调用findReplace函数替换页面。并将物理块中所有页面timer++。

6．LRU页面置换算法

当需要访问一个新的页面，首先调用findExist(i)函数查看物理块中是否就有这个页面。

7. OPT页面置换算法

当需要访问一个新的页面，首先调用findExist(i)函数来查看物理块中是否有这个页面。

8．寻找置换页面函数findReplace比较三个物理块中的时间标记timer，找到时间最久的。

四、源程序结构分析

1． 程序结构

程序共有以下九个部分：

int findSpace(void);//查找是否有空闲内存

int findExist(int curpage);//查找内存中是否有该页面

int findReplace(void);//查找应予置换的页面

void display(void);//显示

void FIFO(void);//FIFO算法

void LRU(void);//LRU算法

void OPT(void);//OPT算法；

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

int main() //主程序

2． 源程序代码

#include

#define Bsize 3

#define Psize 20

struct pageInfor

{

int content;//页面号

int timer;//被访问标记

};

class PRA

{

public:

PRA(void);

int findSpace(void);//查找是否有空闲内存

int findExist(int curpage);//查找内存中是否有该页面

int findReplace(void);//查找应予置换的页面

void display(void);//显示

void FIFO(void);//FIFO算法

void LRU(void);//LRU算法

void Optimal(void);//OPTIMAL算法

void BlockClear(void);//BLOCK恢复

pageInfor * block;//物理块

pageInfor * page;//页面号串

private:

};

PRA::PRA(void)

{

int QString[20]={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};

block = new pageInfor[Bsize];

for(int i=0; i{

block[i].content = -1;

block[i].timer = 0;

}

page = new pageInfor[Psize];

for(i=0; i{

page[i].content = QString[i];

page[i].timer = 0;

}

}

int PRA::findSpace(void)

{

for(int i=0; iif(block[i].content == -1)

return i;//找到空闲内存，返回BLOCK中位置

return -1;

}

int PRA::findExist(int curpage)

{

for(int i=0; iif(block[i].content == page[curpage].content)

return i;//找到内存中有该页面，返回BLOCK中位置

return -1;

}

int PRA::findReplace(void)

{

int pos = 0;

for(int i=0; iif(block[i].timer >= block[pos].timer)

pos = i;//找到应予置换页面，返回BLOCK中位置

return pos;

}

void PRA::display(void)

{

for(int i=0; iif(block[i].content != -1)

cout<cout<}

void PRA::Optimal(void)

{

int exist,space,position ;

for(int i=0; i{

exist = findExist(i);

if(exist != -1)

{ cout<<\"不缺页\"<else

{

space = findSpace();

if(space != -1)

{

block[space] = page[i];

display();

}

else

{

for(int k=0; kfor(int j=i; j{

if(block[k].content != page[j].content)

{ block[k].timer = 1000; }//将来不会用，设置TIMER为一个很大数

else

{

block[k].timer = j;

break;

}

}

position = findReplace();

block[position] = page[i];

display();

}

}

}

}

void PRA::LRU(void)

{

int exist,space,position ;

for(int i=0; i{

exist = findExist(i);

if(exist != -1)

{

cout<<\"不缺页\"<block[exist].timer = -1;//恢复存在的并刚访问过的BLOCK中页面TIMER为-1

}

else

{

space = findSpace();

if(space != -1)

{

block[space] = page[i];

display();

}

else

{

position = findReplace();

block[position] = page[i];

display();

}

}

for(int j=0; jblock[j].timer++;

}

}

void PRA::FIFO(void)

{

int exist,space,position ;

for(int i=0; i{

exist = findExist(i);

if(exist != -1)

{cout<<\"不缺页\"<else

{

space = findSpace();

if(space != -1)

{

block[space] = page[i];

display();

}

else

{

position = findReplace();

block[position] = page[i];

display();

}

}

for(int j=0; jblock[j].timer++;//BLOCK中所有页面TIMER++

}

}

void PRA::BlockClear(void)

{

for(int i=0; i{

block[i].content = -1;

block[i].timer = 0;

}

}

void main(void)

{

cout<<\"|----------页 面 置 换 算 法----------|\"<cout<<\"|---power by wangxinchuang(080501228)---|\"<cout<<\"|-------------------------------------|\"<cout<<\"页面号引用串:7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1\"<cout<<\"----------------------------------------------------\"<cout<<\"选择<1>应用Optimal算法\"<cout<<\"选择<2>应用FIFO算法\"<cout<<\"选择<3>应用LRU算法\"<cout<<\"选择<0>退出\"<int select;

PRA test;

while(select)

{

cin>>select;

switch(select)

{

case 0:

break;

case 1:

cout<<\"Optimal算法结果如下:\"<test.Optimal();

test.BlockClear();

cout<<\"----------------------\"<break;

case 2:

cout<<\"FIFO算法结果如下:\"<test.FIFO();

test.BlockClear();

cout<<\"----------------------\"<break;

case 3:

cout<<\"LRU算法结果如下:\"<test.LRU();

test.BlockClear();

cout<<\"----------------------\"<break;

default:

cout<<\"请输入正确功能号\"<break;

}

}

}

五 、实验结果

1运行后的初始界面

2 opt算法 3.FIFO算法 4LRU算法