一、实验目的理解分区式存储管理的基本原理，熟悉分区分配和回收算法。

即理解在不同的存储管理方式下，如何实现主存空间的分配与回收；并掌握动态分区分配方式中的数据结构和分配算法及动态分区存储管理方式及其实现过程。

二、设备与环境1. 硬件设备：PC机一台2. 软件环境：安装Windows操作系统或者Linux操作系统，并安装相关的程序开发环境，如VC \VC++\Java 等编程语言环境。

三、实验原理实验要求使用可变分区存储管理方式，分区分配中所用的数据结构采用空闲分区表和空闲分区链来进行，分区分配中所用的算法采用首次适应算法、最佳适应算法、最差适应算法三种算法来实现主存的分配与回收。

同时，要求设计一个实用友好的用户界面，并显示分配与回收的过程。

同时要求设计一个实用友好的用户界面,并显示分配与回收的过程。

A、主存空间分配（1）首次适应算法在该算法中，把主存中所有空闲区按其起始地址递增的次序排列。

在为作业分配存储空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到第一个能满足要求的空闲区，从中划出与请求的大小相等的存储空间分配给作业，余下的空闲区仍留在空闲区链中。

（2）最佳适应算法在该算法中，把主存中所有空闲区按其起始地址递增的次序排列。

在为作业分配存储空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个能满足要求的空闲区且该空闲区的大小比其他满足要求的空闲区都小，从中划出与请求的大小相等的存储空间分配给作业，余下的空闲区仍留在空闲区链中（3）最坏适应算法在该算法中，把主存中所有空闲区按其起始地址递增的次序排列。

在为作业分配存储空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个能满足要求的空闲区且该空闲区的大小比其他满足要求的空闲区都大，从中划出与请求的大小相等的存储空间分配给作业，余下的空闲区仍留在空闲区链中。

B、主存空间回收当一个作业执行完成撤离时，作业所占的分区应该归还给系统。

归还的分区如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明链中，此时，相邻空闲区的合并问题，要求考虑四种情况：1.释放区下邻空闲区（低地址邻接）2.释放区上邻空闲区（高地址邻接）3.释放区上下都与空闲区邻接4.释放区上下邻都与空闲区不邻接四、实验要求1. 模拟操作系统的主存分配，运用可变分区的存储管理算法设计主存分配和回收程序，并不实际启动装入作业。

2. 采用首次适应法、最佳适应法、最坏适应法分配主存空间。

3. 当一个新作业要求装入主存时，必须查空闲区表，从中找出一个足够大的空闲区。

若找到的空闲区大于作业需要量，这是应把它分成二部分，一部分为占用区，加一部分又成为一个空闲区。

4. 当一个作业撤离时，归还的区域如果与其他空闲区相邻，则应合并成一个较大的空闲区，登在空闲区表中。

5. 运行所设计的程序，输出有关数据结构表项的变化和内存的当前状态。

五、实验设计参考1.算法流图main函数的流程图选择算法aa=1，首次适应算法a=2，最佳适应算法a=3，最坏适应算法初始化first和end整理分区序号显示空闲分区链选择操作ii=1，分配空间函数a i=0，退出程序i=2，回收空间函数结束分配空间的流程图回收空间的流程图（见下页）2. 相关数据结构及关键函数说明✧ 使用了struct free_table 数据结构用来说明分区。

包含：分区序号（num ）、起始地址（address ）、分区长度（length ）和分区状态（state ）。

✧ 使用了线性表的双向链表存储结构（struct Node ），里面包含前驱指针（prior ）和后继指针（next ）。

一开始定义一条（含有first 和end ）的链，用开始指针和尾指针开创空间链表。

然后分别按三种算法进行分配和回收。

✧ 在该程序中关键函数有，sort （）、allocation （）、recovery （）、和First_fit （）、Best_fit（）、Worst_fit （）。

其中：✧ sort （）函数用来整理分区序号。

如在删序号3时，它与前面序号2相连在一起了，然后序号2中的长度若满足申请的内存大小，就会在序号2中分配，然后序号在2的基础上加1，一直加，加到与原本序号3的下一个序号也就是4相等，这时sort （）就开始有明显的工作了；✧ allocation （）用来分配空间。

也是过渡到三个算法中的，当三个算法中满足或者不满足分配请求，都会又返回值给allocation （）；✧ recovery （）用来回收内存。

包含四种情况的处理，即释放区上与空闲区邻接、释放区下与空闲区邻接、释放区上下都与空闲区邻接、释放区上下都与空闲区不邻接。

分配不成功p->data.length>request分配空间函数a=1 a=2 a=3输入申请内存大小 按顺序找空闲初始化q ，使它指向空闲块中长度小的输入申请内存大小 初始化q ，使它指向空闲块中长度大的p->data.length=requ estp 的状态为已分配剩下p->data.length-=req uest输入申请内存大小YYN返回到整理分区序号实验参考代码如下：#include<stdio.h>#include<stdlib.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// 线性表的双向链表存储结构{ElemType 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;first->next=end;end->prior=first;end->next=NULL;end->data.num=1;end->data.address=40;end->data.length=600;end->data.state=0;return OK;}void sort()//分区序号重新排序{Node *p=first->next,*q;q=p->next;for(;p!=NULL;p=p->next){for(q=p->next;q;q=q->next){if(p->data.num>=q->data.num){q->data.num+=1;}}}}//显示主存分配情况void show(){ int flag=0;//用来记录分区序号Node *p=first;p->data.num=0;p->data.address=0;p->data.length=40;p->data.state=1;sort();printf("\n\t\t》主存空间分配情况《\n");printf("**********************************************************\n\n");printf("分区序号\t起始地址\t分区大小\t分区状态\n\n");while(p){printf("%d\t\t%d\t\t%d",p->data.num,p->data.address,p->data.length);if(p->data.state==0) printf("\t\t空闲\n\n");else printf("\t\t已分配\n\n");p=p->next;}printf("**********************************************************\n\n"); }//首次适应算法Status First_fit(int request){//为申请作业开辟新空间且初始化Node *p=first->next;LinkList temp=(LinkList)malloc(sizeof(Node));temp->data.length=request;temp->data.state=1;p->data.num=1;while(p){if((p->data.state==0)&&(p->data.length==request)){//有大小恰好合适的空闲块p->data.state=1;return OK;break;}else if((p->data.state==0) && (p->data.length>request)){//有空闲块能满足需求且有剩余temp->prior=p->prior;temp->next=p;temp->data.address=p->data.address;temp->data.num=p->data.num;p->prior->next=temp;p->prior=temp;p->data.address=temp->data.address+temp->data.length;p->data.length-=request;p->data.num+=1;return OK;break;}p=p->next;}return ERROR;}//最佳适应算法Status Best_fit(int request){int ch; //记录最小剩余空间Node *p=first;Node *q=NULL; //记录最佳插入位置LinkList temp=(LinkList)malloc(sizeof(Node));temp->data.length=request;temp->data.state=1;p->data.num=1;while(p) //初始化最小空间和最佳位置{if((p->data.state==0) && (p->data.length>=request) ){if(q==NULL){q=p;ch=p->data.length-request;}else if(q->data.length > p->data.length){q=p;ch=p->data.length-request;}}p=p->next;}if(q==NULL) return ERROR;//没有找到空闲块else if(q->data.length==request){q->data.state=1;return OK;}else{temp->prior=q->prior;temp->next=q;temp->data.address=q->data.address;temp->data.num=q->data.num;q->prior->next=temp;q->prior=temp;q->data.address+=request;q->data.length=ch;q->data.num+=1;return OK;}return OK;}//最差适应算法Status Worst_fit(int request){int ch; //记录最大剩余空间Node *p=first->next;Node *q=NULL; //记录最佳插入位置LinkList temp=(LinkList)malloc(sizeof(Node));temp->data.length=request;temp->data.state=1;p->data.num=1;while(p) //初始化最大空间和最佳位置{if(p->data.state==0 && (p->data.length>=request) ){if(q==NULL){q=p;ch=p->data.length-request;}else if(q->data.length < p->data.length){q=p;ch=p->data.length-request;}}p=p->next;}if(q==NULL) return ERROR;//没有找到空闲块else if(q->data.length==request){q->data.length=1;return OK;}else{temp->prior=q->prior;temp->next=q;temp->data.address=q->data.address;temp->data.num=q->data.num;q->prior->next=temp;q->prior=temp;q->data.address+=request;q->data.length=ch;q->data.num+=1;return OK;}return OK;}//分配主存Status allocation(int a){int request;//申请内存大小printf("请输入申请分配的主存大小(单位:KB):"); scanf("%d",&request);if(request<0 ||request==0){printf("分配大小不合适，请重试！");return ERROR;}switch(a){case 1: //默认首次适应算法if(First_fit(request)==OK) printf("\t****分配成功！****");else printf("\t****内存不足，分配失败！****");return OK;break;case 2: //选择最佳适应算法if(Best_fit(request)==OK) printf("\t****分配成功！****");else printf("\t****内存不足，分配失败！****");return OK;break;case 3: //选择最差适应算法if(Worst_fit(request)==OK) printf("\t****分配成功！****");else printf("\t****内存不足，分配失败！****");return OK;break;}}Status deal1(Node *p)//处理回收空间{Node *q=first;for(;q!=NULL;q=q->next){if(q==p){if(q->prior->data.state==0&&q->next->data.state!=0){q->prior->data.length+=q->data.length;q->prior->next=q->next;q->next->prior=q->prior;q=q->prior;q->data.state=0;q->data.num=flag-1;}if(q->prior->data.state!=0&&q->next->data.state==0){q->data.length+=q->next->data.length;q->next=q->next->next;q->next->next->prior=q;q->data.state=0;q->data.num=flag;}if(q->prior->data.state==0&&q->next->data.state==0){q->prior->data.length+=q->data.length;q->prior->next=q->next;q->next->prior=q->prior;q=q->prior;q->data.state=0;q->data.num=flag-1;}if(q->prior->data.state!=0&&q->next->data.state!=0){q->data.state=0;}}}return OK;}Status deal2(Node *p)//处理回收空间{Node *q=first;for(;q!=NULL;q=q->next){if(q==p){if(q->prior->data.state==0&&q->next->data.state!=0){q->prior->data.length+=q->data.length;q->prior->next=q->next;q->next->prior=q->prior;q=p->prior;q->data.state=0;q->data.num=flag-1;}if(q->prior->data.state!=0&&q->next->data.state==0){q->data.state=0;}if(q->prior->data.state==0&&q->next->data.state==0){q->prior->data.length+=q->data.length;q->prior->next=q->next;q->next->prior=q->prior;q=q->prior;q->data.state=0;q->data.num=flag-1;}if(q->prior->data.state!=0&&q->next->data.state!=0){q->data.state=0;}}}return OK;}//主存回收Status recovery(int flag){Node *p=first;for(;p!=NULL;p=p->next){if(p->data.num==flag){if(p->prior==first){if(p->next!=end)//当前P指向的下一个不是最后一个时{if(p->next->data.state==0) //与后面的空闲块相连{p->data.length+=p->next->data.length;p->next->next->prior=p;p->next=p->next->next;p->data.state=0;p->data.num=flag;}else p->data.state=0;}if(p->next==end)//当前P指向的下一个是最后一个时{p->data.state=0;}}//结束if(p->prior==block_first)的情况else if(p->prior!=first){if(p->next!=end){deal1(p);}else{deal2(p);}}//结束if(p->prior!=block_first)的情况}//结束if(p->data.num==flag)的情况}printf("\t****回收成功****");return OK;}//主函数void main(){int i; //操作选择标记int a;//算法选择标记printf("**********************************************************\n");printf("\t\t用以下三种方法实现主存空间的分配\n");printf("\t(1)首次适应算法\t(2)最佳适应算法\t(3)最差适应算法\n");printf("**********************************************************\n");printf("\n");printf("请输入所使用的内存分配算法:");scanf("%d",&a);while(a<1||a>3){printf("输入错误，请重新输入所使用的内存分配算法:\n");scanf("%d",&a);}switch(a){case 1:printf("\n\t****使用首次适应算法：****\n");break;case 2:printf("\n\t****使用最佳适应算法：****\n");break;case 3:printf("\n\t****使用最坏适应算法：****\n");break;}Initblock(); //开创空间表while(1){show();printf("\t1: 分配内存\t2: 回收内存\t0: 退出\n");printf("请输入您的操作：");scanf("%d",&i);if(i==1)allocation(a); // 分配内存else if(i==2) // 内存回收{printf("请输入您要释放的分区号：");scanf("%d",&flag);recovery(flag);}else if(i==0){printf("\n退出程序\n");break; //退出}else //输入操作有误{printf("输入有误，请重试！");continue;}}}。