Nat*_*ebe 7 c algorithm heap microcontroller
我希望在C中为内存受限的微控制器实现堆分配算法.我已将搜索范围缩小到我所知道的两个选项,但我对建议非常开放,我正在寻找有经验的人的建议或意见.
我的要求:
-Speed绝对有意义,但是次要问题.
- 定时确定性并不重要 - 需要确定性最坏情况时序的代码的任何部分都有自己的分配方法.
- 主要要求是碎片免疫力.该设备正在运行lua脚本引擎,这将需要一系列分配大小(32字节块上很重).主要要求是该设备长时间运行而不会将其堆转变为不可用状态.
另请注意:
- 作为参考,我们讨论的是Cortex-M和PIC32部件,内存范围从128K到16MB或内存(重点放在低端).
- 我不想使用编译器的堆,因为1)我希望所有编译器具有一致的性能,2)它们的实现通常非常简单,对于碎片来说是相同或更差的.
- 双重间接选项是因为巨大的Lua代码库,我不想基本上改变和重新验证.
我最喜欢的方法:
1)有一个二进制伙伴分配器,并牺牲内存使用效率(四舍五入为2的大小). - 这将(据我所知)要求每个订单/ bin的二叉树存储按内存地址排序的空闲节点,以便进行快速伙伴块查找以进行重新链接.
2)有两个二进制树用于空闲块,一个按大小排序,一个按内存地址排序.(所有二叉树链接都存储在块本身中) - 使用对表的大小查找最佳匹配 - 然后通过地址从另一个树中删除该块 - 释放将按地址查找相邻块以进行重新连接
- 两种算法还需要在分配块的开始之前存储分配大小,并且具有作为2减4(或8取决于对齐)的幂的块.(除非他们将二叉树存储在别处以跟踪按内存地址排序的分配,我认为这不是一个好选择)
- 两种算法都需要高度平衡的二叉树代码.
- 算法2没有要求通过舍入到2的幂来浪费存储器.
- 在任何一种情况下,我都可能有一个由嵌套位字段分配的固定32字节块,用于卸载此大小或更小的块,这将不受外部碎片的影响.
我的问题:
- 有什么理由为什么方法1对碎片的免疫力比方法2更强？
- 我是否有任何可能符合要求的替代方案？
如果块大小没有四舍五入到 2 的幂或某个等值 (*)，则某些分配和释放序列将生成本质上无限量的碎片，即使在任何给定时间存在的非永久小对象的数量是有限的。当然，二进制伙伴分配器将避免这个特定问题。否则，如果使用有限数量的密切相关的对象大小但不使用“二进制伙伴”系统，则可能仍然需要使用一些判断来决定在哪里分配新块。
另一种需要考虑的方法是对预期永久、临时或半永久的事物采用不同的分配方法。当临时和永久的东西在堆上交错时，碎片通常会造成最大的麻烦。避免这种交错可以最大限度地减少碎片。
最后，我知道您并不是真的想使用双间接指针，但允许对象重定位可以大大减少与碎片相关的问题。许多 Microsoft 衍生的微型计算机 BASIC 使用垃圾收集字符串堆；微软的垃圾收集器确实很糟糕，但它的字符串堆方法可以与一个好的方法一起使用。