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

1、基于Buddy动态存储管理算法的应用研究摘要本文分析了动态存储管理的特性,提出了一种利用哈希表的快速查找特性来优化基于伙伴系统动态存储管理器算法的思想，高效地实现了存储管理器的分配和回收算法，具有简单、速度快、克制了大量存储空间的浪费等优点。关键词动态存储管理伙伴系统哈希表算法1引言动态存储管理在实现中表达为一个动态存储分配器(dynaiallatr)。动态存储分配器的设计目的是尽量减少空间的浪费，减少申请释放存储空间时的时间消耗1。理想的动态存储分配器是在不浪费空间，极少的时耗下，能满足任何次序的存储空间申请和释放。由于减少时间消耗与增加空间利用率往往互相矛盾,现实中理想的分配器是很难甚至是

2、不可能实现的，只能根据特定的环境做出适当的决策2。本文在对当前应用中主要采用的动态存储管理技术进展分析的根底上，提出了一种基于buddy动态存储分配和回收思想，利用哈希查找快速定位最正确可利用空闲块在内存中位置的动态存储管理算法。采用这一算法思想设计的动态存储分配器具有简单、速度快的优点，克制了大量存储空间浪费的问题。2动态存储分配技术对动态存储管理经过多年的研究，已有大量的动态存储管理解决方案和算法提出并应用到不同的系统中3。如：顺序搜索、buddy算法、分类搜索、索引搜索、位图搜索等。其中顺序搜索和分类搜索算法在操作系统动态内存分配中被普遍采用4。采用顺序搜索的动态存储分配器，一般采用“可

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

4、没有相邻空闲块合并的要求，进步了系统执行速度，具有良好的可伸缩性。缺点是在每一个存储区都将有一定的存储空间空闲，且互相之间不能共享，造成较为可观的存储空间浪费。这是典型的以空间换时间的作法。并且存储区划分越细,浪费越严重5。另一种动态存储分配方法是将空闲块组织为伙伴系统(buddysyste)。伙伴系统规定，无论占用块或空闲块其大小均为2的k次幂k为整数。假设系统的可利用空间容量为2个字，那么系统开场运行时，整个内存区是一个大小为2的空闲块，系统运行中可能会形成假设干个空闲块，将一样大小的空闲块都链在的空闲块都链在同一个双重链表中，不同大小空闲块形成k0=k=个空闲块链表。当要分配一长度为n的

5、存储块时，求i使2i1n2i。假设长度为2i的空闲块已耗尽，那么把长为2i1的空闲块分为等长的两半(一对伙伴)，一个用于分配，一个链入长为2i的链表中。假设长为2i1的空闲块也不存在，那么需要对长为2i2的空闲块进展两次分割，依此类推。由此可见，在最坏情况下,可能要进展k次分割才能得到适配块。与一次分配可能要进展屡次分割一样，一次回收也可能要进展屡次合并。其分配和回收的时间性能取决于查找空闲块的位置和分割、合并空闲块所花费的时间。空间性能远优于分类搜索算法，比顺序搜索算法略差。3基于哈希查找的根本思想与构造定义3.1基于哈希查找的根本思想基于哈希查找的根本思想是：利用哈希快速查找优点和空闲块在

6、可利用空间表中的分布规律，构造哈希函数。当恳求分配存储空间时，通过查找以空闲块大小为关键字的哈希表选择适宜的空闲块链，实现最正确分配策略。对系统运行可能形成的k个空闲块链表，将头指针组织成一个向量构造，根据链表中空闲块大小确定链表头指针在向量中的位置。由于申请的空闲块长度n要求满足关系2i1n2i。因此可定义哈希函数如下：哈希函数计算结果确定了所申请大小的空闲块对应链表应在向量表中的位置。3.2存储构造定义空闲块结点构造定义，如图1所示。图1空闲块结点构造结点数据类型定义描绘如下：#definensize/*定义size为可利用空间容量，大小为2的次幂*/typedefstrutRD_NDEi

7、nttag;/*块标志，0：空闲，1：占用*/intkval;/*块大小，值为2的K次幂*/RD_NDE*llink,rlink;/*指向前驱、后继结点的指针域*/therTypether;/*其它部分*/RD_NDE,head;/*内存字类型，结点的第一个字为head*/头指针向量表数据类型定义描绘如下：typedefstrutHeadNdeintndesize;/*该链表空闲块大小*/RD_NDE*first;/*该链表的头指针*/FreeList+1；/*可利用空间表头向量类型*/系统初始状态的可利用空间表状如图2所示。图2可利用空间表初始状态4分配与回收算法41分配算法当用户申请分配长

8、度为n的存储块时,求i=HASH(n),假设FreeListi.first不空，只要删除此链表中的第一个结点，分配给申请者即可；否那么判断FreeListi1所对应的空闲块链表，假设不空，那么把长为2i1的第一个空闲块分为等长的两半(一对伙伴),一个用于分配给申请者，另一个链入FreeListi.first对应的链表中。假设FreeListi1.first仍然为空，那么依次判FreeListi2.first，以此类推。假假设直到ik时，FreeListik.first非空，那么需要从该链表中取出一个结点，将大小为2k的一局部分配给申请者，剩余局部分割成假设干个大小分别为2i+1、2i+2、2i

9、+k-1的结点插入到对应大小的链表中。算法描绘如下：RD_NDE*AllBuddy(FreeListavail,intn)/*申请容量为n的存储空间*/j=HASH(n);hile(!availj.firstj=)j+;if(j)returnNULL;i=j;pa=availi.first;pre=pa-llink;su=pa-rlink;if(pa=su)availi.first=NULL;else从子表删去*pa结点;fr(k=j;ki;k+)pi=pa+2i-k;pi-rlink=pi;pi-llink=pi;pi-tag=0;pi-kval=i-k;availi-k.first=piP

10、a-tag=1;pa-kval=i-(-k);Returnpa;42回收算法回收空闲块时，假设该回收块的伙伴也为空闲块，那么需将他们合并成大的空闲块。然后再判断合并后的空闲块的伙伴是否为空闲块，假设是那么继续合并。否那么只要将释放的空闲块简单地插入到相应空闲块链表中即可。设大小为2i的空闲块起始地址为p，其伙伴块的起始地址可采用下式计算:假设pD2i+1=0，那么其伙伴块的起始地址为p+2i假设pD2i+1=2i，那么其伙伴块的起始地址为p-2i例如，假设p为大小为2i的空闲块的起始地址，当pD2i+1=0时，起始地址为p和p2i的两个空闲块互为伙伴；当pD2i+1=2i时，起始地址为p和p2

11、i的两个空闲块互为伙伴。利用该性质可方便地实现空闲块的合并与回收。这里仅给出回收算法的描绘如下：vidFreeBuddy(avail,*addr,n)/*回收长度为n，起始地址为addr的块*/置回收块标志tag为0，块长kval为n;求回收块的伙伴地址buddy=addr%(2*n)?(addr-n):addr+n);求回收块应在头指针向量中的位置i=HASHn;假如availi.first为空，说明该块没有伙伴，直接插入到插入到该链表中;否那么在当前链表中寻找伙伴地址为buddy的块;假如存在伙伴，并且该伙伴是当前链表中唯一大小为2i的空闲块,那么置availi.first为空;否那么，从当前链表中删去伙伴;修改合并后的新空闲块起始地址addr或buddy以及合并块kval的值为2*n;以新地址和新块长为参数，递归调用FreeBuddy函数，继续调用并合并伙伴块;将得到的最后合并块插入到对应头指针向量所对应的空闲块链表中;5完毕语操作系统动态内存管理方法很多，它们各有其优缺点，各有其适用情形。选择合理的存储分配和管理方案必须建立在设计者对硬件平台和系统中动态内存的申请释放流进展科学评价和分析的根底上。本文所提出的存储管理算法的时间性能主要取决于查找空闲块的位置和分割、合并空闲块所花费的时间。采用哈希快速定位方法查找空闲块的时间