拆半记忆法对最佳适应算法的优化

黎波

(宜宾学院计算机与信息工程学院，四川宜宾644007)

拆半记忆法对最佳适应算法的优化

黎波

(宜宾学院计算机与信息工程学院，四川宜宾644007)

最佳适应算法（BF）是内存空闲块分配的一种常用算法，现行BF算法的空闲块查询方法不当从而导致工作效率低下.使用拆半法替代原有的BF算法在空闲块查询时所采用的线性顺序比较法，同时增加分配记忆功能，对BF算法进行优化并加强算法功能，从而直接改善内存的分配效率，对提高系统吞吐量起到积极的促进作用.

内存分配；最佳适应算法；折半法；拆半记忆

当前的多任务系统操作系统，进程的数量多，内存的使用频率高、各进程在内存中驻留时间长短不一，从而释放内存的时间先后不同，导致内存空闲块（以下简称空闲块）在内存中呈现出间隔不连续的状态[1-2].因此，空闲块的分配算法旨在对进程的内存请求进行分配，使得进程能获得空闲块而运行，且分配算法的优劣将直接影响内存的分配效率高低[3].

在常见的空闲块分配算法中，最佳适应算法BF（Best Fit）最常用也最具代表性，其效率和性能表现良好.但是，随着操作系统功能的不断扩展，系统中运行的进程数急剧增加，对内存空闲块的请求频率和数量也大幅度提高，于是，进程对内存空闲块的高需求和最佳适应算法的内存分配低效率之间的矛盾愈加凸显，进程的请求得不到及时的响应而不能高效运行.因此，需要优化现有的最佳适应算法在内存块分配方法，弥补其不足，以提高BF算法工作效率，且达到提高内存的分配效率和系统的吞吐量的目的.

1 最佳适应算法BF的缺陷分析

欲分析最佳适应算法BF的缺陷，必须首先叙述最佳适应算法BF的工作原理[4]，即操作系统将内存的空闲块按照容量从小到大的顺序（B1＜B2＜B2＜B4＜B5＜ B6＜…Bn）链接起来，形成空闲块队列，如图1所示.当进程请求内存空闲块时，操作系统从该空闲块队列首部向后开始查询各空闲块，如果容量满足便进行分配，不满足则访问下一个空闲块，直到找到一个满足其容量需求的空闲块后便分配给进程，当访问到最后一个空闲块都不能满足进程的要求时，则内存分配失败，对于后续所有进程的空闲块请求，方法相同，分配过程如图2所示.

图1 空闲块队列图

图2 空闲块分配图

据图2所示，当有新的内存块申请Ask出现时，系统便通过空闲块队列的头指针head找到空闲块队列，然后将Ask和B1比较，如果Ask＜=B1，那么就将B1分配给ask对应的进程，如果不满足，即Ask＞B1，则沿着队列向后查询B2是否满足Ask＜=B2，如果满足则分配，不满足则继续向后推进，直到找到一个空闲块满足为止，然后分配，否则到最后一个空闲块都不满足其大小，那么分配失败.

综上所示，最佳适应算法BF存在严重缺陷，如下所述：

1）空闲块查询时采用了“线性顺序比较”的方法，查询效率低.

每个进程提出空闲块请求Ask时，操作系统都从队列的头部开始向后查询比较空闲块的大小，即：从头到尾依次的、线性的查询比较每一个空闲块是否满足ASK的大小，造成时间的浪费，效率较低.

2）后进程不参考前进程分配，即缺乏记忆功能，所有进程的请求都从队列头部开始，依次向后线性查询，导致了查询的重复性，浪费了大量的时间及计算机资源，导致了内存分配效率低下.

尤其当前操作系统中出现进程数量众多的情况，缺陷1和2的愈加明显.所以，对最佳适应算法进行优化改善，才能从算法本身提高内存的分配效率，从而提供操作系统的吞吐量.

2 采用“拆半记忆法”对最佳适应算法进行优化

由于最佳适应算法BF存在上述的1和2的明显缺陷，经过全面的分析和深入的研究，在空闲块的查询分配时，采用折半法代替原本的线性比较法；同时，结合内存块分配记忆，即后进程须参考前进程的分配位置，再决定其向前查询或者向后查询，即查询的方向，较好地提高空闲块的查询速度，提升空闲块的工作效率，实现了对最佳适应算法的优化改进.具体的优化改良措施如下所述：

第一，最小基本块原则节约了内存空闲块，避免了内存的浪费.

空闲块以空间从小到大（容量递增）的方式组成空闲块队列，同时遵循最小基本块原则，最小基本块的容量为Size，即当分配后余下的空间大于Size时，剩余的空间将作为新的空闲块插入到队列中合适的位置；否则，将整个空闲块全部分配给进程.此举能最大限度地节约内存，不会出现过多的内存浪费现象.

第二，拆半法提高了空闲块的查询访问效率.

当进程提出内存请求Ask时，不再采用从队列头部Head向尾部线性顺序比较法查询内存空闲块，而是采用折半法高效地完成内存空闲块的查找[5].

1）将Ask和空闲块队列的中间空闲块mid进行比较，其中Mid=INT((low+high)/2)，如果该空闲块大于等于进程请求的容量，即Ask＜=med，说明该空闲块满足Ask的需要，那么直接将mid空闲块分配给Ask，完成分配.

当Ask＞mid，即空闲块太小不能满足Ask的需要，则直接忽略1～mid间前半段所有空闲块的比较，甩掉了一半的空闲块进行比较，实现了拆半.再以mid为开头到队列尾部之间的空闲块为新队列，low=mid，med=INT ((low+high)/2)，在新队列中，继续采用折半比较法进行比较，依次类推，直到找到满足Ask＜=med的空闲块为止，完成分配，工作原理如图3所示.

图3 拆半记忆法优化原理图

从上述拆半法的工作原理可见，每次比较都能甩掉队列中50%的空闲块，极大地节约了空闲块队列的访问时间，提高了访问效率，从而提高了内存块的分配效率.

2）后续的空闲块请求必须根据上次作业分配的位置，向队列尾查找比较，其方法仍采用折半比较法，找到满足其大小的空闲块，完成分配.

3）当后续作业在分配的过程中，已经没有空闲块满足其需求，此时，立刻进行内存中空闲块的串联组队，串联时仍然以空闲块容量从小到大（即容量递增）的方式组成空闲块队列.

算法图见图3.其中low代表的是空闲队列的第一个空闲块，而high代表的是最后一个队列，mid则表示折半法的中间点，通过以上算法，当Ask(i)＜=mid且mid-Ask(i)＞=size，满足分配条件，从mid中划出Ask(i)所需要的空间给进程，多余的size作为空闲块回收，完成分配；继续判断有无新请求，如果有，则需要参考上次的分配点mid，如果Aski+1＞=mid，则以mid为队首high为队尾（后半段）进行拆半查询，反之，以low为队首mid为队尾（前半段）进行拆半查询.如果整个队列中都没有空闲块满足Aski+1的需要，则重新组织队列，再按照同样的方法折半比较，该算法用伪码表示如下：

3 优化后的最佳适应算法性能分析

在查询空闲分区的时候，采用顺序查找法和折半查找法，所耗的时间不同[6]，如果空闲块数都为n，那么，顺序查找法的时间消耗为k1=(n+1)/2，而折半记忆法可以表示成：

从以上结论可以看出，k2远小于k1，尤其是空闲块数多，即n的值很大的情况下，折半法的效率比顺序查找的效率高很多，如表1所示．

表1 算法对比表

从表1可以看出，采用折半记忆法的性能远优于顺序比较法，因此，在最佳适应算法的基础上，采用折半记忆法查询空闲块，优化后的最佳适应算法能极大地提高了内存空闲块的分配效率，对增加系统的吞吐量有明显的改善效果.

4 总结

采用拆半记忆法优化后的最佳适应算法（BF），在查询空闲块时，不再采用顺序比较，而采用折半法提高了查询效率；同时后续进程申请空闲块的时候增加了记忆功能，后续进程以前导进程的位置为端点形成新的空闲块队列，进一步缩小了查询队列长度.更大程度地提高了比较查询的效率，从根本上降低了最佳适应算法原来的顺序比较法较大的时间开销，加快了空闲块的分配速度，从而提高了内存的工作效率.

[1]程显波.计算机的内存管理与优化[J].辽阳石油化工高等专科学校学报,1999(3):51-54.

[2]瞿朝成,祁建宏,海波,等.动态分区管理中空闲分区的邻接性判断及合并算法研究[J].电脑编程技巧与维护,2012(24):7-8.

[3]吴冰.计算机内存管理的优化[J].电脑技术,1995,(2):41-43.

[4]汤小丹,汤子赢.计算机操作系统[M].第三版.西安:西安电子科技大学出版社,2007.

[5]严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社, 1997.

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

【编校：王露】

Application of Half and Memory Method to Optimize Best Fit Algorithm

LI Bo
(Computer and Information Engineering Faculty,Yibin University,Yibin,Sichuan 644007,China)

Best Fit algorithm(BF)is a common way to cope with memory allocation;the current BF is inefficient especially in free memory block inquiring.Half and Memory method was applied to replace the linear query of BF in memory block requirement, moreover,distribution and memory strategy was added in the half and memory method to strengthen the function,which strengthens the efficiency in memory allocation and promotes the throughput of operating system.

memory allocation;best fit algorithm;half;half and memory algorithm

TP301.6

A

1671-5365(2014)06-0123-03

2013-05-15修回：2014-04-04

黎波(1977-)，男，讲师，硕士研究生，研究方向为计算机应用技术

时间：2014-04-16 16:51

http://www.cnki.net/kcms/detail/51.1630.Z.20140416.1651.009.html