评价网 > 科教论文 > 工学毕业论文 > 计算机应用论文 > 正文

基于Buddy动态存储管理算法的应用研究(1)

2015-09-28 01:12 摘 要 本文分析了动态存储管理的特性, 提出了一种利用哈希表的快速查找特性来优化基于伙伴系统动态存储管理器算法的思想，高效地实现了存储管理器的分配和回收算法，具有简单、速度快、克服了大量存储空间的浪费等优点。 关键词 动态存储管理 伙伴系统 哈希表 算法1 引言 动态存储管理在实现中体现为一个动态存储分配器(dynamic allocator) 。动态存储分配器的设计目标是尽量减少空间的浪费，减少申请释放存储空间时的时间消耗[1]。理想的动态存储分配器是在不浪费空间，极少的时耗下，能满足任何次序的存储空间申请和释放。由于减少时间消耗与增加空间利用率往往相互矛盾, 现实中理想的分配器是很难甚至是不可能实现的，只能根据特定的环境做出适当的决策[2]。 本文在对当前应用中主要采用的动态存储管理技术进行分析的基础上，提出了一种基于buddy动态存储分配和回收思想，利用哈希查找快速定位最佳可利用空闲块在内存中位置的动态存储管理算法。采用这一算法思想设计的动态存储分配器具有简单、速度快的优点，克服了大量存储空间浪费的问题。2 动态存储分配技术 对动态存储管理经过多年的研究，已有大量的动态存储管理解决方案和算法提出并应用到不同的系统中[3]。如：顺序搜索、buddy 算法、分类搜索、索引搜索、位图搜索等。其中顺序搜索和分类搜索算法在操作系统动态内存分配中被普遍采用[4]。 采用顺序搜索的动态存储分配器，一般采用“可利用空间队列”avail链接运行中形成的长度不相等的空闲存储块，采用首次适配(first fit) 、下次适配(next fit) 、最佳适配(best fit) 和最差适配(worst fit) 算法顺序搜索适配块。搜索适配块的时间开销依赖于avail 队列长度。优点是简单，存储空间利用率高。缺点是随着系统规模的增大，会形成许多小碎块，使 avail 队列变长，搜索时间将可能增加到不可接受的程度。 采用分类搜索的动态存储分配器，一般按固定大小将存储空间划分为多个相互独立的存储区，每一个存储区包含一条 avail 队列，存储对象在唯一的 avail 中分配空间。优点是申请分配空间时，不需要进行搜索来查找符合要求的空闲块。释放时也没有相邻空闲块合并的要求，提高了系统执行速度，具有良好的可伸缩性。缺点是在每一个存储区都将有一定的存储空间空闲，且相互之间不能共享，造成较为可观的存储空间浪费。这是典型的以空间换时间的作法。并且存储区划分越细,浪费越严重[5]。 另一种动态存储分配办法是将空闲块组织为伙伴系统(buddy system )。伙伴系统规定，无论占用块或空闲块其大小均为2 的k次幂（k为整数）。假设系统的可利用空间容量为2m 个字，则系统开始运行时，整个内存区是一个大小为2m 的空闲块，系统运行中可能会形成若干个空闲块，将相同大小的空闲块都链在的空闲块都链在同一个双重链表中，不同大小空闲块形成k（0