适用于连续资源块的数组空闲链表的算法

如何来管理空闲资源，显而易见的是组织成一个双向链表，称作freelist，然后每次从该链表上取出一个，释放的时候再放回去。为了减少碎片，最好的策略就是优先分配最近释放掉的那个，如果能考虑合并的话，类似伙伴系统那样，就再好不过了，本文给出的是一个通用的可以将资源映射到一个整型ID的资源分配算法，完全基于一个数组，不需要内存管理，也不需要分配结构体。

       组织链表的时候，内存管理要耗去大量的工作，前向指针和后向指针的修改前提是必须有这些指针。典型的数据结构就是Linux内核的list_head结构体。但是对于静态的类似位图的资源并不适合用list_head来组织，因为这类资源本身可以映射到一块连续的以自然数计数的ID，比较典型的就是磁盘的空闲块，连续内存块的分配。

       既然资源位置是连续的，它就一定能用连续的自然数来表示，那么所有的资源就可以表示成一个数组了-其映射成自然数的ID的数组，记为ArrayA。

       接下来我们需要另外一个数组来表示空闲链表，记为ArrayB。

       接下来的然后，就是构造ArrayB了...ArrayB的大小等于ArrayA大小加上1，多出来的这个元素可以作为不动点存在，它是不会被分配出去的。ArrayB的元素的大小是ArrayA数组大小占据字节数的两倍，是为了在一个元素中存储两个INDEX，比如数组大小可以用8位数据表示，即最多256个元素，那么ArrayB的元素就应该是2*8这么大的，举例说明：

数组大小：short-最多65536个元素

ArrayA的数组定义：int arrayA[MAX];MAX最大65536

ArrayB的数组定义：int arrayB[];int型为两个short型

结构体形象化表示ArrayB：

1

2

3

4

5

6

<code>#define NUM    8</code>

<code>struct</code> <code>freeHL {</code>

<code>        </code><code>short</code> <code>high_preindex; </code><code>//表示前一个ArrayA数组中索引</code>

<code>        </code><code>short</code> <code>low_nextindex;  </code><code>//表示后一个ArrayA数组中索引</code>

<code>};</code>

<code>struct</code> <code>freeHL  freelist[NUM+1];</code>

相当于将ArrayB劈开成了两半。

然后就可以在连续的数组空间进行链接操作了。实际上这个数组表示的freelist和指针表示的prev，next的freelist是一致的，数组下标也是一个指针，只是在数组表示的freelist中，使用的是相对指针偏移而已，表示为下标！

       下面就是一个算法实现问题了，很简单。在freelist中分配了一个index后，需要修改其前向index的后向index以及后向index的前向index，释放过程和分配过程相反。代码如下：

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

<code>short</code> <code>data[NUM]; </code><code>//是为ArrayA</code>

<code>struct</code> <code>freeHL  freelist[NUM+1]; /是为ArrayB</code>

<code>//表示一个下一个分配的index;</code>

<code>unsigned </code><code>int</code> <code>position = 0;</code>

<code>//全局的一次性初始化，注意，如果是序列化到了文件，</code>

<code>//则不能再次初始化了，应该从文件反序列化来初始化。</code>

<code>void</code> <code>list_init()</code>

<code>{</code>

<code>        </code><code>int</code> <code>i = 0, j = -1;</code>

<code>        </code><code>for</code> <code>(; i &lt; NUM+1; i++) {</code>

<code>                </code><code>freelist[i].high_preindex = (i + NUM)%(NUM+1);</code>

<code>                </code><code>freelist[i].low_nextindex = (i + 1)%(NUM+1);</code>

<code>        </code><code>}</code>

<code>        </code><code>position = 0;</code>

<code>}</code>

<code>//分配接口</code>

<code>int</code> <code>nalloc()</code>

<code>        </code><code>int</code> <code>ret_index = -1, next_index = -1, pre_index = -1;</code>

<code>        </code><code>ret_index = position;</code>

<code>    </code><code>//保存当前要分配index的前向index</code>

<code>        </code><code>next_index = freelist[position].low_nextindex;</code>

<code>    </code><code>//保存当前要分配index的后向index</code>

<code>        </code><code>pre_index = freelist[position].high_preindex;</code>

<code>    </code><code>//分配当前index</code>

<code>        </code><code>position = next_index;</code>

<code>        </code><code>if</code> <code>(ret_index == next_index) {</code>

<code>                </code><code>return</code> <code>-1;</code>

<code>    </code><code>//更新当前index前向index的后向index</code>

<code>        </code><code>freelist[freelist[ret_index].high_preindex].low_nextindex = next_index;</code>

<code>    </code><code>//更新当前index后向index的前向index</code>

<code>        </code><code>freelist[freelist[ret_index].low_nextindex].high_preindex = pre_index;</code>

<code>        </code><code>return</code> <code>ret_index;</code>

<code>//释放接口</code>

<code>int</code> <code>nfree(unsigned </code><code>int</code> <code>id)</code>

<code>        </code><code>int</code> <code>pos_pre = -1, pos_next = -1;</code>

<code>    </code><code>//保存下一个要分配的index的前向index，减少碎片以及更加容易命中cache</code>

<code>        </code><code>pos_pre = freelist[position].high_preindex;</code>

<code>    </code><code>//释放index为id的元素</code>

<code>        </code><code>freelist[pos_pre].low_nextindex = id;</code>

<code>        </code><code>freelist[id].high_preindex = pos_pre;</code>

<code>        </code><code>freelist[id].low_nextindex = position;</code>

<code>    </code><code>//下一个要分配的index为刚释放的index</code>

<code>        </code><code>position = id;</code>

下面是一个测试：

<code>int</code> <code>main(</code><code>int</code> <code>argc, </code><code>char</code> <code>**argv)</code>

<code>        </code><code>list_init();</code>

<code>        </code><code>int</code> <code>i = 0;</code>

<code>        </code><code>printf</code><code>(</code><code>"begin\n"</code><code>);</code>

<code>                </code><code>printf</code><code>(</code><code>"\n%d \n"</code><code>, nalloc());</code>

<code>        </code><code>nfree(5);</code>

<code>        </code><code>nfree(0);</code>

<code>        </code><code>nfree(7);</code>

<code>        </code><code>for</code> <code>(i = 0; i &lt; NUM+1; i++) {</code>

<code>        </code><code>printf</code><code>(</code><code>"\nend\n"</code><code>);</code>

这个代码用在何处呢？前面说过，用在资源可以表示为连续ID的场合，这种场合何在？在《编写一个UNIX文件系统》中，我说那个空闲i节点以及空闲块的分配算法不好，而上述的方法就可以用，效果比较好，也就是说，将一点点的工作施放于每次分配/释放的时候，就可以避免在某个时间点做大量的积攒下来的繁重的工作。这个算法省去了遍历操作，代价就是占用了一点连续的地址空间。

 本文转自 dog250 51CTO博客，原文链接:http://blog.51cto.com/dog250/1282347