qingqiufenye.txt

操作系统中请求分页算法

#include<iostream>
using namespace std;
typedef struct
{
	//int key;
	int pagenumber,kuainumber,A,outaddress;  //A是访问字段
	int P,M;  //p是状态位，M是修改位
	//char name;
} records;
typedef records PageTable[100];
typedef records Fast[100];
typedef records Memory[100];
PageTable L;
Fast F;
Memory M;
int length_page,length_fast,volume=1024,memory,countmemory=0,wulikuai[100];
istream & operator >>(istream & stream, records & r)
{
	
	   r.A=0;
	    
	   r.M=0;//修改位都置为0 
       cin>>r.pagenumber;  
	   cin>>r.kuainumber;
       cin>>r.outaddress;
       cin>>r.P;   //0表示在内存，1表示不再内存
	
	return stream;
}

int cm=0;
void Create_PageTable(PageTable & L)
{
	
	cout<<"建立一张页表"<<endl;
	cout<<"输入页表总长度："<<endl;
	cin>>length_page;
	cout<<"输入页的页号，物理块号,外存地址和状态位："<<endl;
	for(int i=0;i<length_page;i++)
	{	cin>>L[i];
     	if(L[i].P==0)
		{
		  M[cm]=L[i];
		  cm++;
		}
	}

		for(int j=0;j<memory;i++)
		{
			if(M[i].kuainumber==wulikuai[j])
				wulikuai[j]=0;
			break;
		}
}


void display_L(PageTable & L)
{
	cout<<"________________________________________________________________________________________________________"<<endl;
	cout<<"页表如下："<<endl;
	for(int i=0;i<length_page;i++)
	{
		if(L[i].P==0)
		{
           cout<<"页号   物理块号   是否在内存   外存地址"<<endl;
		   cout<<" "<<L[i].pagenumber<<"        "<<L[i].kuainumber<<"            "<<"在"<<"          "<<L[i].outaddress<<endl;
		countmemory++;
		for(int j=0;j<memory;j++)
		{
			if(wulikuai[j]==L[i].kuainumber)
				wulikuai[j]=0;
		}
		}
		else 
		{
			cout<<"页号    是否在内存   外存地址"<<endl;
		   cout<<" "<<L[i].pagenumber<<"          "<<"不在"<<"          "<<L[i].outaddress<<endl;

		}


	}
	cout<<"countmemory="<<countmemory<<endl;
	cout<<"________________________________________________________________________________________________________"<<endl;
}
void Create_Fast(Fast & F)
{
	int num=0;
	cout<<"建立一张快表："<<endl;
	cout<<"请输入快表的长度："<<endl;
	cin>>length_fast;
	cout<<"输入要调入页表的页号："<<endl;
	for(int i=0;i<length_fast;i++)
	{
		int k;
		cin>>k;
		for(int j=0;j<length_page;j++)
		{
			if(L[j].pagenumber==k)
			{
				F[num]=L[j];
		    	num++;
				break;
			}	
		}
	}

}


void display_F(Fast & F)
{
	cout<<"________________________________________________________________________________________________________"<<endl;
	cout<<"快表如下："<<endl;
	for(int i=0;i<length_fast;i++)
	{
		if(F[i].P==0)
		{
           cout<<"页号   物理块号   是否在内存   外存地址"<<endl;
		   cout<<" "<<F[i].pagenumber<<"        "<<F[i].kuainumber<<"            "<<"在"<<"          "<<F[i].outaddress<<endl;
		}
		else 
		{
			cout<<"页号   物理块号   是否在内存   外存地址"<<endl;
		   cout<<" "<<F[i].pagenumber<<"        "<<F[i].kuainumber<<"          "<<"不在"<<"          "<<F[i].outaddress<<endl;
		}


	}
cout<<"________________________________________________________________________________________________________"<<endl;
}

void display_M(Memory &M)
{
    cout<<"内存如下："<<endl;
	cout<<"内存中现在有"<<countmemory<<"个页表"<<endl;
	for(int i=0;i<countmemory;i++)
	{
           cout<<"页号   物理块号   外存地址   访问次数"<<endl;
		   cout<<" "<<M[i].pagenumber<<"        "<<M[i].kuainumber<<"          "<<M[i].outaddress<<"         "<<M[i].A<<endl;	
	}
cout<<"________________________________________________________________________________________________________"<<endl;
}

int i1;
void Search(PageTable & L,Fast & F)
{
	int pagenum,pageadd,jurge_xiugai,count=0;
    cout<<"请输入你要查询的页号和页内地址："<<endl;
	cin>>pagenum>>pageadd;

	if(pagenum>length_page)
		cout<<"请求越界!"<<endl;
	 else
	 {
		 cout<<"先搜索快表："<<endl;
		 for(int i=0;i<length_fast;i++)
		 {
			 if(pagenum==F[i].pagenumber)
			 {
cout<<"________________________________________________________________________________________________________"<<endl;
				 cout<<"此页在快表中，所以直接访问快表"<<endl;
			//	 F[i].A++;
				 for(int j=0;j<countmemory;j++)
				 {
					 if(pagenum==M[j].pagenumber)
						 M[j].A++;
				 }
				cout<<"访问的页号对应的物理块是"<<F[i].kuainumber<<endl;
				cout<<"转换成物理地址是："<<F[i].kuainumber*volume+pageadd<<endl;
				cout<<"是否修改？ 0:不修改 1:修改"<<endl;
				 cin>>jurge_xiugai;
				 if(jurge_xiugai==0)
					 cout<<"不修改，不用写回外存"<<endl;
				    else
					{
						F[i].M=1;
						cout<<"修改了，还要写回外存"<<endl;
					} 
cout<<"________________________________________________________________________________________________________"<<endl;
		  break;
			 }
           count++;
		 }

		 if(count==length_fast)
		 {
		cout<<"________________________________________________________________________________________________________"<<endl;
			 cout<<"此页不在快表中，去搜索页表"<<endl;
			 for(int i=0;i<length_page;i++)
			 {
				 if(pagenum==L[i].pagenumber)
				 {
					 if(L[i].P==0)                       //页在内存中
					 {
					cout<<"________________________________________________________________________________________________________"<<endl;
						 cout<<"此页在内存中"<<endl;
						 for(int j=0;j<countmemory;j++)
						 {
							 if(pagenum==M[j].pagenumber)
							 {
								 M[j].A++;
							 }
						 }
						 cout<<"访问的页号对应的物理块是"<<L[i].kuainumber<<endl;
			             cout<<"转换成物理地址是："<<L[i].kuainumber*volume+pageadd<<endl;
                        // L[i].A++;
						 cout<<"是否修改？ 0:不修改 1:修改"<<endl;
				         cin>>jurge_xiugai;
				         if(jurge_xiugai==0)
				     	 cout<<"不修改，不用写回外存"<<endl;
				             else
							 {
					         	F[i].M=1;
					        	cout<<"修改了，还要写回外存"<<endl;
							 }
		cout<<"________________________________________________________________________________________________________"<<endl;
					     break;
					 }
					 else                      //页不在内存中
					 {
					cout<<"________________________________________________________________________________________________________"<<endl;
						 cout<<"此页不在内存中"<<endl;
						 cout<<"产生缺页中断"<<endl;
						 cout<<"保留CPU现场"<<endl;
						 cout<<"从外存中找到缺页"<<endl;

						 if(memory>countmemory)
						 {
							 cout<<"内存未满"<<endl;
							 countmemory++;
							 cout<<"countmemory="<<countmemory<<endl;
							 M[countmemory-1]=L[i];
							 L[i].P=0;
							 M[countmemory-1].A=1;
							 cout<<"此时有物理块";
							 for(int i=0;i<memory;i++)
							 {
								 if(wulikuai[i]!=0)
									 cout<<i<<"  ";
							 }
							 cout<<"可用"<<endl;
							 cout<<"选择一个物理块："<<endl;
							 int wlk;
							 cin>>wlk;
                             M[countmemory-1].kuainumber=wlk;
							 cout<<"访问的页号对应的物理块是"<<M[countmemory-1].kuainumber<<endl;
			                 cout<<"转换成物理地址是："<<M[countmemory-1].kuainumber*volume+pageadd<<endl;
                             wulikuai[wlk]=0;
						 }
						 else
						 {
							 int min=M[0].A;
							 cout<<"内存已满!"<<endl;
							 cout<<"使用LRU置换算法将";
							 for(int z=1;z<countmemory;z++)
							 {
                                  if(min>M[z].A)
									  min=M[z].A;
							 }
							 for( i1=0;i1<countmemory;i1++)
							 {
								 if(M[i1].A==min)
								 {
									 cout<<"页"<<M[i1].pagenumber<<"换出"<<endl;
									 cout<<"所以它对应的物理块"<<M[i1].kuainumber<<"释放，现在可用"<<endl;
									 M[i1].P=1;
									 cout<<"OS命令CPU从外存读取缺页"<<endl;
				                     cout<<"启动I/O硬件"<<endl;
	    		                     cout<<"将这一页放入内存"<<endl;
				                     M[i1]=L[i];
				                     M[i1].A=1;
									 M[i1].kuainumber=L[i].kuainumber;
									 cout<<"访问的页号对应的物理块是"<<M[i1].kuainumber<<endl;
			       cout<<"转换成物理地址是："<<M[i1].kuainumber*volume+pageadd<<endl;
					        	 break;
								 }
							 }
						 }
				  /* cout<<"访问的页号对应的物理块是"<<M[i1].kuainumber<<endl;
			       cout<<"转换成物理地址是："<<M[i1].kuainumber*volume+pageadd<<endl;*/
				   cout<<"是否修改？ 0:不修改 1:修改"<<endl;
			           	 cin>>jurge_xiugai;
				           if(jurge_xiugai==0)
					         cout<<"不修改，不用写回外存"<<endl;
				             else
							 {
					        	F[i].M=1;
					        	cout<<"修改了，还要写回外存"<<endl;
							 }
                   cout<<"________________________________________________________________________________________________________"<<endl;
                   	 }
				 }
			 }

		 }

	 }
	
}

int main()
{
	char jurge='y';
	cout<<"请输入内存中有多少个物理块："<<endl;
	cin>>memory;
	cout<<"此时，物理块"<<endl;
	for(int i=0;i<memory;i++)
	{	wulikuai[i]=i;
	    cout<<i<<"    ";
		cout<<"可用"<<endl;
	}
  Create_PageTable(L);

  display_L(L);
  Create_Fast(F);
  display_F(F);
  display_M(M);
  while(jurge=='y')
  {
      Search(L,F);
	  display_M(M);
	  cout<<"是否继续？ y/n"<<endl;
	  cin>>jurge;
  }
	return 0;
}