opt.cpp

模拟页式虚拟存储管理中缺页中断理想型淘汰算法1． 随机确定内存大小

// 1.cpp : Defines the entry point for the console application.
//

#include <stdlib.h>
#include <iostream.h>
#define NULL 0

struct pfc_struct{
	int pn;         //页面号
	int vpn;        //页号
	int distance;
	int times;
	pfc_struct*next;
}*free_head,*pft;

struct pcb{
	int vp_num;     //进程的页数
	int p_num;      //分配给进程的页面数
	int *vp;        //访问串
	int name;
    struct pfc_struct*head;   //分配给进程的页面
	struct pcb*next;        
}*p[6],*alloc,*unalloc,*pt;                //进程控制块

int memory;
void change_page(pcb*&p)
{
 int i,n,diseffect;
 bool hit; 
 diseffect=0;
 pft=p->head;
 while(pft!=NULL)
 {
  pft->distance=100;
  pft->vpn=-1;
  pft=pft->next;
  
 }
 cout<<"被淘汰的序列:";	 
 for(i=0;i<4*p->vp_num;i++)
 {
  pfc_struct*temp;
  hit=false;
  n=*(p->vp+i);     // 取要即将访问的页面号
  pft=p->head;  
  while(pft!=NULL)
  {
   if(pft->vpn==n) 
   {
    hit=true;
    break;
   }
    pft=pft->next;
  }
 if(hit==false)
  {
  diseffect++;
  pft=p->head;
  
  while(pft!=NULL)
  { pft->distance=100;
   for(int j=i+1;j<4*p->vp_num;j++)
    if(pft->vpn==*(p->vp+j))
	 {
	  pft->distance=j;
	  break;
	 }
	 
	 pft=pft->next;
  }

  pft=p->head;
  temp=pft; 
  while(pft!=NULL)
  {  
   if(temp->distance<pft->distance)
    temp=pft;
   if(temp->distance==pft->distance)
	 if(temp->times<pft->times)
	  temp=pft;
	pft=pft->next;
  }
   if(temp->vpn!=-1)
    cout<<temp->vpn<<" ";
    temp->vpn=*(p->vp+i);
	temp->times=0;

  pft=p->head;
  temp=pft; 
  while(pft!=NULL)
  {  
    pft->times++;
	pft=pft->next;
  }


 }
  
 }  //for
 cout<<"\n缺页次数:"<<diseffect<<"    缺页率:"<<diseffect/(4.0*p->vp_num);
 pft=p->head;
 while(pft->next!=NULL)
  pft=pft->next;
 pft->next=free_head;
 free_head=p->head;  
 memory=memory+p->p_num;    //收回分配给该进程的内存
 delete p;
}


pcb* get(pcb*&p)
{
   struct pcb* temp;
   if(p->next==NULL)
   {
	 pt=p;
	 p=NULL;
   }
   else
   {
	pt=p;
    temp=p;
    while(pt->next!=NULL)
   {
	temp=pt;
	pt=pt->next;
   }
   temp->next=NULL;     //pt为最后一个进程
  }
  return pt;
}


void main()
{
 int n,temp;
 cout<<"假设页长为1K!\n";   //页长为1K
 cout<<"请输入随机种子:";
 int seed;
 cin>>seed;
 srand(seed);
 memory=rand()%10+1;       //内存大小为1K-10K
 cout<<"内存大小:"<<memory<<"K"<<"  页面数:"<<memory<<"  ";
 free_head=NULL;
 for(int i=1;i<=memory;i++)
 {
  pft=new pfc_struct;
  pft->pn=memory-i;
  pft->vpn=-1;
  pft->next=free_head;
  free_head=pft;
 }

 n=rand()%5+1;             //进程个数为1-5
 cout<<"        进程个数:"<<n<<"\n";
 unalloc=NULL;
 for(i=1;i<=n;i++)
 { 
   p[i]=new pcb;
   p[i]->name=i;
   p[i]->vp_num=rand()%5+2;   //每个进程的页数为2-6
   cout<<"p"<<i<<"的页数:"<<p[i]->vp_num<<"  "; 
   if(memory>0)
   {
	if(memory<=p[i]->vp_num)
	  temp=rand()%memory+1;
	else
	  temp=rand()%p[i]->vp_num+1;
	p[i]->p_num=temp;
    cout<<" 分配的页面数:"<<temp<<"  ";  //随机给每个进程分配页面数
    cout<<"  页面号分别是:";
    p[i]->head=free_head;
    for(int j=1;j<temp;j++)
	{
	 cout<<free_head->pn<<" ";
     free_head=free_head->next;
	}
     cout<<free_head->pn<<" ";
	pft=free_head;
    free_head=free_head->next;
    pft->next=NULL;

    p[i]->next=alloc;
	alloc=p[i];          //加入到已分配队列
   
    memory=memory-temp;
   }
   else
   {
	cout<<"分配的页面数:0  ";
	p[i]->p_num=0;
    p[i]->head=NULL;
	p[i]->next=unalloc;
	unalloc=p[i];               //未分配内存的进程
   }
    
   p[i]->vp=new int[p[i]->vp_num*4];
   cout<<"\n访问串:";
   for(int j=0;j<p[i]->vp_num*4;j++)
   {
	*(p[i]->vp+j)=rand()%p[i]->vp_num;
	cout<<*(p[i]->vp+j)<<" ";
   }
   cout<<"\n";
 }
  
  while(alloc!=NULL||unalloc!=NULL)
  {
   if(alloc!=NULL) 
   {
   pt=get(alloc);
   cout<<"\nP"<<pt->name;
   change_page(pt);
   }
   if(unalloc!=NULL)
	{
	 pt=get(unalloc);
     if(memory>0)
     {
	  if(memory<=pt->vp_num)
	   temp=rand()%memory+1;
	  else
	   temp=rand()%pt->vp_num+1;
	  pt->p_num=temp;
      cout<<"\n分配给进程p"<<pt->name<<"的页面数:"<<temp<<"  "; 
	  cout<<"  页面号分别是:";
      pt->head=free_head;
      for(int j=1;j<temp;j++)
	  {
       cout<<free_head->pn<<" ";
       free_head=free_head->next;
	  }
       cout<<free_head->pn<<" ";
	  pft=free_head;
      free_head=free_head->next;
      pft->next=NULL;

      pt->next=alloc;
	  alloc=pt;          //加入到已分配队列
      memory=memory-temp;
    }

   
   }
  }
  cout<<"\n";	 
 
}