计算机操作系统内存标准管理系统可变分区存储管理方式的内存分配回收.doc

课程设计2 可变分区存放管理方法内存分配回收

一、课程设计目标
深入了解采取可变分区存放管理方法内存分配回收实现。
二、预备知识
存放管理中可变分区管理方法。
三、小组组员
四、课程设计内容
编写程序完成可变分区存放管理方法内存分配回收。
具体包含：确定内存空间分配表；
采取最优适应算法完成内存空间分配和回收；
编写主函数对所做工作进行测试。
五、设计思绪：
整体思绪：
可变分区管理方法将内存除操作系统占用区域外空间看做一个大空闲区。看成业要求装入内存时，依据作业需要内存空间大小 查询内存中各个空闲区，当从内存空间中找到一个大于或等于该作业大小内存空闲区时，选择其中一个空闲区，按作业需求量划出一个分区装人该作业，作业实施完后，其所占内存分区被收回，成为一个空闲区。假如该空闲区相邻分区也是空闲区，则需要将相邻空闲区合并成一个空闲区。
设计所才用算法：
采取最优适应算法，每次为作业分配内存时，总是把既能满足要求、又是最小空闲分区分配给作业。 但最优适应算法轻易出现找到一个分区可能只比作业所需求长度略大一点情行，这时，空闲区分割后剩下空闲区就很小以致极难再使用，降低了内存使用率。为处理此问题，设定一个限值minsize，假如空闲区大小减去作业需求长度得到值小于等于minsize，不再将空闲区分成己分分区和空闲区两部分，而是将整个空闲区全部分配给作业。
内存分配和回收所使用结构体：
为便于对内存分配和回收，建立两张表统计内存使用情况。一张为统计作业占用分区“内存分配表”，内容包含分区起始地址、长度、作业名/标志（为0时作为标志位表示空栏目）；一张为统计空闲区“空闲分区表”，内容包含分区起始地址、长度、标志（0表空栏目，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 
七、关键算法：
//最优分配算法实现动态分区
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;
}

八、程序步骤图：
作业分配步骤图：

内存回收步骤图：

九、程序说明：
本程序采取Visual C++编写，模拟可变分区存放管理方法内存分配和回收。假定系统许可最大作业数量为n=10，许可空闲区表最大项数为m=10，判定是否划分空闲区最小限值为minsize=5。初始化用户可占用内存区首地址为1000，大小为1024B。定义两个结构体及其对象free_table[m]和used_table[n]实现内存分配回收及分配表和空闲表登记。用最优分配算法实现动态分配时，调用int distribute(int process_name, float need_length)内存分配函数，设定循环条件查找最好空闲分区，定义int k 以统计最好空闲区首地址，依据找到空闲区大小和作业大小判定是整个分配给作业还是切割空闲区后再分配给作业，并在“内存分配表”和“空闲分区表”中作登记。调用int recycle(int process_name)函数实现内存回收。次序循环“内存分配表”找到要回收作业，将标志位设为“0”，定义float recycle_address, recycle_length;用recycle_address记下回收作业首地址，recycle_length记下回收作业长度。查找空闲表，假如(free_table[i].address+free_table[i].length)==recycle_address，说明有上邻接空闲区，这时上邻接区起始地址不变，长度+ recycle_address； 假如(recycle_address+recycle_length)==free_table[i].address，说明有下邻接，这时下邻接空闲区起始地址改为回收作业起始地址recycle_address，长度+ recycle_length。假如 同时有上下邻接空闲区，则上邻接起始地址不变，长度+recycle_address+下邻接长度，下邻接标志设为“0” 不然，要回收内存没有邻接空闲区，在空闲区中找到一个标志为“0”空栏目登记回收内存。
十、内存分配回收实现截图：
1、后台代码截图：
(1)、假定系统内存分配表许可最大作业项为10，当分配超出10时，提醒“内存分配区已满，分配失败”。

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

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

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

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

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

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

2、制作界面实现截图

十、源程序：

#include
#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; //空闲区表表项全部为未分配
}

//最优分配算法实现动态分区
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) //找到，在已分配区表中登记一个表项
{
usedtable[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;
}

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++;
}
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;
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++)
cout<<"地址："<\n";
for(int j=0;jmory;
bool exitFlag=false;
cout<<" 动态分区分配方法模拟 \n";
cout<<"************************************\n";
cout<<"请选择操作类型：\n";
initialize(); //开创空闲区和已分配区两个表
while(!exitFlag)
{
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;
distribute(job_name, need_memory); // 分配内存
break;
case 2:
int ID;
cout<<"请输入您要释放分区号：";
cin>>ID
recycle(ID); //回收内存
break;
case 3:
show();
break;
}
}
}

十一、心得体会：
每一次实践，全部会有很大收获。决定做这个题目标时候，就针对此题要处理多个问题反复思索，重新翻开教科书把相关内容尤其是算法原理认真细致看了一遍，设想会碰到问题。在内存动态分配程序设计中，最优适应算法比首次要难部分，要加上对分配后该分区是否能最好地利用判定。再一个问题是回收时候合并，对地址修改不是很有把握。着手写程序后，半天才理清回收内存和上下邻合并条件和关系，写此处代码时，逻辑上比较混乱，反复错误反复修改了很数次才调试正确，这也是花了最多时间才得以正确实现部分。之前大多用c语言，对结构体，对象等知识淡忘了很多，这一次实践让我找回了很多学过知识点，也填补了很多不足之处。逻辑思维也得到了锻炼，写代码也不再像初学时候那么繁琐，自己全部能感觉到那一点点进步，立即也认为充实起来。还有一个难点就是为作业找到最好空闲区，此处是参考了部分资料后，理清了条件，然后用一个while（）两个if（）语句循环嵌套就实现了此功效。实践中也发觉本身很多不足，比如上理论课时认为已经了解了算法原理在用代码实践时，发觉还是有模糊和思索不周地方。
实践中最困难是以前没有做过界面，所以即使程序在大家努力下还算顺利地完成了，功效测试也经过了，可是界面制作却成了比较大难题。好在之前在面向对象课程试验和程序设计课程设计中全部用到过MFC，于是确定了用C++来制作界面。不过因为以前界面程序编写较少，所以界面编写碰到了很多困难，尤其是实现内存分配表和空闲分区表输出碰到了很大挫折，最终在查阅资料、认真思索基础上实现内存分配表和空闲分区表输出，并最终作出了内存管理子系统。在添加控件和消息映射时候，问题不是很大，不过在对对应控件添加代码和给类添加组员函数时候，要将源代码对应部分添加进去，且要注意修包含头文件。这些地方一直频繁犯错，或在功效得不到实现，大家一起边找资料边学习新知识，经过很数次尝试，最终做出了界面，即使不太好看，而且功效也很简单，但这也是也经过大家很大努力才完成。
学习着，收获着，并愉快着，这真是小组组员们共同感慨。对于本身不足地方，大家也有了比较清楚认识，对未来发展，也有了个参考，将碰到困难一个个跨过，并最终完成此次课程设计，真感觉很有收获很有成就感。同时也培养了团体合作精神，几次讨论，大大提升了我们合作默契度，体会到合作关键性。动手能力也得到了提升，当然，我们设计还有很多不足之处，有些问题没能很好处理，但经过不停学习和实践，我们一定会做愈加好。