www.pudn.com > Memory_Dis_RE.rar > Memory_Dis_RE.CPP
#include
#include
#include
#include
#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->sizenext;
if(pointer1==link)
{//只有一个结点
if(pointer1->sizesize>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!"<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<<"队列中没有适合的分区!"<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->sizenext!=NULL)
pointer=pointer->next;
if(pointer->next==NULL)
{
cout<<"队列中没有适合的分区!"<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<<"……………………………已经使用区队列情况…………………………………………"<adr<<'\t';
cout<<"Size:"<size<next;//指针后移
}
cout<<"……………………………已经使用区队列情况…………………………………………"<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<<"回收错误"<next;
Size=pointer->size;
p->next=pointer->next;
pointer->next=NULL;
}
}
return pointer;
}
void Print_Empty(node *link)
{//输出空闲区队列的排序
node *pointer;
pointer=link;
cout<<"---------------------------空闲区队列情况-------------------------------"<adr<<'\t';
cout<<"Size:"<size<next;//指针后移
}
cout<<"------------------------------------------------------------------------"<size==0)//队列中没有元素
empty=Node;
else if(Node->adr+Node->sizeadr)
{//
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<<"︿﹀︿﹀︿﹀︿﹀︿﹀︿﹀︿﹀︿﹀︿﹀︿﹀︿﹀︿﹀︿﹀︿﹀︿﹀︿﹀︿︿﹀﹀"<>algorithm;
cout<<"------------------------------"<>select;
cout<<"------------------------------"<>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；然后，提示用户使用哪种分配算法，再提示是分配还是回收；分配时要求输入申请区的大小，回收时要求输入释放区的首址和大小。
（四）输出
要求每执行一次，输出一次空闲区队列情况，内容包括：
编号 首址 终址 大小
注：输出空闲区队列的排序，应符合所用分配算法的要求。
*/