cpp1.cpp

FIFO置换算法的模拟程序

****FIFO算法**** 
程序设计思想：通过定义一个队列实现先进先出算法。
**********************************************/
#include<iostream>
using namespace std;
typedef struct QNode{  //定义一个结点，包含一个数据和指向下一个结点的指针
	int data;
	struct QNode * next;
}QNode,*QueuePtr;
typedef struct{          //定义队列的头
    QueuePtr front;
	QueuePtr rear;
}LinkQueue;
void InitQueue(LinkQueue &Q){//初始化队列
	Q.front=Q.rear=new QNode;
	if(!Q.front){
		cout<<"OVERFLOW!"<<endl;
		return ;
	}
	Q.front->next=NULL;
}
void EnQueue(LinkQueue & Q,int e){ //将e插入队列队尾
	QueuePtr p1=new QNode;
	if(!p1){
		cout<<"OVERFLOW!"<<endl;
		return ;
	}
	p1->data=e; 
	p1->next=NULL;
	Q.rear->next=p1;
	Q.rear=p1;
}
void DeQueue(LinkQueue & Q){ //删除队头元素
	if(Q.front==Q.rear)
		return ;
	QueuePtr p2=new QNode;
	p2=Q.front->next;
	Q.front->next=p2->next;
	if(Q.rear==p2) Q.rear=Q.front;
	delete p2; 
}
int QueueLength(LinkQueue &Q){//计算对列长度函数，返回队列长度
	QueuePtr p3=Q.front;
	int counter=-1;
	while(p3!=NULL){
		p3=p3->next;
		counter++;
	}
	return counter;
}
bool SeQueue(LinkQueue &Q,int e){ //遍历队列，看e是否在队列中，在则返回true
	QueuePtr q=Q.front;
	int flag=0;
	if(Q.front==Q.rear)
		return false;
	else{
	  while(q!=NULL){
	    	if(e==q->data)
		    	flag=1;
			q=q->next;
	  }
	  if(flag==1)
    	return true;
	  else
    	return false;
	}
}
int main()
{
	int count;
	int shiye_num;
	static int queye_count;
	cout<<"==========================================="<<endl;
	cout<<"假设有某一进程将要被系统执行             \n";
	cout<<"                                         \n";
	cout<<"请输入系统为进程分配实页数：";
	cin>>shiye_num;
	cout<<"==========================================="<<endl;
	cout<<"请输入访问页面次数："<<endl;
	cin>>count;
	cout<<"==========================================="<<endl;
	int *ptr=new int [count];
	cout<<"请输入所访问的页面顺序："<<endl;
	for(int i=0;i<count;i++)
	cin>>ptr[i];
	cout<<"==========================================="<<endl;
	LinkQueue L;
    InitQueue(L);
	for(int j=0;j<count;j++){
		if(SeQueue(L,ptr[j])){
			cout<<"******  "<<ptr[j]<<" 页在内存中已经存在。"<<"        ******\n";
			continue;
		}
		else if(QueueLength(L)<shiye_num){
			EnQueue(L,ptr[j]);
			queye_count++;
			cout<<"******  "<<ptr[j]<<" 页直接进入内存实页。"<<"        ******\n";
		}
		else{
            EnQueue(L,ptr[j]);
			DeQueue(L);
			queye_count++;
			cout<<"******  "<<ptr[j]<<" 页进入内存，队首元素被删除。"<<"******\n";
		}
	}
	cout<<"==========================================="<<endl;
	cout<<"利用FIFO算法当系统分配的实页数为"<<shiye_num<<"时\n";
	cout<<"                                         \n";
	cout<<"产生的缺页数为："<<queye_count<<endl;
	cout<<"                                         \n";
	cout<<"从而产生的缺页率为："<<(float)queye_count/count*100<<"%"<<endl;
	cout<<"==========================================="<<endl;
	delete[] ptr;
	return 0;
}