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

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

一、课程设计目标

深入了解采取可变分区存放管理方法内存分配回收实现。

二、预备知识

存放管理中可变分区管理方法。

三、小组组员

四、课程设计内容

编写程序完成可变分区存放管理方法内存分配回收。

具体包含：确定内存空间分配表；

采取最优适应算法完成内存空间分配和回收；

编写主函数对所做工作进行测试，

五、设计思绪：

整体思绪：

可变分区管理方法将内存除操作系统占用区域外空间看做一个大空闲区。看

成业要求装入内存时，依据作业需要内存空间大小查询内存中各个空闲区，当

从内存空间中找到一个大于或等于该作业大小内存空闲区时，选择其中一个空闲

区，按作业需求量划出一个分区装人该作业，作业实施完后，其所占内存分区被

收回，成为一个空闲区。假如该空闲区相邻分区也是空闲区，则需要将相邻空闲

区合并成一个空闲区。

设计所才用算法：

采取最优适应算法，每次为作业分配内存时，总是把既能满足要求、又是最

小空闲分区分配给作业。但最优适应算法轻易出现找到一个分区可能只比作业

所需求长度略大一点情行，这时，空闲区分割后剩下空闲区就很小以致极难再使

用，降低了内存使用率。为处理此问题，设定一个限值minsize,假如空闲区大

小减去作业需求长度得到值小于等于minsize,不再将空闲区分成己分分区和空

闲区两部分，而是将整个空闲区全部分配给作业。

内存分配和回收所使用结构体：

为便于对内存分配和回收，建立两张表统计内存使用情况。一张为统计作业

占用分区“内存分配表”，内容包含分区起始地址、长度、作业名/标志（为。时

作为标志位表示空栏目）；一张为统计空闲区”空闲分区表”，内容包含分区起始

地址、长度、标志（（）表空栏目，1表未分配）。两张表全部采取次序表形式。

相关分配留下内存小碎片问题：

当要装入一个作业时，从“空闲分区表”中查找标志为“1”（未分配）且满

足作业所需内存大小最小空闲区，若空闲区大小和作业所需大小差值小于或等于

minsize,把该分区全部分配给作业，并把该空闲区标志改为“0”（空栏目）。同

时，在已分配区表中找到一个标志为“0”栏目登记新装人作业所占用分区起始

地址，长度和作业名。若空闲区大小和作业所需大小差值大于minsize。则把空

闲区分成两部分，-一部分用来装入作业，另外一部分仍为空闲区。这时只要修改

原空闲区长度，且把新装人作业登记到己分配区表中。

内存回收：

在可变分区方法下回收内存空间时，先检验是否有和归还区相邻空闲区（上

邻空闲区，下邻空闲区若有，则将它们合件成一个空闲区。程序实现时，首

先将要释放作业在“内存分配表”中统计项标志改为“（）”（空栏目），然后检验

“空闲区表”中标志为'1'（未分配）栏目，查找是否有相邻空闲区，若有，将

之合并，并修改空闲区起始地址和长度。

六：数据结构

（1）已分配表定义：

struct

{floataddress;〃已分分区起始地址

floatlength;〃已分分区长度，单位为字节

intflag;〃已分配区表登记栏标志，“0”表示空栏目，试验中只

支持一个字符作业名

}used_table[n];〃已分配区表

(2)空闲分区表定义：

struct

{floataddress;〃空闲区起始地址

floatlength;〃空闲区长度，单位为字节

intflag;〃空闲区表登记栏标志，用“0”表示空栏目，用“1”

表示未分配

}free_table[m];〃空闲区表

(3)全局变量

floatminsize=5;

#definen10〃假定系统许可最大作业数量为n

#definem10〃假定系统许可空闲区表最大为m

七、关键算法：

//最优分配算法实现动态分区

intdistribute(intprocess_namezfloatneed_length)

{

inti,k=-l;//k用于定位在空闲表中选择未分配栏

floatads,len;

intcount=0;

i=0;

//关键查找条件，找到最优空闲区

while(i<=m-l)//循环找到最好空闲分区

if(free_table[i].flag==l&&need_length

<=free_table[i].length)

<

count++;

if(count==111free_table[i].length<

free_table[k].length)

k=i;

)

i=i+l;

}

if(k!=-l)

{

if((free_table[k].length-need_length)v=minsize)〃整个分配

{

free_table[k].flag=O;

ads=free_table[k].address;

len=free_table[k].length;

}

else

{〃切割空闲区

ads=free_table[k],address;

len=need_length;

free_table[k].address+=needjength;

free_table[k].length-=need_length;

?

i=0;

〃循环寻求内存分配表中标志为空栏目标项

while(used_table[i].flag!=O)

(i=i+l；}

if(i<=n-l)〃找到，在已分配区表中登记一个表项

{

used_table[i].address=ads;

used_table[i].length=len;

used_table[i].flag=process_name;

countl+4-;

}

else〃已分配区表长度不足

if(free_table[k].flag==0)〃将已做整个分配撤销

{

free_table[k].flag=l;

free_table[k].address=ads;

free_table[k].length=len;

}

else〃将已做切割分配撤销

{

free_table[k].address=ads;

free_table[k].lengths=len;

}

coutvv”内存分配区已满,分配失败!\nn

return0;

}

}

else

{

coutvv“无法为该作业找到适宜分区！\n";

return0;

)

returnprocess_name;

八、程序步骤图:

作业分配步骤图：

作业j申请Xk大小的内存空间

分配失败

为第姜若甫暮求的结束

或第i栏空闲区长度小于

▼第k栏空闲区长度？尸分配整个分区：切割空闲区：

第k栏状态为空第k栏长度减去xk

ad二第k栏起始地址ad二第k栏起始地址-

xk;第k栏长度第k栏长度

i=i+1

第i栏是已分配区赛-Y

中一栏且第i栏状态一T1

不为空？

N♦

内存回收步骤图:

开始

作业」归还空间

分分区表第

态为作业j(s<=n)

未找到作业S二已分分区表第s栏起始地址

L=已分分区表第s栏长度

已分分区表第s栏状态为空

______♦__________________

口设下邻空闱区在第j栏厂7

假设上邻空闲区在第k栏k=-1

收分

有上邻?

;是空闲区表中

空闲区均找

收分收分

i=i+1

下邻

N

和上下邻三项合

井：第k栏长度二t=0和上邻合并

i栏状态栏长度+L：第」栏长度

J栏状态:“空”t=t+1=第」栏长+L

t栏为空第j栏起始地

N中非空栏?址”

和上邻合并；Ianqishi

第k栏长度;第

k栏长扎

t栏是空

▼N衰中一栏?

Y

已分分区表第sN»

栏状态为J空闲还分区填入空阑区

区表长度不足，

:第t栏起始地飞

回收失败

t栏状态长度=L

第t栏状态为未分配

结束

九、程序说明:

本程序米取VisualC++编写,模拟可变分区存放管理方法内存分配和回收。

假定系统许可最大作业数量为n=10,许可空闲区表最大项数为m=10,判定是否

划分空闲区最小限值为minsize=5。初始化用户可占用内存区首地址为1()0(),大

小为1024B。定义两个结构体及其对象free」ab®m]和used」able[n]实现内存分

配回收及分配表和空闲表登记。用最优分配算法实现动态分配时，调用im

distribute(intprocess_name,floatneed」ength)内存分配函数,设定循环条件查找最

好空闲分区，定义inik以统计最好空闱区首地垃，依据找到空闲区大小和作业

大小判定是整个分配给作业还是切割空闲区后再分配给作业，并在“内存分配表”

和“空闲分区表”中作登记。调用intrecycle(intprocess_name)函数实现内存回收。

次序循环“内存分配表”找到要回收作业，将标志位设为“0”，定义float

recycle_address,recycle_length;用recycle_address记下回收作业首地址，

recyclejength记下回收作业长度。查找空闲表，假如

(free_table[i].address+free_table[i].length)==recycle_address,说明有上邻接空闲

区，这时上邻接区起始地址不变，长度+recycle_address；假如

(recycle_address+recycle_length)==free_table[i].address,说明有下邻接，这时下邻

接空闲区起始地址改为回收作业起始地址recycle_address,长度+recycle_lengtho

假如同时有上下邻接空闲区，则上邻接起始地址不变，长度+recycle_address+

下邻接长度，下邻接标志设为“0”不然，要回收内存没有邻接空闲区，在空闲

区中找到一个标志为“0”空栏目登记回收内存。

十、内存分配回收实现截图：

1、后台代码截图：

(1)、假定系统内存分配表许可最大作业项为10,当分配超出10时，提醒“内

存分配区已满，分配失败”。

rC:\DocuaentsandSettings\Ad*inistrator\桌面,桌面\l

目

年

一区

：♦♦♦♦

长

皮

：1185839

：♦

分配♦♦♦♦

一区

：

M++++

长:

100010

长

101029

长M:M

1039:12

长B

1051:10

长M

1061:20

长M

1081:20

长M

1101:15

长M

1116:14

长M

1130:28

长

质

115827

1=分配内存2：回收内存

3：查看分配0：退出

操

清

您的

作

•1

仝•

名

业

作

专

J^Arl内存1125

月

而

己

区

配

配

s=失

存>

内^1>^

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

存在”。

印C:\DocuneritsandSettings\Ad>inistrato八桌面,桌面

4+H♦

作

度++

/

++地-■•+♦+-■-•♦9

址

业

1185长83

4一-+

地

++区

酉

己

++++三+■♦

分

地

+T++++

♦+一+

午

度

：

地/10

业

++址

1000长

/度29

地

业

址

1010长

/度12

业

址

地

1039长

/度10

业

址

长

地1051

度20

业

址Z/1

1061长

度20

地

业

址

/，

1081长

度15

地

业

址1101/

长

度14

业

址/

地111628

长

度

业

址1130/27

地

度

长

业

址1158

->2长)*

一

一

1:分配内存2：回收内存

3:查看分配0：退出

请

入您

i的曩S

入

您

请

f要

在!而分区号;

业

不

该

f存

(3)、当要释放某个作业时，将已分配表中此作业标志置为'0',并在空闲区做

对应登记。

状

长

址

10824SS2态1

:94

二

+++♦+二+

京++

+-++配

++区

己♦

S♦♦

10

100028车业名：1

B10107任业名：2

1

103827；业名：3

1055**乍业名：4

**1：分配内存2：回收内存

**3：查看分配0：退出

馆输入您要释放的分区号：J_

"1：分配内存2：回收内存

[**3：查看分配0：退出

♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦

+++++++空闲区++++++

++++++++++++++++++-»+++++++++++++++++++

上也址：1082作业长度：942状态：1

施址，1010作业长度，28状—查，1

K-++

++分配

♦♦♦-♦+

:::▲上-.■44■a■

如

+答

♦长

地101

1•••

此1000

•答

长

地280

•

如

1010答

长

地173

出

1038答

长•

地274

1055TT•

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

闲区直接分配给作业。

R*

址

长

吴

卷8991

，t8z

址

态

1125长

1:201

美:

址1015

态

长25:1

1055/+

配++♦♦♦♦

++++

分ES+♦+

/♦♦+

姜

一

H++一♦+++++

名

址

业

++业R

长151

1000.

上

址

名

业

20业0

长.

10151:

上

址

名

业

20业.3

长

址1035

上

业

业

1:25名0

长:

址

上

业

业

105520名

长5

1:•

址

上

业

业

108025名

长•6

1100>:•

美

请瑜入作业名和所需内存：721

**1=分配内存2：回收内存

**3：查看分配0：退出

请输入您的操作：

空区

++++

地址：1125899

地址；101520

地址：105525

♦广

♦-S+

一

匚

++++；区

.-

业t*

♦♦三

地

++址

争

—

1000业：151

地

三

址

争

1055业t：2517

地

址E

J零

1035业：203

地

址-

i

1055业t।250

地1

址l

E'§嗓

1080业：2015

址

地

1100trl,：：256

址

地.0

0作业名：0

(5)、分配作业大小14B和找到最优空闲区大小2DB差值大于5B,所以将整块空

闲区分割成两部分，然后修改空闲表。

空闲

tl

己分配

地址

度

业名

长

业

、

L・

址

业

地

名

度

长

m业

址

业

地

名

长

度

业r

iJj

址

业

地

名

业

长

度

址

业

业

地

名

长

I度

请输入作业名和所需内存：614

**1：分配内存2：回收内存

**3：查看分配0：退出

iH己分配区

H+

『+

也

址

度

,乍'V长

1000-L-*度20：

也

址1

长

1020/八上度

卅25

也L2

长

布\(/一

址

也104514

长

，'度

址-1-A30

也1065:4

长

度

址：

也1095205

作业

.,长0

0M:作业名：0

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

♦♦♦♦♦♦己分配区++++++

r4~aa~a~a~4aaaa，v■-■■-■r■・，・▼▼▼▼▼▼▼▼

也址:1000作2上长度:201管《名：1

：

Silt1020垄度:25公

味度:0

版址：104520，受《名：3

版址：1065*度:10f摩：4

/度：

后址：107515作2监：5

♦空闲区

+-+♦

♦

地

止m♦

1090氏度：934状态：1

地

止2度：45状态：1

1020.

地

止

作业长甘7^~状态：0

1♦0

-♦♦

业

业复

长

三201

iftii

1：1000三^:

业

业

长250

苞

一«:

电1；1：蔗

1020业

业

长

二200

—

地划1:1045业

长

七^:10

蔗

地力171065一

—

业

长1

”5

地切t：1075

(7)、空闲区有两个长度分别为20B和18B未分配烂，现为作业6分配14B内存,

用最好分配算法找到空闲区。

空闲区

++♦♦

晒1：1103*〜彳总：921委1

地划/-唾：20[

1；1010▲£态：1

地引1;1055./-蔻:18力L态：11

♦♦♦•.♦♦.4♦♦

).

已/土配区

+♦**■**■**■++**■++♦♦♦

::1000<£度：10f巨绻1

地九工1010£意:20三）/名:0

谈;25f港;3

她到1；1030伊三]

1：1055'*Z一-£总：18f>2：。

；：1073*/-£度：30f品：5

空闲区

++++

址：1103921

地址：101020

地址：105518

♦一♦♦♦

X

♦配.

~♦

/质10

s

：1000l18

-瓦

：1055SJ2

，5

：1030S匮

/18

：1055S30

：/.^:

1073不

S业

：0•«:0名：0

2、制作界面实现截图

X

3mt长度状态业号

(1095100

107520

11060154

I1035250

11010252

1000101

1000

000

000

长度状态」

1095929

1035251

°00

000

000

000

000

°00

°00

L9___________001

十、源程序:

#include<iostream.h>

#include<iomanip.h>

//全局变量

floatminsize=5;

intcountl=0;

intcount2=0;

#definem10//假定系统许可空闲区表最大为m

#definen10//假定系统许可最大作业数量为n

//已分配表定义

struct

<floataddress;//己分分区起始地址

floatlength;//已分分区长度，单位为字节

intflag;//已分配区表登记栏标志，“0”表示空栏目

}used_table[n];//已分配区表对象名

//空闲区表定义：

struct

<floataddress;〃空闲区起始地址

floatlength;//空闲区长度，单位为字节

intflag;//空闲区表登记栏标志，用“0”表示空栏目，用表示未

分配

}free_table[m];//空闲区表对象名

//函数申明

voidinitialize(void);

intdistribute(int,float);

intrecycle(int);

voidshow();

//初始化两个表

voidinitialize(void)

<

inta;

for(a=0;a<=n-l;a++)

used_table[a].flag=O;//已分配表表项全部置为空表项

free_table[0].address=1000;

free_table[0].length=1024;

free_table[O].flag=l;〃空闲区表表项全部为未分配

)

//最优分配算法实现动态分区

intdistribute(intprocess_namezfloatneed_length)

{

inti,k=-l;//k用于定位在空闲表中选择未分配栏

floatads,len;

intcount=0;

i=0;

while(i<=m-l)//循环找到最好空闲分区

<

if(free_table[i].flag==l&&need_length

<=free_table[i].length)

{

count++;

if(count==l||free_table[i].length<

free_table[k].length)

k=i;

)

i=i+l;

)

if(k!=-l)

if((free_table[k].length-need__length)<=minsize)〃整

个分配

free_table[k].flag=O;

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!=O)

{i=i+l；?

if(i<=n-l)//找到，在己分配区表中登记一个表项

<

used_table[i].address=ads;

used_table[i].length=len;

used_table[i].flag=process_name;

countl++;

else//已分配区表长度不足

if(free_table[k].flag==0)//将已做整个分配撤销

free__table[k].flag=l;

free_table[k].address=ads;

free__table[k].length=len;

)

else//将己做切割分配撤销

<

free_table[k].address=ads;

free_table[k].length+=len;

}

coutvv”内存分配区已满，分配失败！\n”；

return0;

)

}

else

<

coutvv”无法为该作业找到适宜分区！\n”；

return0;

}

returnprocess_name;

}

intrecycle(intprocess__name)

inty=0;

floatrecycle_addresszrecycle_length;

int\,j,k;//j栏是下邻空闲区，k栏是上栏空闲区

intx;

//在内存分配表中找到要回收作业

while(y<=n-18i&used_table[y].flag!=process_name)

{y=y+l;}

if(y<=n-l)//找到作业后，将该栏标志置为‘0’

<

recycle_address=used_table[y].address;

recycle_length=used_table[y].length;

used_table[y].flag=O;

count2++;

}

else//未能找到作业，回收失败

{

coutvv”该作业不存在！\n";

return0;

}

j=k=-l;

i=0;

while(!(i>=m||(k!=-l&&j!=-l)))//修改空闲分区表

<

if(free_table[i].flag==l)

if((free_table[i].address+free_table[i].length)==recycle_

address)

k=i;//判定是否有上邻接

if((recycle_address+recycle_length)==free_table[i].addr

ess)

j=i;//判定是否有下邻接

)

i=i+l;

}

//合并空闲区

if(k!=-l)//回收区有上邻接

{

if(j!=-l)<//回收区也有下邻接，和上下领接合并

free_table[k],length+=free_tableO].length+recycle_leng

th;

free_table[j].flag=O;〃将第j栏标识置为'O'

)

else//不存在下邻接，和上邻接合并

free_table[k].length+=recycle_length;

}

elseif(j!=-l)

{//只有下邻接，和下邻接合并

free_table[j].length+=recycle_length;

free_table0].address=recycle_address;

}

else

//上下邻接全部没有

x=0;

while(free_table[x].flag!=O)

x=x+l;//在空闲区表中查找一个状态为‘0’栏目

if(x<=m-l)

{//找到后，在空闲分区中登记回收内存

free_table[x].address=recycle_address;

free_table[x].length=recycle_length;

free_table[x].flag=l;

)

else

<