一、概述1、设计目的（1）了解多道程序系统中，多个进程并发执行的内存资源分配。

（2）模拟可变分区存储管理算法实现分区管理的最佳适应分配算法（3）利用最佳适应算法动态实现内存分配与回收（3）通过实现最佳算法来进一步了解动态分区模式的优缺点。

（4）掌握最佳适应分配算法，深刻了解各进程在内存中的具体分配策略。

2、开发环境PC机WINDOWS环境Visual C++6.0 for Windows二、实验基本原理１、可变分区存储管理之循环首次适应算法分配的概念：分区存储管理是给内存中的进程划分适当大小的存储区，以连续存储各进程的程序和数据，使各进程能并发地执行。

循环首次适应分配算法扫描整个未分配区表或链表，从空闲区中挑选一个能满足用户进程要求的最小分区进行分配。

2、关于循环首次适应的一些基本原理：在可变分区模式下，在系统初启且用户作业尚未装入主存储器之前，整个用户区是一个大空闲分区，随着作业的装入和撤离，主存空间被分成许多分区，有的分区被占用，而有的分区时空闲的。

为了方便主存空间的分配和去配，用于管理的数据结构可由两张表组成：“已分配区表”和“未分配区表”。

在“未分配表中”将空闲区按长度递增顺序排列，当装入新作业时，从未分配区表中挑选一个能满足用户进程要求的分区进行分配。

这时从已分配表中找出一个空栏目登记新作业的起始地址和占用长度，同时修改未分配区表中空闲区的长度和起始地址。

当作业撤离时已分配区表中的相应状态变为“空”，而将收回的分区登记到未分配区表中，若有相邻空闲区再将其连接后登记。

三、数据结构设计1、内存块struct mem{int pr_num; //进程号char * start_addr; //起始地址int size; //大小struct mem * next; //指向下一个内存块};2、程序流程图2.1、整体程序流程图2.2、内存分配流程图2.3、内存回收流程图四、算法的实现1、程序主要功能函数设计思想int neicun();int siquence[MAX]; 存储进程号的数组void showmem(char *); 显示内存分配情况void Menu(void ); 显示操作信息int getnum(void ); 获取进程序号void insert(struct mem *,struct mem *); 将释放内存控制块插入到free列队中int check(int n); 判断是否存在序号为n的进程,存在返回1 void showmcb(struct mem *,int i); 将free,used的信息输出void ch_siquence(int); 进程序列号变反void writemem(char *addr,int snum,int size ); 对内存写入void deletmem(char *addr,int size); 撤消内存内容void freeunion(struct mem * ); 合并空闲表2、程序清单int neicun(void){struct mem *free,*sta_free=NULL,*used,*sta_used,*change;char * mem_addr,*staticmem;char commu;int pro_size,flag=0,snum,i;//flag标志是否获得内存struct mem *temp=sta_free,*p,*temp_used;staticmem=mem_addr=(char *)malloc(SIZE*sizeof(char));//分配内存for(i=0;i<MAX;i++) //进程序列初始化siquence[i]=0;for(i=0;i<SIZE;i++,mem_addr++) //内存初始化(*mem_addr)='_';sta_free=free=(struct mem*)malloc(sizeof(struct mem));free->pr_num=-1;free->start_addr=staticmem;free->size=SIZE;free->next=NULL;sta_used=used=(struct mem*)malloc(sizeof(struct mem));used->pr_num=0;used->start_addr=NULL;used->size=0;used->next=NULL;int cycle=1;while(cycle){Menu(); //显示主菜单scanf("%c%*c",&commu);switch(commu){case 'g':{//为进程分配内存printf("请输入需要的内存大小:");scanf("%d",&pro_size);for(flag=0,temp=sta_free;temp!=NULL;temp=temp->next){if(temp->size>=pro_size){//分配新的内存管理块p=(struct mem *)malloc(sizeof(struct mem));p->pr_num=getnum();p->start_addr=temp->start_addr;p->size=pro_size;p->next=NULL;writemem(p->start_addr,p->pr_num,p->size);//写内容temp->start_addr=temp->start_addr+pro_size;temp->size=temp->size-pro_size;flag=1;break;}}if(flag==1){if(DEBUG) printf("已做过flag==1部分\n");//将新管理块插入到used列队中for(temp_used=sta_used;temp_used->next!=NULL;)temp_used=temp_used->next;temp_used->next=p;printf("成功分配内存块\n请按任意键继续......\n");}else printf("分配内存出错,无法分配所需内存!\n请按任意键继续......\n"); }break;case 'd':{//释放内存snumprintf("输入要释放的进程号:");scanf("%d",&snum);if(check(snum)==1)//判断输入的号码是否正确{//序号正确for(temp_used=sta_used;temp_used->next!=NULL&&temp_used->next->pr_num!=snum;) temp_used=temp_used->next;//往下寻找snum序号if(temp_used->next!=NULL){//找到所需释放的进程deletmem(temp_used->next->start_addr,temp_used->next->size);//删除内容ch_siquence(temp_used->next->pr_num);//进程号变反temp_used->next->pr_num=-1;//撤消进程号change=temp_used->next;temp_used->next=temp_used->next->next;//将内存块从used队列中删除insert(sta_free,change);//将所需释放的内存块插入到free队列中freeunion(sta_free);printf("释放进程%d成功\n请按任意键继续......\n",snum);}}else printf("出错,该序号无效\n请按任意键继续......\n");}break;case 's':{ //显示目前内存分配情况showmem(staticmem);printf("内存起始地址:%d\n",staticmem);showmcb(sta_free,0);showmcb(sta_used,1);printf("请按任意键继续......\n");}break;case 'b':{printf("请按任意键继续......\n");cycle=0;break;}default:{printf(" 对不起,你的输入不合法,请确保你的输入为g,d,s,b中的任一个\n");printf(" 请按任意键继续......\n");}}getchar();}return 0;}//菜单选择函数void Menu(void){system("color 9f"); //背景颜色函数printf("\t 输入命令\n");printf("\t ===============\n");printf("\t g--分配内存\n");printf("\t d--释放内存\n");printf("\t s--显示信息\n");printf("\t b--退出系统\n");printf("\t ===============\n");printf("\t 请选择:");}//显示整个内存起始地址void showmem(char *mem_addr){int i;printf("\n内存内容:\n");for(i=1;i<=SIZE;i++,mem_addr++){printf("%c ",*mem_addr);if(i%20==0)printf("\n");}printf("\n");}//将空闲，分派内存的信息输出void showmcb(struct mem * base,int i){if(i==0) //空闲表{printf("-----------------------------------------\n");printf("空闲表:\n");for(;base!=NULL;base=base->next)printf("起始地址%d:大小%d\n",base->start_addr,base->size); printf("----------------------------------------\n");}if(i==1) //已占表{printf("已分配表:\n");for(base=base->next;base!=NULL;base=base->next)printf("进程号%d,起始地址%d:大小%d\n",base->pr_num,base->start_addr,base->size); printf("-----------------------------------------\n");}}//获取进程序号int getnum(void ){int i;for(i=0;siquence[i]>0;)i++;if(siquence[i]==0){siquence[i]=i+1;return siquence[i] ;}else{siquence[i]*=-1;return siquence[i];}}//对内存写入void writemem(char *addr,int snum,int size ){for(int i=1;i<=size;i++,addr++)*addr=snum+'0';}void insert(struct mem *base,struct mem *p){//将释放内存控制块插入到free列队中for(;base->next!=NULL&&p->start_addr<base->next->start_addr;) base=base->next;if(base->next==NULL){//已到末尾，在末尾插入pbase->next=p;p->next=NULL;}else{ //在链表中间插入pp->next=base->next;base->next=p;}}//判断是否存在序号为n的进程,存在返回1int check(int n){for(int i=0;siquence[i]!=0;i++)if(siquence[i]==n){return 1;break;}return 0;}//进程序列号变反void ch_siquence(int n){for(int i=0;siquence[i]!=0;i++)if(siquence[i]==n)siquence[i]*=-1;}//撤消内存内容void deletmem(char *addr,int size){for(int i=1;i<=size;i++,addr++)*addr='_';}//对空闲表中相邻的空闲块合并void freeunion(struct mem * base){for(;base!=NULL;){if(base->next!=NULL&&base->start_addr==base->next->start_addr+base->next->size) {base->start_addr=base->next->start_addr;base->size=base->size+base->next->size;base->next=base->next->next;}elsebase=base->next;}}3、测试用例与程序运行结果截图3.1、菜单选错误用例：t图1 程序运行结果：输入不合法3.2、内存分配正确测试用例用例：（g, 4）图2 程序运行结果：分配成功3.3、内存分配错误测试用例用例：（g，101）图3 程序运行结果：内存分配错误3.4、内存显示测试用例用例：(s)图4 程序运行结果：显示内存分配情况3.5、内存回收测试用例用例：(d,1),(d,3)图5 程序运行结果：释放成功3.6、循环首次适应算法测试用例用例：(g,51),(g,5)图6 分配成功五、总结1、经验总结：设计程序时，最好将不同的功能用不同的函数实现。