memorysource.cpp

关于存储管理实验的实现

#include<iostream.h>
#include<stdlib.h>
#include<string.h>
#include "conio.h"

#define NULL 0
#define getspace(type) (type*)malloc(sizeof(type))
#define ProNum 6  //
#define codemaxlen 16  //程序段的最大长度
#define codeminlen 8   //程序段的最小长度
#define jcbcodemaxlen 128 //作业程序段的最大长度
#define spacenumber 6     //分区数目
#define memorylen 352     //可用内存大小

char *BasicPro[]={"PLUS","MINUS","TIMES","SLASH",
"READ","WRITE"};
int SpaceSize[spacenumber]={32,32,32,64,64,128};  //表示分区大小，小分区长度、中分区长度、大分区长度
typedef enum{PLUS,MINUS,TIMES,SLASH,READ,WRITE}ProName;

struct Instruction{  //定义指令流模块
	bool BOOL;       //如果BOOL为false表示要访问的是当前程序段中某条指令或数据
	                 //如果是true则表示要访问的是另个一程序段
	long current;    //当前指令的相对地址
	long back;       //下一条指令地址(当BOOL为true时是程序段地址)
	Instruction *next;
}*InstructionLink=NULL,*curInstruction,*JcbInsLink=NULL,*curJcbIns;

Instruction memoryarray[memorylen];   //在内存中存放指令流的空间

struct Procedure{  //程序段模块
	int  name;     //程序段名称(枚举类型ProName)
	int  size;     //该程序段的长度
	Instruction *Inslink;//该程序段指令流的首地址
	Procedure *next;
}*Basic=NULL,*curProcedure;

struct ProNameLink{
	int name;    //因为程序段模块中的程序段名是用整型(int)表示的
	ProNameLink *next;
}*NameLink=NULL,*curName;

struct Jcb{   //作业模块
	char name[10];  //作业名称
	int  super;     //作业优先级
	long size;      //作业代码长度
	Instruction *Inslink; //该作业指令流的首地址
    ProNameLink  *Prolink; //程序段链表
	Jcb *next;
}*ready=NULL,*curJcb;

struct SpaceAllocation{ //空间分配表
	char Sname[10];
	int number;  //编号
	long size;    //大小
	long cursize; //实际使用的大小
	long endAddr; //该分区中作业最后那条指令的地址
	long beginAddr; //起始地址
	long curAddr;   //将要执行的指令地址
	bool BOOL;     //使用情况，false表示未使用，true表示已经分配
}*Space[spacenumber];

typedef Instruction     INSTRUCTION;
typedef Procedure       PROCEDURE;
typedef ProNameLink     PRONAME;
typedef Jcb             JCB;
typedef SpaceAllocation ALLOCATION;

//------------------------------------------------------------------------------------------------
void sortInstruction()  //将程序段的指令流链成链表
{
	Instruction *fir,*sec;
	if(InstructionLink == NULL)
	{
		curInstruction->next = InstructionLink;
		InstructionLink = curInstruction;
	}
	else
	{
		fir = InstructionLink;
		sec = fir->next;
		while(sec != NULL)
		{
			fir = fir->next;
			sec = sec->next;
		}
		fir->next = curInstruction;
	}
}
//------------------------------------------------------------------------------------------------
void sortProcedure()  //将基本程序段链成链表，Basic
{
	Procedure *fir,*sec;
	if(Basic == NULL)
	{
		curProcedure->next = Basic;
		Basic = curProcedure;
	}
	else
	{
		fir = Basic;
		sec = fir->next;
		while(sec != NULL)
		{
			fir = fir->next;
			sec = sec->next;
		}
		fir->next = curProcedure;
	}
}
//------------------------------------------------------------------------------------------------
void Initialize()   //初始化基本程序段 系统给出的可以调用的程序段为：
            //"PLUS","MINUS","TIMES","SLASH","READ","WRITE"
			//用户的作业可以由上面的若干程序段构成，内部代码为：0、1、2、3、4、5
{
	int len,i,j;
	bool flag;
	for(i=0;i<ProNum;i++)
	{
		flag = true;
		len = 0; 
		curProcedure=getspace(PROCEDURE);
		while(len<codeminlen || len>codemaxlen){
			len = rand();
		}
		curProcedure->name = i;
		curProcedure->size = len;

		for(j=0;j<len;j++)
		{   
			int call=0,call_num = -1;

			curInstruction = getspace(INSTRUCTION);
			while(call<10 || call>20)
			{
				call = rand();				
			}
			if(call == 15 && flag)  //每条指令中有1/(20-10)可能是调用其它程序段的
			{
				curInstruction->BOOL = true;  //表示要访问的是其他程序段
				flag = false;
			}
			else
				curInstruction->BOOL = false; //表示要访问的是本程序段

			curInstruction->current = j;      //当前相对地址
			if(curInstruction->BOOL)
			{
				while(call_num<0 || call_num>=ProNum || call_num==i)
				   	call_num = rand();
				curInstruction->back = call_num;
			}
			else
				curInstruction->back = j+1;

			curInstruction->next = NULL;
			sortInstruction();
		}
		curProcedure->Inslink = InstructionLink;
		InstructionLink = NULL;
		curProcedure->next = NULL;
		sortProcedure();
	}
}
//------------------------------------------------------------------------------------------------
void DisplayBasicCode()  //打印基本程序段的指令流
{
	Instruction *p;
	Procedure *fir;
	fir = Basic;
	for(int j=0;j<ProNum;j++)
	{
		cout<<"\n程序段名称："<<BasicPro[fir->name]<<endl;
		cout<<"程序段长度："<<fir->size<<endl;
		cout<<"程序段指令流："<<endl;
		cout<<"Current\tAction\tNext"<<endl;
		
		p = fir->Inslink;
		for(int i=0;i<fir->size;i++)
		{
			cout<<p->current<<"\t";
			if(p->BOOL)
				cout<<"CALL\t"<<BasicPro[p->back]<<endl;
			else
				cout<<"GOTO\t"<<p->back<<endl;
			p=p->next;
		}
		fir = fir->next;
	}
	
}
//------------------------------------------------------------------------------------------------
void sortNameLink()  //将用户输入的某作业所用到的程序段链成链表
{
	ProNameLink *fir,*sec;
	if(NameLink == NULL)
	{
		curName->next = NameLink;
		NameLink = curName;
	}
	else
	{
		fir = NameLink;
		sec = fir->next;
		while(sec != NULL)
		{
			fir = fir->next;
			sec = sec->next;
		}
		fir->next = curName;
	}
}
//------------------------------------------------------------------------------------------------
void sortJcb()   //将用户输入的作业按优先级先后链成链表
{
	Jcb *fir,*sec;
	bool BOOL = true;
	if(ready == NULL || curJcb->super > ready->super)
	{
		curJcb->next = ready;
		ready = curJcb;
	}
	else
	{
		fir = ready;
		sec = fir->next;
		while(sec != NULL)
		{
			if(curJcb->super > sec->super)
			{
				fir->next = curJcb;
				curJcb->next = sec;
				sec = NULL;
				BOOL = false;
			}
			else
			{
				fir = fir->next;
				sec = sec->next;
			}
		}
		if(BOOL) fir->next = curJcb;
	}
}
//------------------------------------------------------------------------------------------------
void Input()  //输入作业的信息
{
	int jcbnum,num,i,j;
	cout<<"\n请输入作业的个数：";
	cin>>jcbnum;
	for(i=0;i<jcbnum;i++)
	{
		curJcb = getspace(JCB);
		cout<<"\n请输入作业 "<<i+1<<" 的名称：";
		cin>>curJcb->name;
		cout<<"\n优先级：";
		cin>>curJcb->super;
		cout<<"\n输入该作业程序段的总数：";
		cin>>num;
		cout<<"\n它们按先后顺序排列为：";
		for(j=0;j<num;j++)
		{
			curName = getspace(PRONAME);
			cout<<"\n程序代码 "<<j+1<<" :";	
			cin>>curName->name;
			curName->next = NULL;
			sortNameLink();
		}
		cout<<endl;
		curJcb->size = 0;
		curJcb->Inslink = NULL;
		curJcb->Prolink = NameLink;
		curJcb->next = NULL;
		NameLink = NULL;
		sortJcb();
	}
}
//------------------------------------------------------------------------------------------------
void sortJcbIns()  //将某一作业所用到的指令流逐个插入指令流链表中
{
	Instruction *fir,*sec;
	if(JcbInsLink == NULL)
	{
		JcbInsLink = curJcbIns;
	}
	else
	{
		fir = JcbInsLink;
		sec = fir->next;
		while(sec!=NULL)
		{ 
			fir = fir->next;
			sec = sec->next;
		}
		fir->next = curJcbIns;
	}
}
//------------------------------------------------------------------------------------------------
int InsToJcb(int name,int Original)  //将作业所用的程序段转化为指令流序列
{
	Procedure *prolink;
	Instruction *inslink;
	prolink = Basic;
	int len;
	while(prolink != NULL)
	{
		if(name == prolink->name)
			break;
		else
			prolink = prolink->next;
	}
	if(prolink != NULL)
	{
		len = 0;
		inslink = prolink->Inslink;
		while(len<prolink->size && inslink != NULL)
		{						
			if(inslink->BOOL)  //访问另一段程序
			{
				cout<<"\nCall to "<<BasicPro[inslink->back];  //
				Original += inslink->current;
				Original = InsToJcb(inslink->back,Original);
				cout<<"\nReturn from "<<BasicPro[inslink->back];  //
				Original -= (inslink->current+1);
			}
			else
			{
				curJcbIns = getspace(INSTRUCTION);
	    		curJcbIns->BOOL = inslink->BOOL;
	    		curJcbIns->current = inslink->current+Original;
    			curJcbIns->back = inslink->back+Original;
    			curJcbIns->next = NULL;
				cout<<"\n"<<curJcbIns->current<<"\t"<<curJcbIns->BOOL<<"\t"<<curJcbIns->back;  //
				sortJcbIns();
			}
			inslink = inslink->next;
			len++;
		}
		Original = curJcbIns->back;
		return Original;
	}
	else
	{
		cout<<"\n程序出错..."<<endl;
		getch();
		return -1;
	}
}
//------------------------------------------------------------------------------------------------
void DisplayJcbCode()  ////将作业的程序静态连接成固定模块，并打印连接后各作业的指令流
{
	int Original;   //起始地址
	Jcb *fir;
	ProNameLink *namelink;
	fir = ready;
	while(fir != NULL)
	{
		Original = 0;
		cout<<"\n作业名称： "<<fir->name;
		cout<<"\n程序指令流： "<<endl;
		namelink = fir->Prolink;
		cout<<"Current\tAction\tNext"<<endl;
		while(namelink != NULL)
		{
			cout<<"                            "<<BasicPro[namelink->name]<<endl;
			getch();
			Original = InsToJcb(namelink->name,Original); //将该作业所需要的程序
			                                              //静态连接成一个完整模块
			namelink = namelink->next;
		}
		fir->Inslink = JcbInsLink;  //当前作业的指令流
		fir->size = Original;
		cout<<"\n"<<fir->name<<"的长度："<<fir->size<<endl;
		getch();
		JcbInsLink = NULL;
		fir = fir->next;
	}
}
//------------------------------------------------------------------------------------------------
void InitSpace()  //初始化内存使用情况
{
	int i,addr=0;
	for(i=0;i<spacenumber;i++)
	{
		Space[i] = getspace(SpaceAllocation);
		strcpy(Space[i]->Sname," ");
		Space[i]->number = i;    //分区号
		Space[i]->beginAddr = addr; //起始地址
		Space[i]->size = SpaceSize[i]; //分区长度
		Space[i]->cursize = 0;    //作业实际使用该分区的长度
		Space[i]->endAddr = Space[i]->beginAddr;
		Space[i]->curAddr = -1;   //作业下一条将要执行的指令地址
		Space[i]->BOOL = false;	
		addr += SpaceSize[i];   //起始地址
	}
}
//------------------------------------------------------------------------------------------------
void Assign()   //为就绪队列作业分配内存空间
{
	int i,z;
	Jcb *fir,*sec,*thr;
	sec = fir = ready;
	while(sec != NULL)
	{
		for(i=0;i<spacenumber;i++)
		{
			if(!Space[i]->BOOL) //该分区未使用
				if(sec->size <= Space[i]->size)  //大小适中
				{
					strcpy(Space[i]->Sname,sec->name);
					Space[i]->BOOL = true;  //该模块已经分配给作业
					Space[i]->cursize = sec->size; //实际使用的长度等于作业的长度
					Space[i]->curAddr = Space[i]->beginAddr; //该作业将执行的指令地址为起始地址
					Space[i]->endAddr = Space[i]->beginAddr + Space[i]->cursize;
					                            //作业最后一条指令地址
					z = Space[i]->beginAddr;  //起始地址					
					curJcbIns = sec->Inslink; 
					while(curJcbIns!=NULL)    //将作业的指令流写入内存
					{
						memoryarray[z].BOOL = curJcbIns->BOOL;
						memoryarray[z].current = curJcbIns->current+Space[i]->beginAddr;
						memoryarray[z].back = curJcbIns->back+Space[i]->beginAddr;
						memoryarray[z].next = NULL;
						z++;
						curJcbIns = curJcbIns->next;
					}
					if(sec == ready)  //将已经写入内存的作业从就绪队列清除
					{
						thr = ready;
						ready = ready->next;
						fir = sec = ready;
					}
					else
					{
						thr = sec;
						fir->next = sec->next;
						sec = sec->next;
					}
					delete thr;
					break;
				}
		}
		if(i==spacenumber)
		{
			cout<<"\n当前无法给作业 "<<sec->name<<" 分配内存！"<<endl;
			fir = sec;
			sec = sec->next;
		}
	}
}
//------------------------------------------------------------------------------------------------
void Check()  //检查内存的使用情况
{
	int i,j,z;
	for(i=0;i<spacenumber;i++)
	{
		if(Space[i]->BOOL)
		{
			cout<<endl;
			z = Space[i]->beginAddr;
			cout<<"\n内存分配情况，在模块 "<<i<<" 中的作业名称："<<Space[i]->Sname<<endl;
			getch();
			for(j=0;j<Space[i]->cursize;j++)
			{
				cout<<memoryarray[z].current<<"\t"<<memoryarray[z].BOOL<<"\t"
			    	<<memoryarray[z].back<<endl;
				z++;
			}
			getch();
		}	
	}
}
//------------------------------------------------------------------------------------------------
void CallBack(int number)   //回收内存
{
	int i = number;
	strcpy(Space[i]->Sname," ");
	Space[i]->BOOL = false;
	Space[i]->curAddr = Space[i]->beginAddr;
	Space[i]->cursize = 0;
	Space[i]->endAddr = Space[i]->beginAddr;
}
//------------------------------------------------------------------------------------------------
void Run()  //运行在内存中的作业
{
	int i;
	bool BOOL=true;
	while(BOOL)
	{
    	for(i=0;i<spacenumber;i++)
		{
    		if(Space[i]->BOOL)
			{
	    		Space[i]->curAddr++; //指向下一条指令
	    		if(Space[i]->curAddr == Space[i]->endAddr) //已经是最后一条指令
				{
					cout<<"\n作业 "<<Space[i]->Sname<<" 已经完成"<<endl;
					getch();
	    			CallBack(i);      //回收该内存,传递该内存分区的地址i
					BOOL = false;     //有作业完成，返回主函数main为就绪队列作业分配内存
				}
			}
		}
	}
}
//------------------------------------------------------------------------------------------------
void main()
{
	Initialize();   //初始化基本程序段
	DisplayBasicCode();
	Input();
	DisplayJcbCode(); //将作业的程序静态连接成固定模块，并打印连接后各作业的指令流
	InitSpace();    //初始化分区使用表
	while(ready != NULL)
	{
		Assign();       //为作业分配内存
    	Check();        //查看分配情况
		Run();          //作业运行
	}
	cout<<"\n作业已经全部运行完毕。"<<endl;
	cout<<"\nPress any key exit..."<<endl;
	getch();
}