实验4主存空间的分配与回收.docx

实验4主存空间的分配与回收.docx

《实验4主存空间的分配与回收.docx》由会员分享，可在线阅读，更多相关《实验4主存空间的分配与回收.docx（34页珍藏版）》请在冰点文库上搜索。

实验4主存空间的分配与回收

实验四主存空间的分配和回收

1.目的和要求

1.1.实验目的

用高级语言完成一个主存空间的分配和回收程序，以加深对动态分区分配方式及其算法的理解。

1.2.实验要求

采用连续分配方式之动态分区分配存储管理，使用首次适应算法、最佳适应算法2种算法完成设计。

（1）**设计一个作业申请队列以及作业完成后的释放顺序，实现主存的分配和回收。

采用分区说明表进行。

（2）或在程序运行过程，由用户指定申请与释放。

（3）设计一个空闲区说明表，以保存某时刻主存空间占用情况。

把空闲区说明表的变化情况以及各作业的申请、释放情况显示。

[提示]：

（1） 动态分区（可变分区方式）是按作业需要的主存空间大小来分割分区的。

当要装入一个作业时，根据作业需要的主存容量查看是否有足够的空闲空间，若有，则按需分配，否则，作业无法装入。

假定内存大小为256KB，空闲区说明表格式为：

·起始地址——指出空闲区的起始地址；

·长度——一个连续空闲区的长度；

·状态——有两种状态，一种是“已分配”状态；另一种是“空表目”状态，表示该表项目前没有使用。

（2） 采用首次适应算法分配回收内存空间。

运行时，输入一系列分配请求和回收请求。

要求能接受来自键盘的空间申请及释放请求，能显示分区分配及回收后的内存布局情况。

2、源程序代码

#include"stdio.h"

#include

#include

#include"iostream.h"

#definegetjcb（type）（type*）malloc（sizeof（type））

#definegetsub（type）（type*）malloc（sizeof（type））

#defineNULL0

intnum,num2;//要调度的作业数和要回收的区域数

intm=0;//已分配作业数

intflag;//分配成功标志

intisup,isdown;//回收区域存在上邻和下邻的标志

intis=0;

structjcb{

charname[10];

charstate;

intntime;//所需时间

intsize;//所需空间大小

intaddr;//所分配分区的首地址

structjcb*link;

}*ready=NULL,*p,*q,*as=NULL;

//作业队列ready,已分配作业队列as

typedefstructjcbJCB;

structsubarea{//分区块

charname[10];

intaddr;//分区首地址

intsize;//分区大小

charstate;

structsubarea*link;

}*sub=NULL,*r,*s,*cur;

//空闲分区队列sub,当前分区指针cur

typedefstructsubareaSUB;

voidsort_sub（）/*对空闲分区按从小到大排序*/

{SUB*first,*second;

intinsert=0;

if（（sub==NULL）||（（s->size）<（sub->size）））/*插在队列之首*/

{s->link=sub;

sub=s;

}

else{first=sub;/*寻找适当的位置插入*/

second=first->link;

while（second!

=NULL）

{

if（（s->size）<（second->size））

{

s->link=second;

first->link=s;

second=NULL;

insert=1;

}

else

{

first=first->link;

second=second->link;

}

}

if（insert==0）first->link=s;/*插在队尾*/

}

}

voidsort_sub（）/*对空闲分区按从小到大排序*/sort*/

{

JCB*first;

if（ready==NULL）ready=p;

else{

first=ready;

while（first->link!

=NULL）

first=first->link;

first->link=p;

p->link=NULL;

}

}

voidlastsort（）/*建立对已分配作业队列的排列函数,直接插在队列之尾sort3*/

{

JCB*fir;

if（as==NULL）as=q;

else{

fir=as;

while（fir->link!

=NULL）

fir=fir->link;

fir->link=q;

q->link=NULL;

}

m++;

}

voidinput（）/*建立作业控制块函数*/

{

inti;

printf（"\n请输入要调度的总作业数:

"）;

scanf（"%d",&num）;

for（i=0;i

{

printf（"\n作业号No.%d:

\n",i）;

p=getjcb（JCB）;

printf（"\n输入作业名:

"）;

scanf（"%s",&p->name）;

printf（"\n输入作业的大小:

"）;

scanf（"%d",&p->size）;

printf（"\n输入作业所需运行时间:

"）;

scanf（"%d",&p->ntime）;

p->state='w';

p->link=NULL;

firstsort（）;/*调用sort函数*/

}

printf（"\n按任一键继续......\n"）;

getch（）;

}

voidinput2（）/*建立要回收区域的函数*/

{

JCB*k;

inthas;

q=getjcb（JCB）;

printf（"\n输入区域名（作业名）:

"）;

scanf（"%s",&q->name）;

p=as;

while（p!

=NULL）

{if（strcmp（p->name,q->name）==0）/*在已分配作业队列中寻找*/

{

q->addr=p->addr;

q->size=p->size;

has=1;/*输入作业名存在标志位*/

if（p==as）as=p->link;/*在已分配作业队列中删除该作业*/

else

{k=as;

while（k->link!

=p）k=k->link;

k->link=k->link->link;/*删除*/

}

printf（"输出该作业首地址:

%d\n",q->addr）;

printf（"输出该作业大小:

%d\n\n",q->size）;

q->link=NULL;

break;

}

else

{p=p->link;has=0;}/*输入作业名不存在标志*/

}

if（has==0）

{printf（"\n输入作业名错误!

请重新输入!

\n"）;

input2（）;

}

}

voidinit_sub（）/*初始化空闲分区表*/

{

r=getsub（SUB）;

strcpy（r->name,"one"）;r->addr=5;r->size=10;r->state='n';

sub=r;

s=getsub（SUB）;

strcpy（s->name,"two"）;s->addr=20;s->size=120;s->state='n';

sub->link=s;r=s;

s=getsub（SUB）;

strcpy（s->name,"three"）;s->addr=160;s->size=40;s->state='n';

r->link=s;r=s;

s=getsub（SUB）;

strcpy（s->name,"four"）;s->addr=220;s->size=10;s->state='n';

r->link=s;r=s;

s=getsub（SUB）;

strcpy（s->name,"five"）;s->addr=250;s->size=20;s->state='n';

r->link=s;

}

voiddisp（）/*空闲分区表的显示函数*/

{

printf（"\t\t分区首地址长度状态\n"）;

r=sub;

while（r!

=NULL）

{

printf（"\t\t%s\t\t%d\t\t%d\t\t%c\n",r->name,r->addr,r->size,r->state）;

r=r->link;

}

printf（"\n"）;

}

voiddisp2（）/*显示已分配内存的作业表函数*/

{

printf（"\t\t作业名首地址长度状态\n"）;

p=as;

while（p!

=NULL）

{

printf（"\t\t%s\t\t%d\t\t%d\t\t%c\n",p->name,p->addr,p->size,p->state）;

p=p->link;

}

printf（"\n\n"）;

}

voidperfit（JCB*pr）/*最佳适应作业分区assign*/

{

SUB*k;

r=sub;

while（r!

=NULL）

{

if（（（r->size）>（pr->size））&&（r->state=='n'））/*有空闲分区大于作业大小的情况*/

{

pr->addr=r->addr;

r->size-=pr->size;

r->addr+=pr->size;

if（r==sub）sub=r->link;/*删除空闲分区*/

else

{s=sub;

while（s->link!

=r）s=s->link;

s->link=s->link->link;/*删除空闲分区*/

}

flag=1;/*分配成功标志位置1*/

q=pr;

lastsort（）;/*插入已分配作业队列*/

//重新插入剩余空闲分区,插在合适位置

if（r->sizesize）/*插入队首*/

{

r->link=sub;

sub=r;

}

else/*插在适当的位置*/

{

s=sub;

while（（s->size）<=（r->size））s=s->link;

k=sub;

if（k==s）{r->link=sub->link;sub=r;}/*插在队首的后一个位置*/

else/*第二个以后的位置*/

{

while（k->link!

=s）k=k->link;

r->link=s;

k->link=r;

}

}

printf（"作业%s的分区为[%s],首地址为%d.\n",p->name,r->name,pr->addr）;

break;

}

elseif（（（r->size）==（pr->size））&&（r->state=='n'））/*有空闲分区等于作业大小的情况*/

{

pr->addr=r->addr;

flag=1;/*分配成功标志位置1*/

q=pr;

lastsort（）;/*插入已分配作业队列*/

s=sub;/*空闲分区已完成分配,应删除*/

while（s->link!

=r）s=s->link;

s->link=s->link->link;/*删除空闲分区*/

printf（"作业%s的分区为[%s],首地址为%d.\n",p->name,r->name,pr->addr）;

break;

}

else

{r=r->link;flag=0;}

}

if（flag==0）/*作业过大的情况*/

{

printf（"作业%s长度过大，内存不足，分区分配出错!

\n",p->name）;

is=1;

}

}

voidfirstfit（JCB*pr）/*首次适应作业分区*/

{

SUB*k;

r=sub;/*从空闲表头开始寻找*/

while（r!

=NULL）

{

if（（（r->size）>（pr->size））&&（r->state=='n'））/*有空闲分区大于作业大小的情况*/

{

pr->addr=r->addr;

r->size-=pr->size;

r->addr+=pr->size;

flag=1;/*分配成功标志位置1*/

q=pr;

q->state='r';

lastsort（）;/*插入已分配作业队列*/

printf（"作业%s的分区为[%s],首地址为%d.\n",p->name,r->name,pr->addr）;

break;

}

elseif（（（r->size）==（pr->size））&&（r->state=='n'））/*有空闲分区等于作业大小的情况*/

{

pr->addr=r->addr;

flag=1;/*分配成功标志位置1*/

q=pr;

lastsort（）;/*插入已分配作业队列*/

s=sub;/*空闲分区已完成分配,应删除*/

while（s->link!

=r）s=s->link;

s->link=s->link->link;/*删除空闲分区*/

printf（"作业%s的分区为[%s],首地址为%d.\n",p->name,r->name,pr->addr）;

break;

}

else

{r=r->link;flag=0;}

}

if（flag==0）/*作业过大的情况*/

{

printf（"作业%s长度过大，内存不足，分区分配出错!

\n",p->name）;

is=1;

}

}

voidcyclefit（JCB*pr）/*循环首次适应作业分区*/

{

SUB*k;

r=cur;/*从当前指针开始寻找*/

while（r!

=NULL）

{

if（（（r->size）>（pr->size））&&（r->state=='n'））/*有空闲分区大于作业大小的情况*/

{

pr->addr=r->addr;

r->size-=pr->size;

r->addr+=pr->size;

flag=1;/*分配成功标志位置1*/

cur=r;/*更新当前指针*/

q=pr;

q->state='r';

lastsort（）;/*插入已分配作业队列*/

printf（"作业%s的分区为[%s],首地址为%d.\n",p->name,r->name,pr->addr）;

break;

}

elseif（（（r->size）==（pr->size））&&（r->state=='n'））/*有空闲分区等于作业大小的情况*/

{

pr->addr=r->addr;

flag=1;/*分配成功标志位置1*/

cur=r;

q=pr;

lastsort（）;/*插入已分配作业队列*/

s=sub;/*空闲分区已完成分配,应删除*/

while（s->link!

=r）s=s->link;

s->link=s->link->link;/*删除空闲分区*/

printf（"作业%s的分区为[%s],首地址为%d.\n",p->name,r->name,pr->addr）;

break;

}

else

{

r=r->link;

if（r==NULL）/*当前指针为空时,重新由空闲区队列之首寻找*/

{

k=cur;/*作保存当前指针用*/

cur=sub;

r=cur;

}

if（k==r）/*又回到开始的指针时,确定为没有空间满足要求*/

{

cur=k;

break;

}

flag=0;/*分配不成功标志*/

}

}

if（flag==0）/*作业过大的情况*/

{

printf（"作业%s长度过大，内存不足，分区分配出错!

\n",p->name）;

is=1;

}

}

voidless_to_more（）/*把分区按大小从小到大排序*/

{

r=sub;

sub=NULL;

while（r!

=NULL）

{

s=r;

r=s->link;

s->link=NULL;

sort_sub（）;/*调用排序函数*/

}

}

voidreclperfit（JCB*pr）/*最佳适应回收区域,按分区大小排列*/

{

SUB*k;

r=sub;

while（r!

=NULL）

{

if（r->addr==（（pr->addr）+（pr->size）））/*回收区域有下邻*/

{

pr->size+=r->size;

s=sub;

isdown=1;/*下邻标志位置1*/

while（s!

=NULL）

{

if（（（s->addr）+（s->size））==（pr->addr））/*有下邻又有上邻*/

{

s->size+=pr->size;

k=sub;

while（k->link!

=r）k=k->link;

k->link=k->link->link;

isup=1;/*上邻标志位置1*/

break;

}

else

{s=s->link;isup=0;}/*上邻标志位置0*/

}

if（isup==0）/*有下邻无上邻*/

{

r->addr=pr->addr;

r->size=pr->size;

}

break;

}

else

{r=r->link;isdown=0;}/*下邻标志位置0*/

}

if（isdown==0）/*区域无下邻*/

{

s=sub;

while（s!

=NULL）

{

if（（（s->addr）+（s->size））==（pr->addr））/*无下邻但有上邻*/

{

s->size+=pr->size;

isup=1;/*上邻标志位置1*/

break;

}

else

{s=s->link;isup=0;}/*上邻标志位置0*/

}

if（isup==0）/*无下邻且无上邻*/

{

k=getsub（SUB）;/*重新生成一个新的分区结点*/

strcpy（k->name,pr->name）;

k->addr=pr->addr;

k->size=pr->size;

k->state='n';

r=sub;

while（r!

=NULL）

{

if（（r->size）>（k->size））/*按分区大小排列,回收区域插在合适的位置*/

{

if（r==sub）/*第一个空闲分区大于回收区域的情况*/

{k->link=r;sub->link=k;}

else

{

s=sub;

while（s->link!

=r）s=s->link;

k->link=r;

s->link=k;

}

break;

}

elser=r->link;

}

if（r==NULL）/*所有空闲分区都大于回收区域的情况*/

{

s=sub;

while（s->link!

=NULL）s=s->link;

s->link=k;

k->link=NULL;

}

}

}

printf（"\n区域%s己回收.",pr->name）;

}

voidreclfirst（JCB*pr）/*首次适应与循环首次适应区域回收*/

{

SUB*k;

r=sub;

while（r!

=NULL）

{

if（r->addr==（（pr->addr）+（pr->size）））/*回收区域有下邻*/

{

pr->size+=r->size;

s=sub;

isdown=1;/*下邻标志位置1*/

while（s!

=NULL）

{

if（（（s->addr）+（s->size））==（pr->addr））/*有下邻又有上邻*/

{

s->size+=pr->size;

k=sub;

while（k->link!

=r）k=k->link;

k->link=k->link->link;

isup=1;/*上邻标志位置1*/

break;

}

else

{s=s->link;isup=0;}/*上邻标志位置0*/

}

if（isup==0）/*有下邻无上邻*/

{

r->addr=pr->addr;

r->size=pr->size;

}

break;

}

else

{r=r->link;isdown=0;}/*下邻标志位置0*/

}

if（isdown==0）/*区域无下邻*/

{

s=sub;

while（s!

=NULL）

{

if（（（s->addr）+（s->size））==（pr->addr））/*无下邻但有上邻*/

{

s->size+=pr->size;

isup=1;/*上邻标志位置1*/

break;

}

else

{s=s->link;isup=0;}/*上邻标志位置0*/

}

if（isup==0）/*无下邻且无上邻*/

{

k=getsub（SUB）;/*重新生成一个新的分区结点*/

strcpy（k->name,pr->name）;

k->addr=pr->addr;

k->size=pr->size;

k->state='n';

r=sub;

while（r!

=NULL）

{

if（（r->addr）>（k->addr））/*按分区首地址排列,回收区域插在合适的位置*/

{

if（r==sub）/*第一个空闲分区首址大于回收区域的情况*/

{k->link=r;sub->link=k;}

else

{

s=sub;

while（s->link!

=r）s=s->link;

k->link=r;

s->link=k;

}

break;

}

elser=r->