yw_os2_1.cpp

本次程序的题目为：进程管理——支持多个进程并发运行的简单的进程管理模拟系统

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

#define MIN 5  //碎片最小容量
#define MAX 1024 //存储区的最大容量
#define MATSIZE 100 //作业分配表的最大容量
#define NOT_EXIST -1  //不存在
#define SUCCESS 1 //成功
#define FAILED 0 //失败
#define EXIT 0 //退出
#define NO_OPERATE -1//无操作

//+*+*+*+*+ 程序主要变量 +*+*+*+*+
typedef struct Free_Area FREEAREA;//***** 定义"空闲块链表"结构 *****
typedef struct Free_Area{
 int size;  //空区大小(以字节计),包括区头所占空间
 int address;  //空闲块首地址
 FREEAREA *next;  //前向链指针,指向下一个空区
 FREEAREA *back;  //反向链指针,指向上一个空区
}FREEAREA;     //**********  **********

typedef struct MAT_Table  //***** 定义"作业分配表"结构 *****
{
 int  name;  //用户作业名
 int length; //作业所占分区大小
 int addr;  //作业所占分区首地址
}MATS;               //**********  **********

MATS MAT[MATSIZE];  //定义"作业分配表"变量

FREEAREA *head; //定义"空闲块链表"变量

int FreeAreaLength;//空闲分区的数目
int MAT_Length;//作业分配表的数目
//+*+*+*+*+ end 变量 +*+*+*+*+

//  !*!*!*!*! 程序主要函数 !*!*!*!*!
void init();         //初始化作业分配表
void InitFreeArea(); //初始化空闲块链表
void print_MAT_table();  // 打印MAT表 
void print_FreeTable(); // 打印空闲链表
int COALESCEC(int worksize);  //            紧凑模块
int FFALOCATION(int worksize,int workname);//分配模块
char instruct();//指令打印
void time();    //延迟
//  !*!*!*!*! end 函数 !*!*!*!*!

//        ***** ***** ***** 初始化 ***** ***** *****
void init()  //初始化作业分配表
{
   MAT_Length=0;//作业分配表的有效长度
   for(int i=0;i<MATSIZE;i++)
   {
     MAT[i].name=NOT_EXIST;
     MAT[i].length=NOT_EXIST;	 
     MAT[i].addr=NOT_EXIST;
   }
}

void InitFreeArea() //初始化空闲块链表
{ 
	FreeAreaLength=0; //空闲分区的数目初始化为0
	head=new FREEAREA;//创建一整块空闲分区
    head->next=head->back=head; //让首、尾指针指向本身
	head->size=MAX; //大小赋值为:整个物理空间的大小
	head->address=0;  //空闲区的首地址为0
	++FreeAreaLength;//空闲分区的数目变为1
}
//        *****  ***** end 初始化 *****  *****

      
void print_MAT_table()  //***** ***** ***** 打印MAT表 ***** ***** *****
{ 
  cout<<"=================================================================="<<endl;
  cout<<"$********************** 作业分配表MAT ***************************$"<<endl;
  cout<<"\n 表项\t 作业名name \t 作业大小length \t 作业首址addr "<<endl;
  for(int i=0;i<MAT_Length;i++)
      printf("%3d\t%6d\t\t%7d\t\t\t%7d\n",i,MAT[i].name,MAT[i].length,MAT[i].addr);
  cout<<"\n$************************** END *********************************$"<<endl;
  cout<<"==================================================================\n\n"<<endl;
}           //***** ***** end 打印MAT表 ***** *****


void print_FreeTable()  //***** ***** ***** 打印空闲链表 ***** ***** *****
{ 
  FREEAREA *freep=head;//将'空闲链表头指针'赋值给'空闲分区链查找指针'
  cout<<"_________________________________________________________________"<<endl;
  cout<<"$********************** 空闲链表 *******************************$"<<endl;
  cout<<"\n 表项 \t 空闲块大小size \t 空闲块首址address"<<endl;
  for(int i=0;i<FreeAreaLength;i++)
  {   
	  printf("%3d \t %6d \t\t %5d \n",i,freep->size,freep->address);
      freep=freep->next;
  }
  cout<<"\n$************************ END **********************************$"<<endl;
  cout<<"-----------------------------------------------------------------\n\n"<<endl;
}


//***** ***** ***** ***** 分配模块 ***** ***** ***** *****              
int FFALOCATION(int worksize,int workname)//分配模块
{  
   FREEAREA *freep=head;//将'空闲链表头指针'赋值给'空闲分区链查找指针'
   int i=0; //FreeArea监督长度值
   while(freep && i<FreeAreaLength) //***** 首次适应法 *****
   {
	 if((freep->size)>=worksize)//遇到头一块适合的空闲区
	 { 
		      //$$$$$ 判断剩余空闲空间是否大于规定的碎片最小容量MIN $$$$$
	    if(freep->size-worksize>=MIN)//是，则分割分配                            
		{
		   MAT[MAT_Length].name=workname;
           MAT[MAT_Length].length=worksize;
		   MAT[MAT_Length].addr=freep->size-worksize+freep->address;
		   freep->size-=worksize;
		}
		else//否则,完全分配
		{
		   --FreeAreaLength;
		   MAT[MAT_Length].name=workname;
           MAT[MAT_Length].length= freep->size;
		   MAT[MAT_Length].addr=freep->address;
		               //***** 判断分配后是否还有空闲区 *****
		   if(FreeAreaLength==0)//无,则置空
			   freep->next=freep->back=NULL;
		   else//有,则去除此结点
		   {
		     freep->back->next=freep->next;
			 freep->next->back=freep->back;
		   }

		   delete freep;
		}
		++MAT_Length;//分配表长度加1
	    return(SUCCESS);
	 }
	 else//未遇到合适的空闲区,则向后查找
	 {   ++i;
	     freep=freep->next;
	 }
   }
      if((freep->size=COALESCEC(worksize))!=0)//如无合适区域,且可紧凑,则同上处理
	
	  {       
		  	      //$$$$$ 判断剩余空闲空间是否大于规定的碎片最小容量MIN $$$$$
		       if((freep->size-worksize)>=MIN)//是，则分割分配
			  {
		           MAT[MAT_Length].name=workname;
                   MAT[MAT_Length].length=worksize;
		           MAT[MAT_Length].addr=freep->size-worksize+freep->address;
				   freep->size-=worksize;
			  }
	   	      else//否则,完全分配
			  {
		           --FreeAreaLength;
		           MAT[MAT_Length].name=workname;
                   MAT[MAT_Length].length= freep->size;
		           MAT[MAT_Length].addr=freep->address;
				   freep->next=freep->back=NULL;
				   delete freep;
			  }
		++MAT_Length;//分配表长度加1
	    return(SUCCESS);
	 }
      else//无合适区域,且不可紧凑
	   {
         cout<<"! ! !*************** 内存不足，不能分配 **************! ! !\n"<<endl;
	       return(FAILED);
	   }
}
//***** ***** ***** ***** end 分配模块 ***** ***** ***** *****           

//***** ***** ***** ***** ***** 回收模块 ***** ***** ***** ***** ***** *****
void FFCOLLECTION(int workname)//回收模块
{ 
	   FREEAREA *freep=head;//将'空闲链表头指针'赋值给'空闲分区链查找指针'
       int i=0;//用于记录在欲回收模块之前的模块数
       int location=-1;//用于记录欲回收模块在表中的位置,初始值为-1
	   for(int m=0;m<MAT_Length;m++)//***** 查找欲回收模块 *****
	   {
	      if(MAT[m].name==workname)
		  {
			location=m;
		    break;
		  }
	   }                           //***** *****
	  
		
	   if(location!=-1)//如找到了欲回收模块
	   {
	       --MAT_Length;//有效长度减1
		        //*** 计算在欲回收模块之前的模块数,并将与此模块最近的空闲区(地址在此模块之后)找到 ***
           while(i<FreeAreaLength && MAT[location].addr>freep->address)
		   {
		        freep=freep->next;
		        ++i;
		   }   //*** ***

          if(freep->back->size+freep->back->address==MAT[location].addr && freep->address==MAT[location].addr+MAT[location].length)//欲回收模块前后都有空闲区
		  {
               freep->back->size=freep->back->size+freep->size+MAT[location].length;
	           freep->back->next=freep->next;
               freep->next->back=freep->back;
		  } 

          if(freep->back->size+freep->back->address==MAT[location].addr && freep->address!=MAT[location].addr+MAT[location].length)//欲回收模块前都有空闲区
		  {
               freep->back->size+=MAT[location].length;
		  }	

          if(freep->back->size+freep->back->address!=MAT[location].addr && freep->address==MAT[location].addr+MAT[location].length)//欲回收模块后都有空闲区
		  {
               freep->size+=MAT[location].length;
	           freep->address=MAT[location].addr;
		  }

          if(freep->back->size+freep->back->address!=MAT[location].addr && freep->address!=MAT[location].addr+MAT[location].length)//欲回收模块前后都没有空闲区
		  {
               ++FreeAreaLength;
               FREEAREA *freep1=new FREEAREA;
               freep1->size=MAT[location].length;
               freep1->address=MAT[location].addr;
	           freep1->back=freep->next;
	           freep->back->next=freep1;
	           freep1->next=freep;
               freep->back=freep1;
		  } 
 
     	  for(int j=location;j<MAT_Length;j++)//****** 分配表中的值向前移,消除回收项 ******
		  {    
			    MAT[j].addr=MAT[j+1].addr;
                MAT[j].length=MAT[j+1].length;
	            MAT[j].name=MAT[j+1].name;
		  }                                   //****** ******
	   }
      else//如未找到了欲回收模块
		  printf("\n\n! ! !********不存在这样的作业*********! ! !\n\n");

}
//***** ***** ***** ***** ***** end 回收模块 ***** ***** ***** ***** *****                

//***** ***** ***** ***** ***** 紧凑模块 ***** ***** ***** ***** *****               

int COALESCEC(int worksize)//紧凑模块
{  
   FREEAREA *freep=head;//将'空闲链表头指针'赋值给'空闲分区链查找指针'
   FREEAREA *colloctp=freep;//将'空闲分区链查找指针'赋值给'空闲分区紧凑指针'
   for(int j=0;j<FreeAreaLength-1;j++)//将'空闲分区紧凑指针'的大小赋值为'整个空闲区的大小和'
   {
     freep=freep->next;
	 colloctp->size+=freep->size;
   }
   if(colloctp->size>=worksize)//如果紧凑后能满足分配要求,则紧凑分配
   { 
	 int i;
	 FreeAreaLength=1;
	 cout<<"\n*********开始紧凑碎片************\n"<<endl;
     cout<<"\n*********************************\n"<<endl;

     freep->address=0;
	 freep->size=colloctp->size;
	 freep->next=freep->back=freep;
	 
	 MAT[0].addr=freep->size;
	 for(i=1;i<MAT_Length;i++)
	 {
		 MAT[i].addr=MAT[i-1].addr+MAT[i-1].length;
	 }
	 return (freep->size);//返回空闲区的大小
   } 
   else 
	   return(FAILED);
}

//***** ***** ***** ***** ***** end 紧凑模块 ***** ***** ***** ***** *****              
 
//***** ***** ***** ***** 模块处理 ***** ***** ***** *****             
int MENU()//模块处理
{
    
	int worksize;//欲分配模块大小
    int workname;//欲分配模块名字
	char answer;//回答
	int reply;//响应
	
	cout<<"选择要执行的操作: (H.指令提示;)\n\t\t  ";
	cin>>answer;

	if(answer=='H'||answer=='h')
		answer=instruct();
    
	if(answer=='A'||answer=='a')
		reply=1;
	else if(answer=='B'||answer=='b')
		reply=2;
	else if(answer=='C'||answer=='c')
		reply=3;
	else if(answer=='D'||answer=='d')
		reply=4;
	else if(answer=='E'||answer=='e')
		reply=5;
	else 
		reply=-1;

	switch(reply)
	{
	
	   case 1:
		   {     
			     int name;
		    	 cout<<"输入要回收的作业名 : ";
				 cin>>name;
                 FFCOLLECTION(name);
			     break;
			}
       case 2:
			{
			  
			  printf("作业请求分配内存:\n");
			  printf("************!!!注意：作业名字只可为整数!!!**************");
			  cout<<"\r                                                          ";
			  time();
              cout<<"\r       ----------作业名字(name)=";
              cin>>workname;
			  cout<<"       ----------作业大小(size)=";//输入作业大小worksize
			  cin>>worksize;
              FFALOCATION(worksize,workname);
			  break;
			}
       case 3:
			 return(EXIT);
			 break;
	   case 4:
		     print_FreeTable(); 
			 break;
	   case 5:
		     print_MAT_table();
			 break;
	   default:
		   {
		    cout<<" !-!-!-!-! 警告提示:"<<endl;
			cout<<"****************不存在这样的操作，请重试***************\n"<<endl;
		   }
	}
	return NO_OPERATE;//
}
//***** ***** ***** ***** end 模块处理 ***** ***** ***** *****             

//***** ***** ***** 指令打印 ***** ***** *****            
char instruct()//指令打印
{
   char answer;
YUNWEI:
   cout<<" \t\t\b @*******系统指令***********@"<<endl;
   cout<<" \t\t作业回收：   A \n\t\t作业分配：   B \n\t\t退出程序：   C \n\t\t打印空闲链表:D \n\t\t打印分配表： E"<<endl;
   cout<<" \t\t\b @**************************@\n"<<endl;
   cout<<"选择要执行的操作 : ";
   cin>>answer;
   if(answer=='h'||answer=='H')
	   goto YUNWEI;
   return answer;
}
//***** ***** ***** end 指令打印 ***** ***** ***** 

//***** ***** ***** 延迟 ***** ***** *****                    
void time()//延迟
{
 for(int x=0;x<3000;x++)
	for(int y=0;y<3000;y++)
		for(int z=0;z<50;z++);
}
//***** ***** ****** end 延迟 ***** ***** *****                  

//***** ***** ***** ***** ***** 主函数 ***** ***** ***** ***** *****       
void main()
{ cout<<")-------------- 采用可变分区存储器管理方案的模拟系统 ---------------(\n"<<endl;
  init();
  InitFreeArea();
  while(1)
  {
	  if( MENU()==0)
		  break;
  }
  cout<<")---------------------- ALL THE WORK OVER --------------------------(\n"<<endl;
}
//***** ***** ***** ***** ***** end of all ***** ***** ***** ***** *****