动态分区分配方式的模拟C语言代码和C++代码

实验三 使用动态分区分配方式的模拟

1、实验目的

了解动态分区分配方式中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。 2、实验内容

(1) 用C语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloc( )和回收过程free( )。其中，空闲分区通过空闲分区链来管理：在进行内存分配时，系统优先使用空闲区低端的空间。

(2) 假设初始状态下，可用的内存空间为640KB，并有下列的请求序列： ?作业1申请130KB。 ?作业2申请60KB。 ?作业3申请100KB。 ?作业2释放60KB。 ?作业4申请200KB。 ?作业3释放100KB。 ?作业1释放130KB。 ?作业5申请140KB。 ?作业6申请60KB。 ?作业7申请50KB。 ?作业6释放60KB。

请分别采用首次适应算法和最佳适应算法，对内存块进行分配和回收，要求每次分配和回收后显示出空闲分区链的情况。

程序代码——C语言实现

#include #include

struct node //空闲分区链结点的定义 { node *before; node *after; int size; int address; int state; };

node L;

struct usenode { usenode *next; int num; int add; int size; }U,*n;

void Init() //空闲分区链的初始化 { node *p; p=(node *)malloc(sizeof(node)); p->before=&L; p->after=NULL; p->size=640; p->address=0; p->state=0; L.after=p; L.before=NULL; L.size=0; U.next=NULL; n=&U; }

node *search(int a) { node *p=L.after; if(p==NULL) { printf(\没有空闲的区域!\ p=NULL; return p; } else { while(p!=NULL && a>p->size) p=p->after; if(p==NULL) { printf(\没有找到合适的空闲空间!\ p=NULL; return p; } else return p; } }

void recovery(int a,int b) //内存回收算法 {

node *c,*s,*r=L.after; node *d=L.after,*e; usenode *k=U.next,*h=&U;

while(k!=NULL && a!=k->num) { h=k; k=k->next; } if(k==NULL) printf(\没有找到这样的作业!\ else { h->next=k->next; if(h->next==NULL) n=h; } while(r!=NULL) //若回收得到的空闲块的前方有空闲块合并此空闲块 { if(k->add==r->address+r->size) { r->size=r->size+k->size; break; } else r=r->after; }

if(r==NULL) //若回收得到的空闲块的后面有空闲块合并此空闲块 { r=L.after; while(r!=NULL) { if(k->add+k->size==r->address) { r->address=k->add; r->size=r->size+k->size; break; } else r=r->after;

} } while(d!=NULL) //保证空闲链表中没有相邻的空闲空间 { if(d->after!=NULL) e=d->after; else break; if(d->address+d->size==e->address) { d->after=e->after; while(e->after!=NULL) e->after->before=d; d->size=d->size+e->size; free(e); break; } else d=d->after; } if(r==NULL) { r=L.after;

c=(node *)malloc(sizeof(node)); c->size=b; c->address=k->add; if(L.after==NULL) { c->after=L.after; c->before=&L; L.after=c; } else { r=L.after; while(r!=NULL) { if(r->address>c->address) { c->after=r;

c->before=r->before; r->before->after=c; r->before=c; free(k); return; } else r=r->after; } } } free(k); }

void alloc(int a ,int b) //分配内存算法 { node *p,*q=L.after; usenode *m; p=search(b); if(p==NULL) return; m=(usenode *)malloc(sizeof(usenode));//生成一个被占用链表的结点,并插入到该链表的尾部 m->add=p->address; m->size=b; m->num=a; m->next=n->next; n->next=m; n=m; //保证n始终指向被占用链表的尾部，方便以后新生成结点的插入 if(p->size>b) //如果申请空间的大小小于找到空闲空间的大小的处理 { p->size=p->size-b; p->address=p->address+b; } else //如果申请空间的大小等于找到空闲空间的大小的处理 {

p->before->after=p->after; if(p->after!=NULL) p->after->before=p->before; free(p); }