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

    动态存储管理在实现中体现为一个动态存储分配器(dynamic allocator) 。动态存储分配器的设计目标是尽量减少空间的浪费，减少申请释放存储空间时的时间消耗^[1]。理想的动态存储分配器是在不浪费空间，极少的时耗下，能满足任何次序的存储空间申请和释放。由于减少时间消耗与增加空间利用率往往相互矛盾, 现实中理想的分配器是很难甚至是不可能实现的，只能根据特定的环境做出适当的决策^[2]。

     本文在对当前应用中主要采用的动态存储管理技术进行分析的基础上，提出了一种基于buddy动态存储分配和回收思想，利用哈希查找快速定位最佳可利用空闲块在内存中位置的动态存储管理算法。采用这一算法思想设计的动态存储分配器具有简单、速度快的优点，克服了大量存储空间浪费的问题。

    对动态存储管理经过多年的研究，已有大量的动态存储管理解决方案和算法提出并应用到不同的系统中^[3]。如：顺序搜索、buddy 算法、分类搜索、索引搜索、位图搜索等。其中顺序搜索和分类搜索算法在操作系统动态内存分配中被普遍采用^[4]。

    采用顺序搜索的动态存储分配器，一般采用“可利用空间队列”avail链接运行中形成的长度不相等的空闲存储块，采用首次适配(first fit) 、下次适配(next fit) 、最佳适配(best fit) 和最差适配(worst fit) 算法顺序搜索适配块。搜索适配块的时间开销依赖于avail 队列长度。优点是简单，存储空间利用率高。缺点是随着系统规模的增大，会形成许多小碎块，使 avail 队列变长，搜索时间将可能增加到不可接受的程度。

    采用分类搜索的动态存储分配器，一般按固定大小将存储空间划分为多个相互独立的存储区，每一个存储区包含一条 avail 队列，存储对象在唯一的 avail 中分配空间。优点是申请分配空间时，不需要进行搜索来查找符合要求的空闲块。释放时也没有相邻空闲块合并的要求，提高了系统执行速度，具有良好的可伸缩性。缺点是在每一个存储区都将有一定的存储空间空闲，且相互之间不能共享，造成较为可观的存储空间浪费。这是典型的以空间换时间的作法。并且存储区划分越细,浪费越严重^[5]。

    另一种动态存储分配办法是将空闲块组织为伙伴系统(buddy system )。伙伴系统规定，无论占用块或空闲块其大小均为2 的k次幂（k为整数）。假设系统的可利用空间容量为2^m 个字，则系统开始运行时，整个内存区是一个大小为2^m 的空闲块，系统运行中可能会形成若干个空闲块，将相同大小的空闲块都链在的空闲块都链在同一个双重链表中，不同大小空闲块形成k（0<=k<=m）个空闲块链表。当要分配一长度为n 的存储块时，求i 使2^i－1 < n ≤2ⁱ。若长度为2ⁱ 的空闲块已耗尽，则把长为2^i＋1的空闲块分为等长的两半(一对伙伴)，一个用于分配，一个链入长为2ⁱ 的链表中。若长为2^i＋1的空闲块也不存在，则需要对长为2^i＋2的空闲块进行两次分割，依此类推。由此可见，在最坏情况下, 可能要进行k 次分割才能得到适配块。与一次分配可能要进行多次分割一样，一次回收也可能要进行多次合并。其分配和回收的时间性能取决于查找空闲块的位置和分割、合并空闲块所花费的时间。空间性能远优于分类搜索算法，比顺序搜索算法略差。

    基于哈希查找的基本思想是：利用哈希快速查找优点和空闲块在可利用空间表中的分布规律，构造哈希函数。当请求分配存储空间时，通过查找以空闲块大小为关键字的哈希表选择合适的空闲块链，实现最佳分配策略。

    对系统运行可能形成的k个空闲块链表，将头指针组织成一个向量结构，根据链表中空闲块大小确定链表头指针在向量中的位置。

    由于申请的空闲块长度 n 要求满足关系2^i－1 < n ≤2ⁱ。因此可定义哈希函数如下：

   

    哈希函数计算结果确定了所申请大小的空闲块对应链表应在向量表中的位置。

    空闲块结点结构定义，如图1所示。

    { int  tag; /*块标志，0：空闲，1：占用*/

       int  kval; /*块大小，值为2的K次幂*/

        WORD_NODE  *llink,rlink; /*指向前驱、后继结点的指针域*/

        OtherType  other;  /*其它部分*/

    }WORD_NODE,head;     /*内存字类型，结点的第一个字为head*/

    头指针向量表数据类型定义描述如下：

    typedef struct HeadNode

   { int nodesize;  /*该链表空闲块大小*/

   WORD_NODE  *first; /*该链表的头指针 */

  }FreeList[m+1]；/*可利用空间表头向量类型*/

    系统初始状态的可利用空间表状如图2所示。