防碎裂微控制器堆算法

Question

我希望在C中为内存受限的微控制器实现堆分配算法。我已经缩小了我的搜索范围，我知道两个选项，但我非常开放的建议，我正在寻找任何有经验的人的建议或意见。

My Requirements:

-Speed当然很重要，但它是次要的问题。

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

-The的主要要求是碎裂免疫。该设备正在运行一个lua脚本引擎，它将需要一系列的分配大小(在32字节块上很重)。主要的要求是该设备能够长时间运行，而不会将堆搅动到不可用的状态。

还注意到：

-For引用，我们讨论的是Cortex-M和PIC32部件，内存范围从128 K和16 M不等，或者内存(集中在低端)。

-I不想使用编译器的堆，因为1)我希望所有编译器都具有一致的性能；2)它们的实现通常非常简单，对于碎片来说，它们的实现是相同的或更糟的。

-double间接选项被淘汰了，因为我不想对它进行根本的修改和重新验证。

到目前为止我最喜欢的方法：

1)有一个二进制伙伴分配器，并牺牲内存使用效率(取2倍的幂)。据我所知，-this将需要为每个订单/bin设置一棵二叉树，以存储按内存地址排序的空闲节点，以便快速查找好友块以进行检索。

2)为空闲块设置两个二叉树，一个按大小排序，另一个按内存地址排序。(所有二叉树链接都存储在块本身中)使用按大小对表进行查找，-allocation将是最适合的，然后按地址从另一棵树中删除该块，-deallocation将按地址查找相邻的块以进行重新查找。

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

-Both算法需要高度平衡的二叉树编码.

-Algorithm 2不需要将内存舍入到2的幂，从而浪费内存。

无论是哪种情况，我可能都会有一个固定的32字节块，由嵌套位字段分配给这个大小或更小的卸载块，这样就不会受到外部碎片的影响。

我的问题：

-Is --有什么原因可以解释为什么方法1比方法2更容易受到碎片的影响？

-Are，有什么可供选择的，我错过了，可能符合要求？

Answer 1

如果块大小没有舍入到两个或几个等价(*)的幂，那么即使在任何给定时间存在的非永久性小对象的数量是有限的，某些分配和去分配序列也会产生本质上无界的碎片数量。当然，二进制伙伴分配器将避免这个特殊问题。否则，如果您使用的对象大小有限，但不使用“二进制伙伴”系统，那么在决定在何处分配新的块时，可能仍然需要使用一些判断。

另一种需要考虑的方法是，对于那些被认为是永久的、暂时的或半持续的事物，有不同的分配方法。当临时的和永久的东西交织在堆上时，碎片往往会造成最大的麻烦。避免这种交错可能会使碎裂最小化。

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

Answer 2

您可以在http://www.mcdowella.demon.co.uk/buddy.html获得一个(从未用于真正的) Buddy系统分配器，并为您所喜欢的任何目的提供我的祝福。但是，我不认为您有一个问题是很容易解决的，只要插入一个内存分配器。我所熟悉的长时间运行的高完整性系统具有可预测的资源使用情况，在30+页面文档中对每个资源(主要是cpu和I/O总线带宽-内存)进行了描述，因为它们在每次启动时都会分配相同的资源，而以后就不会再分配了。

在您的例子中，没有任何常见的技巧--静态分配、空闲列表、堆栈上的分配--都可以显示出来，因为--至少正如我们所描述的--背景中有一个Lua被解释为悬停在后台，谁知道在运行时做什么--如果它只是进入一个分配内存的循环，直到它用完为止呢？

您能否将内存使用分为两部分--传统代码分配启动时所需的几乎所有的内容，再也不允许使用的代码(例如Lua)允许在需要时分配它所需要的任何东西，以及静态分配后遗留下来的内容？然后，如果它能够在不影响传统代码的情况下使用其所有内存区域或碎片，那么您能触发重新启动或某种形式的代码清理吗？