请求页式存储管理-fifo.cpp

请求页式存储管理-FIFO的算法

#include<iostream.h>
#include<stdlib.h>

#define Ye 2048//页面大小为2k
#define Number 128//内存物理块数量

struct Weinode{
	int WSTu[8][16];//用8*16的二维数组来表示内存使用情况，即位示图
	int free;//空闲块的数量
}WeiTu;

struct YeNode{//页表
	int Yehao;//逻辑页号
	int Kuaihao;//物理块号
	int m;//修改位 
	int r;//访问位
};

struct PCB//进程信息
{
	char name;//进程名	
	int Length;//进程长度
	int Logic;//对进程划分的逻辑块起始编号
	int num;//计数页表的项数
    struct YeNode Ybiao[6];//为每一个进程建立一个页表	
	int number;
	struct PCB *link;
};

struct Proc//进程链表头
{
	int n;//记录有多少个进程
	struct PCB *next;
};


//输入进程信息
void InputProc(Proc *P,struct Weinode &WeiTu)
{
	int a=1,j,k,b=0;
	j=k=0;
	struct PCB *h;
	PCB *m=(PCB*)malloc(sizeof(PCB));
	cout<<"输入进程名(一个字符):";
	cin>>m->name;
	cout<<"输入进程长度(整数):";
	cin>>m->Length;
	m->number=a;
	m->num=0;
	a++;
	m->Logic=b;
	b=b+m->Length;	
	for(int i=0;i<6;i++)
	{
		m->Ybiao[i].Kuaihao=0;
		m->Ybiao[i].m=0;
		m->Ybiao[i].r=0;
		m->Ybiao[i].Yehao=0;
	}	
	m->link=P->next;
	P->next=m;
	P->n++;
	h=P->next;
	char flag;
	cout<<"是否要继续添加进程信息：y/n:";
	cin>>flag;	
	while(flag!='n')//建立进程队列
	{
		PCB *t=(PCB*)malloc(sizeof(PCB));
		cout<<"输入进程名(一个字符):";
		cin>>t->name;
		cout<<"输入进程长度(整数):";
		cin>>t->Length;
		t->number=a;
		t->num=0;
		a++;
		t->Logic=b;
	    b=b+t->Length;	
		for(int i=0;i<6;i++)
		{
		m->Ybiao[i].Kuaihao=0;
		m->Ybiao[i].m=0;
		m->Ybiao[i].r=0;
		m->Ybiao[i].Yehao=0;
		}	
		t->link=h->link;
		h->link=t;
		h=t;
		P->n++;   //进程数加一
		cout<<"是否要继续添加进程信息：y/n:";
		cin>>flag;
	}
}
//调入进程到内存,调入一个页面,初始化页表
void DoProcess(Proc *P,struct Weinode &WeiTu)
{
	int a=1,i,j;
	i=j=0;
	PCB *q;
	q=P->next;
	cout<<"**************************************"<<endl;
	cout<<"开始调入进程到内存..........."<<endl;
	while(q)
	{
		cout<<"调入进程"<<q->name<<"到内存......"<<endl;
		q->Ybiao[0].Yehao=q->Logic;
		q->Ybiao[0].Kuaihao=a;
		q->Ybiao[0].m=0;
		q->Ybiao[0].r=0;
		q->num++;
		WeiTu.WSTu[i][j]=1;
		j++;
		if(j>=16)
		{
			i++;
			j=0;
		}
		a++;
		q=q->link;
	}
	cout<<"进程调入完毕..........."<<endl;
	cout<<"******************************************"<<endl;

}


//在内存中寻找空闲块
int SearchFree(struct Weinode &WeiTu)
{	int i,j;
	for(i=0; i<8; i++)
		for(j=0; j<16; j++)
		{
			if(WeiTu.WSTu[i][j]==0)
			{
				WeiTu.WSTu[i][j]=1;
				return (i+1)*(j+1);
			}
		}
		return 0;
}
//如果当前页已经在内存,则返回1,否则返回0,n存放该进程编号
int SearchYe(Proc *P,int YeHao,int &n)
{
	PCB *temp;
	temp=P->next;
	while(temp)
	{
		for(int j=0; j<6; j++)
		{
			if(temp->Ybiao[j].Yehao==YeHao)
			{
				n=temp->number;
				return 1;
			}
		}
		temp=temp->link;
	}
	return 0;
}

//查找该页属于那个进程
int SearchProc(Proc *P,int YeHao,int &m)
{
	PCB *temp;
	temp=P->next;
	while(temp)
	{
		if(temp->Logic<=YeHao && YeHao<=(temp->Logic+temp->Length-1))
		{
			m=temp->number;
			return 1;
		}
		temp=temp->link;
	}
	return 0;
}

//根据输入的指令地址,为指令分配一个物理块,并在页表中建立对应关系,以及访问和修改情况
void LogicToPhysics(Proc *P,struct Weinode &WeiTu)
{
	long int address,dataadr;
	int num,temp=0;
	char answer='y';
	//bool ttp=false;
	while(answer!='n')
	{
		num=0;
		cout<<"请输入指令地址:";
		cin>>address;
		cout<<"MOV AX,";
		cin>>dataadr;
		temp++;
		int n;
		if(SearchYe(P,address/Ye,n)==1)//该页已经调入内存
		{
			PCB *B;
			B=P->next;
			for(int j=1;j<n;j++)//找到该进程
				B=B->link;
			for(j=0; j<6; j++)//在该进程的页表中查找该页
			{
				if(B->Ybiao[j].Yehao==address/Ye)
				{
					cout<<"当前运行的是进程"<<B->name<<endl;
					cout<<"指令地址转换结果为: ";
					cout<<address<<"---"<<(B->Ybiao[j].Kuaihao*Ye+address%Ye)<<"  "<<dataadr<<"---"<<(B->Ybiao[j].Kuaihao*Ye+dataadr)<<endl;
					if(temp>2)//输入指令数为3条后,提示将访问位清零
					{
						cout<<"时钟中断到请将访问位清零"<<endl;
						for(int j=0;j<6;j++)
						{
							if(B->Ybiao[j].r==1)
							{
								cout<<"请将页面"<<B->Ybiao[j].Yehao<<"清零:";
								cin>>B->Ybiao[j].r;
							}
						}
						temp=0;
					}
					break;
				}
			}
		}
	//找到该页所属进程,并调入内存,填写页表
		else
		{ 
			int m;
			if(SearchProc(P,address/Ye,m)==1)
			{
				PCB *T;
				T=P->next;			
				for(int k=1;k<m;k++)
					T=T->link;				
				for(k=0; k<6; k++)//寻找页表中的空闲项
				{
					if(T->Ybiao[k].Yehao==0 && T->Ybiao[k].Kuaihao==0)
					{
						T->Ybiao[k].Yehao=address/Ye;
						T->Ybiao[k].Kuaihao=SearchFree(WeiTu);
						T->Ybiao[k].r=1;
						T->Ybiao[k].m=0;
						T->num++;
						WeiTu.free--;
						cout<<"当前运行的是进程"<<T->name<<endl;
						cout<<"指令地址转换结果为: ";
						cout<<address<<"---"<<(T->Ybiao[k].Kuaihao*Ye+address%Ye)<<"  "<<dataadr<<"---"<<(T->Ybiao[k].Kuaihao*Ye+dataadr)<<endl;
						
						if(temp>2)//输入指令数为3条后,提示将访问为清零
						{
							cout<<"时钟中断到请将访问位清零"<<endl;
							for(int j=0;j<6;j++)
							{
								if(T->Ybiao[j].r==1)
								{
									cout<<"请将页面"<<T->Ybiao[j].Yehao<<"清零:";
									cin>>T->Ybiao[j].r;
								}
							}
							temp=0;
						}
						break;
					}				
				}
				if(T->num >= 6 )//页表已经没有空闲项
				{
					cout<<"发生缺页中断"<<endl;
					cout<<"正在进行页面置换处理....."<<endl;
					for(int l=0;l<6;l++)
					{
						if(T->Ybiao[l].r==0)
						{
							T->Ybiao[k].Yehao=address/Ye;
							T->Ybiao[k].r=1;
							T->Ybiao[k].m=0;							
							cout<<"当前运行的是进程"<<T->name<<endl;
							cout<<"指令地址转换结果为: ";
							cout<<address<<"---"<<(T->Ybiao[k].Kuaihao*Ye+address%Ye)<<"  "<<dataadr<<"---"<<(T->Ybiao[k].Kuaihao*Ye+dataadr)<<endl;
							if(temp>2)//输入指令数为3条后,提示将访问为清零
							{
								cout<<"时钟中断到请将访问位清零"<<endl;
								for(int j=0;j<6;j++)
								{
									if(T->Ybiao[j].r==1)
									{
										cout<<"请将页面"<<T->Ybiao[j].Yehao<<"清零:";
										cin>>T->Ybiao[j].r;
									}
								}
								temp=0;
							}
							break;
						}
					}
				}
				
			}
			else
				{
					cout<<"该指令是一条非法指令"<<endl;
				}
		}
			cout<<"是否要输入下一条指令(y/n):";
			cin>>answer;
}
}

int main()
{
    WeiTu.free=128;//初始空闲块数量为128
	Proc *P=(Proc*)malloc(sizeof(Proc));
	P->n=0;
	P->next=NULL;	
    InputProc(P,WeiTu);
	DoProcess(P,WeiTu);
	LogicToPhysics(P,WeiTu);	
	return 0;
}