页面置换算法.cpp

当年上操作系统课后

// 页面置换算法.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream.h>
#include<stdlib.h>
int npage=20;//请求页面数
int mpage=3;//内存中最大页面数
int pagequeue[20];//请求页面队列
int b[20]={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};
int page[10];//内存中页面
int state[10];
int modify[20]={0,1,1,0,1,0,0,1,1,1,1,0,0,1,0,1,0,1,0,2};
float misshit;
int select2=9;
char select1;
int begin;
int i,j;
float missrate;
  struct 
{
 int value[10];
 int state[10];
 int rear;
} queue;
void print();
void init()
{
	int t=0;
	int q=0;
	bool full=false;
	misshit=0;
	begin=0;
   missrate=0;	
  for(i=0;i<mpage;i++)
	  page[i]=-1;
  while(t<npage)
  {
	  bool get=false;
	  for(i=0;i<mpage;i++)
	  {
		  if(page[i]==pagequeue[t])
		  {
			  get=true;
	          state[i]=1;
		  }
	  }
	  if(get==true)
		  printf("页面%d在内存中已经存在，即访问命中!\n",pagequeue[t]);
	  if(get==false)
	  {
		  printf("页面%d在内存中不存在，将其调入内存!\n",pagequeue[t]);
		  page[q]=pagequeue[t];
		  
		 state[q]=1;
		  q++;
	}

	print();
	if(q==3) 
	{
		break;
	}
	t++;
	begin=t;
  }//while
}

void print()
{
	int b;

  for(b=0;b<mpage;b++)
	  if(page[b]!=-1)
	  {
		if(select2==4)
		{
			printf("%d(%d)  \n",page[b],state[b]);
		}
		if(select2==5)
			printf("%d(%d,%d)  \n",page[b],state[b],modify[b]);
			else
		 printf("%d  ",page[b]);
	  }
	  printf("\n");
}

void Optimal()
{
  int t=begin+1;
  while(t<npage)
  {
	  int c=0;
  bool get=false;

  int place[10]={0};
  int longest=0;
  for(i=0;i<mpage;i++)
  {
    if(pagequeue[t]==page[i])
	{
	 get=true;
	}
  }
  if(get==true)
	  printf("\n页面%d 访问命中!\n",pagequeue[t]);
  if(get==false)
  {
    for(i=0;i<mpage;i++)
	{
		  bool have=false;
		for(j=t+1;j<npage;j++)
		{
			if(page[i]==pagequeue[j])
			{
				place[i]=j;
				have=true;
			    break;
			}
		}
		if(have==false)
		{
		  place[i]=100;
		}
	}//for
	for(i=0;i<mpage;i++)
	{

	  if(place[i]>c)
	  {
		  c=place[i];
		  longest=i;
	  }

	}
	printf("页面%d 发生缺页中断!将页面%d 换出页面!\n",pagequeue[t],page[longest]);
	page[longest]=pagequeue[t];
	misshit++;
  }//if
  print();
  t++;
  }//while
   missrate=misshit/npage;
  printf("计算缺页率为： %f\n",missrate);
}
void FIFO()
{
int t=begin+1;
int q=0;
while(t<npage)
{
  bool get=false;
  for(i=0;i<mpage;i++)
  {
    if(pagequeue[t]==page[i])
	{
	 get=true;
	}
  }
  if(get==true)
	  printf("页面%d在内存中已经存在，即访问命中!\n",pagequeue[t]);
   if(get==false)
   {
	   printf("页面%d 发生缺页中断!将页面%d 换出!\n",pagequeue[t],page[q]);
	  page[q]=pagequeue[t];

	  q++;
      misshit++;
   }
  if(q==mpage)
     q=0;
print();
t++;
}//while
   missrate=misshit/npage;
  printf("计算缺页率为： %f\n",missrate);
}

void LRU()
{
  int t=begin+1;
  int time[10]={0};
 for(i=0;i<mpage;i++)
	 time[i]=i;
 while(t<npage)
 {
	 bool get=false;
  for(i=0;i<mpage;i++) 
  {
   if(page[i]==pagequeue[t])
   {
   get=true;
   time[i]=t;
   }
  }
  if(get==true)
	   printf("页面%d在内存中已经存在，即访问命中!\n",pagequeue[t]);
  if(get==false)
  {
    int temp=100;
	int min;
	for(i=0;i<mpage;i++)
	{
	  if(time[i]<=temp)
	  {
		  temp=time[i];
          min=i;
	  }

	}//for
	printf("页面%d 发生缺页中断!将页面%d 换出!\n",pagequeue[t],page[min]);
	page[min]=pagequeue[t];
	time[min]=t;
	misshit++;
 }//if
  print();
   t++;
 }//while
  missrate=misshit/npage;
  printf("计算缺页率为： %f\n",missrate);

}

void Clock()
{
int t=begin+1;
int q=0;

while(t<npage)

{
  bool get=false;
  for(i=0;i<mpage;i++)
  {
    if(pagequeue[t]==page[i])
	{
	 get=true;
	 state[i]=1;
	}
  }
  if(get==true)
	   printf("页面%d在内存中已经存在，即访问命中!\n",pagequeue[t]);
   if(get==false)
   {
	   int n=2;
	   while(n>0)
	   {
	     while(q<mpage)
		   {
	         if(state[q]==0)
			 {
				 printf("页面%d 发生缺页中断!将页面%d 换出!\n",pagequeue[t],page[q]);
	           page[q]=pagequeue[t];
			   state[q]=1;
			   
	           q++;
			   	 if(q==3)
			 {
			 q=0;
			 }
				  
			   get=true;
			   break;
			 }
	        else
			{
		     state[q]=0;
		     q++;
			 if(q==3)
			 {
			 q=0;
			 }
			}//else
		 }//while
		 if(get==true) break;
		 q=0;
         n--;
	   }//whlie
      misshit++;
   }//if
  
print();


t++;
}//while
  missrate=misshit/npage;
  printf("计算缺页率为： %f\n",missrate);

 
}
void  improve_Clock()
{
int t=begin+1;
int q=0;
while(t<npage)
{ 
  bool get=false;
  for(i=0;i<mpage;i++)
  {
    if(pagequeue[t]==page[i])
	{
	 get=true;
	 modify[q]=modify[t];
	 state[i]=1;
	}
  }

  if(get==true)
	  printf("页面%d在内存中已经存在，即访问命中!\n",pagequeue[t]);

   if(get==false)
   {
	   int m=2;
	   while(m>0)
	   {
	   int n=3;
	   while(n>0)
	   {
	     while(q<mpage&&n==3)
		   {
	         if(state[q]==0&&modify[q]==0)
			 {
				 printf("页面%d 发生缺页中断!将页面%d 换出!\n",pagequeue[t],page[q]);
	           page[q]=pagequeue[t];
			   modify[q]=modify[t];
			   state[q]=1;
			  get=true;
	
			   break;
			 }
			  q++;
		
		
	        }//while第一遍循环
		 q=0;
		 while(q<mpage&&n==2)
		 {
		   if(state[q]==0&&modify[q]==1)
		   {
			    printf("页面%d 发生缺页中断!将页面%d 换出!\n",pagequeue[t],page[q]);
		
		   modify[q]=modify[t];
		     page[q]=pagequeue[t];
			 state[q]=1;
		
			  get=true;
			 
			   break;
		   }
		   	   q++;
			  
			
		 }
		 q=0;
		   while(q<mpage&&n==1&&m==2)
		   {
		     state[q]=0;
		      q++;
		
		 }
		 if(get==true) break;
		 q=0;
         n--;
	   }//whlien
	   if(get==true) break;
	   m--;
	   }//whilem
      misshit++;
   }//if
  for(i=0;i<mpage;i++)
  printf("%d(%d,%d)  \n",page[i],state[i],modify[i]);

t++;
}//while

missrate=misshit/npage;
  printf("计算缺页率为： %f\n",missrate);

 
}
void main()
{
	cout<<"是否随机产生页面访问序列？（y/n）";
	cin>>select1;
	if(select1=='y')
	{
		cout<<"通过随机方式，产生的页面访问序列为："<<endl;
	   for(i=0;i<npage;i++)
	   {
	      pagequeue[i]=rand()%7;
		  cout<<pagequeue[i]<<"  ";
	   }
	}
	else
	{

   for(i=0;i<npage;i++)
   {
   pagequeue[i]=b[i];
   }
	}
	cout<<endl;
	cout<<"0:退出"<<endl;
	cout<<"1:最佳置换算法"<<endl;
	cout<<"2:先进先出页面置换算法"<<endl;
	cout<<"3:最近最久未使用置换算法"<<endl;
	cout<<"4:简单Clock置换算法"<<endl;
    cout<<"5:优化Clock置换算法"<<endl;

	printf("请选择置换算法：\n");
	while(select2!=0)
	{
		scanf("%d",&select2);
		printf("\n");
		switch (select2)
		{
		case 1:
			init();
            Optimal();
		    break;
	    case 2:
			init();
			FIFO();
		    break;
	    case 3:
			init();
			LRU();
		    break;
	    case 4:
		    init();
            Clock();
		   break;
	    case 5:
		    init();
            improve_Clock();
		    break;
		}
	}
	
}