我正在寻找在C中为内存受限的微 Controller 实现堆分配算法的方法。我已将搜索范围缩小到我知道的2个选项，但是我非常乐意提供建议，并且正在寻找有经验的人提供建议或意见。
我的要求:
-速度绝对很重要，但这是次要的问题。
-确定性计时并不重要-需要确定性最坏情况计时的代码的任何部分都有其自己的分配方法。
-MAIN的要求是碎片免疫。该设备正在运行lua脚本引擎，这将需要一定范围的分配大小(在32个字节的块上比较大)。主要要求是该设备可以长时间运行，而不会使其堆变为不可用状态。
另请注意:
-作为引用，我们讨论的是Cortex-M和PIC32器件，其内存范围为128K和16MB或内存(重点放在低端)。
-我不想使用编译器的堆，因为1)我希望所有编译器都具有一致的性能，并且2)它们的实现通常非常简单，并且对于碎片化而言相同或更差。
-double间接选项被淘汰了，因为我不想通过Lua的庞大代码库进行基础更改和重新验证。
到目前为止，我最喜欢的方法:
1)使用二进制伙伴分配器，并牺牲内存使用效率(四舍五入为2的幂)。
-(据我了解)，这对于每个顺序/bin都需要一个二叉树，以存储按内存地址排序的空闲节点，以快速查找伙伴块以进行重新链接。
2)对于空闲块有两个二进制树，一棵按大小排序，一棵按内存地址排序。 (所有二叉树链接都存储在块本身中)
-allocation将最适合使用按大小在表上查找，然后按地址从另一棵树中删除该块
-deallocation将按地址查找相邻块以进行重新链接
-两种算法都还需要在分配的块开始之前存储分配大小，并且使块以2乘4的幂(或8取决于对齐)而消失。 (除非它们将二进制树存储在其他位置以跟踪按内存地址排序的分配，但我认为这不是一个好选择)
-这两种算法都需要高度平衡的二叉树代码。
-算法2不需要四舍五入为2的幂来浪费内存。
-在任何一种情况下，我可能都会有一个固定的32字节块库，该块库由嵌套的位字段分配来卸载此大小或更小的块，这将不受外部碎片的影响。
我的问题:
-是否有任何理由使方法1比方法2更能抵抗碎片？
-我是否缺少其他符合要求的替代方案？
最佳答案
如果块大小未舍入为2或某个等价(*)的幂，则即使在任何给定时间存在的非永久性小对象的数量为有限的。当然，二元伙伴分配器将避免该特定问题。否则，如果使用有限数量的良好对象大小而不使用“二进制伙伴”系统，则在决定在何处分配新块时可能仍需使用一些判断。
要考虑的另一种方法是对预期为永久，临时或半永久的事物使用不同的分配方法。当临时性和永久性内容在堆上交错时，碎片化通常会带来最大的麻烦。避免这种交错可以最大程度地减少碎片。
最后，我知道您并不是真的想使用双间接指针，但是允许对象重定位可以大大减少与碎片相关的问题。许多Microsoft派生的微型计算机BASIC都使用了垃圾回收的字符串堆。微软的垃圾收集器确实很可怕，但是它的字符串堆方法可以很好地使用。
关于c - 防碎片微 Controller 堆算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/10805087/