c - 抗碎片微 Controller 堆算法

Question

我希望用 C 语言为内存受限的微 Controller 实现堆分配算法。我已将搜索范围缩小到我知道的 2 个选项，但是我非常愿意接受建议，并且我正在寻找任何有这方面经验的人的建议或意见。

我的要求:

-速度绝对重要，但它是次要问题。

-时序确定性并不重要 - 需要确定性最坏情况时序的代码的任何部分都有其自己的分配方法。

-主要要求是碎片免疫。该设备正在运行一个 lua 脚本引擎，这将需要一系列分配大小(在 32 字节 block 上很重)。主要要求是该设备能够长时间运行，而不会使其堆进入不可用状态。

另请注意:

-作为引用，我们谈论的是 Cortex-M 和 PIC32 部件，内存范围从 128K 到 16MB 或内存(重点放在低端)。

-我不想使用编译器的堆，因为 1) 我希望所有编译器的性能一致，以及 2) 它们的实现通常非常简单，并且在碎片化方面相同或更差。

-由于我不想从根本上改变和重新验证庞大的 Lua 代码库，所以双重间接选项已被淘汰。

迄今为止我最喜欢的方法:

1) 有一个二进制伙伴分配器，并牺牲内存使用效率(四舍五入到 2 的幂大小)。- 这将(据我所知)需要为每个订单/bin 存储一个二叉树来存储按内存地址排序的空闲节点，以便快速查找好友 block 以进行重新链接。

2) 有两棵用于空闲 block 的二叉树，一棵按大小排序，一棵按内存地址排序。 (所有二叉树链接都存储在 block 本身中)-分配最适合使用按大小查找表，然后按地址从另一棵树中删除该 block -解除分配将通过重新链接的地址查找相邻 block

-两种算法还需要在分配 block 开始之前存储分配大小，并让 block 以 2 减 4 的幂(或 8，取决于对齐方式)输出。 (除非他们在别处存储二叉树以跟踪按内存地址排序的分配，我认为这不是一个好的选择)

-两种算法都需要高度平衡的二叉树代码。

-算法2没有四舍五入到2的幂浪费内存的需求。

-在任何一种情况下，我都可能有一个由嵌套位字段分配的 32 字节 block 的固定库来卸载这个大小或更小的 block ，这将不受外部碎片的影响。

我的问题:

-为什么方法 1 比方法 2 更能避免碎片化？

-我是否缺少任何可能符合要求的替代方案？

Answer 1

如果 block 大小没有四舍五入到 2 的幂或某些等价物 (*)，某些分配和释放序列将产生本质上无限量的碎片，即使任何位置存在的非永久性小对象的数量也是如此时间有限。当然，二进制伙伴分配器将避免该特定问题。否则，如果使用有限数量的相关对象大小但不使用“二进制伙伴”系统，则在决定在哪里分配新 block 时可能仍然需要进行一些判断。

要考虑的另一种方法是对预期为永久性、临时性或半永久性的事物采用不同的分配方法。当临时和永久的东西在堆上交错时，碎片通常会造成最大的麻烦。避免这种交错可以最大限度地减少碎片。

最后，我知道您并不是真的想使用双重间接指针，但允许对象重定位可以大大减少与碎片相关的问题。许多 Microsoft 派生的微型计算机 BASIC 使用垃圾收集字符串堆； Microsoft 的垃圾收集器真的很糟糕，但它的字符串堆方法可以与一个好的垃圾收集器一起使用。