操作系统中的内存分配与回收

课程设计2可变分区存储管理方式的内存分派回收

一、课程设计目的

深入理解采用可变分区存储管理方式口勺内存分派回收口勺实现。

二、预备知识

存储管理中可变分区的管理方式。

三、小组组员

四、课程设计内容

编写程序完毕可变分区存储管理方式的内存分派回收。

详细包括：确定内存空间分派表；

采用最优适应算法完毕内存空间的分派和回收；

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

五、设计思绪：

整体思绪：

可变分区管理方式将内存除操作系统占用区域外的空间看做一种大口勺空闲

区。当作业规定装入内存时，根据作业需要内存空间H勺大小查询内存中的各个

空闲区，当从内存空间中找到一种不小于或等于该作业大小口勺内存空闲区时，选

择其中一种空闲区，按作业需求量划出一种分区装入该作业，作业执行完后，其

所占的内存分区被收回，成为一种空闲区。假如该空闲区H勺相邻分区也是空闲区,

则需要将相邻空闲区合并成一种空闲区。

设计所才用的算法:

采用最优适应算法，每次为作业分派内存时，总是把既能满足规定、又是最

小日勺空闲分辨别配给作业。但最优适应算法轻易出现找到的一种分区也许只比

作业所需求日勺长度略大一点日勺情行，这时，空闲辨别割后剩余的空闲区就很小以

致很难再使用，减少了内存日勺使用率。为处理此问题，设定一种限值minsize,

假如空闲区日勺大小减去作业需求长度得到时值不不小于等于minsize,不再将空

闲辨别成己分分区和空闲区两部分，而是将整个空闲区都分派给作业。

内存分派与回收所使用的构造体：

为便于对内存的分派和回收，建立两张表记录内存日勺使用状况。一张为记录

作业占用分区的1“内存分派表”，内容包括分区起始地址、长度、作业名/标志（为

（）时作为标志位表达空栏目）；一张为记录空闲区日勺“空闲分区表”，内容包括分

区起始地址、长度、标志（（）表空栏目，1表未分派）。两张表都采用次序表形式。

有关分派留下的内存小碎片问题：

当要装入一种作时，从“空闲分区表”中杳找标志为“1”（未分派）目满

足作业所需内存大小的最小空闲区，若空闲区的大小与作业所需大小的差值不不

小于或等于minsize,把该分区所有分派给作业，并把该空闲区的标志改为“0”

（空栏目）。同步，在已分派区表中找到一种标志为“0”的栏目登记新装人作业

所占用分区口勺起始地址，长度和作业名。若空闲区口勺大小与作业所需大小的差值

不小于minsizeo则把空闲辨别成两部分，一部分用来装入作业，此外一部分仍

为空闲区。这时只要修改原空闲区口勺长度，且把新装人口勺作业登记到已分派区表

中。

内存的回收:

在可变分区方式下回收内存空间时，先检查与否有与偿还区相邻日勺空闲区

（上邻空闲区，下邻空闲区）。若有，则将它们合件成一种空闲区。程序实现时,

首先将要释放日勺作业在“内存分派表”中日勺记录项的标志改为“0”（空栏目）,

然后检查“空闲区表”中标志为'1'（未分派）的栏目，查找与否有相邻的空闲

区，若有，将之合并，并修改空闲区日勺起始地址和长度。

六：数据构造

（1）已分派表的定义：

struct

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

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

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

支持一种字符日勺作业名

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

（2）空闲分区表的定义：

struct

{floataddress;〃空闲区起始地址

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

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

表达未分派

}free_table[m];〃空闲区表

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+=need_length;

free_table[k].length-=need_length;

}

i=0;

〃循环寻找内存分派表中标志为空栏目的I项

while(used_table[i].flag!=O)〃假如标一；只栏不空，查找下一种

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=1;

free_table[k].address=ads;

free_table[k],length=len;

)

else〃将已做日勺切割分派撤销

{

free_table[k].address=ads;

free_table[k].lengths=len;

)

coutvv”内存分派区已满，分派失败！\n";

return0;

?

}

else

{

coutvv”无法为该作业找到合适分区！\nn;

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栏j=7

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

可收分

有上邻?

Y

1是空闲区表中

一栏或回收分区的上下

邻空闲区均找到？

收分巨收分

i=i+1

［下邻。下邻

N和上下邻三项合

井：第k栏长度二N和上邻合并

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

第j栏状态二“空”二第j栏长+L

t栏为第j栏起始地

♦N中非空栏?

址二s

和上邻合并：

Ianqishi

第k栏长度;第

k栏长扎

t栏是空

表中一栏?

Y

已分分区表第s

栏状态为j空闱归还分区填入空闲区

区表长度不足，

表：第栏起始地

回收失败t=6

第t栏状态长度=L

,第t栏状态为未分配

*结束<

九、程序阐明:

本程序采用VisualC++编写，模拟可变分区存储管理方式H勺内存分派与回

收。假定系统容许欧I最大作业数量为n=10,容许日勺空闲区表最大项数为m=10,

判断与否划分空闲区的最小限值为minsize=5o初始化顾客可占用内存区的首地

址为1000,大小为1024B。定义两个构造体及其对象free」able[m]和used_table[n]

实现内存日勺分派回收及分派表和空闲表的登记。用最优分派算法实现动态分派

时，调用intdistribute(intprocess_name,floatneed」ength)内存分派函数，设定循

环条件查找最佳空闲分区，定义intk以记录最佳空闲区的首地址，根据找到欧I

空闲区大小和作业大小判断是整个分派给作业还是切割空闲区后再分派给作业，

并在“内存分派表”和“空闲分区表”中作登记。调用intrecycle(intprocess_name)

函数实现内存的I回收。次序循环“内存分派表”找到要回收日勺作业，将标志位设

为"0"，定义floatrecycle_address,recycle_length;fflrecycle_address记下回收作

业的I首地址，recycle_length记下回收作业长度。查找空闲表，假如

(free_table[ij.address+free_table[ij.length)==recycle_address,阐明有上令N接空闲

区，这时上邻接区H勺起始地卅不变，长度+recycle_address：假如

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

接空闲区的起始地址改为回收作业的起始地址rccycle_addrcss,长度十

recyclejengtho假如同步有上下邻接空闲区，则上邻接H勺起始地址不变，长度

+recycle_address+下邻接的长度，下邻接标志设为“0”否则，要回收的内存没

有邻接空闲区，在空闲区中找到一种标志为“0”的空栏目登记回收的内存。

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

1、后台代码的截图：

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

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

-C:\Docuaentsand$6七七11185\4(1>:£111516七0「\桌面\桌面\1

+空闱区—

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

：1185作业长度：839状态：1

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

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

一

"一­♦♦♦

长

地10

址

长

地:100029

址J^:

：M

长

地1010:12

址：1039M

地

长:10

址M

地

:1051长:20

址：M

地1061

长:20

址：M

地1081

长15

址:

：M

地

1101长

址:14

：M

地

址111628

长M:

址27

地

s1130长:

：1158俄

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

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

请臧入您的操作：1

请喻入作业名知所需内存：1125

内存分配区已满，分配失败！

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

不存在

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

4+H♦

作

++■-++-■-度++

地

•址

♦业

/长•♦9

118583

4一+

地-++

区

酉

己+++■

++三

分♦

地♦+

T+一+++

：

地

午

++度

址/10

业

1000长

度

址

地29

/业

1010长

度

址/12

业

地

1039长

度

址/10

业

长

地1051

度

址20

业

1061Z1长

度

址

地/20

业

1081长

址

度15

/，

业

地

1101长4

址

/度1

业

地

1116长28

址

/度

业

长

地113027

址

/度

业

1158长

*

一2)

->

一

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

3:查看分配0：退出

请

入您

i的曩S

入

您

请

f要

在!而分区号;

业

不

该

f存

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

做对应登记。

也址

长

第

4S归态

942•.

百

二

♦♦♦♦♦二+

♦京

己++

*配+

卜

一

+一一

t九长

业

rj1000答

九长

业

1010告

业

t九长

J告

J-

t1038业

九长

rj1055答

】

j一

攵

r存

回t

：分配内存r

1出

3：查看分配退

*一*

请输入您要释放的分区号：2_

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

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

XSS5SFTT™™™™

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

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

♦+++++++++++++++++-»+++++++++++++++++++

地址：1082作业长度：942状态：1

附址,1010彳三业W彦,28状态T1

“

-一++++

++分ES

♦+配

-一♦+

++

一

一^+♦♦4+

♦+长

地♦♦

业

址10/

♦++名+1

业

1000I

长2

地

业

址Js

:8/名0

M业

1010长

址

地

业

:17/名3

业

量

1038长

址2

地

业

7/名4

1055业

(4)、分派日勺作业大小21B与找到的最优空闲区大小25B差值不不小于5B,因此

将整块空闲区直接分派给作业。

空闲区

地划1：1125,，—氏度：899注态:1

蜘1：1015•/-肉度：20*态：1

/-*

期11/

1：10551长姜25犬态：1

44,，4，，a，j

■«■■■■■■■■■1r▼p■■▼1~■■■■■■■■■■■■■■■■■1rL，»，■a■

己).

♦♦士•f4-4-4卜♦♦・

/土配区

.44aaa44

laaa・■■■■■■■■ir▼p,a■a■▼&4■'■■■■■■■■■,a■1■■■▼▼▼▼riaaa

他/*，一/

£麦：A喀(A\4•

1:10001511

，八，'三'

地划1：10154£度：20，名.0

地划1：1035ZA/-£度:20/，幺・3

械1：1055■为£,麦：25，-2《名.0

w/-，名J

地1111：10804£度：20JLA\4•5

A,'I/，幺*

地1111：1100£妾：25XA1j•6

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

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

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

请输入您的操作：

空区

++++

地址：1125899

地址；101520

地址：105525

♦广

♦-S+

一

匚

；区

++++.-

*

++业

♦♦址t

地

三

争

—

业

址1000：1

地15

三

争

业：

址10552517

地Et

J零

业

址1035：3

地-20

i

业

址10550

地।251

lt'§

E嗓

业

址1080：5

地201

trl,

址

地1100：：256

.0

0作业名：0

(5)、分派的作业大小14B与找到的最优空闲区大小20B差值不小于5B,因此将

整块空闲辨别割成两部分，然后修改空闲表。

空闲区

♦♦♦♦

：1115作业909

：104520

tl;♦♦♦♦

己配区

业答

长20

：1

业

1000^:答

羡

长252

：业

1020答

K/郎200

：业

1045答

J304

K^:

乱

：业

1065答

长205

：1095(

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

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

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

请输入您的操作：3

+++++++空河区++++++

地址：1115作业长度：909状态：1

他址，1059作业工度，6忙WU

分

己

n酉

iHl♦

HI♦♦

也

址++Js++

++度

^i营1

也

址Jk2

-i度

长

卅

也

乍Y

1045^度6

址

也^

1^Jk；

065i度4

址

也

1095^J上5

l^n度

址

也0r

住

作

业

^。

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

zH

讨++

区

oH♦

++4

他址：1090E9

i一21

_

ft-teijE：1020对

HH+

分

：

配

：++

区*+

度

i♦+HH1+

度

业

<•<•名

长M20/1

h地l*址::

业

1000名0

女rK

:25/1

业

也址:1020名

长M0

地址::2/3

业

10450名

长11Z14

h地it址:

业

10655名

长:1/5

地址:1075.M

.:

.

.

空闲区

址：1090作业长度:934

M：1020匚井K庆:45

作业长反.：0~

己分配区

一

业

长20

址

业

长

址25

反

业

长

地

址20

业

长

地

址

1065度10

业

长

地

址15

⑺、空闲区有两个长度分别为20B和18B的未分派烂，现为作业6分派14B的

内存，用最佳分派算法找到空闲区。

♦一-1

闭

区

空

我

+^+

地±111：1103

iiijj1；1010^

iftil1：1055

已++

分

也

业

址

长1

1081

业

也1000*2

基J00

X等

业

也1010

\25

址§

1030业

也K^

18

K隹

址

业

也1055

长3

作

又0

1073

计-

G三

f区

l

♦+A+I

三

址

++度

业

址1103^

业

度

址1010

业W

度