请求分页.cpp

操作系统的页面置换算法,FIFO,LRU

//#include "stdafx.h"

 #include   <iomanip.h>
#include <windows.h>
#include "stdio.h"
#include "iostream.h"
#include "stdlib.h"
#include "time.h"

//________________顺序栈定义_________________
#define maxsize 10	
typedef struct             
{
	int pagelistID[maxsize];
	int top;
}seqstack;
seqstack *seq;//顺序栈指针 
//_______________几个全局变量________________
int memory[8][8];//模拟内存，为后面位示图用
int backup[50][2];
int backbit[8][8];
int count=0;//backup得计数器
int pagelength;//页表长度  6
int memorylength;//块数目等于栈数目 3/4
int pagesize;//每页大小 1k/4k
/*FIFO*/		/*LRU*/
int lakepage=0,lakepageLRU=0;//缺页.lake缺**
int visit=0,visitLRU=0;;//访问次数
int hit=0,hitLRU=0;//命中次数
int replace=0,replaceLRU=0;//置换次数
//-------------扩充页表带状态标志位----------------------
typedef struct 
{
	int physical;//物理块号就是位示图中的块号
	int sign;//状态标志
	int physicalLRU;//LRU
	int signLRU;//LRU状态标志
}pagelist;
pagelist *page;//页表的指针
      
//-----------------------------------------------


void menu()
{
	cout<<"\t**********************************"<<endl;
	cout<<"\t*********请求分页实验二***********"<<endl;
	cout<<"\t*********叶相延  20063838*********"<<endl;
	cout<<"\t**********************************"<<endl;
}
void BitShow(int a[8][8])//位示图  8*8矩阵 1行为1  剩下七行随即
{
	cout<<"\n\t*******示位图******"<<endl;
	cout<<"       第0 1 2 3 4 5 6 7 列\n"<<endl;
    for(int i=0;i<8;i++)
	{
		cout<<i<<"行\t";
        for(int j=0;j<8;j++)
		{
	        cout<<" "<<a[i][j];
		}
	    cout<<endl;
	}
}

void chushihua()
{
	srand( (unsigned)time( NULL ) ); //以系统时间作为随机数种子
	int i,j;
//_________________位示图初始化______________________________________
	for(i=1;i<8;i++)//行
	{
     for(j=0;j<8;j++)//列
	 {
		 memory[0][j]=1;//0为1
	     memory[i][j]=rand()%2;//其他行为随即数
	 }
	}
				//-------------------位示图备份--------------------------------
	for(i=0;i<8;i++)
	{
		for(j=0;j<8;j++)
		{
			backbit[i][j]=memory[i][j];
		}
	}

//____________________创建页表数据________________________________
	cout<<"\n\t初始化页表数据.......\n";
	cout<<"\n\t输入页表长度(max=10):";
	cin>>pagelength;//页表长度
	cout<<"\n\t输入内存块数:";
	cin>>memorylength;//栈长度=内存块数
	cout<<"\n\t输入页大小,单位KB:";
	cin>>pagesize;//页长度
	cout<<endl;	
//___________________动态分配空间________________
	seq=new seqstack;
	page=new pagelist[pagelength];
//____________________________________________________________
	for(i=0;i<pagelength;i++)//长度小于pagelength循环初始化
	{//页号   物理块号 状态位
		page[i].sign =0;//初始化页没有进入内存全部置为0
		page[i].physical=-1;//-1表示空,没有对应的物理块
		page[i].signLRU=0;//初始化页没有进入内存全部置为0
		page[i].physicalLRU=-1;//-1表示空,没有对应的物理块
	}	
	
	for(i=0;i<memorylength;i++)//小于栈长度,栈置空
	{   
	seq->pagelistID[i]=-1;
	}
	seq->top=-1;
}

void chushihuaLRU()
{
	int i;
	seq->top=-1;
	for(i=0;i<pagelength;i++)
	{
		page[i].signLRU=0;
		page[i].physicalLRU=-1;
	}
}

void displaym()//内存和页表,显示函数
{
	cout<<"\n******************************\n";
	cout<<"\t页表\t\n";
	cout<<"**********************************\n";
	cout<<"页号"<<"\t"<<"物理块号"<<"\t"<<"状态位"<<"\t"<<endl;	
	for(int i=0;i<pagelength;i++)
	{
		cout<<i<<"\t"<<dec<<page[i].physical<<"\t\t"<<dec<<page[i].sign <<endl;
	}
	cout<<"\n******************************\n";
	cout<<"内存/栈内"<<endl;
	cout<<" ￣￣￣￣￣ ￣￣￣￣￣"<<endl;
	cout<<"|   栈号   |   页号   |"<<endl;
	for(i=seq->top;i>=0;i--)
	{
	cout<<"|__________|__________|"<<endl;
	cout<<"|     "<<i<<"    |     "<<dec<<seq->pagelistID[i]<<"    |\n";
	}
	cout<<"|__________|__________|"<<endl;
}

void displaymLRU()//内存和页表,显示函数LRU
{
	cout<<"\n******************************\n";
	cout<<"\t LRU页表\t\n";
	cout<<"**********************************\n";
	cout<<"页号"<<"\t"<<"物理块号"<<"\t"<<"状态位"<<"\t"<<endl;	
	for(int i=0;i<pagelength;i++)
	{
		cout<<i<<"\t"<<dec<<page[i].physicalLRU<<"\t\t"<<dec<<page[i].signLRU<<endl;
	}
	cout<<"******************************\n";
	cout<<"内存/栈内"<<endl;
	cout<<" ￣￣￣￣￣ ￣￣￣￣￣"<<endl;
	cout<<"|   栈号   |   页号   |"<<endl;
	for(i=seq->top;i>=0;i--)
	{
	cout<<"|__________|__________|"<<endl;
	cout<<"|     "<<i<<"    |     "<<dec<<seq->pagelistID[i]<<"    |\n";
	}
	cout<<"|__________|__________|"<<endl;
}

void displays(int ps,int pl,int ml,int lp,int vt,int ht,int rep)//缺页等显示函数
{
	cout<<"\n******FIFO页表状态*********\n";
	cout<<"页(内存块)大小KB："<<ps;
	cout<<"\n页表长度："<<pl;
	cout<<"\n内存栈个数："<<ml;
	cout<<"\n缺页数："<<lp;
	cout<<"\n访问次数："<<vt;
	cout<<"\n命中次数："<<ht;
	cout<<"\n置换次数: "<<rep;
	cout<<"\n缺页率："<<lp*100/vt<<"."<<lp*100%vt<<"%";
	cout<<"\n命中率："<<ht*100/vt<<"."<<ht*100%vt<<"%";
}
int changBitShow(int a[8][8])//修改位示图
{
	int i,j;
	for(i=0;i<8;i++)//修改位示图
	{
		for(j=0;j<8;j++)
		{
			if(a[i][j]==0)
			{
				a[i][j]=1;
			    return i*8+j+1;	
			}
		}
	}
     return -1;
}


void FIFO(int pagep,int paged)
{

	int i=0;	

		visit++;//访问增加一次
		if(page[pagep].sign==1)
		{
			cout<<"\t**********\n";
			cout<<"\t***命中***\n";
			cout<<"\t**********\n";
			hit++;
		}//命中+1
		else 
		{	
			cout<<"\n**************\n";
			cout<<"***发生缺页***\n";
			cout<<"**************\n";
			lakepage++;
			page[pagep].sign=1;//修改占用标志
			if(seq->top<memorylength-1)//栈不满
			{
				seq->top++;
				seq->pagelistID[seq->top]=pagep;//页号入栈
				page[pagep].physical=changBitShow(memory);
				BitShow(memory);//改位示图
			}
			else 
			{
				replace++;
				page[seq->pagelistID[0]].sign =0;
				int x;
				x=page[seq->pagelistID[0]].physical;
				page[seq->pagelistID[0]].physical=-1;
				for(i=0;i<seq->top;i++)
				{seq->pagelistID [i]=seq->pagelistID[i+1];}
				page[pagep].physical=x;				
				seq->pagelistID [seq->top]=pagep;								
			}
		}
		cout<<"*****逻辑地址："<<hex<<pagesize*1024*pagep+paged;		
		cout<<"\n*****物理地址:"<<hex<<pagesize*1024*(page[pagep].physical)+paged;
		displaym();
		return;
	
}
void LRU(int pagep,int paged)
{
	int temp;

		visitLRU++;//访问增加一次
		if(page[pagep].signLRU==1)//在内存
		{
			cout<<"\n***********\n";
			cout<<"***命中***\n";
			cout<<"**********\n";
			hitLRU++;
			int i=0;
			while(i<=seq->top)
			{
				if(seq->pagelistID[i]==pagep)break;
				i++;
			}
			while(i<seq->top)
			{
				temp=seq->pagelistID[i];
				seq->pagelistID[i]=seq->pagelistID[i+1];
				seq->pagelistID[i+1]=temp;
				i++;
			}
		}
		else//不在内存
		{
			cout<<"\n**************\n";
			cout<<"***发生缺页***\n";
			cout<<"**************\n";
			lakepageLRU++;
			page[pagep].signLRU=1;//修改占用标志
			if(seq->top<memorylength-1)//栈不满
			{
				seq->top++;
				seq->pagelistID[seq->top]=pagep;//页号入栈
				page[pagep].physicalLRU=changBitShow(backbit);//改位示图
				BitShow(backbit);
			}
			else
			{
				replaceLRU++;
				page[seq->pagelistID[0]].signLRU=0;
				int x,i;
				x=page[seq->pagelistID[0]].physicalLRU;
				page[seq->pagelistID[0]].physicalLRU=-1;
				for(i=0;i<seq->top;i++)
				{seq->pagelistID[i]=seq->pagelistID[i+1];}
				page[pagep].physicalLRU=x;				
				seq->pagelistID[seq->top]=pagep;								
			}
		}		
		cout<<"逻辑地址：\n"<<hex<<pagesize*1024*pagep+paged;		
		cout<<"\n物理地址：\n"<<hex<<pagesize*1024*(page[pagep].physicalLRU)+paged;
		displaymLRU();
		return;

}
void main()
{


	menu();
//	
	char c='0';
	int logicadd;//逻辑地址
	int pagep,p;//页号
	int paged,d;//页内地址
	while(c!='#')
	{
	chushihua();
	char s='0';


	while(s!='#')
	{
		cout<<"输入逻辑地址(16位):";
		cin>>hex>>logicadd;
		cin.get();
		pagep=logicadd/(pagesize*1024);//页号
		paged=logicadd%(pagesize*1024);//偏移量
		while(pagep>pagelength-1)
		{
			cout<<"输入逻辑地址*越界*,重新输入........\n";
			goto loop;
		}
		backup[count][0]=pagep;//保存页号
		backup[count][1]=paged;//页内偏移地址
		count++;		
loop:	cout<<"按#结束输入,按其他键继续.....................\n";

	s=cin.get();   
	}
	BitShow(memory);
	cout<<"输入的逻辑地址，将要访问页号为：\n";
	for(int i=0;i<count;i++)
	{
		cout<<backup[i][0]<<"\t";
	}
	cout<<"\n*************************FIFO算法显示*******************************\n";
	for(i=0;i<count;i++)
	{
		p=backup[i][0];
		d=backup[i][1];
		FIFO(p,d);
		system("pause");
	}
	displays(pagesize,pagelength,memorylength,lakepage,visit,hit,replace);	
	cout<<"\n***********FIFO算法显示完毕，按任意键继续LRU************************\n";
	cout<<"\n***************************LRU算法显示*********************************\n";
	chushihuaLRU();
	system("pause");
	for(i=0;i<count;i++)
	{
		p=backup[i][0];
		d=backup[i][1];
		LRU(p,d);
		system("pause");
	}
	displays(pagesize,pagelength,memorylength,lakepageLRU,visitLRU,hitLRU,replaceLRU);
	cout<<"运算完毕,本次请求分页即将结束,如继续进行,请按任意键.....\n退出请按'#'.......\n";

	cin>>c;   
	system("cls");
	}

}