动态分区存储管理方式的模拟

黄祖贤

(中南大学 信息科学与工程学院，湖南 长沙 410083)



动态分区存储管理方式的模拟

黄祖贤

(中南大学 信息科学与工程学院，湖南 长沙 410083)

采用Java语言展现动态分区中的两种分配算法——首次适应算法和最佳适应算法，以及内存的回收过程的动态模拟实现。该模拟实验可以帮助学生理解内存管理的分配算法，并激发学生学习的兴趣。

存储管理; 动态分区; 内存分配; 内存回收; Java

操作系统是计算机专业的主干课程，整个课程概念抽象，理论性强，控制方法多样，对于普通高校计算机专业学生来讲，在理解和掌握上存在一定的困难。如何将操作系统课程中抽象的原理与具体繁琐的操作系统实现技术有机地结合起来，以比较直观、易于理解、易于掌握的形式展现出来，一直是操作系统课程教学过程中关心与探讨的问题。内存动态分区管理是操作系统课程中一个重要内容。由于该部分内容的理论知识较为抽象，如果在教学过程中辅以适当的实验，将有助于学生加深对所学内容的理解，并激发学生学习的兴趣。本实验采用Java语言模拟作业的执行, 实现动态分区中的两种分配算法——首次适应算法和最佳适应算法，并实现内存的回收过程。

一、动态分区的存储管理方式

有效管理、合理分配、使用有限而昂贵的内存资源，对提升系统性能，尤其是内存的使用效率和进程的运行速度显得尤为重要。[1]内存分配策略中有固定尺寸分配策略和可变大小分配策略，也就是动态分区管理方式。动态分区是根据进程的实际需要，动态地为之分配内存空间。使用的数据结构通常有位示图、空闲表或空闲链表。[2-3]通常的分配算法有首次适应法(FF)，循环首次适应法(NF)，最佳适应法(BF)，最坏适应法(WF)等。[4]

动态分区的内存分配过程是从数据结构中选择一块空闲分区，然后将此分区分割为两个小分区，一个用来装入请求进程，另一个仍作为空闲区，各种分配算法的主要区别在于如何从数据结构中选择空闲分区。[2]

二、动态分区的模拟设计

(一)设计思想

假设内存中空闲分区个数为n，空闲分区大小分别为P1, … ,Pn，在动态分区分配过程中需要分配的进程个数为m(m≤n)，它们需要的分区大小分别为S1, … ,Sm，利用动态分区分配算法将m个进程放入n个空闲分区，给出进程在空闲分区中的分配情况。在最终实现的成果中，用户可以选择需要模拟的分配算法、输入内存大小、碎片大小等，本设计中对需要分配的进程的输入采取命令语句形式：

(1)ADD 进程名 需求内存大小

如：ADD A 128 表示为进程A分配大小为128的内存空间。

(2)DELETE 进程名

如：DELETE A 表示释放进程A占用的内存空间。

(二)分配算法

设计程序模拟两种动态分区分配算法：首次适应算法和最佳适应算法。

1.首次适应算法

FF算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止；然后再按照作业的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲链中。若从链首至链尾都不能找到一个满足要求的分区，则此次内存分配失败，返回。

2.最佳适应算法

所谓"最佳"是指每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业。该算法要求将所有的空闲分区按其容量从小到大的顺序形成一空闲分区链。这样，第一次找到的能满足要求的空闲区，必然是最佳的。

分配过程中，容易出现找到的一个分区可能只比作业所需求的长度略大一点的情形，这时，空闲区分割后剩下的空闲区就很小以致很难再使用，降低了内存的使用率。为解决此问题，可以设定一个最小的碎片大小minsize，即本设计中初始化时需要输入的碎片大小，如果空闲区的大小减去进程需求长度得到的值小于等于minsize，不再将空闲区分成己分分区和空闲区两部分，而是将整个空闲区都分配给作业。

(三)内存回收

动态分区内存的回收主要是分区合并问题，需合并的情况有三种：回收区在一个空闲区之后，回收区在一个空闲区之前，回收区在两个空闲区之间。

(四)功能模块

1.进程(MemoryPCB)信息

主要负责保存需要分配内存的各进程基本信息，如进程名，需求内存大小、实际分配内存大小、分配内存起始地址等。提供外部状态设置和读取接口。

2.空闲内存区块(MemoryBlock)信息

主要负责保存内存分配中的空闲区块基本信息，如空闲区块的起始地址、空闲区块的大小等。提供外部状态设置和读取接口。

3.分配回收(MemoryStrategy)类

(1)从空闲内存区块队列里取相应内存区块；(2)确定一个空闲块是否可以分配给一个进程；(3)给进程分配内存；(4)释放内存空间，合并空闲区块；(5)提供相应分配算法进行内存分配的外部接口以及各个内存状态数据的获取。

4.视图类

(1)提供用户操作接口(分配策略选择、内存初始化、内存分配命令)；(2)显示已分配内存进程状态列表，空闲、内存区块列表。

(五)类与算法设计

1.类图(图1)

2.算法设计

(1)allocateMemoryBlock()函数

allocateMemoryBlock()函数给进程分配内存，它是抽象类MemoryStrategy定义的抽象方法，在其子类FF和BF中提供具体实现。该函数只有一个参数，是申请内存分配的进程信息块。

(2)sortIdleQueue()函数

sortIdleQueue()函数按照一定的策略给空闲队列进行排序，它同样是抽象类MemoryStrategy定义的抽象方法，在其子类FF和BF中提供具体实现。在首次适应算法(FF)中，空闲队列以起始地址进行排序。在最佳适应算法(BF)中，空闲队列以空闲块容量大小进行排序。进程的内存分配流程如图2。

图2 内存分配流程图

(3)releaseMemoryBlock()函数

releaseMemoryBlock()函数回收进程所占用的内存空间，它是类MemoryStrategy定义的方法。该函数只有一个参数，是申请内存分配的进程信息块。

进程的内存回收流程如图3。

(六)模拟结果(图4、图5)

图4 首次适应算法模拟结果

图5 最佳适应算法模拟结果

三、结论

通过对动态分区策略中首次适应算法、最佳适应算法以及内存回收的模拟实现，有利于加深对操作系统中内存的管理与应用。可以进一步对其它的动态分区存储管理策略，如循环首次适应算法与最坏适应算法进行模拟实现。

[1]张琼声,刘冬萍.操作系统内核内存分配算法的分析与性能评价[J].计算机系统应用,2007(1):40-43.

[2]邓曦辉.动态分区分配与回收算法的模拟[J].电脑开发与应用,2013,26(4):61-63.

[3]Woodhull, Albert S Tanenbaum, Andrew S.OperatingSystems:DesignandImplementation[M]. New Jersey:Prentice Hall,2006:50-55.

[4]汤小丹,梁红兵,哲凤屏.计算机操作系统[M].西安:西安电子科技大学出版社,2007:20-23.

(责任编辑 汪继友)

Simulation of Dynamic Partition Storage Management

HUANG Zu-xian

(School of Information Science and Engineering,Central South University,Changsha 410083,Hunan,China)

Two dynamic partition allocation algorithms have been introduced,including first-fit algorithm and the best-fit algorithm in java language,together with the dynamic simulation implementation of memory recovery process.This simulation experiment could help learners understand storage management algorithms and arouse their learning interest.

storage management;dynamic partitioning;memory allocation;memory recovery; java

2015-01-04

黄祖贤(1993-)，女，安徽马鞍山人，中南大学信息科学与工程学院学生。

G642;TP312

A

1671-9247(2015)02-0103-02