实验五 动态分区存储管理
一、实验目的
深入了解采用动态分区存储管理方式的内存分配回收的实现。通过编写和调试存储管理的模拟程序以加深对存储管理方案的理解，熟悉动态分区存储管理的内存分配和回收。
二、实验内容
编写程序完成动态分区存储管理方式的内存分配回收。 具体包括：确定内存空间分配表；
采用最优适应算法完成内存空间的分配和回收； 编写主函数对所做工作进行测试。
三、设计思路
整体思路：
动态分区管理方式将内存除操作系统占用区域外的空间看成一个大的空闲区。当作业要求装入内存时，根据作业需要内存空间的大小 查询内存中的各个空闲区，当从内存空间中找到一个大于或等于该作业大小的内存空闲区时，选择其中一个空闲区，按作业需求量划出一个分区装人该作业，作业执行完后，其所占的内存分区被收回，成为一个空闲区。如果该空闲区的相邻分区也是空闲区，则需要将相邻空闲区合并成一个空闲区。 设计所采用的算法：
采用最优适应算法，每次为作业分配内存时，总是把既能满足要求、又是最小的空闲分区分配给作业。 但最优适应算法容易出现找到的一个分区可能只比作业所需求的长度略大一点的情行，这时，空闲区分割后剩下的空闲区就很小以致很难再使用，降低了内存的使用率。为解决此问题，设定一个限值minsize，如果空闲区的大小减去作业需求长度得到的值小于等于minsize，不再将空闲区分成己分分区和空闲区两部分，而是将整个空闲区都分配给作业。
内存分配与回收所使用的结构体：
为便于对内存的分配和回收，建立两张表记录内存的使用情况。一张为记录作业占用分区的“内存分配表”，内容包括分区起始地址、长度、作业名/标志（为0时作为标志位表示空栏目）；一张为记录空闲区的“空闲分区表”，内容包括分区起始地址、长度、标志（0表空栏目，1表未分配）。两张表都采用顺序表形式。
1
关于分配留下的内存小碎片问题：
当要装入一个作业时，从“空闲分区表”中查找标志为“1”（未分配）且满足作业所需内存大小的最小空闲区，若空闲区的大小与作业所需大小的差值小于或等于minsize，把该分区全部分配给作业，并把该空闲区的标志改为“0”（空栏目）。同时，在已分配区表中找到一个标志为“0”的栏目登记新装人作业所占用分区的起始地址，长度和作业名。若空闲区的大小与作业所需大小的差值大于minsize。则把空闲区分成两部分，一部分用来装入作业，另外一部分仍为空闲区。这时只要修改原空闲区的长度，且把新装人的作业登记到已分配区表中。
内存的回收：
在动态分区方式下回收内存空间时，先检查是否有与归还区相邻的空闲区（上邻空闲区，下邻空闲区）。若有，则将它们合件成一个空闲区。程序实现时，首先将要释放的作业在“内存分配表”中的记录项的标志改为“0”（空栏目），然后检查“空闲区表”中标志为‘1’（未分配）的栏目，查找是否有相邻的空闲区，若有，将之合并，并修改空闲区的起始地址和长度。
四、数据结构定义
（1）已分配表的定义：
struct
{float address; //已分分区起始地址
float length; //已分分区长度，单位为字节 int flag; //已分配区表登记栏标志，\"0\"表示空栏目，实验中只支持一个字符的作业名
}used_table[n]; //已分配区表
（2）空闲分区表的定义：
struct
{float address; //空闲区起始地址 float length; //空闲区长度，单位为字节
int flag; //空闲区表登记栏标志，用\"0\"表示空栏目，用\"1\"表示未分配 }free_table[m]; //空闲区表
(3)全局变量
float minsize=5;
#define n 10 //假定系统允许的最大作业数量为n #define m 10 //假定系统允许的空闲区表最大为m
2
五、源程序代码
#include //全局变量 float minsize=5; int count1=0; int count2=0; #define M 10 //假定系统允许的空闲区表最大为m #define N 10 //假定系统允许的最大作业数量为n //已分配表的定义 struct {float address; //已分分区起始地址 float length; //已分分区长度，单位为字节 int flag; //已分配区表登记栏标志，\"0\"表示空栏目 }used_table[N]; //已分配区表对象名 //空闲区表的定义： struct {float address; //空闲区起始地址 float length; //空闲区长度，单位为字节 int flag; //空闲区表登记栏标志，用\"0\"表示空栏目，用\"1\"表示未分配 }free_table[M]; //空闲区表对象名 //函数声明 void initialize(void); int distribute(int, float); int recycle(int); void show(); //初始化两个表 void initialize(void) { int a; for(a=0; a<=N-1; a++) used_table[a].flag=0; //已分配表的表项全部置为空表项 free_table[0].address=1000; free_table[0].length=1024; free_table[0].flag=1; //空闲区表的表项全部为未分配 } 3 //最优分配算法实现的动态分区 int distribute(int process_name, float need_length) { int i, k=-1; //k用于定位在空闲表中选择的未分配栏 float ads, len; int count=0; i=0; while(i<=M-1) //循环找到最佳的空闲分区 { if(free_table[i].flag==1 && need_length <=free_table[i].length) { count++; if(count==1||free_table[i].length < free_table[k].length) k=i; } i=i+1; } if(k!=-1) { if((free_table[k].length-need_length)<=minsize) //整个分配 { free_table[k].flag=0; ads=free_table[k].address; len=free_table[k].length; } else { //切割空闲区 ads=free_table[k].address; len=need_length; free_table[k].address+=need_length; free_table[k].length-=need_length; } i=0; //循环寻找内存分配表中标志为空栏目的项 while(used_table[i].flag!=0) {i=i+1;} if(i<=N-1) //找到，在已分配区表中登记一个表项 { used_table[i].address=ads; used_table[i].length=len; 4 used_table[i].flag=process_name; count1++; } else //已分配区表长度不足 { if(free_table[k].flag == 0) //将已做的整个分配撤销 { free_table[k].flag=1; free_table[k].address=ads; free_table[k].length=len; } else //将已做的切割分配撤销 { free_table[k].address=ads; free_table[k].length+=len; } cout<<\"内存分配区已满，分配失败！\\n\"; return 0; } } else { cout <<\"无法为该作业找到合适分区！\\n\"; return 0; } return process_name; } int recycle(int process_name) { int y=0; float recycle_address, recycle_length; int i, j, k; //j栏是下邻空闲区，k栏是上栏空闲区 int x; //在内存分配表中找到要回收的作业 while(y<=N-1&&used_table[y].flag!=process_name) { y=y+1;} if(y<=N-1) //找到作业后，将该栏的标志置为'0' { recycle_address=used_table[y].address; recycle_length=used_table[y].length; used_table[y].flag=0; count2++; } 5 else //未能找到作业，回收失败 { cout<<\"该作业不存在！\\n\"; return 0; } j=k=-1; i=0; while(!(i>=M||(k!=-1&&j!=-1))) //修改空闲分区表 { if(free_table[i].flag==1) { if((free_table[i].address+free_table[i].length)==recycle_address) k=i; //判断是否有上邻接 if((recycle_address+recycle_length)==free_table[i].address) j=i; //判断是否有下邻接 } i=i+1; } //合并空闲区 if(k!=-1) //回收区有上邻接 { if(j!=-1){ //回收区也有下邻接，和上下邻接合并 free_table[k].length+=free_table[j].length+recycle_length; free_table[j].flag=0; //将第j栏的标记置为'0' } else //不存在下邻接，和上邻接合并 free_table[k].length+=recycle_length; } else if(j!=-1) { //只有下邻接，和下邻接合并 free_table[j].length+=recycle_length; free_table[j].address=recycle_address; } else { //上下邻接都没有 x=0; while(free_table[x].flag!=0) x=x+1; //在空闲区表中查找一个状态为'0'的栏目 if(x<=M-1) { //找到后，在空闲分区中登记回收的内存 free_table[x].address=recycle_address; free_table[x].length=recycle_length; 6 free_table[x].flag=1; } else { //空闲表已满，执行回收失败 used_table[y].flag=process_name; cout<<\"空闲区已满，回收失败！\\n\"; return 0; } } return process_name; } void show() //程序执行时输出模拟的内存分配回收表 { cout<<\"+++++++++++++++++++++++++++++++++++++++\\n\"; cout<<\"+++++++ 空 闲 区 +++++++\\n\"; cout<<\"+++++++++++++++++++++++++++++++++++++++\\n\"; for(int i=0;i<=count2;i++) if(free_table[i].flag!=0) cout<<\"初始地址：\"< cout<<\"+++++++++++++++++++++++++++++++++++++++\\n\"; for(int j=0;j int job_name; float need_memory; bool exitFlag=false; cout<<\" 动态分区分配方式的模拟 \\n\"; cout<<\"************************************\\n\"; cout<<\"请选择操作类型：\\n\"; initialize(); //开创空闲区和已分配区两个表 while(!exitFlag) 7 { cout<<\"********************************************\\n\"; cout<<\"** 1: 分配内存 2: 回收内存 **\\n\"; cout<<\"** 3: 查看分配 0: 退 出 **\\n\"; cout<<\"********************************************\\n\"; cout<<\"请输入您的操作 ：\"; cin>>choice; switch(choice) { case 0: exitFlag=true; //退出操作 break; case 1: cout<<\"请输入作业号和所需内存：\"; cin>>job_name>>need_memory; if(job_name!=0&&need_memory!=0) distribute(job_name, need_memory); // 分配内存 else if(job_name==0) cout<<\"作业号不能为零!\\n请重新选择操作：\\n\"; else if(need_memory==0) cout<<\"内存分配数不能为零!\\n请重新选择操作：\\n\"; break; case 2: int ID; cout<<\"请输入您要释放的作业号：\"; cin>>ID; if(ID!=0) recycle(ID); //回收内存 else cout<<\"作业名不能为零!\\n请重新选择操作：\\n\"; break; case 3: show(); break; } } } 六、实验结果分析 1. 运行源程序，模拟内存的分配与回收操作，并记录实验结果。 2. 简要分析distribute函数和recycle函数的执行流程。 8 因篇幅问题不能全部显示，请点此查看更多更全内容