memory_dis_re.cpp

此程序模拟内存的动态分配与回收,希望能给大家帮助,并能得到大家的意见,谢谢!

#include<iostream.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
#define NULL 0
static bool EXIT=0;
#define MAXLONGTH 32767
int Add;//释放区的首址
int Size;//释放区的大小
struct node;//结点声明
node *NODE;//临时变量
node *empty=NULL;//空闲区队列首指针
node *used=NULL;//指向释放区node结构的指针
int Free;//用户申请存储区的大小
struct node{//分区结点类型
			int  adr;//分区首地址
			int  size;//分区大小
			node *next;//指向下一个分区的指针
		   };

int First_Fit( node *link,int Size)
{//First Fit Algorithm  返回分配内存的首地址
  node *pointer1;//临时指针
  node *pointer2;//临时指针
  int address;
  pointer1=link;
  while(pointer1->next!=NULL&&pointer1->size<Size)
	    pointer1=pointer1->next;
  if(pointer1==link)
	{//只有一个结点
	  if(pointer1->size<Size)
		{
		  cout<<"队列中没有适合的分区1111!"<<endl;
		  address=-1;
		}
	  else if(pointer1->size>Size)
		{
		  address=pointer1->adr;//
		  pointer1->size=pointer1->size-Size;
		  pointer1->adr=pointer1->adr+Size;//重新设置信息
		}
	  else//pointer1->size equal the Size
		{
		  address=pointer1->adr;
		  pointer1->size=-1;
		  empty=empty->next;
		  //link=link->next;//只有一个元素	NULL;
		  delete pointer1;
		}
	}
  else if(pointer1->next==NULL)//找到最后没的找到
	{
      cout<<"队列中没有适合的分区22222!"<<endl;
	  address=-1;
	}
  else
	{//找到了
	  if(pointer1->size>Size)
		{//分区大于需要分配的块
		  address=pointer1->adr;//
		  pointer1->size=pointer1->size-Size;
		  pointer1->adr=pointer1->adr+Size;//重新设置信息
		}
	  else
		{//空间大小相同
		  address=pointer1->adr;
		  if(link==pointer1)
			  link=NULL;//只有一个元素
		  else if(link->next==pointer1)
			  link->next=NULL;
		  else
			{
			  pointer2=link;
			  while(pointer2->next!=pointer1)
				  pointer2=pointer2->next;//找到pointer1的父结点
			  pointer2->next=pointer1->next;//删除pointer1所指向的结点
			}			  
		}		
	}
  return address;
}

int Best_Fit(node *link,int SIZE)
{//最佳适用算法，是从不到大排列的
  int address;
  node *pointer;
  pointer=link;
  if(link==NULL)
	{//队列为空
	  cout<<"队列中没有适合的分区!"<<endl;
	  address=-1;
	}
  else if(pointer->size==SIZE)
	{//队列中的空间大小正好
	  address=pointer->adr;
	  link=NULL;
	}
  else if(pointer->size>SIZE)
	{//第一个元素最小但是大小所需空间
	  address=pointer->adr;
	  pointer->size=pointer->size-SIZE;
	  pointer->adr=pointer->adr+SIZE;
	}
  else
	{//大于第一个元素的空间
	  while(pointer->size<SIZE&&pointer->next!=NULL)
		  pointer=pointer->next;
	  if(pointer->next==NULL)
		{
			cout<<"队列中没有适合的分区!"<<endl;
			address=-1;
		}
	  else
		{
		  if(pointer->next->size==SIZE)
			{//删除该结点
			  address=pointer->next->adr;
			  pointer->next=pointer->next->next;
		  	}
		  else
			{//改变该结点
			  address=pointer->next->adr;
			  pointer->next->adr=pointer->next->adr+SIZE;
			  pointer->next->size=pointer->next->size-SIZE;
			}		
		}

	}
	return address;
}

void Print_Used(node *link)
{//输出空闲区队列的排序
  node *pointer;
  pointer=link;
  cout<<"……………………………已经使用区队列情况…………………………………………"<<endl;
  while(pointer!=NULL)
	{
	  cout<<"Address:"<<pointer->adr<<'\t';
	  cout<<"Size:"<<pointer->size<<endl;
	  pointer=pointer->next;//指针后移
	}
  cout<<"……………………………已经使用区队列情况…………………………………………"<<endl;
}

node* Used_Del(int add)
{//used队列中的元素删除函数
	node *pointer;
	pointer=used;
	if(pointer==NULL)
	  {
		cout<<"回收错误"<<endl;
		Add=-1;
		pointer=NULL;
	  }
	else if(pointer->adr==add)
		{
		  Size=pointer->size;
		  if(pointer->next==NULL)
			{
			 used=NULL;	 
			}
		  else
			{
			 node *p;
			 p=pointer;
			 p=p->next;
			 pointer->next=NULL;
			 used=p;		 
			}
		}
	else
	  {//有多于一人元素
		while(pointer->next!=NULL&&pointer->next->adr!=add)
			pointer=pointer->next;
		if(pointer->next==NULL)
			{
			  cout<<"回收错误"<<endl;
		      Add=-1;
			  pointer=NULL;
			}
		else
		  {
			node *p;
			p=pointer;
			pointer=pointer->next;
			Size=pointer->size;
			p->next=pointer->next;
			pointer->next=NULL;		
		  }
	  }
	return pointer;
}

void Print_Empty(node *link)
{//输出空闲区队列的排序
  node *pointer;
  pointer=link;
  cout<<"---------------------------空闲区队列情况-------------------------------"<<endl;
  while(pointer!=NULL)
	{
	  cout<<"Address:"<<pointer->adr<<'\t';
	  cout<<"Size:"<<pointer->size<<endl;
	  pointer=pointer->next;//指针后移
	}
  cout<<"------------------------------------------------------------------------"<<endl;
}

void Fir_Accepment(int add)
{
  node *Node; //传回的结点
  if(Add!=-1)
	{
	  node *p=empty;//当前链的临时指针
      Node=NODE;
	  if(empty->size==0)//队列中没有元素
		  empty=Node;
	  else if(Node->adr+Node->size<p->adr)
		{//
		  Node->next=empty;
		  empty=Node;
		}
	  else if(Node->adr+Node->size==p->adr)
		{
		  p->adr=Node->adr;
		  p->size=p->size+Node->size;
		  delete Node;
		}
	  else if(Node->adr==p->adr+p->size)
		{
		  p->size=p->size+Node->size;
		  delete Node;
		  if(p->adr+p->size==p->next->adr)
			{ 
			  Node=p; //Node=p->next;
			  p=p->next;//p->size=Node->size+p->size;
			  p->size=p->size+Node->size;//p->next=Node->next;
			  p->adr=Node->adr;
			  empty=p;
			  Node->next=NULL;
			  delete Node;

			}
		}
	  else//
		{
		  while((p->next!=NULL)&&(Node->adr>=(p->next->adr+p->next->size)))
			  p=p->next;
		  if(p->next==NULL)			
			  p->next=Node;
		  else if(Node->adr==(p->next->adr+p->next->size))
			{
			  p->next->size=p->next->size+Node->size;
			  delete Node;
			  if(p->next->adr+p->next->size==p->next->next->adr)
				{
				  p=p->next;
				  Node=p->next;
				  p->size=p->size+Node->size;
				  p->next=Node->next;
				  delete Node;
				}
			}
		  else
			{//结点地址大于当前指针所指向的最大地址
			  if(Node->adr+Node->size==p->next->adr)
				{
				  p->next->adr=Node->adr;
				  p->next->size=p->next->size+Node->size;
				  delete Node;
				}
			  else
				{
				  Node->next=p->next;
				  p->next=Node;
				}

			}
		}
	}
}


node* Insert_empty(node *link,node *p)
{
	node *ptr;
	ptr=link;
	if(link==NULL)
		link=p;
	else if(p->size<=link->size)//p->size<=link->size
		{
		  p->next=link;
		  link=p;
		}
	else
	  {

	    while(ptr->next!=NULL&&(p->size>ptr->next->size))
		   ptr=ptr->next;
	    if(ptr->next==NULL)
		   ptr->next=p;
	    else
		  {  
		    p->next=ptr->next;
		    ptr->next=p;
	      }
	    }
return link;
}

void Bes_Accepment(int add)
{
  node *Node; 
  if(Add!=-1)
	{
	  node *p=empty;
	  Node=NODE;
	  if(empty->size==0)
		  empty=Node;
	  else 
		{
		  if(Node->adr+Node->size==empty->adr)
			{
			  empty->adr=Node->adr;
			  empty->size=empty->size+Node->size;
			  Node=empty;
			  empty=empty->next;
			  Node->next=NULL;
			}
		  else
			{		  
			  while(p->next!=NULL&&(Node->adr+Node->size!=p->next->adr))
				  p=p->next;
			  if(p->next!=NULL)
				{
				  p->next->adr=Node->adr;
				  p->next->size=Node->size+p->next->size;
				  delete Node;
				  Node=p->next;
				  p->next=Node->next;
				  p->next=NULL;
				}
			  
			}
		  p=empty;
		  if(empty!=NULL)
			{
			  if(p->adr+p->size==Node->adr)
				{
					p->size=p->size+Node->size;
					delete Node;
					Node=p;
					empty=empty->next;
					Node->next=NULL;
				}
			  else
				{
		   	    while(p->next!=NULL&&(p->next->adr+p->next->size!=Node->adr))
				  p=p->next;
		        if(p->next!=NULL)
					{
					 p->next->size=p->next->size+Node->size;
					 delete Node;
					 Node=p->next;
					 p->next=Node->next;
					 Node->next=NULL;

					}

		        
				}
			empty=Insert_empty(empty,Node);
		  }
		 else
		  { 
		    empty=Node;
		  }
		}

			

	}
}


node* Inset_link(node *link,node& N )
{//队列尾部插入函数
	node *pointer;//临时指针
	pointer=link;//指针赋值	
	if(link==NULL)//队列为空
		link=&N;
	else//队列非空
		{
		  while(pointer->next!=NULL)
			  pointer=pointer->next;//指针后移
		  pointer->next=&N;//进程块插入队尾
		}
	return link;
}

void main()
{

int memory[MAXLONGTH]={0};//程序首先申请一整块空闲区，其首址为0，大小为32767；
int algorithm;//用户使用哪种分配算法
int select;//分配还是回收
///////////////////////
empty=new node;
empty->adr=0;
empty->size=MAXLONGTH;
empty->next=NULL;
//////////////////////////////////以上段完成第一个空链表结点
cout<<"︿﹀︿﹀︿﹀︿﹀︿﹀︿﹀︿﹀︿﹀︿﹀︿﹀︿﹀︿﹀︿﹀︿﹀︿﹀︿﹀︿︿﹀﹀"<<endl;
cout<<"请输入算法: '1'--Fir_Fit_Algorithm, '2'--Bes_Fit_Algorithm, '4'--EXIT:"<<endl;
cout<<"︿﹀︿﹀︿﹀︿﹀︿﹀︿﹀︿﹀︿﹀︿﹀︿﹀︿﹀︿﹀︿﹀︿﹀︿﹀︿﹀︿︿﹀﹀"<<endl;
while(algorithm!=1&&algorithm!=2&&algorithm!=4)
	{//算法选择
	 cout<<"------------------------------"<<endl;
	 cout<<"Please input correct:";	 
	 cin>>algorithm;
	 cout<<"------------------------------"<<endl;
	 if(algorithm==4)
		 EXIT=1;
	}
while(!EXIT){
///////////////////////////////////以上段完成算法选择
cout<<"︽︾︽︾︽︾︽︾︽︾︽︾︽︾︽︾︽︾︽︾︽︾︽︾︽︾︽︾︽︾"<<endl;
cout<<"请选择:分配、回收,退出: '1'--分配,  '2'--回收, '4'--EXIT"<<endl;
cout<<"︽︾︽︾︽︾︽︾︽︾︽︾︽︾︽︾︽︾︽︾︽︾︽︾︽︾︽︾︽︾"<<endl;
	while(select!=1&&select!=2&&select!=4)
		{//输入，回收选择
		 cout<<"------------------------------"<<endl;		
		 cout<<"Please input correct:";		  
		 cin>>select;
		 cout<<"------------------------------"<<endl;
		 if(select==4)
			 EXIT=1;
		 break;
		}	
/////////////////////////////////////以上段完成分配，回收选择
	if(select==1)//进行分配
	  {
		node *N_node;//临时结点	
		N_node=new node;
		cout<<"Please input the SIZE:";
		cin>>Free;
		N_node->size=Free;
		N_node->next=NULL;
		if(algorithm==1)
			{
			  int ADDR;
			  ADDR=First_Fit(empty,Free);
			  if(ADDR==-1)
				  continue;
			  N_node->adr=ADDR;
			  used=Inset_link(used,*N_node);
			}
		else 
			{
			  int ADDR;
			  ADDR=Best_Fit(empty,Free);
			  if(ADDR==-1)
				  continue;
			  N_node->adr=ADDR;
			  used=Inset_link(used,*N_node);
			}
	  }
    else if(select==2)//进行回收
	  {
		cout<<"Please input the address you want to recive:";
		cin>>Add;
		NODE=Used_Del(Add);
		if(algorithm==1)
			Fir_Accepment(Add);
		else
			Bes_Accepment(Add);
	  }
	else
		EXIT=1;
Print_Used(used);	
Print_Empty(empty);
select=0;

}

}
/*
《OS》实验任务书二

题目：存储管理动态分区分配及回收算法

一、目的和要求
分区管理是应用较广泛的一种存储管理技术。本实验要求用一种结构化高级语言构造分区描述器，编制动态分区分配算法和回收算法模拟程序，并讨论不同分配算法的特点。

二、实验内容
    1.编写：First Fit Algorithm
    2.编写：Best Fit Algorithm
3.编写：空闲区回收算法

三、提示和说明
   （一）主程序 
      1.定义分区描述器node，包括 3个元素：
       （1）adr--分区首地址
       （2）size--分区大小
       （3）next--指向下一个分区的指针
      2.定义 3个指向node结构的指针变量：
       （1）head1--空闲区队列首指针
       （2）back1--指向释放区node结构的指针
       （3）assign--指向申请的内存分区node结构的指针
      3.定义 1个整形变量：
            free--用户申请存储区的大小（由用户键入）
   （二）过程
      1.定义check过程，用于检查指定的释放块（由用户键入）的合法性
      2.定义assignment1过程，实现First Fit Algorithm
      3.定义assignment2过程，实现Best Fit Algorithm
      4.定义acceptment1过程，实现First Fit Algorithm的回收算法
      5.定义acceptment2过程，实现Best Fit Algorithm的回收算法
      6.定义print过程，打印空闲区队列
   （三）执行
    程序首先申请一整块空闲区，其首址为0，大小为32767；然后，提示用户使用哪种分配算法，再提示是分配还是回收；分配时要求输入申请区的大小，回收时要求输入释放区的首址和大小。
   （四）输出    
    要求每执行一次，输出一次空闲区队列情况，内容包括：
	编号  首址  终址  大小
    注：输出空闲区队列的排序，应符合所用分配算法的要求。

*/