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

1、实验四 主存空间的分配和回收1. 目的和要求1.1. 实验目的用高级语言完成一个主存空间的分配和回收程序，以加深对动态分区分配方式及其算法的理解。1.2. 实验要求/采用连续分配方式之动态分区分配存储管理，使用首次适应算法、/最佳适应算法2种算法完成设计。（1）*设计一个作业申请队列以及作业完成后的释放顺序，实现 主存的分配和回收。采用分区说明表进行。（2）或在程序运行过程，由用户指定申请与释放。（3）设计一个空闲区说明表，以保存某时刻主存空间占用情况。把空闲区说明表的变化情况以及各作业的申请、释放情况显示。提示:（1）动态分区（可变分区方式）是按作业需要的主存空间大小来分割分区的。当要装入一

2、个作业时，根据作业需要的主存容量查看是否有足够的空闲空间，若有,则按需分配，否则，作业无法装入。假定内存大小为256KB空闲区说明表格式为：起始地址一一指出空闲区的起始地址；长度一一一个连续空闲区的长度；状态有两种状态，一种是“已分配”状态；另一种是“空表目”状态，表 示该表项目前没有使用。（2）采用首次适应算法分配回收内存空间。 运行时，输入一系列分配请求和回收 请求。要求能接受来自键盘的空间申请及释放请求， 能显示分区分配及回收后的内存布 局情况。2、源程序代码#include ""#include <>#include <>#include &

3、quot;"#define getjcb(type) (type*)malloc(sizeof(type)#define getsub(type) (type*)malloc(sizeof(type)#define NULL 0int num,num2; d:n",i);p=getjcb(JCB);printf("n输入作业名:");scanf("%s",&p->name);printf("n输入作业的大小:");scanf("%d",&p->size);printf

4、("n输入作业所需运行时间：")；scanf("%d",&p->ntime);p_>state='w：p->link=NULL;firstsort(); /*调用 sort 函数 */printf("n 按任一键继续n");getch();void input2() | /* 建立要回收区域的函数 */JCB *k;int has;q=getjcb(JCB);printf("n 输入区域名(作业名):");scanf("%s", &q->name)

5、;p=as;while(p!=NULL)if(strcmp(p->name,q->name)=O) /*在已分配作业队列中寻找 */q->addr=p->addr;q->size=p->size;has=1; /*输入作业名存在标志位 */if(p=as) as=p->link; /*在已分配作业队列中删除该作业*/elsek=as;while(k->link!=p) k=k->link;k->link=k->link->link; /*删除 */printf(" 输出该作业首地址:%dn",q->

6、;addr);printf(”输出该作业大小：dnn",q->size);q->link=NULL;break;elsep=p->link; has=O; /*输入作业名不存在标志*/if(has=0)printf("n输入作业名错误！请重新输入!n");input2();void init_sub()/*初始化空闲分区表*/r=getsub(SUB);strcpy(r->name,"one"); r->addr=5; r->size=10; r->state='n'sub=r;s=ge

7、tsub(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->a

8、ddr=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;void disp() /*空闲分区表的显示函数 */printf("tt 分区首地址长度状态n");r=sub;while(r!=NULL)printf("tt %stt%dtt%dtt%cn"

9、,r->name,r->addr,r->size,r->state);r=r->link;printf("n");void disp2() /*显示已分配内存的作业表函数 */printf("tt 作业名首地址长度状态n");p=as;while(p!=NULL)printf("tt %stt%dtt%dtt%cn",p->name,p->addr,p->size,p->state);p=p_>link;printf("nn");void perfit(J

10、CB *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; /*删除空闲分区 */elses=sub;while(s->link!=r) s=s->link;s->l

11、ink=s->link->link; /*删除空闲分区 */flag=1; /*分配成功标志位置1*/q=pr;lastsort(); /*插入已分配作业队列*/n",p->name,r->name,pr->addr);break;else if(r->size)=(pr->size)&&(r->state='n') /*有空闲分区等于作业大小的情况 */pr->addr=r->addr;flag=1; /*分配成功标志位置 1*/q=pr;lastsort();/*插入已分配作业队列*/s=

12、sub; /*空闲分区已完成分配，应删除*/while(s->link!=r) s=s->link;s->link=s->link->link;/* 删除空闲分区 */printf(”作业 $的分区为%s,首地址为 d.n",p->name,r->name,pr->addr);break;elser=r->link; flag=O;if(flag=0) /*作业过大的情况*/printf("作业$长度过大，内存不足，分区分配出错！n",p->name);is=1;void firstfit(JCB *pr

13、)/*首次适应作业分区*/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(" 作业 $的分

14、区为%s,首地址为 %d.n",p->name,r->name,pr->addr);break;else if(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->li

15、nk->link;/* 删除空闲分区 */printf(" 作业 $的分区为%s,首地址为 %d.n",p->name,r->name,pr->addr);break;elser=r->link; flag=O;if(flag=O) /*作业过大的情况*/printf(”作业$长度过大，内存不足，分区分配出错 ！n",p->name);is=1;void cyclefit(JCB *pr) /*循环首次适应作业分区*/SUB *k;r=cur; /*从当前指针开始寻找*/while(r!=NULL)if(r->size)&

16、gt;(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,首地址为 %d.n",p->name,r->name,pr->addr);

17、break;else if(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,

18、首地址为 %d.n",p->name,r->name,pr->addr);break;elser=r->link;if(r=NULL)/*当前指针为空时，重新由空闲区队列之首寻找 */k=cur; /*cur=sub;r=cur;if(k=r) /*cur=k;break;flag=0; /*if(flag=0)/*作保存当前指针用*/又回到开始的指针时，确定为没有空间满足要求*/分配不成功标志*/作业过大的情况*/printf（”作业$长度过大，内存不足，分区分配出错！n",p->name）;is=1;void less_to_more()

19、/*把分区按大小从小到大排序 */ r=sub;sub=NULL;while(r!=NULL)s=r;r=s->link;s->link=NULL;sort_sub(); /* 调用排序函数*/reclperfit(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->siz

20、e)=(pr->addr) /*有下邻又有上邻*/s->size+=pr->size;k=sub;while(k->link!=r) k=k->link;k->link=k->link->link;上邻标志位置1*/isup=1;/*break;elses=s->link; isup=O; /*上邻标志位置0*/if(isup=0)/*有下邻无上邻*/r->addr=pr->addr;r->size=pr->size;break;elser=r->link; isdown=0; /*下邻标志位置0*/if(is

21、down=0)/*区域无下邻*/s=sub;while(s!=NULL)if(s->addr)+(s->size)=(pr->addr) /*无下邻但有上邻*/s->size+=pr->size;isup=1;break;else s=s->link; isup=0;/*上邻标志位置0*/上邻标志位置1*/if(isup=0)/*k=getsub(SUB); /*无下邻且无上邻*/重新生成一个新的分区结点*/strcpy(k->name,pr->name);k_>addr=pr->addr;k->size=pr->size

22、;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;else r=r->link;if(r=NULL) /*所有空闲分区都大于回收区域的情况*/s=sub;while(s-

23、>link!=NULL) s=s->link;s->link=k;k->link=NULL; printf("n 区域s己回收.",pr->name);void reclfirst(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->a

24、ddr)+(s->size)=(pr->addr) /*s->size+=pr->size;有下邻又有上邻*/k=sub;while(k->link!=r) k=k->link;k->link=k->link->link;上邻标志位置1*/isup=1;/*break;elses=s->link; isup=O; /*上邻标志位置0*/if(isup=0)/*有下邻无上邻*/r->addr=pr->addr;r->size=pr->size;elsebreak;if(isdown=0)r=r->link;

25、 isdown=0; /*下邻标志位置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;if(isup=0)/*k=getsub(SUB); /*上邻标志位置0*/无下邻且无上邻*/重新生成一个新的分区结点*/strcpy(k->name,pr->name);k_>addr=pr->addr;k->si

26、ze=pr->size;k->state='n'r=sub;while(r!=NULL)if(r->addr)>(k->addr) /*按分区首地址排列，回收区域插在合适的位置*/if(r=sub) /*第一个空闲分区首址大于回收区域的情况*/ k->link=r; sub->link=k; elses=sub;/ while(s->link!=r) s=s->link;k->link=r;s->link=k;break;else r=r->link;if(r=NULL) /*所有空闲分区的首址都大于回收区

27、域首址的情况*/s=sub;while(s->link!=NULL) s=s->link;s->link=k;k->link=NULL;printf("n 区域s己回收.",pr->name);void print()显示空闲分区n");printf("ttt 2.分配作业n");printf("ttt 3.回收作业n");printf("ttt 0.返回菜单n");printf("ttt请选择你要的操作:");firstfitf()Jelse print

28、f("n作业没有全部被分配内存.n");getch(); system("cls"); firstfitf(); break;case 3:system("cls");disp2();printf("nn按任意键进行区域回收.");printf("n");while(as!=NULL)getch();input2();printf("按任意键继续.")；getch();printf("n");/ reclfirst(q);getch();printf(&q

29、uot;ntt回收后的空闲分区表n");disp();printf("ntt已分配作业表n");disp2();printf("n继续回收.(Enter)");printf("n所有已分配作业已完成r)；printf("nPress any key to return.");getch();system("cls");firstfitf();break;system("cls");firstfitf();break;cyclefirstf();else printf(&quo

30、t;n作业没有全部被分配内存.n");getch();system("cls");cyclefirstf();break;case '3':system("cls");disp2();printf("nn按任意键进行区域回收.")；while(as!=NULL)getch();printf("n");input2();printf("按任意键继续.")；getch();printf("n");reclfirst(q);getch();printf(&

31、quot;ntt回收后的空闲分区表n");disp();printf("ntt已分配作业表n");disp2();printf("n继续回收.(Enter)");printf("n所有已分配作业已完成r)；getch();system("cls");cyclefirstf();break;case 'O':break;default:getch();system("cls");cyclefirstf();break;perfitf() ;else printf("n作业

32、没有全部被分配内存.n");getch();system("cls");perfitf();break;case '3':system("cls");disp2();printf("nn按任意键进行区域回收.");while(as!=NULL)getch();printf("n");input2();printf(”按任意键继续.")；getch();printf("n");reclperfit(q);getch();printf("ntt回收后的空

33、闲分区表n");disp();printf("ntt已分配作业表n");disp2();printf("n继续回收.(Enter)");printf("n所有已分配作业已完成r)；getch();system("cls");perfitf();break;case 'O':break;default:getch();system("cls");perfitf();break;void menu()/* 菜单函数*/int i;printf("nnntt*n")

34、;printf("ttt主存空间的分配与回收演示n");printf("tt*n");>printf("tttnn");printf("ttt 1.首次适应算法n");printf("ttt 2.循环首次适应算法nprintf("ttt 3.最佳适应算法n");printf("ttt 0.退出n");printf("ttt请选择你要的操作："）；switch(getchar()");case '1':system(

35、"cls");firstfitf();getch();system("cls"); menu();break;case '2':system("cls");cyclefirstf();getch();system("cls"); / menu();break;case 3:system("cls");perfitf();getch();system("cls");menu();break;case 'O':break;default:getch();system("cls");menu(); break;void main() /* 主函数 */init_sub();print();menu();八、执行结果和结果分析1进入操作界面如下：课件'计算机操作系统嗓作垂统实螫1实螫住存主存空间的分配与回收演示KXHKHlOOIBKMHXHiH HN*弭HXH耗 KHiCIOIXZHK