欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

操作系统——页面置换算法c++的实现(fifo和lru)

程序员文章站 2022-07-12 17:15:15
...

1、首先建立本次实验的流程图:
操作系统——页面置换算法c++的实现(fifo和lru)
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
结果如图所示:
操作系统——页面置换算法c++的实现(fifo和lru)
所以可以看出fifo算法的缺页率是比较高的,fifo会使一些页面频繁的被替换掉,导致缺页率较高,二而lru算法缺页率是比较低的,效率要好一些
V. 结论
Fifo算法的原理就是将最先进来hiy的给替换掉,不考虑进程频繁切换进程的后果,lru算法的原理是将最近一段时间内没有访问到的进程给替换掉,也就是lru只考虑最久没有被访问的页面将其替换掉这是两种思路。Fifo算法的缺点很显而易见就是因为它总是优先把先进来的替换掉,如果在一个程序里面交替出现了很多次这样的页面,那么这个页面会不断地把前面的顶替掉因此会出现很多缺页,而lru算法就可以避免这个问题。本次编程时fifo算法相对比较简单,因为只需要设置一个指针,每次往后指就好了,而写lru算法的时候计算每个进程的等待时间是一个挺麻烦的事情,一个不小心就导致全部出错,另外本次要从文件中读取,有好几次从文件中读取之后忘记关闭文件了,也造成了很大的问题。

相关标签: 操作系统 c++