操作系统课设页面置换算法
- 格式：doc
- 大小：185.50 KB
- 文档页数：10
沈阳理工大学课程设计专用纸 No1
1 目录
一、课程设计目的及要求 ................................ 1
二、相关知识 .......................................... 1
三、题目分析 .......................................... 2
四、概要设计 .......................................... 3
五、代码及流程 ........................................ 3
六、运行结果 .......................................... 7
七、设计心得 .......................................... 8
八、参考文献 .......................................... 9 沈阳理工大学课程设计专用纸 No1
1 一、课程设计目的及要求
页面置换算法
实验目的：深入掌握内存调度算法的概念原理和实现方法。
设计要求：编写程序实现：1）先进先出页面置换算法（FIFO）
2）最近最久未使用页面置换算法（LRU）
3）最佳置换页面置换算法（OPT）
演示页面置换的三种算法。
二、相关知识
2.1 先进先出（FIFO）算法
这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面，按照先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总指向最老的页面。但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如，含有全局变量、常用函数、例程等的页面，FIFO算法并不能保证这些页面不被淘汰。
2.2 最近最久未使用（LRU）算法
FIFO置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。最近最久未使用（LRU）的页面置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。
2.3 最佳（Optimal）算法
沈阳理工大学课程设计专用纸 No1
2 最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰的页面，将是以后永不使用的，或是在最长（未来）时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人们目前还无法预知一个进程在内存的若干个页面中，哪一个页面是将来最长时间内不再访问的，因而该算法时无法实现的，但可以利用该算法评价其他算法。
三、题目分析
熟悉页面置换算法及其实现。页面置换算法是虚拟存储管理实现的关键，通过本次课程设计理解内存页面调度的机制，在模拟实现FIFO、LRU和OPT几种经典页面置换算法的基础上，比较各种置换算法的效率及优缺点，从而了解虚拟存储实现的过程。
沈阳理工大学课程设计专用纸 No1
3 四、概要设计
4.1进入系统模块。进入登陆界面，输入内存页面数和实际页数。
4.2页面号打印模块。打印输入的页面号。
4.3菜单选择模块。选择相应的页面的置换方式，选择相应的字母，进入相应的功能。
4.4算法模块。选择相应的页面置换算法。
4.5显示输出模块。显示页面被置换的情况。
4.6缺页次数和缺页率模块。计算页面号输入的结果。
4.7退出系统模块。退出置换页面。
五、代码及流程
#include
#define M 40
int N;
struct Pro//内存页的结构体
{
int num,time;
};
int Input(int m,Pro p[M]) //输入函数，输入实际页号和实际页数
{
cout<<"请输入实际页数：";
do
{
cin>>m;
if(m>M)cout<<"数目太多，请重试"<
else break;
}
while(1);
cout<
for(int i=0;i
{
cin>>p[i].num;//num页面号
p[i].time=0;
}
return m;//m代表实际页面走向数
}
void print(Pro* page1) //打印当前内存中存放的页面
{
Pro*page=new Pro[N];//定义一个指针
page=page1;
for(int i=0;i
4 if(page[i].num==-1)
cout<<" ";
else
cout<
cout<
}
int Search(int e,Pro*page1) //查找内存中是否存在要调入的页面
{
Pro*page=new Pro[N];
page=page1;
for(int i=0;i
return -1;
}
int Max(Pro*page1)//找出离现在时间最长的页面
{
Pro*page=new Pro[N];
page=page1;
int e=page[0].time,i=0;
while(i
{
if(e
i++;
}
for(i=0;i
if(e==page[i].time) return i;//找最长时间的下标
return -1;
}
int Compfu(Pro*page1,int i,int t,Pro p[M])//找到最久不使用的页面
{
Pro*page=new Pro[N];
page=page1;
int count=0;
for(int j=i;j
{
if(page[t].num==p[j].num) break;//当前页面开始往后查找在内存中的页帧号
else count++;
}
return count;
}
int main()
{
cout<<"可用内存页面数"<
cin>>N;
Pro p[M]; 沈阳理工大学课程设计专用纸 No1
5 Pro*page=new Pro[N];
char c;
int m=0,t=0;
float n=0;
m=Input(m,p);
do{
for(int j=0;j
{
page[j].num=-1;
page[j].time=2-j;
}
int i=0;
cout<<"f:FIFO页面置换"<
cout<<"l:LRU 页面置换"<
cout<<"o:OPT 页面置换"<
cout<<"按其它键结束"<
cin>>c;
if(c=='f') //FIFO页面置换
{
n=0;//记录缺页数
cout<<"页面置换情况: "<
while(i
{
if(Search(p[i].num,page)>=0) ++i;//找到相同的页面
else
{
n++;
page[t].num=p[i].num;//如果没有找到相同的页，则进行页面替换，缺页数加一
print(page);
t=(++t)%N;
}
}
cout<<"缺页次数: "<
}
if(c=='l') //LRU页面置换
{
n=0;//记录缺页数
cout<<"页面置换情况："<
while(i
{
int k;
k=t=Search(p[i].num,page);
if(t>=0) 沈阳理工大学课程设计专用纸 No1
6 page[t].time=0;
else
{
n++;
t=Max(page);
page[t].num=p[i].num;
page[t].time=0;
}
if(t==0){page[t+1].time++;page[t+2].time++;}
if(t==1){page[2].time++;page[0].time++;}
if(t==2){page[1].time++;page[0].time++;}
if(k==-1) print(page);
i++;
}
cout<<"缺页次数："<
}
if(c=='o')//OPT页面置换
{
n=0;//记录缺页数
while(i
{
if(Search(p[i].num,page)>=0)i++;
else
{
int temp=0,cn;
for(t=0;t
{
if(temp
{
temp=Compfu(page,i,t,p);
cn=t;
}
}
page[cn]=p[i];
n++;
print(page);
i++;
}
}
cout<<"缺页次数："<
}
}
while(c=='f'||c=='l'||c=='o');
return 0;
