可变分区内存管理实验.doc

题目: 可变分区内存管理实验
学 号
10130506
学生姓名
李文涛
专业（班级）
软件工程
设计题目
可变分区内存管理实验
设
计
技
术
参
数
系统平台：windows XP/windows 7
开发工具：vc6.0

设
计
要
求
实现一个完整的可变分区管理器，包括分配，回收，分区碎片整理等。
工
作
量
课程设计报告要求不少于3000字。

工
作
计
划

：熟悉题目并理解，及找寻相关资料。
：熟悉vc6.0及其操作。
：完成界面及word文档。

参
考
资
料

11年 12 月 2 日
摘 要
可变分区是指系统不预先划分固定分区，而是在装入程序的时候划分内存区域，使得为程序分配的分区大小恰好等于该程序的需求量，且分区的个数是可变的。显然可变分区有较大的灵活性，较之固定分区能获得好的内存利用率。

关键词：目 录
1 需求分析 2
1.1确定目标系统的功能…………………………………………..........................................2
2 总体设计.3
2.1 整体思路 3
2.2 设计所采用的算法……………………………………………………….......................3
2.3 内存的分配与回收所采用的结构体...............................................................3
2.4 关于内存分配留下的小碎片问题.....................................................................................3
2.5 内存的回收.........................................................................................................................4

3 详细设计 4
3.1 系统采用的数据结构 4
3.2 系统的核心算法 5
3.3 流程图.................................................................................................................................8
3.4 内存的分配与回收截图...................................................................................................10
4 总结 15
4.1设计体会……………………………………………………….. ....................................15
4.2系统改进……………………………………………………….......................................15
参考文献....................................................................15

1 需求分析
1.1 确定目标系统功能

实现一个完整的可变分区管理器，包括分配，回收，分区碎片整理等。
具有一定的容错性，当操作出现错误，比如空间不足，空指针引用等的情况下可以进行处理。
空闲块可以合并。
能对已分配空间进行跟踪。当做碎片整理时，需要跟踪分配的空间，修改其引用以保证引用的正确性。

2. 总体设计
2.1 整体思路：
可变分区管理方式将内存除操作系统占用区域外的空间看做一个大的空闲区。当作业要求装入内存时，根据作业需要内存空间的大小 查询内存中的各个空闲区，当从内存空间中找到一个大于或等于该作业大小的内存空闲区时，选择其中一个空闲区，按作业需求量划出一个分区装人该作业，作业执行完后，其所占的内存分区被收回，成为一个空闲区。如果该空闲区的相邻分区也是空闲区，则需要将相邻空闲区合并成一个空闲区
2.2设计所采用的算法：
采用最优适应算法，每次为作业分配内存时，总是把既能满足要求、又是最小的空闲分区分配给作业。 但最优适应算法容易出现找到的一个分区可能只比作业所需求的长度略大一点的情行，这时，空闲区分割后剩下的空闲区就很小以致很难再使用，降低了内存的使用率。为解决此问题，设定一个限值minsize，如果空闲区的大小减去作业需求长度得到的值小于等于minsize，不再将空闲区分成己分分区和空闲区两部分，而是将整个空闲区都分配给作业。

2.3内存分配与回收所使用的结构体：
为便于对内存的分配和回收，建立两张表记录内存的使用情况。一张为记录作业占用分区的“内存分配表”，内容包括分区起始地址、长度、作业名/标志（为0时作为标志位表示空栏目）；一张为记录空闲区的“空闲分区表”，内容包括分区起始地址、长度、标志（0表空栏目，1表未分配）。两张表都采用顺序表形式。
2.4关于分配留下的内存小碎片问题：
当要装入一个作业时，从“空闲分区表”中查找标志为“1”（未分配）且满足作业所需内存大小的最小空闲区，若空闲区的大小与作业所需大小的差值小于或等于minsize，把该分区全部分配给作业，并把该空闲区的标志改为“0”（空栏目）。同时，在已分配区表中找到一个标志为“0”的栏目登记新装人作业所占用分区的起始地址，长度和作业名。若空闲区的大小与作业所需大小的差值大于minsize。则把空闲区分成两部分，一部分用来装入作业，另外一部分仍为空闲区。这时只要修改原空闲区的长度，且把新装人的作业登记到已分配区表中。
2.5内存的回收：
在可变分区方式下回收内存空间时，先检查是否有与归还区相邻的空闲区（上邻空闲区，下邻空闲区）。若有，则将它们合件成一个空闲区。程序实现时，首先将要释放的作业在“内存分配表”中的记录项的标志改为“0”（空栏目），然后检查“空闲区表”中标志为‘1’（未分配）的栏目，查找是否有相邻的空闲区，若有，将之合并，并修改空闲区的起始地址和长度。
3.详细设计
3.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 
下图是空闲链表的示意图。

3.2核心算法：
//最优分配算法实现的动态分区
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;
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;
}
3.3程序流程图
作业分配流程图：

内存回收流程图：

3.4内存分配回收实现截图：
1、后台代码的截图：
(1)、假定系统内存分配表允许的最大作业项为10，当分配超过10时，提示“内存分配区已满，分配失败”。

(2)、回收作业所占内存时，当输入的作业名不存在，回收失败，提示“该作业不存在”。

(3)、当要释放某个作业时，将已分配表中此作业的标志置为‘0’，并在空闲区做相应登记。

(4)、分配的作业大小21B与找到的最优空闲区大小25B差值小于5B所以将整块空闲区直接分配给作业。

(5)、分配的作业大小14B与找到的最优空闲区大小20B差值大于5B，所以将整块空闲区分割成两部分，然后修改空闲表。

(6)、要回收的内存在空闲表中有上邻，将其合并

(7)、空闲区有两个长度分别为20B和18B的未分配烂，现为作业6分配14B的内存，用最佳分配算法找到空闲区。

4 总结
4.1设计体会：
在内存动态分配程序设计中，最优适应算法比首次要难一些，要加上对分配后该分区是否能最好地利用的判断。再一个问题是回收时候的合并，对地址的修改不是很有把握。着手写程序后，半天才理清回收的内存和上下邻合并的条件与关系，写此处的代码时，逻辑上比较混乱，反复错误反复修改了很多次才调试正确，这也是花了最多时间才得以正确实现的部分。之前大多用的c语言，对结构体，对象等知识淡忘了很多，这一次的实践让我找回了很多学过的知识点，也弥补了很多的不足之处。
4.2 系统改进
由于对做界面比较生疏，至今没能捣鼓出个界面来。设计还有很多的不足之处，有些问题没能很好解决.
参考文献
《计算机操作系统》 汤小丹 梁红兵 哲风屏 汤子嬴 编著
《软件开发》 visual C++ 郭清宇 王海龙 王国胜 编著
Baidu
15