适用于連續資源塊的數組空閑連結清單的算法

如何來管理空閑資源，顯而易見的是組織成一個雙向連結清單，稱作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