2023年11月26日发(作者：)
.
一．实验目的
通过编写和调试存储管理的模拟程序以加深对存储管理方案的理解，熟悉可变分区存储
管理的内存分配和回收。
二．实验内容
1．确定内存空间分配表；
2．采用最优适应算法完成内存空间的分配和回收；
3．编写主函数对所做工作进行测试。
三．实验背景材料
实现可变分区的分配和回收，主要考虑的问题有三个：第一，设计记录内存使用情况的
数据表格，用来记录空闲区和作业占用的区域；第二，在设计的数据表格基础上设计内存分
配算法；第三，在设计的数据表格基础上设计内存回收算法。
首先，考虑第一个问题，设计记录内存使用情况的数据表格，用来记录空间区和作业占
用的区域。
由于可变分区的大小是由作业需求量决定的，故分区的长度是预先不固定的，且分区的
个数也随内存分配和回收变动。总之，所有分区情况随时可能发生变化，数据表格的设计必
须和这个特点相适应。由于分区长度不同，因此设计的表格应该包括分区在内存中的起始地
址和长度。由于分配时空闲区有时会变成两个分区：空闲区和已分分区，回收内存分区时，
可能会合并空闲分区，这样如果整个内存采用一张表格记录己分分区和空闲区，就会使表格
操作繁琐。分配内存时查找空闲区进行分配，然后填写己分配区表，主要操作在空闲区；某
个作业执行完后，将该分区变成空闲区，并将其与相邻的空闲区合并，主要操作也在空闲区。
由此可见，内存的分配和回收主要是对空闲区的操作。这样为了便于对内存空间的分配和回
收，就建立两张分区表记录内存使用情况，一张表格记录作业占用分区的“己分分区表”；
一张是记录空闲区的“空闲区表”。这两张表的实现方法一般有两种：一种是链表形式，一
种是顺序表形式。在实验中，采用顺序表形式，用数组模拟。由于顺序表的长度必须提前固
定，所以无论是“已分分区表”还是“空闲区表”都必须事先确定长度。它们的长度必须是
系统可能的最大项数。
“已分分区表”的结构定义
#define n 10 //假定系统允许的最大作业数量为n
struct
{ float address; //已分分区起始地址
float length; //已分分区长度、单位为字节
int flag; //已分分区表登记栏标志，“0”表示空栏目，实验中只支持一个字符的作业
名
}used_table[n]; //已分分区表
“空闲区表”的结构定义
#define m 10 //假定系统允许的空闲区最大为m
struct
{ float address; //空闲区起始地址
float length; //空闲区长度、单位为字节
int flag; //空闲区表登记栏标志，“0”表示空栏目，“1”表示未分配
}used_table[n]; //空闲区表
第二，在设计的数据表格基础上设计内存分配。
装入一个作业时，从空闲区表中查找满足作业长度的未分配区，如大于作业，空闲区划
可编辑修改
1
.
分成两个分区，一个给作业，一个成为小空闲分区。
实验中内存分配的算法采用“最优适应”算法，即选择一个能满足要求的最小空闲分区。
第三，在设计的数据表格基础上设计内存回收问题。内存回收时若相邻有空闲分区则合
并空闲区，修改空闲区表。
四、参考程序
#define n 10 //假定系统允许的最大作业数量为n
#define m 10 //假定系统允许的空闲区最大为m
#define minisize 100
struct
{ float address; //已分分区起始地址
float length; //已分分区长度、单位为字节
int flag; //已分分区表登记栏标志，“0”表示空栏目，实验中只支持一个
字符的作业名
}used_table[n]; //已分分区表
struct
{ float address; //空闲区起始地址
float length; //空闲区长度、单位为字节
int flag; //空闲区表登记栏标志，“0”表示空栏目，“1”表示未分配
}used_table[n]; //空闲区表
allocate(J,xk) //采用最优分配算法分配xk大小的空间
char J;
float xk;
{int i,k;
float ad;
k=-1;
for(i=0;i if(free_table[i].length>=xk&&free_table[i].flag==1) if(k==-1||free_table[i].length k=i; if(k==-1) //未找到空闲区，返回 {printf("无可用的空闲区n"); return; } //找到可用空闲区，开始分配；若空闲区大小与要求分配的空间差小于minisize大 小，则空闲区全部分配； //若空闲区大小与要求分配的空间差大于minisize大小，则从空闲区划分一部分分 配 if(free_table[k].length-xk<=minisize) {free_table[k].flag=0; ad=free_table[k].address; 可编辑修改 2 . xk=free_table[k].length; } else {free_table[k].length=free_table[k].length-xk; ad=free_table[k].address+free_table[k].length; } //修改已分配区表 i=0; while(used_table[i].flag!=0&&i i++; if(i>=n) //无表目填写已分分区 {printf("无表目填写以分分区，错误n"); if(free_table[k].flag==0) //前面找到的是整个空闲区 free_table[k].flag=1; else //前面找到的是某个空闲区的一部分 free_table[k].length=free_table[k].length+xk; return; } else //修改已分配区表 {used_table[i].address=ad; used_table[i].length=xk; used_table[i].flag=J; } return; }//内存分配函数结束 reclaim(J) //回收作业名为J的作业所占的内存空间 char J: {int i,k,j,s,t; float S,L; //寻找已分分区表中对应的登记项 S=0; . //寻找回收分区的上下邻空闲区，上邻表目K，下邻表目J while(i {if(free_table[i].flag==0) {if(free_table[i].address+free_table[i].length==0) k=i; //找到上邻 {if(free_table[i].address==S+L) j=1; //找到下邻 } i++; } if(k!=-1) if(j!=-1) //上邻空闲区，下邻空闲区，三项合并 {free_table[k].length=free_table[j].length+free_table[k].length+L; free_table[j].flag+0; } else //上邻空闲区，下邻非空闲区，与上邻合并 free_table[k].length=free_table[k].length+L; else if(j!=-1) //上邻非空闲区，下邻空闲区，与下邻合并 {free_table[j].address=S; free_table[j].length=free_table[j].length+L; } else { //上下邻均为非空闲区，回收区域直接填入 t=0; //在空闲区表中寻找空栏目 while(free_table[t].flag==1&&t t++; if(t>=m) //空闲区表满,回收空间失败,将已分配分区 表复原 {printf("内存空闲表没有空间，回收空间失败n"); used_table[S].flag=J; . free_table[0].length=102400; free_table[0].flag=1; for(i=1;i free_table[i].flag=0; //已分分区表初始化 for(i=1;i used_table[i].flag=0; while(1) {printf("选择功能项（0—退出，1—分配内存，2-回收内存，3-显示内存）n"); printf("选择功项（0-3）："); scanf("%d",&a); switch(a) { case 0;exit(0); //a=0程序结束 case 1; //a=1 分配内存空间 printf("输入作业名J和作业所需长度XK："); scanf("%c%c%f",&j,&xk); allocate(j,xk); //分配内存空间 break; case 2; //a=2 回收内存空间 printf("输入要回放分区的作业名"); scanf("%c%c",&j); reclaim(j); //回收内存空间 break; case 3; //a=3显示内存情况，输出空闲区表和已分分区表 printf("输出空闲区表：n起始地址 分区长度 标志n"); for(i=0;i printf("%5.0f%10.0f%6dn",free_table[i].address,free_table[i].length,free _table[i].flag); printf("按任意键，输出已分分区表n"); getch(); printf("输出已分分区表：n起始地址 分区长度 标志n"); for(i=0;i if(used table[i].flag!=0) printf("%6.0f%9.0f%6cn",used_table[i].address,used_table[i].length,used_ table[i].flag); else printf("%6.0f%9.0f%6cn",used_table[i].address,used_table[i].length,used_ table[i].flag); break; default:printf("没有该选项n"); } } } 可编辑修改 5 可编辑修改 . 6
发布评论