实验2源程序.txt

虚拟存储器的实现

#include<iostream>
#include<stdlib.h>
#include<string>
using namespace std;

class linklist; //前视定义，以便使用友元
class node
{
  friend class linklist;     //定义linklist类为友元
  private:
      node * next;           //结点指针
      int page_number;       //页面号
	  int flag;              //标志，是否在主存 
      int mm_number;         //所在主存块号
	  int unit_number;       //单元号
	  int disk_number;       //磁盘位置
	  
  public:
	 
	  node(node *pnext=NULL,int pn=-1,int mmn=-1,int un=-1,int dn=-1)  //构造函数  
	  { 
		  next=pnext;
		  page_number=pn;
		  flag=0;        //设置标志初始值为0，即不在主存
		  mm_number=mmn;        
		  unit_number=un;
		  disk_number=dn;     
	  }
	  
	  ~node(){};    //析构函数      
};

class linklist
{
private:
	node * head;     //头指针
 
public:
	
	linklist()      //构造函数
	{
	   head=new node(NULL,-1,-1,-1,-1);  //构造头结点，设置初值
	  
	}

	
	~linklist(){}   //析构函数

			
	void insert(int pn,int mmn,int un,int dn)      //插入一个结点,按页面号从小到大排列
	{
		if(head->next==NULL)   //当前链表为空
		{  
			node * newnode=new node(NULL,pn,mmn,un,dn);
			head->next=newnode;
		}
		else
		{ 
        	node * p=head->next;
			node * pt=head;          //记录指针p的前一个位置
			while(p->page_number<=pn&&p->next!=NULL)   //寻找当前插入结点的位置
			{
				  pt=pt->next;
			      p=p->next;
			}
			if(p->next==NULL&&p->page_number<=pn)         //应该插入的未知结点为最后一个结点
			{
				node * newnode=new node(NULL,pn,mmn,un,dn);
				p->next=newnode;
			}
			else
			{
				node * newnode=new node(p,pn,mmn,un,dn);
			    pt->next=newnode;
			}
		}
		
	}

	
	void show()     //输出当前页表的情况
	{
	    
		if(head->next==NULL)
			cout<<"没有页表!"<<endl;
		else
		{ 
        	cout<<"page_number  flag     mm_number  unit_number  disk_number"<<endl;
		    node * p=head->next;
	    	while(p!=NULL)
			{
			   cout<<"      "<<p->page_number<<"       "<<p->flag<<"          "
				   <<p->mm_number<<"             "<<p->unit_number<<"             "<<p->disk_number<<endl;
		       p=p->next;
			}
            
		}
        
	}

	
	void FIFO()      //FIFO调度算法
	{
        int i=0,j=0,n=0,m=0,a[20],b[20];
		node * p,* pt,* pc,* pct;
				
		for(i=0;i<20;i++)
		{a[i]=rand()%7; 
		 b[i]=-1;
		}
		
		cout<<"任务需要调度的页面号序列如下:"<<endl;
		for(i=0;i<20;i++)  
		{cout<<a[i]<<"  ";}
		cout<<endl;
        cout<<endl;

		for(i=0;i<20;i++)
		{
			cout<<"--------------------------------RUN----------------------------------"<<endl;
			p=pc=head->next; 
			pt=pct=head;
			while(p->page_number!=a[i])      //寻找当前的页面
			{p=p->next;pt=pt->next;}

			if(p->flag==1)      //未发生缺页中断
			{
				cout<<"当前调用页面为:"<<p->page_number<<"   "<<"未发生缺页中断"<<endl;
				cout<<"绝对地址为:"<<p->mm_number<<" * "<<"128"<<" + "<<p->unit_number<<" = "<<p->mm_number*128+p->unit_number<<endl;
				cout<<endl;
				show();
			}

			else                           //发生缺页中断
			{
                j++;                       //缺页中断次数加1
				b[j-1]=a[i];               //记录缺页中断的页面
				
				if(j<=4)
				{
					while(pc->flag==1)
					{pc=pc->next;pct=pct->next;}
					
					p->mm_number=j-1;
					p->flag=1;

					if(p->next==NULL)
					{pt->next=NULL;p->next=pct->next;pct->next=p;}
					else
					{pt->next=p->next;p->next=pct->next;pct->next=p;}
				}
				else
				{   
					n=j;
					if(n%4==0)
						n=4;
					else
						n=n%4;
                    
					for(m=1;m<n;m++)
					{pct=pct->next;pc=pc->next;}
					
					p->mm_number=pc->mm_number;
					p->flag=1;
					pc->flag=0;
					pc->mm_number=-1;
                                        
					if(p->next==NULL)
					{pt->next=NULL;
					 p->next=pct->next;
					 pct->next=p;
					
					 p->next=pc->next;
					 pc->next=NULL;
					 pt->next=pc;
					}
					else
					{pt->next=p->next;
					 p->next=pct->next;
					 pct->next=p;
					
                     p->next=pc->next;
					 pc->next=pt->next;
				 	 pt->next=pc;
					}

					

				}
				p=head->next;
				while(p->page_number!=a[i])
				{p=p->next;}

                cout<<"当前调用页面为:"<<p->page_number<<"   "<<"发生缺页中断,采用FIFO调度"<<endl;
				cout<<"绝对地址为:"<<p->mm_number<<" * "<<"128"<<" + "<<p->unit_number<<" = "<<p->mm_number*128+p->unit_number<<endl;
				if(j>4) 
				{cout<<"淘汰页面为:"<<b[j-5]<<endl;}
				cout<<endl;
				show();
			}
		}
		cout<<"-----------------------------END-------------------------------"<<endl;
		cout<<"发生缺页中断的次数为:"<<j<<endl;
		cout<<"发生缺页中断的页面为:";
		for(i=0;i<j;i++)
		{cout<<b[i]<<"  ";}
		cout<<endl;
		cout<<"所淘汰页面为:";
		for(i=0;i<j-4;i++)
		{cout<<b[i]<<"  ";}
		cout<<endl;
		cout<<"缺页中断率为:"<<5*j<<"%"<<endl;
	}


	
	void clear()    //释放空间
	{
		node * p=head->next;
		delete head;
		while(p->next!=NULL)
        delete p;
	}

};


void main()
{
	 linklist page;
	 int pn,mmn,un,dn;
	 for(int i=0;i<7;i++)
	 {
		 pn=i;
		 mmn=-1;
		 un=rand()%10;
		 dn=rand()%10;
		 page.insert(pn,mmn,un,dn);
	 }
	 
	 cout<<"主存划分为4块，块号为0号~3号，块大小为128字节"<<endl;
     cout<<"共有7个页面，页面号为0号~6号，每页信息如下:"<<endl;

	 page.show();
     page.FIFO();
	 page.clear();
	 
}