paging.cpp

操作系统——页面置换算法

// paging.cpp: implementation of the paging class.
//
//////////////////////////////////////////////////////////////////////

#include "paging.h"
#include<fstream.h>
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

paging::paging()
{
//	size=10001;
//	data=NULL;

}


paging::paging(char* fn,int _size,int _bsize)
{
	ifstream in(fn,ios::in);	
	if(!in)
	  cout<<"Can not open file!\n";
//	size=13;
//	bsize=4;
//	size=10001;
//	bsize=11;
	size=_size;
	bsize=_bsize;
	data=new com[size];
	block=new com[bsize];
	int i=1;
	lost=0;
	while(in>>data[i].key)	
		i++;
	for(i=1;i<bsize;i++)
	{
		block[i].key=0;
		block[i].tag=0;
	}
}

int paging::findspace(int start)
{
	for(int i=start+1;i<size;i++)
		if(data[i].key==data[start].key)
			return i;
	return size+1;
}


int paging::find(int label1,int start)
{
	for(int i=1;i<bsize;i++)
		if(block[i].key==data[label1].key)
		{		
			return i;
		}
	for(i=start;i<bsize+start;i++)
		if(block[(i-1)%(bsize-1)+1].tag==0)
		{			
			return (i-1)%(bsize-1)+1;
		}
	return -1;
}


void paging::OPT(void)
{
	int position;
	int max;
	for(int i=1;i<size;i++)
	{
		position=find(i,1);
	    if(position!=-1)
		{
			block[position].key=data[i].key;
			block[position].tag=findspace(i);
		}
		else{
			max=1;
			for(int j=1;j<bsize;j++)
			{
				if(block[max].tag<block[j].tag)
					max=j;
			}
			block[max].key=data[i].key;
			block[max].tag=findspace(i);
			lost++;
		}
	}
}
void paging::LRU(void)
{
	int position;
	int k;
	for(int i=1;i<size;i++)
	{
		position=find(i,1);
		if(position!=-1)		
		{
			block[position].key=data[i].key;
//			block[position].tag=(i<bsize)?i:block[position].tag;
//			if(block[position].tag==0)
				block[position].tag=i;
		}
		else{			
/*			for(int j=1;j<i;j++)
			{
				for( k=1;k<bsize;k++)
				{
					if(data[j].key==block[k].key)
						continue;
				}
				break;
			}
			
*/	        k=1;
			for(int j=1;j<bsize;j++)
				if(block[j].tag<block[k].tag)
					k=j;
			block[k].key=data[i].key;
			block[k].tag=i;
//			block[j].tag=findspace(i);
			lost++;
		}
	}
}


void paging::FIFO(void)	
{
	int position,min;
//	int flag=0;
	for(int i=1;i<size;i++)
	{
		position=find(i,1);
		if(position!=-1)
		{
			block[position].key=data[i].key;
			if(block[position].tag==0)
				block[position].tag=i;
			
		}
		else{
			min=1;
			for(int k=1;k<bsize;k++)
			{
				if(block[k].tag<=block[min].tag)
					min=k;
			}			
			block[min].key=data[i].key;
			block[min].tag=i;
			lost++;
//			flag=1;
		}
	}
}

void paging::Clock(void)
{
	int position,recent=1;
	for(int i=1;i<size;i++)
	{
		position=find(i,recent);
		if(position!=-1)
		{
		
			recent=(block[position].tag==0)?recent%(bsize-1)+1:recent;
			block[position].tag=1;	
			if(block[position].key!=data[i].key&&block[position].key!=0)
				lost++;
			block[position].key=data[i].key;
		}
		else{
			for(int j=recent;j<recent+bsize;j++)
					block[(j-1)%(bsize-1)+1].tag=0;
			lost++;
			position=find(i,recent);
			block[position].key=data[i].key;
			block[position].tag=1;
			recent=recent%(bsize-1)+1;

		}
	}
}

void paging::clear()
{
	for(int i=1;i<bsize;i++)
	{
		block[i].key=0;
		block[i].tag=0;
	}
	lost=0;
}


paging::~paging()
{

}