首页 > 代码库 > 操作系统的页面置换C++算法:OPT FIFO LRU CLOCK 计算缺页率

操作系统的页面置换C++算法:OPT FIFO LRU CLOCK 计算缺页率

暴力直接上代码,主要是用了vector来实现,有些方法比较费时,不太好,请各位大神斧正。这是个人的作业,大笑  这是代码下载页http://download.csdn.net/detail/l631068264/7644569   里面还有多级反馈队列进程调度的MFC版

#include <iostream>
#include <algorithm>
#include <vector>
#include <stdio.h>
#include <stdlib.h> /*用到了srand函数*/ 
#include <time.h> /*用到了time函数*/ 
using namespace std;

const int AddressSize = 320;//地址数组大小
const int AddressRange = 319;//地址值范围
struct TimeNode{
	int data;//页面序列号
	int read;//引用位
};
class PageReplace{
public:
	void Create();//创建地址序列
	void AddChangePage(int size);//转换为页面序列
	void Print();//打印控制
	PageReplace();
	~PageReplace();
private:
	int PageSize;//页面大小	
	int PageNum;//页面数
	int* Address;//地址数组
	vector< int > PageOrder;//页面序列
	double OPT(int j);//j 是物理块数
	double FIFO(int j);
	double LRU(int j);
	double CLOCK(int j);
};
PageReplace::PageReplace()
{
	Address = new int[AddressSize];
}
PageReplace::~PageReplace()
{
	delete[]Address;
}
void PageReplace::Create()
{
	srand((unsigned)time(NULL));
	int i;
	int Range = AddressRange;
	for (i=0;i<AddressSize;i=i+5)
	{
		Address[i]  = rand()%AddressRange;
		Address[i+1] = Address[i]+1;
		Address[i+2] = rand()%Address[i+1];
		Address[i+3] = Address[i+2]+1;
		//rand%(b-a+1) + a =>[a,b]随机数
		Address[i+4] = Address[i+3]+1+(rand()%AddressRange-Address[i+3]);
	}	
	for (int j=0;j<AddressSize;j++)
	{
		printf("%3d ",Address[j]);
		if ((j+1)%18==0)
		{
			cout<<endl;
		}
	}
	cout<<endl;
}
void PageReplace::AddChangePage(int size)
{   
	//页面大小	K
	PageSize = size;
	int i,j;
	int AddNum_PerPage = 10*PageSize;//每K 10条指令排列虚地址  每页指令数
	PageNum = AddressSize/AddNum_PerPage;//页面数
	for (i=0;i<AddressSize-1;i++)
	{//计算页号
		int m = Address[i]/AddNum_PerPage;		
		int n = Address[i+1]/AddNum_PerPage;
		if (m != n)
		{//序列相邻相同的不要
			PageOrder.push_back(m);
		}		
	}
	for (j=0;j<PageOrder.size();j++)
	{
		printf("%2d ",PageOrder[j]);
		if ((j+1)%20==0)
		{
			cout<<endl;
		}
	}
	cout<<endl;
}
double PageReplace::OPT(int j)
{
	vector<int> opt;//代替内存块
	int i,d2,k;
	double l=0;
	for (i=0;i<PageOrder.size();i++)
	{//缺页判断
		vector<int >::iterator flag = find(opt.begin(),opt.end(),PageOrder[i]);		
		if (flag == opt.end())
		{	
			l++;//缺页数					
			if (opt.size()<j)
			{
				opt.push_back(PageOrder[i]);				
			}
			else
			{//找出当前序列位置 最迟访问
				vector<int>::iterator m = find(PageOrder.begin()+i,PageOrder.end(),PageOrder[i]);
                int max = 0;
				for ( k=0;k<opt.size();k++)
				{										
					vector<int>::iterator n = find(PageOrder.begin()+i,PageOrder.end(),opt[k]);
					if (max < n-m)
					{
						max = n-m;
						d2 = k;//块下标
					}
				}
				opt[d2] = PageOrder[i];
			}
		}
	}
	return (double)l/PageOrder.size();//缺页率	
}

double PageReplace::FIFO(int j)
{	
	int i;
	double l=0;
	vector<int> fifo;

	for (i=0;i<PageOrder.size();i++)
	{
		vector<int >::iterator flag = find(fifo.begin(),fifo.end(),PageOrder[i]);
		if (flag==fifo.end())
		{	
			l++;
			if (fifo.size()<j)
			{
				//头插入
				fifo.push_back(PageOrder[i]);
			}
			else{
				fifo.erase(fifo.begin());
				fifo.push_back(PageOrder[i]);
			}
		}
	}
	return (double)l/PageOrder.size();
}
double PageReplace::LRU(int j)
{	
	vector<int> lru;
	int i;
	double l=0;
	for (i=0;i<PageOrder.size();i++)
	{
		vector<int >::iterator flag = find(lru.begin(),lru.end(),PageOrder[i]);
		if (flag == lru.end())
		{//缺页
			l++;
			if (lru.size()<j)
			{	//头插入
				lru.push_back(PageOrder[i]);
			}
			else{
				lru.erase(lru.begin());
				lru.push_back(PageOrder[i]);
			}
		}
		else
		{//不缺页
			for (int m =0 ;m<lru.size();m++)
			{
				if (lru[m] == PageOrder[i])
				{
					lru.erase(lru.begin()+m);
					lru.push_back(PageOrder[i]);
					break;
				}
			}
		}
	}
	return (double)l/PageOrder.size();
}
double PageReplace::CLOCK(int j)
{
	int i,m,flag;
	double l=0; 
	TimeNode p;
	vector<TimeNode> time;
	for (i=0;i<PageOrder.size();i++)
	{
		for (m=0;m<time.size();m++)
		{
			if(time[m].data =http://www.mamicode.com/=PageOrder[i])>