操作系统——页面置换算法c++的实现(fifo和lru)
1、首先建立本次实验的流程图:
1、 然后建立储存相应页面的物理块:
struct Physicalblock{
int name;
int nomber;//优先级1,2,3
}pb[10];
其中name表示页面名,nomber在lru算法中起到标记时间的作用
2、 设置一个指针,在fifo算法中指向最老进程
Physicalblock *p=pb;//指向最老进程的指针
3、 因为本程序中需要从文件中进行输出,所以本次实验在源文件夹中设置“data.txt”文件,储存需要用到的页面
执行程序如下:
ifstream openfile("data.txt");
4、 在程序开始时对进程块进行初始化:
ifstream openfile2("data.txt");
while(n1--)
{
if(openfile2.eof())
{
cout<<"引用串已经分配完毕"<<endl;
break;
}
openfile2>>num;
pb[t].nomber=0;
pb[t++].name=num;
}
openfile2.close();
5、 调用fifo算法,在调用时,要先比对是否已经存在相同页面
如果有那么要标记一下,如果没有就将最老的替换掉,并且输出,输出之后将指向最老进程的指针后移
void fifo(int n1)//先进先出置换算法
{
cout<<"使用fifo的置换方法结果为:"<<endl<<"淘汰的为:";
int num,t=1,flag=0,total=0;
ifstream openfile("data.txt");
while(!openfile.eof())
{
flag=0;
openfile>>num;
t++;
if(t>=n1)
{
for(int i=0;i<n;i++)
{
if(num==pb[i].name)
{
flag=1;
}
}
if(flag==0)
{
total++;
cout<<p->name<<" ";
p->name=num;
p++;
if(total%n1==0)
{
p=pb;
}
}
}
}
openfile.close();
cout<<endl<<"缺页的总次数为:"<<total<<endl;
cout<<"缺页率为: "<<(total/(s+0.0))*100<<"%"<<endl<<endl;
}
6、 在lru算法中要设置nomber用以记录每个进程等待的时间,每次替换之前要查找最大的,然后替换一个之后,这个页面的时间就要变为0,其他的要加一
void lru(int n1)//最近久未使用算法
{
cout<<"使用lru的置换方法结果为:"<<endl<<"淘汰的为:";
int num,t=0,flag=0,total=0,count=0;
ifstream openfile("data.txt");
while(!openfile.eof())
{
int max=-999,maxnomber=0,flag=0;//flag=0表示没有一样的,=1表示有一样的
openfile>>num;
count++;
if(count>=n1)
{
for(int i=0;i<n1;i++)//找出最大的
{
if(num==pb[i].name)//检查是否有一样的
{
flag=1;//flag变为1
pb[i].nomber=0;//一样的这个变为0
for(int j=0;j<n1;j++)//其他几个的等待时间加一
{
if(i==j)//除了这个一样的 不用加一
{
continue;
}
else pb[j].nomber++;//其余的都要加一
}
}
if(pb[i].nomber>max)//同时再查找最大的
{
max=pb[i].nomber;
maxnomber=i;//maxnomber标记最大的序号
}
}
if(flag==0)//如果没有一样的
{
cout<<pb[maxnomber].name<<" ";//把淘汰的输出
total++;//总数加一
pb[maxnomber].name=num;//把淘汰的名字换掉
pb[maxnomber].nomber=0;//时间变为0
for(int j=0;j<n1;j++)//除了这个其他的都加一
{
if(j==maxnomber) continue;
else pb[j].nomber++;
}
}
}
}
openfile.close();
cout<<endl<<"缺页的总次数为:"<<total<<endl;
cout<<"缺页率为: "<<(total/(s+0.0))*100<<"%"<<endl;
}
7、 程序源代码如下:
#include<iostream>
#include<fstream>//进行文件读取的库函数
using namespace std;
int n,s=0;//n物理块数目,s页面总数
struct Physicalblock{
int name;
int nomber;//优先级1,2,3
}pb[10];
Physicalblock *p=pb;//指向最老进程的指针
void fifo(int n1)//先进先出置换算法
{
cout<<"使用fifo的置换方法结果为:"<<endl<<"淘汰的为:";
int num,t=1,flag=0,total=0;
ifstream openfile("data.txt");
while(!openfile.eof())
{
flag=0;
openfile>>num;
t++;
if(t>=n1)
{ for(int i=0;i<n;i++)
{ if(num==pb[i].name)
{ flag=1; } }
if(flag==0)
{ total++;
cout<<p->name<<" ";
p->name=num;
p++;
if(total%n1==0)
{p=pb;}}}}
openfile.close();
cout<<endl<<"缺页的总次数为:"<<total<<endl;
cout<<"缺页率为: "<<(total/(s+0.0))*100<<"%"<<endl<<endl;
}
void lru(int n1)//最近久未使用算法
{
cout<<"使用lru的置换方法结果为:"<<endl<<"淘汰的为:";
int num,t=0,flag=0,total=0,count=0;
ifstream openfile("data.txt");
while(!openfile.eof())
{
int max=-999,maxnomber=0,flag=0;//flag=0表示没有一样的,=1表示有一样的
openfile>>num;
count++;
if(count>=n1)
{ for(int i=0;i<n1;i++)//找出最大的
{if(num==pb[i].name)//检查是否有一样的
{flag=1;//flag变为1
pb[i].nomber=0;//一样的这个变为0
for(int j=0;j<n1;j++)//其他几个的等待时间加一
{ if(i==j)//除了这个一样的 不用加一
{continue;}
else pb[j].nomber++;//其余的都要加一
} }
if(pb[i].nomber>max)//同时再查找最大的
{max=pb[i].nomber;
maxnomber=i;//maxnomber标记最大的序号
} }
if(flag==0)//如果没有一样的
{cout<<pb[maxnomber].name<<" ";//把淘汰的输出
total++;//总数加一
pb[maxnomber].name=num;//把淘汰的名字换掉
pb[maxnomber].nomber=0;//时间变为0
for(int j=0;j<n1;j++)//除了这个其他的都加一
{if(j==maxnomber) continue;
else pb[j].nomber++;}} }}
openfile.close();
cout<<endl<<"缺页的总次数为:"<<total<<endl;
cout<<"缺页率为: "<<(total/(s+0.0))*100<<"%"<<endl; }
int main()
{
ifstream openfile("data.txt");//打开分页序列
int num,n1,t=0,nomber=1;//num表示数字,n1用来临时取代n
cout<<"系统需要调用的页面有:"<<endl;
while(!openfile.eof())
{s++;
openfile>>num;
cout<<num<<" "; }
cout<<endl;
openfile.close();
cout<<"请输入物理块的个数:"<<endl;
cin>>n; n1=n;
ifstream openfile2("data.txt");
while(n1--)
{if(openfile2.eof())
{cout<<"引用串已经分配完毕"<<endl;
break;}
openfile2>>num;
pb[t].nomber=0;
pb[t++].name=num;}
openfile2.close();
fifo(n);
lru(n);}
IV. 分析和讨论
本次实验输入3个物理块,实验数据为:
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
结果如图所示:
所以可以看出fifo算法的缺页率是比较高的,fifo会使一些页面频繁的被替换掉,导致缺页率较高,二而lru算法缺页率是比较低的,效率要好一些
V. 结论
Fifo算法的原理就是将最先进来hiy的给替换掉,不考虑进程频繁切换进程的后果,lru算法的原理是将最近一段时间内没有访问到的进程给替换掉,也就是lru只考虑最久没有被访问的页面将其替换掉这是两种思路。Fifo算法的缺点很显而易见就是因为它总是优先把先进来的替换掉,如果在一个程序里面交替出现了很多次这样的页面,那么这个页面会不断地把前面的顶替掉因此会出现很多缺页,而lru算法就可以避免这个问题。本次编程时fifo算法相对比较简单,因为只需要设置一个指针,每次往后指就好了,而写lru算法的时候计算每个进程的等待时间是一个挺麻烦的事情,一个不小心就导致全部出错,另外本次要从文件中读取,有好几次从文件中读取之后忘记关闭文件了,也造成了很大的问题。
上一篇: adb环境配置