如何来管理空闲资源，显而易见的是组织成一个双向链表，称作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
|
#define NUM 8
struct
freeHL {
short
high_preindex;
//表示前一个ArrayA数组中索引
short
low_nextindex;
//表示后一个ArrayA数组中索引
};
struct
freeHL freelist[NUM+1];
|
相当于将ArrayB劈开成了两半。
然后就可以在连续的数组空间进行链接操作了。实际上这个数组表示的freelist和指针表示的prev，next的freelist是一致的，数组下标也是一个指针，只是在数组表示的freelist中，使用的是相对指针偏移而已，表示为下标！
下面就是一个算法实现问题了，很简单。在freelist中分配了一个index后，需要修改其前向index的后向index以及后向index的前向index，释放过程和分配过程相反。代码如下：
|
1
2
3
4
5
6
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
|
short
data[NUM];
//是为ArrayA
struct
freeHL freelist[NUM+1]; /是为ArrayB
//表示一个下一个分配的index;
unsigned
int
position = 0;
//全局的一次性初始化，注意，如果是序列化到了文件，
//则不能再次初始化了，应该从文件反序列化来初始化。
void
list_init()
{
int
i = 0, j = -1;
for
(; i < NUM+1; i++) {
freelist[i].high_preindex = (i + NUM)%(NUM+1);
freelist[i].low_nextindex = (i + 1)%(NUM+1);
}
position = 0;
}
//分配接口
int
nalloc()
{
int
ret_index = -1, next_index = -1, pre_index = -1;
ret_index = position;
//保存当前要分配index的前向index
next_index = freelist[position].low_nextindex;
//保存当前要分配index的后向index
pre_index = freelist[position].high_preindex;
//分配当前index
position = next_index;
if
(ret_index == next_index) {
return
-1;
}
//更新当前index前向index的后向index
freelist[freelist[ret_index].high_preindex].low_nextindex = next_index;
//更新当前index后向index的前向index
freelist[freelist[ret_index].low_nextindex].high_preindex = pre_index;
return
ret_index;
}
//释放接口
int
nfree(unsigned
int
id)
{
int
pos_pre = -1, pos_next = -1;
//保存下一个要分配的index的前向index，减少碎片以及更加容易命中cache
pos_pre = freelist[position].high_preindex;
//释放index为id的元素
freelist[pos_pre].low_nextindex = id;
freelist[id].high_preindex = pos_pre;
freelist[id].low_nextindex = position;
//下一个要分配的index为刚释放的index
position = id;
}
|
下面是一个测试：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
int
main(
int
argc,
char
**argv)
{
list_init();
int
i = 0;
printf
(
"begin\n"
);
for
(; i < NUM+1; i++) {
printf
(
"\n%d \n"
, nalloc());
}
nfree(5);
nfree(0);
nfree(7);
for
(i = 0; i < NUM+1; i++) {
printf
(
"\n%d \n"
, nalloc());
}
printf
(
"\nend\n"
);
}
|
这个代码用在何处呢？前面说过，用在资源可以表示为连续ID的场合，这种场合何在？在《编写一个UNIX文件系统》中，我说那个空闲i节点以及空闲块的分配算法不好，而上述的方法就可以用，效果比较好，也就是说，将一点点的工作施放于每次分配/释放的时候，就可以避免在某个时间点做大量的积攒下来的繁重的工作。这个算法省去了遍历操作，代价就是占用了一点连续的地址空间。
本文转自 dog250 51CTO博客，原文链接:http://blog.51cto.com/dog250/1282347
