动态分区算法

一. 软硬件环境

1.硬件环境: PC机

内存 256M；硬盘40G

2.软件环境： 操作系统：windows xp sp2

编辑环境：Visual C++6.0

word2002

二. 课程设计目的和意义

了解动态分区存储管理方式中的数据结构和分配算法，加深对动态分区存储管理方式及其实现技术的理解。。

三. 课程设计具体过程及内容

用C语言或Pascal语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程Allocate()和回收过程Free()。其中，空闲分区采用空闲分区链来组织，内存分配时，优先使用空闲区低地址部分的空间。假设初始状态，可用内存空间为640KB，作业请求序列如下（也可以编程从键盘输入，R表示请求，F表示释放）：

作业1请求130 KB。

作业2请求60 KB。

作业3请求100 KB。

作业2释放60 KB。

作业4请求200 KB。

作业3释放100 KB。

作业1释放130 KB。

作业5请求140 KB。

作业6请求60 KB。

作业7请求50 KB。

作业6释放60 KB。

要求每次分配和回收后显示出空闲区链的情况。如果不能为作业的请求进行内存分配，给出相应的提示信息。

四. 运行结果及说明

实验请求从源程序输入

int work[]={130,60,100,200,140,60,50};//作业请求序列

（1）菜单

（2）首次适应算法

（3）最佳适应算法

源程序：

#include

#include

#include

using namespace std;

struct memory

{

struct memory *former;

int address;//地址

int num;//作业号

int size;//分配内存大小

int state;//状态0表示空闲1表示已分配

struct memory *next;

};

typedef struct memory MEMORY;

MEMORY *mem;

const int size_min=10;//内存允许的最小空闲块的大小

bool is_optimist=false;//判断是否是最佳适应算法

void init();

void FF();

void alloc(MEMORY *,MEMORY *);//首次适应算法分配内存

void free(MEMORY *);//首次适应算法回收内存

void sort(MEMORY *);//对内存链进行排序

void insert(MEMORY *,MEMORY *);

void free_optimist(MEMORY *);

void print(MEMORY *);//打印内存链

int main()

{

int i=0;

while(1)

{

cout<<("\n请选择(1,2,0)");

cout<<("\n 1--首次适应算法");

cout<<"\n 2--最佳适应算法"<

cout<<" 0--中止程序"<

cin>>i;

if(i==1)

{

cout<<("\n结果如下:\n");

is_optimist=false;

init();

FF();

}

else if(i==2)

{

cout<<"\n结果如下：\n";

is_optimist=true;

init();

FF();

}

else if(i==0)

{

exit(1);

}

}

}

void init()

{

mem=new MEMORY;

mem->size=640;

//mem->state=0;

mem->former=0;

mem->next=0;

}

void FF()//首次适应算法

{

int i;

int work[]={130,60,100,200,140,60,50};//作业请求序列

//int assignment;

MEMORY *running;

for(i=0;i

{

running=(MEMORY *)malloc(sizeof(MEMORY));//初始化作业

if(running!=NULL)

{

running->former=NULL;

running->address=0;

running->num=i+1;

running->size=work[i];

running->state=0;

running->next=NULL;

//cout<<"作业初始化成功"<num<

if(is_optimist==true)//最佳适应算法

{

//cout<<"xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"<

alloc(mem,running);

}

else//首次适应算法

{

alloc(mem,running);

}

print(mem);

cout<

}

else

cout<<"没有足够的内存空间"<

if(rand()%3==1)

{

if(is_optimist==false)//首次适应算法

{

free(mem);

}

else//最佳适应算法

{

::free_optimist(mem);

}

}

}

}

void free(MEMORY *ptr)//作业处理完后释放内存空间

{

MEMORY *previous,*current;

previous=ptr;

current=previous->next;

while(current!=NULL)

{

if(current->state==1&&rand()%3==1)

{

break;

}

previous=current;

current=current->next;

}

if(current==NULL)

{

//cout<<"内存中没有任何作业！！！"<

return;

}

else if(current->next==NULL)

{

if(previous->state==0)

{

MEMORY *temp;

temp=current;

previous->size=previous->size+current->size;

previous->next=NULL;

cout<<"作业 "<<(current->num)<<"释放 "<<(current->size)<<"k 的空间"<

delete temp;

print(mem);

}

else

{

current->state=0;

cout<<"作业 "<<(current->num)<<"释放 "<<(current->size)<<"k 的空间"<

print(mem);

}

}

else if((current->next)->next==NULL)

{

if(previous->state==0&&(current->next)->state==0)

{

MEMORY *temp1,*temp2;

temp1=current;

temp2=current->next;

previous->size=previous->size+current->size+(current->next)->size;

previous->next=NULL;

cout<<"作业 "<<(current->num)<<"释放 "<<(current->size)<<"k 的空间"<

delete temp1;

delete temp2;

print(mem);

}

else if(previous->state==0)//释放的地址空间前面有空闲块则把它和前面的合并

{

MEMORY *temp;

temp=current;

previous->size=previous->size+current->size;

(current->next)->former=previous;

previous->next=current->next;

cout<<"作业 "<<(current->num)<<"释放 "<<(current->size)<<"k 的空间"<

delete temp;

print(mem);

}

else if((current->next)->state==0)//释放的地址空间后面有空闲块则把它和后面的空闲块合并

{

MEMORY *temp;

temp=current->next;

current->size=current->size+(current->next)->size;

current->state=0;

current->next=NULL;

cout<<"作业 "<<(current->num)<<"释放 "<<(current->size)<<"k 的空间"<

delete temp;

print(mem);

}

else//处理完的作业前后都没有空闲块时直接把它的状态改为没分配

{

current->state=0;

cout<<"作业 "<<(current->num)<<"释放 "<<(current->size)<<"k 的空间"<

print(mem);

}

}

else

{

if(previous->state==0&&(current->next)->state==0)

{

MEMORY *temp1,*temp2;

temp1=current;

temp2=current->next;

previous->size=previous->size+current->size+(current->next)->size;

((current->next)->next)->former=previous;

previous->next=(current->next)->next;

cout<<"作业 "<<(current->num)<<"释放 "<<(current->size)<<"k 的空间"<

delete temp1;

delete temp2;

print(mem);

}

else if(previous->state==0)//释放的地址空间前面有空闲块则把它和前面的合并

{

MEMORY *temp;

temp=current;

previous->size=previous->size+current->size;

(current->next)->former=previous;

previous->next=current->next;

cout<<"作业 "<<(current->num)<<"释放 "<<(current->size)<<"k 的空间"<

delete temp;

print(mem);

}

else if((current->next)->state==0)//释放的地址空间后面有空闲块则把它和后面的空闲块合并

{

MEMORY *temp;

temp=current->next;

current->size=current->size+(current->next)->size;

current->state=0;

((current->next)->next)->former=current;

current->next=(current->next)->next;

cout<<"作业 "<<(current->num)<<"释放 "<<(current->size)<<"k 的空间"<

delete temp;

print(mem);

}

else//处理完的作业前后都没有空闲块时直接把它的状态改为没分配

{

current->state=0;

cout<<"作业 "<<(current->num)<<"释放 "<<(current->size)<<"k 的空间"<

print(mem);

}

}

}

void alloc(MEMORY *ptr,MEMORY *assign)//内存分配

{

if(ptr->next==NULL)//内存没有作业运行

{

if(ptr->size>=assign->size)//内存空间大于作业所需空间

{

ptr->size=ptr->size-assign->size;//为内存分配空间

assign->state=1;

ptr->next=assign;

assign->former=ptr;

cout<<"作业 "<<(assign->num)<<"申请"<<(assign->size)<<" "<<"k的内存空间"<

}

else

{

cout<<"没有足够的内存空间为作业"<<(assign->num)<<"分配"<

delete assign;

}

}

else//内存中如果已经分配了空间

{

MEMORY *previous,*current;

previous=ptr;

current=previous->next;

while(current!=NULL)

{

if(current->size>assign->state==0)//如果当前内存空间大于作业所需空间并且内存没有被分配

{

break;

}

previous=current;

current=current->next;

}

if(current==NULL)//空闲链中没有为作业分配所需的空间

{

if(ptr->size>=assign->size)//内存中还有足够没分配的空间为此作业分配

{

assign->address =640-(ptr->size);//max+size_offset;//作业在内存中的首地址

ptr->size=ptr->size-assign->size;

assign->state=1;

assign->former=previous;

previous->next=assign;

cout<<"作业 "<<(assign->num)<<"申请"<<(assign->size)<<" "<<"k的内存空间"<

}

else

{

cout<<"没有足够的内存空间为作业"<<(assign->num)<<"分配"<

}

}

else//空闲链中有可为此作业分配的空间

{

if((current->size-assign->size)<=size_min)//空闲链所具备的空间与作业所需空间大小差不多时

{ //直接把整个空闲块的空间分配给作业否则从空闲块中

current->num=assign->num; //划出与作业等同的空间

current->state=1;

delete assign;//free(assign);

cout<<"作业 "<<(current->num)<<"申请"<<(current->size)<<" "<<"k的内存间"<

}

else//从空闲块中划分一块与作业大小等同的空间

{

current->size=current->size-assign->size;

assign->state=1;

assign->address=current->address+current->size;

if(current->next==NULL)//此要分配的空间是空闲链的最后一个元素

{

assign->former=current;

current->next=assign;

}

else

{

assign->next=current->next;

(current->next)->former=assign;

assign->former=current;

current->next=assign;

}

cout<<"作业 "<<(assign->num)<<"申请"<<(assign->size)<<" "<<"k的内存空间"<

}

}

}

if((ptr->next)->next!=NULL&&is_optimist==true)

sort(ptr);//排序由空闲块从小到大

//print(ptr);

}

void sort(MEMORY *ptr)

{

MEMORY *temp=new MEMORY;

temp->next=0;

temp->former=0;

while(ptr->next)

{

if((ptr->next)->next==NULL)//内存链中只有两个元素

{

MEMORY *p;

p=ptr->next;

ptr->next=NULL;

insert(temp,p);

}

else//内存链中有多个元素

{

MEMORY *p;

p=ptr->next;

p->former=ptr;

ptr->next=p->next;

(p->next)->former=ptr;

insert(temp,p);

}

}

ptr->next=temp->next;

(temp->next)->former=ptr;

delete temp;

}

void insert(MEMORY *queue,MEMORY *item)

{

MEMORY *previous,*current;

previous=queue;

current=previous->next;

while(current!=NULL && item->size>=current->size)

{

previous=current;

current=current->next;

}

if(previous==queue)//所要插入的元素最小

{

if(queue->next==NULL)//内存链中只有一个元素

{

item->next=0;

queue->next=item;

item->former=queue;

}

else//内存链中有多个元素

{

item->next=queue->next;

(queue->next)->former=item;

item->former=queue;

queue->next=item;

}

}

else//定位到要插入的元素

{

item->next=current;

item->former=previous;

if(current==NULL)

{

previous->next=item;

}

else

{

current->former=item;

previous->next=item;

}

}

}

void free_optimist(MEMORY *ptr)

{

MEMORY *previous,*current;

previous=ptr;

current=previous->next;

while(current!=NULL)

{

if(current->state==1&&rand()%3==1)

{

break;

}

previous=current;

current=current->next;

}

if(current==NULL)

{

//cout<<"内存中没有任何作业！！！"<

return;

}

else if(current->next==NULL)

{

if(previous->state==0&&((previous->address+previous->size)==current->address))

{

MEMORY *temp;

temp=current;

previous->size=previous->size+current->size;

previous->next=NULL;

cout<<"作业 "<<(current->num)<<"释放 "<<(current->size)<<"k 的空间"<

delete temp;

print(mem);

}

else

{

current->state=0;

cout<<"作业 "<<(current->num)<<"释放 "<<(current->size)<<"k 的空间"<

print(mem);

}

}

else if((current->next)->next==NULL)

{

if(previous->state==0&&(current->next)->state==0&&((previous->address+previous->size)==current->address)&&((current->size+current->address)==(current->next)->address))

{

MEMORY *temp1,*temp2;

temp1=current;

temp2=current->next;

previous->size=previous->size+current->size+(current->next)->size;

previous->next=NULL;

cout<<"作业 "<<(current->num)<<"释放 "<<(current->size)<<"k 的空间"<

delete temp1;

delete temp2;

print(mem);

}

else if(previous->state==0&&((previous->address+previous->size)==current->address))//释放的地址空间前面有空闲块则把它和前面的合并

{

MEMORY *temp;

temp=current;

previous->size=previous->size+current->size;

(current->next)->former=previous;

previous->next=current->next;

cout<<"作业 "<<(current->num)<<"释放 "<<(current->size)<<"k 的空间"<

delete temp;

print(mem);

}

else if((current->next)->state==0&&((current->size+current->address)==(current->next)->address))//释放的地址空间后面有空闲块则把它和后面的空闲块合并

{

MEMORY *temp;

temp=current->next;

current->size=current->size+(current->next)->size;

current->state=0;

current->next=NULL;

cout<<"作业 "<<(current->num)<<"释放 "<<(current->size)<<"k 的空间"<

delete temp;

print(mem);

}

}

else

{

if(previous->state==0&&(current->next)->state==0&&((previous->address+previous->size)==current->address)&&((current->size+current->address)==(current->next)->address))

{

MEMORY *temp1,*temp2;

temp1=current;

temp2=current->next;

previous->size=previous->size+current->size+(current->next)->size;

((current->next)->next)->former=previous;

previous->next=(current->next)->next;

cout<<"作业 "<<(current->num)<<"释放 "<<(current->size)<<"k 的空间"<

delete temp1;

delete temp2;

print(mem);

}

else if(previous->state==0&&(previous->address+previous->size)==current->address)//释放的地址空间前面有空闲块则把它和前面的合并

{

MEMORY *temp;

temp=current;

previous->size=previous->size+current->size;

previous->state=0;

(current->next)->former=previous;

previous->next=current->next;

cout<<"作业 "<<(current->num)<<"释放 "<<(current->size)<<"k 的空间"<

delete temp;

print(mem);

}

else if((current->next)->state==0&&((current->size+current->address)==(current->next)->address))//释放的地址空间后面有空闲块则把它和后面的空闲块合并

{

MEMORY *temp;

temp=current->next;

current->size=current->size+(current->next)->size;

current->state=0;

((current->next)->next)->former=current;

current->next=(current->next)->next;

cout<<"作业 "<<(current->num)<<"释放 "<<(current->size)<<"k 的空间"<

delete temp;

print(mem);

}

else//处理完的作业前后都没有空闲块时直接把它的状态改为没分配

{

current->state=0;

cout<<"作业 "<<(current->num)<<"释放 "<<(current->size)<<"k 的空间"<

print(mem);

}

}

if((ptr->next)->next!=NULL)

sort(ptr);//排序由空闲块从小到大

}

void print(MEMORY *ptr)

{

MEMORY *temp;

temp=ptr->next;

cout<<"\n内存链的状态为："<

while(temp!=NULL)

{

cout<<"分配的地址为："<address<<" 分配的空间："<size<<"k"

<<" 运行的作业号:"<num;

if(temp->state==0)

{

cout<<" 内存空闲";

}

else

{

cout<<" 内存已分配";

}

cout<

temp=temp->next;

}

}

本文来源：https://www.2haoxitong.net/k/doc/5891f9eeb84ae45c3a358c0d.html