基于buddy动态存储管理算法的应用研究

《基于buddy动态存储管理算法的应用研究》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、从本学科出发，应着重选对国民经济具有一定实用价值和理论意义的课题。课题具有先进性，便于研究生提出新见解，特别是博士生必须有创新性的成果基于Buddy动态存储管理算法的应用研究摘要本文分析了动态存储管理的特性,提出了一种利用哈希表的快速查找特性来优化基于伙伴系统动态存储管理器算法的思想，高效地实现了存储管理器的分配和回收算法，具有简单、速度快、克服了大量存储空间的浪费等优点。关键词动态存储管理伙伴系统哈希表算法1引言动态存储管理在实现中体现为一个动态存储分配器(dynamicallocator)。动态存储分配器的设计目标是尽量减少空间的浪费，

2、减少申请释放存储空间时的时间消耗[1]。理想的动态存储分配器是在不浪费空间，极少的时耗下，能满足任何次序的存储空间申请和释放。由于减少时间消耗与增加空间利用率往往相互矛盾,现实中理想的分配器是很难甚至是不可能实现的，只能根据特定的环境做出适当的决策[2]。本文在对当前应用中主要采用的动态存储管理技术进行分析的基础上，提出了一种基于buddy动态存储分配和回收思想，利用哈希查找快速定位最佳可利用空闲块在内存中位置的动态存储管理算法。采用这一算法思想设计的动态存储分配器具有简单、速度快的优点，克服了大量存储空间浪费的问题。动态存储分配技术对动态

3、存储管理经过多年的研究，已有大量的动态存储管理解决方案和算法提出并应用到不同的系统中[3]。如：顺序搜索、buddy课题份量和难易程度要恰当，博士生能在二年内作出结果，硕士生能在一年内作出结果，特别是对实验条件等要有恰当的估计。从本学科出发，应着重选对国民经济具有一定实用价值和理论意义的课题。课题具有先进性，便于研究生提出新见解，特别是博士生必须有创新性的成果算法、分类搜索、索引搜索、位图搜索等。其中顺序搜索和分类搜索算法在操作系统动态内存分配中被普遍采用[4]。采用顺序搜索的动态存储分配器，一般采用“可利用空间队列”avail链接运行中形

4、成的长度不相等的空闲存储块，采用首次适配(firstfit)、下次适配(nextfit)、最佳适配(bestfit)和最差适配(worstfit)算法顺序搜索适配块。搜索适配块的时间开销依赖于avail队列长度。优点是简单，存储空间利用率高。缺点是随着系统规模的增大，会形成许多小碎块，使avail队列变长，搜索时间将可能增加到不可接受的程度。采用分类搜索的动态存储分配器，一般按固定大小将存储空间划分为多个相互独立的存储区，每一个存储区包含一条avail队列，存储对象在唯一的avail中分配空间。优点是申请分配空间时，不需要进行搜索来查找符合

5、要求的空闲块。释放时也没有相邻空闲块合并的要求，提高了系统执行速度，具有良好的可伸缩性。缺点是在每一个存储区都将有一定的存储空间空闲，且相互之间不能共享，造成较为可观的存储空间浪费。这是典型的以空间换时间的作法。并且存储区划分越细,浪费越严重[5]。另一种动态存储分配办法是将空闲块组织为伙伴系统(buddysystem)。伙伴系统规定，无论占用块或空闲块其大小均为的k次幂。假设系统的可利用空间容量为2m个字，则系统开始运行时，整个内存区是一个大小为2m课题份量和难易程度要恰当，博士生能在二年内作出结果，硕士生能在一年内作出结果，特别是对实验

6、条件等要有恰当的估计。从本学科出发，应着重选对国民经济具有一定实用价值和理论意义的课题。课题具有先进性，便于研究生提出新见解，特别是博士生必须有创新性的成果的空闲块，系统运行中可能会形成若干个空闲块，将相同大小的空闲块都链在的空闲块都链在同一个双重链表中，不同大小空闲块形成k个空闲块链表。当要分配一长度为n的存储块时，求i使2i－1i。若长度为2i的空闲块已耗尽，则把长为2i＋1的空闲块分为等长的两半(一对伙伴)，一个用于分配，一个链入长为2i的链表中。若长为2i＋1的空闲块也不存在，则需要对长为2i＋2的空闲块进行两次分割，依此类推。由此

7、可见，在最坏情况下,可能要进行k次分割才能得到适配块。与一次分配可能要进行多次分割一样，一次回收也可能要进行多次合并。其分配和回收的时间性能取决于查找空闲块的位置和分割、合并空闲块所花费的时间。空间性能远优于分类搜索算法，比顺序搜索算法略差。基于哈希查找的基本思想与结构定义基于哈希查找的基本思想基于哈希查找的基本思想是：利用哈希快速查找优点和空闲块在可利用空间表中的分布规律，构造哈希函数。当请求分配存储空间时，通过查找以空闲块大小为关键字的哈希表选择合适的空闲块链，实现最佳分配策略。对系统运行可能形成的k个空闲块链表，将头指针组织成一个向量

8、结构，根据链表中空闲块大小确定链表头指针在向量中的位置。由于申请的空闲块长度n要求满足关系2i－1i。因此可定义哈希函数如下：哈希函数计算结果确定了所申请大小的空闲块对应链表应在