1、空闲分区链：使用链指针把所有的空闲分区链成一条链，为了实现对空闲分区的分配和链接，在每个分区的起始部分设置状态位、分区的大小和链接各个分区的前向指针，由状态位指示该分区是否分配出去了；同时，在分区尾部还设置有一后向指针，用来链接后面的分区；分区中间部分是用来存放作业的空闲内存空间，当该分区分配出去后，状态位就由“0”置为“1”。设置一个内存空闲分区链，内存空间分区通过空闲分区链来管理，在进行内存分配时，系统优先使用空闲低端的空间。设计一个空闲分区说明链，设计一个某时刻主存空间占用情况表，作为主存当前使用基础。初始化空间区和已分配区说明链的值，设计作业申请队列以及作业完成后释放顺序，实现主存的分
2、配和回收。要求每次分配和回收后显示出空闲内存分区链的情况。把空闲区说明链的变化情况以及各作业的申请、释放情况显示打印出来。2.采用可变分区存储管理，分别采用首次适应算法、最佳适应算法和最坏适应算法实现主存分配和回收。3、主存空间分配 （1）首次适应算法在该算法中，把主存中所有空闲区按其起始地址递增的次序排列。在为作业分配存储空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到第一个能满足要求的空闲区，从中划出与请求的大小相等的存储空间分配给作业，余下的空闲区仍留在空闲区链中。（2）最佳适应算法在为作业分配存储空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个能满足要求
3、的空闲区且该空闲区的大小比其他满足要求的空闲区都小，从中划出与请求的大小相等的存储空间分配给作业，余下的空闲区仍留在空闲区链中（3）最坏适应算法在为作业分配存储空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个能满足要求的空闲区且该空闲区的大小比其他满足要求的空闲区都大，从中划出与请求的大小相等的存储空间分配给作业，余下的空闲区仍留在空闲区链中。4、主存空间回收 当一个作业执行完成撤离时，作业所占的分区应该归还给系统。归还的分区如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明链中，此时，相邻空闲区的合并问题，要求考虑四种情况：（1） 释放区下邻空闲区（低地址邻接
4、）（2） 释放区上邻空闲区（高地址邻接）（3） 释放区上下都与空闲区邻接（4） 释放区上下邻都与空闲区不邻接五、程序流程图main函数里的流程图分配空间里的流程图回收空间里的流程图六、相关数据结构及关键函数说明本程序采用了一个struct free_table数据结构，里面包含分区序号（num）、起始地址（address）、分区长度（length）和分区状态（state）。还用了线性表的双性链表存储结构（struct Node），里面包含前区指针（prior）和后继指针（next）。一开始定义一条（含有first和end）的链，用开始指针和尾指针开创空间链表。然后分别按三种算法进行分配和回收。
5、在该程序中关键函数有，sort（）、allocation（）、recovery（）、和First_fit（）、Best_fit（）、Worst_fit（）；其中sort（）函数是用来整理分区序号的，如在删序号3时，她与前面序号2相连在一起了，然后序号2中的长度总满足申请的内存大小，就会在序号2中分配，然后序号在2的基础上加1，一直加，加到与原本序号3的下一个序号也就是4相等，这时sort（）就开始有明显的工作了；allocation（）是分配空间的，也是过渡到三个算法中的，当三个算法中满足或者不满足分配请求，都会又返回值给allocation（）；recovery（）是用来回收内存的，里面包含
6、了四种情况相连结果，即释放区上与空闲区邻接、释放区下与空闲区邻接、释放区上下都与空闲区邻接、释放区上下都与空闲区不邻接这四种情况的结果。七、源代码#includestdlib.h#define OK 1 /完成#define ERROR 0 /出错typedef int Status;typedef struct free_table/定义一个空闲区说明表结构 int num; /分区序号 long address; /起始地址 long length; /分区大小 int state; /分区状态ElemType;typedef struct Node/ 线性表的双向链表存储结构 ElemT
7、ype data; struct Node *prior; /前趋指针 struct Node *next; /后继指针Node,*LinkList;LinkList first; /头结点LinkList end; /尾结点int flag;/记录要删除的分区序号Status Initblock（）/开创带头结点的内存空间链表 first=（LinkList）malloc（sizeof（Node）; end=（LinkList）malloc（sizeof（Node）; first-prior=NULL;next=end; end-prior=first;next=NULL;data.num=
8、1;data.address=40;data.length=600;data.state=0; return OK;void sort（）/分区序号重新排序 Node *p=first-next,*q; q=p-next; for（;p!=NULL;p=p-next） for（q=p-q;q=q- if（p-data.num=q-data.num） q-data.num+=1; /显示主存分配情况void show（） int flag=0;/用来记录分区序号 Node *p=first; p-data.num=0;data.address=0;data.length=40;data.stat
9、e=1; sort（）; printf（ntt主存空间分配情况n）;*nn分区序号t起始地址t分区大小t分区状态nn while（p）%dtt%dtt%d,p-data.num,p-data.address,p-data.length）; if（p-data.state=0） printf（tt空闲nn else printf（tt已分配nn p=p-/首次适应算法Status First_fit（int request） /为申请作业开辟新空间且初始化 LinkList temp=（LinkList）malloc（sizeof（Node）; temp-data.length=request;
10、 if（p-data.state=0）&（p-data.length=request） /有大小恰好合适的空闲块 break; else if（p-data.state=0） & （p-data.lengthrequest） /有空闲块能满足需求且有剩余prior=p-prior;next=p;data.address=p-data.address;data.num=p-data.num;prior-next=temp;prior=temp;data.address=temp-data.address+temp-data.length;data.length-=request; return
11、ERROR;/最佳适应算法Status Best_fit（int request） int ch; /记录最小剩余空间 Node *q=NULL; /记录最佳插入位置 p- while（p） /初始化最小空间和最佳位置=request） ） if（q=NULL） q=p; ch=p-data.length-request; else if（q-data.length data.length） if（q=NULL） return ERROR;/没有找到空闲块data.length=request） q- elseprior=q-next=q;data.address=q-data.num=q-d
12、ata.address+=request;data.length=ch;/最差适应算法Status Worst_fit（int request） /记录最大剩余空间 while（p） /初始化最大空间和最佳位置data.state=0 &data.length data.length=1;/分配主存Status allocation（int a） int request;/申请内存大小请输入申请分配的主存大小（单位:KB）: scanf（%d,&request）; if（requestdata.state=0&q-next-data.state!=0）data.length+=q-next=q
13、- q=q-data.num=flag-1; if（q-=0&data.state=0）prior=q;data.num=flag;data.state=0） =0） Status deal2（Node *p）/处理回收空间/主存回收Status recovery（int flag）next） data.num=flag） prior=first）next!=end）/当前P指向的下一个不是最后一个时 if（p-data.state=0） /与后面的空闲块相连data.length+=p-prior=p;next=p- else p-next=end）/当前P指向的下一个是最后一个时 /结束if（p-prior=block_first）的情况 else if（p-prior!=first）=end） deal1（p）; else deal2（p）;=block_first）的情况 /结束if（p-data.num=flag）的情况t*回收成功*/主函数void main（） int i; /操作选择标记 int a;/算法选择标记*ntt用以下三种方法实现主存空间的分配nt（1）首次适应算法t（2）最佳适应算法t（3）最差适应算法nn请输入所使用的内存分配算法:a）; while（a3）输入错误，请重新输入所使用的内存分配算法: switch（a
