操作系统的页面置换C++算法：OPT FIFO LRU CLOC

暴力直接上代码，主要是用了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 ==PageOrder[i])
			{
				 flag = m;
				break;
			}
		}
		//vector<TimeNode>::iterator flag = find(time.begin(),time.end(),PageOrder[i]);
		if (flag<0)
		{
			l++;
			if (time.size()<j)
			{
				p.data = PageOrder[i];
				p.read = 0;
				time.push_back(p);
			}
			else
			{
				for (m=0;m<time.size();m++)				
					if (time[m].read == 0)
					{
						time.erase(time.begin()+m);
						p.data = PageOrder[i];
						p.read = 0;
						time.push_back(p);
						break;
					}			
			}
		}
		else
		{
			time[flag].read = 1;
		}
		//相当于定时器 每调用5个页面全部引用位清0
		if ((i+1)%5 == 0)
		{
			for (m=0;m<time.size();m++)	
				time[m].read = 0;
		}
	}
	return (double)l/PageOrder.size();
}
void PageReplace::Print()
{
	int i;
	printf("页面大小 %d K\n",PageSize);
	printf("输入分配内存块数( 1 ~ %d )\n",PageNum);
	scanf("%d",&i);
	printf("OPT 算法 缺页中断率: %.2f%%\n",OPT(i)*100);
	printf("FIFO 算法 缺页中断率: %.2f%%\n",FIFO(i)*100);
	printf("LRU 算法 缺页中断率: %.2f%%\n",LRU(i)*100);
	printf("CLOCK 算法 缺页中断率: %.2f%%\n",CLOCK(i)*100);
	cout<<endl;	
}

int main()
{
	PageReplace p;
	bool flag=true;
	while(flag)
	{
		cout<<"1. 页面置换实验  0. 退出"<<endl;
		int choice,size;
		cin>>choice;
		switch (choice)
		{
		case 1:
			cout<<"生成新序列"<<endl;
			p.Create();
			cout<<"输入页面大小（1/2/4/8/16）单位 K    按0 退出页面大小选择"<<endl;
			cin>>size;
			while (size)
			{
				p.AddChangePage(size);
				p.Print();
				
				cout<<"输入页面大小（1/2/4/8/16）单位 K    按0 退出页面大小选择"<<endl;
				cin>>size;
			}
			break;
		case 0:
			flag = false;
			break;
		}
	}	
	return 0;
}