c - c 中自定义存储分配器的示例或文档？

Question

我分配了一个很大的内存区域，比如 1000 字节的 x。

// I am using c language and all of this is just pseudo code(function prototypes mostly) so far.
pointer = malloc( size(1000 units) ); // this pointer points to region of memory we created.

现在我们通过指针选择这个区域并将其中的内存分配给更小的 block ，例如

void *allocate_from_region( size_of_block1(300) );  //1000-300=700 (left free)
void *allocate_from_region( size_of_block2(100) );  //700-100 =600
void *allocate_from_region( size_of_block3(300) );  //600-300 =300 
void *allocate_from_region( size_of_block4(100) );  //300-100 =200
void *allocate_from_region( size_of_block5(150) );  //200-150 =50
// here we almost finished space we have in region (only 50 is left free in region)


boolean free_from_region(pointer_to_block2);        //free 100 more 
//total free = 100+50 but are not contiguous in memory

void *allocate_from_region( size_of_block6(150) );  // this one will fail and gives null as it cant find 150 units memory(contiguous) in region.

boolean free_from_region(pointer_to_block3); // this free 300 more so total free = 100+300+50 but contiguous free is 100+300 (from block 2 and 3)

void *allocate_from_region( size_of_block6(150); // this time it is successful 

有没有这样管理内存的例子？

到目前为止，我只做了一些示例，在这些示例中，我可以在内存区域中彼此相邻地分配 block ，并在该区域内的内存用完后结束它。但是如何搜索区域内空闲的 block ，然后检查是否有足够的连续内存可用。我确信应该有一些 c 语言的文档或示例来说明如何做到这一点。

Answer 1

当然。您所提议的或多或少正是某些 malloc 实现所做的。他们维护一个“免费列表”。最初，单个大块在此列表中。当你发出请求时，分配n个字节的算法是:

search the free list to find a block at B of size m >= n
Remove B from the free list.
Return the block from B+n through B+m-1 (size m-n) to the free list (unless m-n==0) 
Return a pointer to B

要释放 B 处大小为 n 的 block ，我们必须将其放回空闲列表中。然而这并不是结束。我们还必须将它与相邻的空闲 block “合并”，如果有的话，可以在上方或下方或两者兼而有之。这就是算法。

Let p = B; m = n;  // pointer to base and size of block to be freed
If there is a block of size x on the free list and at the address B + n, 
  remove it, set m=m+x.  // coalescing block above
If there is a block of size y on the free list and at address B - y, 
  remove it and set p=B-y; m=m+y;  // coalescing block below
Return block at p of size m to the free list.

剩下的问题是如何设置空闲列表，以便在分配期间快速找到合适大小的 block ，并在空闲操作期间找到用于合并的相邻 block 。最简单的方法是单链表。但是有许多可能的替代方案可以产生更快的速度，通常会以一些额外的数据结构空间为代价。

此外，当多个 block 足够大时，可以选择分配哪个 block 。通常的选择是“最适合”和“最适合”。对于第一次适合，只取第一个发现的。通常最好的技术是(而不是每次都从最低地址开始)记住刚刚分配的 block 之后的空闲 block ，并将其用作下一次搜索的起点。这称为“旋转首次适配”。

为了最好，适合，根据需要遍历尽可能多的 block 以找到与请求的大小最匹配的 block 。

如果分配是随机的，就内存碎片而言，首先适应实际上比最佳适应要好一些。碎片是所有非压缩分配器的祸根。