一、概述
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;isiquence[i]=0;
for(i=0;i(*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;
