attemper.cpp

操作系统课程设计

#include <iostream.h>
#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define FIFO 0//先进先出
#define LRR  1//最近最少使用
#define LFR  2//最少访问页面
#define NRU  3//最近最不经常使用

//for lfr ,and nru
//作为LFR算法时r表示页面访问的次数，在NRU算法中r表示R位，即最近一个滴答是否有访问
typedef struct{
	int page;//虚拟页面号
	int r;
}Page;


static int dic[320];//320条指令
static int count = 0;//执行的指令条数

int page_used1 = 0;//记录第一种算法中已经使用的物理页面
int page_used2 = 0;//记录第二种算法中已经使用的物理页面
int page_used3 = 0;//记录第三种算法中已经使用的物理页面
int page_used4 = 0;//记录第四种算法中已经使用的物理页面

int hit1 = 0;//采用第一种算法是击中的次数
int hit2 = 0;//采用第二种算法是击中的次数
int hit3 = 0;//采用第三种算法是击中的次数
int hit4 = 0;//采用第四种算法是击中的次数

// pagei指针储存物理页面里存放的虚拟页面号，大小为用户的物理页面数
int* page1;
int* page2;
Page* page3;
int min_page = 0;//最少访问次数的页面所在的物理页面
int min = 1;//最少访问次数 
Page* page4;
int dida = 4;//对于NRU，每dida条指令就检查当前的R位并清0

int N;//用户内存容量 N个页面

//执行一条指令,method表示采用何种算法
void run(int index,int method);

//以下是四种页面置换算法
void fifo(int index);
void lrr(int index);
void lfr(int index);
void nru(int index);

void main()
{
	
	int i;
	cout<<"please input number of pages that user has:";//输入用户的物理内存大小即物理页面数
	cin>>N;

	page1 = new int[N];
	page2 = new int[N];
	page3 = new Page[N];
	page4 = new Page[N];
	//初始化物理页面的存储内容
	for(i = 0;i<N;i++)
		{
		page1[i] = -1;
		page2[i] = -1;
		page3[i].page = -1;
		page3[i].r = 0;
		page4[i].page = -1;
		page4[i].r = 0;
		}

	cout<<"index\t\top\t\tpage\t\tfifo\tlrr\tlfr\tnru"<<endl;

	//在[0~319]随机选取一条指令
	int begin;
	srand((unsigned)time(NULL)); 
	begin = rand()%320;

	//以随机数产生伪指令
	for(i=0;i<320;i++)
		{
		dic[i] = rand()%10000;
		}

	int index1;
	int index2;

	while(count<320)
		{
		for(i=0;i<4;i++)//表示执行每一条指令时都用四种算法去置换页面
			run(begin,i);//顺序部分
		index1 = rand()%(begin+1);
		for(i=0;i<4;i++)
			run(index1,i);//前地址部分
		for(i=0;i<4;i++)
			run((index1+1)%320,i);//顺序部分
		
		index2 = (index1+2) + rand()%(319-index1-1);
		index2 = index2%320;
		for(i=0;i<4;i++)
			run(index2,i);//后地址部分
		
		begin = (index2+1)%320;
	}
	//计算四种算法下各自的命中率
	cout<<"the ration of fifo:"<<(double)hit1/320<<endl;
	cout<<"the ration of lrr:"<<(double)hit2/320<<endl;
	cout<<"the ration of lfr:"<<(double)hit3/320<<endl;
	cout<<"the ration of nru:"<<(double)hit4/320<<endl;
}


void run(int index , int method)
{
	switch(method)
		{
		case FIFO:
			cout<<"["<<index<<"]"<<"\t\t"<<dic[index];
			fifo(index);
			count++;//计算执行的指令条数
			break;
		case LRR:
			lrr(index);break;
		case LFR:
			lfr(index);break;
		case NRU:
			nru(index);break;
		}
	
}

void fifo(int index)//先进先出
{
	int i;
	for(i=0;i<=page_used1-1;i++)
		{
		if((index/10) == page1[i])//计算所在页面，并查询是否击中
			break;
		}
	cout<<"\t\t"<<index/10;
	if(i<=page_used1-1)  //击中
		{
			hit1++;
			cout<<"\t\thit";
		}
	else{                //不击中
		cout<<"\t\t   ";
		if(page_used1<N)  //物理页面还没满，直接加进新页面
			{
			page_used1++; //使用的物理页面数加1
			}
		else{             //物理页面已满
			for(i = 0;i<page_used1-1;i++)//弹出最尾页面page[0]
				{
				page1[i] = page1[i+1];
				}
			}
		page1[page_used1-1] = index/10;//加入最新页面
		}
}

void lrr(int index)//最近最少使用
{
	int i;
	int temp;
	for(i=0;i<=page_used2-1;i++)
		{
		if((index/10) == page2[i])//计算所在页面，并查询是否击中
			break;
		}
	
	if(i<=page_used2-1)  //击中
		{
			hit2++;
			cout<<"\thit";
			temp = page2[i];//记下这一次访问的页面
			for(int j = i;j<page_used2-1;j++)//重排序按最近使用的在头，最近最少使用的页面放在最尾的一页
				{
				page2[j] = page2[j+1];
				}
			page2[page_used2-1] = temp;
		}
	else{                    //不击中
		cout<<"\t   ";
		if(page_used2<N)     //物理页面还没满，直接加进新页面
			{
			page_used2++;    //使用的物理页面数加1
			} 
		else{
			//弹出最尾的页面即page[0]记录的页面
			for(i = 0;i<page_used2-1;i++)
				{
				page2[i] = page2[i+1];
				}
			}
		page2[page_used2-1] = index/10;//加入最新该次需要调入的页面
		
		}
}

//每次替换页面时，找到访问次数最少的页面所在的物理页面，写入新的页面号
void lfr(int index)
{
	int i;
	for(i=0;i<=page_used3-1;i++)
		{
		if((index/10) == page3[i].page)//计算所在页面，并查询是否击中
			break;
		}
	if(i<=page_used3-1)  //击中
		{
			hit3++;
			cout<<"\thit";
			page3[i].r++;//击中页面的访问次数加1
			if(i == min_page)//刚好击中最少访问页面
				{
				min++;
				//遍历使用的物理页面，找出新的最少访问次数和页面所在
				for(int j=0;j<=page_used3-1;j++)
					{
					if(page3[j].r <=min)
						{
						min = page3[j].r;//记录最新的最少访问次数
						min_page = j;//记录最新的最少访问次数的页面所在的物理页面
						}
					}
				}
		}
	else{                    //not hit
		cout<<"\t   ";
		if(page_used3<N)//物理页面还没满
			{
			page_used3++;
			page3[page_used3-1].page = index/10;
			page3[page_used3-1].r = 1;
			if(min>1)//如果之前的最少访问次数大于1
				{
				min_page = page_used3-1;//修改最少访问页面号
				}
			} 
		else{//min_page不变，因为调入的新页访问次数为1，一定是最少的
			page3[min_page].page = index/10;
			page3[min_page].r = 1;
			}
		min = 1;  //最少访问次数改为1
		}
}

void nru(int index)//最近最不经常使用算法，只考虑R位，因为执行指令是一个访问页面过程
{
	int i;
	if((count+1)%dida==0)//每条指令就对所有物理页面存的虚拟页面的R位清0
		{
		for(i=0;i<=page_used4-1;i++)
			{
			page4[i].r = 0;
			}
		}
	for(i=0;i<=page_used4-1;i++)//是否击中
		{
		if((index/10) == page4[i].page)
			break;
		}
	if(i<=page_used4-1)  //击中
		{
			hit4++;
			cout<<"\thit";
			page4[i].r = 1;
		}
	else{               //不击中
		cout<<"\t   ";
		if(page_used4<N)//物理页面还没满
			{
			page_used4++;
			page4[page_used4-1].page = index/10;
			page4[page_used4-1].r = 1;
			} 
		else{
			for(int j=0;j<page_used4;j++)
				{
				if(page4[j].r == 0)//找到第一个R位为0的页面
					{
					break;
					}
				}
			if(j<=page_used4-1)//在找到的第一个R位为0所在的物理页面写入新的虚拟页面，R位重置为1
				{
				page4[j].page = index/10;
				page4[j].r = 1;
				}
			else{             //如果没有R位为0的页面，则置换最尾的页面
				page4[0].page = index/10;
				page4[0].r = 1;
				}
			}
		}
	cout<<endl;
}