1、实验4主存空间的分配与回收实验四 主存空间的分配和回收1. 目的和要求1.1. 实验目的用高级语言完成一个主存空间的分配和回收程序，以加深对动态分区分配方式及其算法的理解。1.2. 实验要求采用连续分配方式之动态分区分配存储管理，使用首次适应算法、最佳适应算法2种算法完成设计。（1）*设计一个作业申请队列以及作业完成后的释放顺序，实现主存的分配和回收。采用分区说明表进行。（2）或在程序运行过程，由用户指定申请与释放。（3）设计一个空闲区说明表，以保存某时刻主存空间占用情况。把空闲区说明表的变化情况以及各作业的申请、释放情况显示。提示：(1) 动态分区（可变分区方式）是按作业需要的主存空间大小来
2、分割分区的。当要装入一个作业时，根据作业需要的主存容量查看是否有足够的空闲空间，若有，则按需分配，否则，作业无法装入。假定内存大小为256KB，空闲区说明表格式为：起始地址指出空闲区的起始地址；长度一个连续空闲区的长度；状态有两种状态，一种是“已分配”状态；另一种是“空表目”状态，表示该表项目前没有使用。(2) 采用首次适应算法分配回收内存空间。运行时，输入一系列分配请求和回收请求。要求能接受来自键盘的空间申请及释放请求，能显示分区分配及回收后的内存布局情况。2、源程序代码 #include stdio.h#include #include #include iostream.h#define
3、 getjcb(type) (type*)malloc(sizeof(type)#define getsub(type) (type*)malloc(sizeof(type)#define NULL 0int num,num2; /要调度的作业数和要回收的区域数int m=0; /已分配作业数int flag; /分配成功标志int isup,isdown; /回收区域存在上邻和下邻的标志int is=0;struct jcb char name10; char state; int ntime; /所需时间 int size; /所需空间大小 int addr; /所分配分区的首地址 str
4、uct jcb *link; *ready =NULL, *p,*q,*as=NULL; /作业队列ready,已分配作业队列as typedef struct jcb JCB;struct subarea /分区块 char name10; int addr; /分区首地址 int size; /分区大小 char state; struct subarea *link; *sub=NULL,*r,*s,*cur; /空闲分区队列sub,当前分区指针cur typedef struct subarea SUB;void sort_sub() /*对空闲分区按从小到大排序*/ SUB *fir
5、st,*second; int insert=0; if(sub=NULL)|(s-size)size) /*插在队列之首*/ s-link=sub; sub=s; elsefirst=sub; /*寻找适当的位置插入*/ second=first-link; while(second!=NULL) if(s-size)size) s-link=second; first-link=s; second=NULL; insert=1; else first=first-link; second=second-link; if(insert=0)first-link=s; /*插在队尾*/ voi
6、d sort_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; void lastsort() /*建立对已分配作业队列的排列函数,直接插在队列之尾sort3*/ JCB *fir; if(as=NULL) as=q; else fir=as; while(fir-link!=NULL) fir=fir-link; fir-link=q; q-
7、link=NULL; m+;void input() /* 建立作业控制块函数*/ int i; printf(n请输入要调度的总作业数:); scanf(%d,&num); for(i=0;iname); printf(n输入作业的大小:); scanf(%d,&p-size); printf(n输入作业所需运行时间:); scanf(%d,&p-ntime); p-state=w; p-link=NULL; firstsort(); /* 调用sort函数*/ printf(n 按任一键继续.n); getch();void input2() /*建立要回收区域的函数*/ JCB *k;
8、int has; 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(输出该作业首地
9、址:%dn,q-addr); printf(输出该作业大小:%dnn,q-size); q-link=NULL; break; else p=p-link; has=0; /*输入作业名不存在标志*/ 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=getsub(SUB); strcpy(s-name,two); s-addr=20; s-si
10、ze=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;void disp() /*空闲分
11、区表的显示函数*/ printf(tt 分区 首地址 长度 状态 n); r=sub; while(r!=NULL) printf(tt %stt%dtt%dtt%cn,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 p
12、erfit(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; last
13、sort(); /*插入已分配作业队列*/ /重新插入剩余空闲分区,插在合适位置 if(r-sizesize) /*插入队首*/ r-link=sub; sub=r; else /*插在适当的位置*/ s=sub; while(s-size)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-
14、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-link-link; /*删除空闲分区*/ printf(作业%s的分区为%s,首地址为%d.n,p-name,r-name,pr-addr); break; else r=r-link; fla
15、g=0; if(flag=0) /*作业过大的情况*/ printf(作业%s长度过大，内存不足，分区分配出错!n,p-name); is=1; void firstfit(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; lastsor
16、t(); /*插入已分配作业队列*/ printf(作业%s的分区为%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-link-link; /*删除空闲分区*/ printf(作业%s的分
17、区为%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; void cyclefit(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
18、; 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; else if(r-size)=(pr-size)&(r-state=n) /*有空闲分区等于作业大小的情况*/ pr-addr=r-addr; flag=1; /*分配成功标志位置1*/ cur=r; q=pr; lastsort(); /*插入已分配作业队列*/ s=sub;
19、 /*空闲分区已完成分配,应删除*/ 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)
20、 /*作业过大的情况*/ printf(作业%s长度过大，内存不足，分区分配出错!n,p-name); is=1; void less_to_more() /*把分区按大小从小到大排序*/ r=sub; sub=NULL; while(r!=NULL) s=r; r=s-link; s-link=NULL; sort_sub(); /*调用排序函数*/ void reclperfit(JCB *pr) /*最佳适应回收区域,按分区大小排列*/ SUB *k; r=sub; while(r!=NULL) if(r-addr=(pr-addr)+(pr-size) /*回收区域有下邻*/ pr-s
21、ize+=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=
22、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
23、-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; else r=r-link; if(r=NULL) /*所有空闲分区都大于回收区域的情况*/ s=sub; while(s-link!=NULL) s=s-link; s-link=k; k-li
24、nk=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-addr)+(s-size)=(pr-addr) /*有下邻又有上邻*/ s-size+=pr-size; k=sub; while(k-link!=r) k=k-
25、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; /*
26、上邻标志位置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; else r=r-
