References:

1. http://blog.csdn.net/zhouzhanglong/archive/2009/04/17/4086349.aspx

Next Fit算法

首先为了作一个对比，使用了一个来自于《C程序设计语言》上面的malloc版本来进行比对。

这个简单版本的思想是使用一个循环单链表来进行空闲块的维护，base变量表示该链表的头，freep表示上次操作的(malloc或者free)的空闲块。

分配一定大小的块的时候，从freep开始找，知道找到一个空闲块其大小大于等于请求块的大小。如果大小刚好，则直接分配出去，否则从尾部开始分配请求大小的块，剩余的大小就变成新的空闲块，这样做的好处是不用维护一个指向freep前一个空闲块的指针，而只需要改变size值就可以。这个算法在操作系统的术语里面叫做Next Fit。

这个算法具有一定的随机性的思想，所以总体来说块的分配会比较平均。

以下是malloc.h的内容：

#ifndef _MALLOC_H_<br /> #define _MALLOC_H_<br /> typedef long Align;<br /> union header {<br /> struct {<br /> union header *ptr;<br /> unsigned size;<br /> } s;<br /> Align x; /* used for alignment */<br /> };<br /> typedef union header Header;<br /> void *malloc(unsigned);<br /> void free(void *);<br /> #endif

下面是malloc和free的函数定义：

#include "malloc.h"<br /> #include <stddef.h><br /> static Header base; /* the beginning of the free block list */<br /> static Header *freep = NULL; /* pointer to the block we just dealing with */<br /> static Header *morecore(unsigned nu);<br /> void *malloc(unsigned nbytes)<br /> {<br /> Header *p, *prevp;<br /> unsigned nunits;<br /> nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;<br /> if ((prevp = freep) == NULL)<br /> {<br /> base.s.ptr = freep = prevp = &base;<br /> base.s.size = 0;<br /> }<br /> for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr)<br /> {<br /> if (p->s.size >= nunits)<br /> {<br /> if (p->s.size == nunits)<br /> prevp->s.ptr = p->s.ptr;<br /> else<br /> {<br /> p->s.size -= nunits;<br /> p += p->s.size;<br /> p->s.size = nunits;<br /> }<br /> freep = prevp;<br /> return (void *)(p + 1);<br /> }<br /> if (p == freep)<br /> if ((p = morecore(nunits)) == NULL)<br /> return NULL;<br /> }<br /> return 0;<br /> }<br /> void free(void *ap)<br /> {<br /> Header *bp, *p;<br /> bp = (Header *)ap - 1;<br /> for (p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)<br /> if (p >= p->s.ptr && (bp > p || bp < p->s.ptr))<br /> break;<br /> if (bp + bp->s.size == p->s.ptr)<br /> {<br /> bp->s.size += p->s.ptr->s.size;<br /> bp->s.ptr = p->s.ptr->s.ptr;<br /> }<br /> else<br /> {<br /> bp->s.ptr = p->s.ptr;<br /> }<br /> if (p + p->s.size == bp)<br /> {<br /> p->s.size += bp->s.size;<br /> p->s.ptr = bp->s.ptr;<br /> }<br /> else<br /> p->s.ptr = bp;<br /> freep = p;<br /> }<br /> #define NALLOC 1024<br /> static Header *morecore(unsigned nu)<br /> {<br /> char *cp, *sbrk(int);<br /> Header *up;<br /> if (nu < NALLOC)<br /> nu = NALLOC;<br /> cp = sbrk(nu * sizeof(Header));<br /> if (cp == (char *) -1)<br /> return NULL;<br /> up = (Header *) cp;<br /> up->s.size = nu;<br /> free((void *)(up + 1));<br /> return freep;<br /> }

Buddy Algorithm(伙伴算法)

就如Reference里面的算法描述，伙伴算法的核心思想是把块的大小都定好，一般是2的幂的大小。

在这里我们会有一个最大的幂值，称为u，也就是最大块就是2^u那么大。

有一个最小幂值，称为l，最小块的大小就是2^l那么大。

然后不同大小的块使用不同的链表来管理，总的是一个free_area的数组来存储这些链表的表头。其中数组free_area里面的下标表示的就是这个链表对应的块的大小的幂数。

然后在分配空闲块的时候首先从最小的大于申请大小的块开始查找。如果这个申请块的幂数是7那么就从free_area[7]开始查找。如果这个链表为空，则往大的链表开始搜索，如果搜索到了的话，将大块分割成两个小块，其中一块用来分配，另外一块用来存在小的块的链表里面。

这里我的实现是使用了双向链表来实现。

而在free的过程中，就查看这个释放块的相邻块是否也是空闲，这里相邻块称为伙伴(buddy)。如果伙伴也是在空闲块的块的话，那么就将这两个块合并，这个过程递归，不能再合并为止。

下面是buddy.h里面关于函数的定义：

#ifndef _BUDDY_H_<br /> #define _BUDDY_H_<br /> void *buddy_alloc(unsigned int);<br /> void buddy_free(void *);<br /> void buddy_showblocks();<br /> #endif

下面相关的数据结构和函数定义：

#include "buddy.h"<br /> #include <stdio.h><br /> #include <stddef.h><br /> /* u = 15, l = 6 */<br /> #define BUF_SIZE 32768<br /> #define MIN_ORDER 6<br /> #define MAX_ORDER 15<br /> typedef long Align;<br /> union header {<br /> struct {<br /> union header *next;<br /> union header *prev;<br /> unsigned size;<br /> } s;<br /> Align x; /* used for alignment */<br /> };<br /> typedef union header Header;<br /> static char buffer[BUF_SIZE];<br /> static Header *free_area[MAX_ORDER + 1] = {NULL};<br /> static Header *free_buf = NULL;<br /> unsigned int round2power(unsigned int num)<br /> {<br /> unsigned int init = 1 << MIN_ORDER;<br /> unsigned int count = MIN_ORDER;<br /> while (init < num)<br /> {<br /> init <<= 1;<br /> count++;<br /> }<br /> return count <= MAX_ORDER? count : MAX_ORDER;<br /> }<br /> static void insert(Header **listp, Header *block)<br /> {<br /> Header *prev = NULL, *current = *listp;</p> <p> if (*listp == NULL)<br /> {<br /> *listp = block;<br /> block->s.prev = NULL;<br /> block->s.next = NULL;<br /> return;<br /> }<br /> while (current != NULL)<br /> {<br /> if (prev == NULL && block < current)<br /> {<br /> *listp = block;<br /> block->s.next = current;<br /> current->s.prev = block;<br /> block->s.prev = NULL;<br /> return;<br /> }<br /> if(block < current)<br /> {<br /> prev->s.next = block;<br /> block->s.prev = prev;<br /> block->s.next = current;<br /> current->s.prev = block;<br /> return;<br /> }</p> <p> prev = current;<br /> current = current->s.next;<br /> }<br /> if (prev != NULL)<br /> {<br /> prev->s.next = block;<br /> block->s.prev = prev;<br /> block->s.next = NULL;<br /> return;<br /> }<br /> }<br /> static void delete(Header **listp, Header *block)<br /> {<br /> if (*listp == NULL)<br /> return;<br /> /* If the block is the head of the list */<br /> if (*listp == block)<br /> {<br /> *listp = block->s.next;<br /> }<br /> if (block->s.prev != NULL)<br /> {<br /> block->s.prev->s.next = block->s.next;<br /> }<br /> if (block->s.next != NULL)<br /> {<br /> block->s.next->s.prev = block->s.prev;<br /> }<br /> return;<br /> }<br /> static int continous(Header *p1, Header *p2)<br /> {<br /> char *ptr1 = (char *) p1;<br /> char *ptr2 = (char *) p2;<br /> return (ptr1 + p1->s.size) == ptr2;<br /> }<br /> static Header *combine(Header *p1, Header *p2)<br /> {<br /> if (p1->s.size != p2->s.size)<br /> return NULL;<br /> p1->s.size <<= 1;<br /> return p1;<br /> }<br /> void *buddy_alloc(unsigned int nbytes)<br /> {<br /> Header *p;<br /> unsigned nunits, idx;<br /> int i;<br /> idx = round2power(nbytes + sizeof(Header));<br /> /* Initilize the header block */<br /> if (free_buf == NULL)<br /> {<br /> free_buf = free_area[MAX_ORDER] = (Header *) buffer;<br /> free_area[MAX_ORDER]->s.next = NULL;<br /> free_area[MAX_ORDER]->s.prev = NULL;<br /> free_area[MAX_ORDER]->s.size = 1 << MAX_ORDER;<br /> }<br /> for (i = idx; i <= MAX_ORDER; i++)<br /> {<br /> if (free_area[i] != NULL)<br /> {<br /> unsigned int j = i - 1;<br /> unsigned int size = 1 << j;<br /> Header *firstp, *secondp;<br /> for (firstp = free_area[i]; j >= idx; j--, size >>= 1)<br /> {<br /> secondp = (Header *)((char *)firstp + size);<br /> secondp->s.next = NULL;<br /> secondp->s.prev = NULL;<br /> secondp->s.size = size;<br /> insert(&free_area[j], secondp);<br /> }<br /> free_area[i] = firstp->s.next;<br /> p = firstp;<br /> p->s.next = NULL;<br /> p->s.prev = NULL;<br /> p->s.size = 1 << idx;<br /> return p + 1;<br /> }<br /> }<br /> return NULL;<br /> }<br /> void buddy_free(void *bp)<br /> {<br /> Header *prev, *p, *next;<br /> unsigned int idx;<br /> p = (Header *) bp - 1;<br /> idx = round2power(p->s.size);<br /> insert(&free_area[idx], p);<br /> prev = p->s.prev;<br /> next = p->s.next;<br /> /* check whether the buddies can be combined into the larger one */<br /> if (prev != NULL)<br /> {<br /> if (continous(prev, p))<br /> {<br /> delete(&free_area[idx], p);<br /> delete(&free_area[idx], prev);<br /> prev = combine(prev, p);<br /> buddy_free((void *) (prev + 1));<br /> return;<br /> }<br /> }<br /> if (next != NULL)<br /> {<br /> if (continous(p, next))<br /> {<br /> delete(&free_area[idx], p);<br /> delete(&free_area[idx], next);<br /> next = combine(p, next);<br /> buddy_free((void *) (next + 1));<br /> return;<br /> }<br /> }<br /> }<br /> void buddy_showblocks_test();<br /> void buddy_showblocks()<br /> {<br /> buddy_showblocks_test();<br /> unsigned int size = 1 << MIN_ORDER;<br /> int i;<br /> unsigned int bsize;<br /> Header *bp;<br /> char *ptr = buffer;<br /> char *buf_end = &buffer[BUF_SIZE - 1] + 1;<br /> for (bp = (Header *) ptr; ptr < buf_end; ptr += size, bp = (Header *)ptr)<br /> {<br /> bsize = bp->s.size;<br /> unsigned int tmpsize = bsize / size;<br /> int idx = round2power(bsize);<br /> Header *tp = free_area[idx];</p> <p> while (tp != NULL)<br /> if (tp == bp)<br /> break;<br /> else<br /> tp = tp->s.next;<br /> if (tp != NULL)<br /> {<br /> for (i = 0; i < tmpsize; i++)<br /> {<br /> printf("---/n");<br /> }<br /> }<br /> else<br /> {<br /> for (i = 0; i < tmpsize; i++)<br /> {<br /> printf("***/n");<br /> }<br /> }</p> <p> }<br /> }<br /> void buddy_showblocks_test()<br /> {<br /> int i;</p> <p> for (i = MIN_ORDER; i <= MAX_ORDER; i++)<br /> {<br /> if (free_area[i] != NULL)<br /> {<br /> Header *tmp = free_area[i];<br /> int j;<br /> for (j = 0; tmp != NULL; j++, tmp = tmp->s.next)<br /> ;<br /> printf("%d has blocks: %d/n", i, j);<br /> }<br /> else<br /> printf("%d is empty./n", i);<br /> }<br /> }

可以看到伙伴算法对于零散块的处理是比较好的。伙伴算法相对于Next Fit算法的好处是减少了External Fragmentation(外部碎块，也就是在分配块之间的洞)，但是增加了Internal Fragmentation(内部碎块，也就是在申请块内部有一部分是没有被用到的)。

经过测试，使用了100次随机从20到120的随机大小块分配，然后再随机的从这些分配块里面释放。

得到的结果是Next Fit的碎片数目是16，而Buddy的数目是11。

从这个数字多少可以感受到对于碎片的处理，Buddy的确是优于Next Fit。