我希望在内存受限的微控制器中实现堆分配算法。我已经缩小了搜索范围,只剩下两个选项,但我非常乐意听取有经验的人的建议或意见。
我的要求:
-速度当然很重要,但是不是首要关注点。
-确定性时间不重要——任何需要确定性最坏情况时间的代码部分都有自己的分配方法。
-主要要求是免疫碎片化。设备正在运行一个Lua脚本引擎,它将需要一系列分配大小(重点是32字节块)。主要要求是使该设备长时间运行而不会使其堆转变为无法使用的状态。 还请注意: -参考资料,我们谈论的是Cortex-M和PIC32部件,内存范围从128K到16MB(重点关注较低端)。
-我不想使用编译器的堆,因为1)我希望所有编译器具有一致的性能,2)它们的实现通常非常简单,并且对于碎片化来说相同或更差。
-双重间接选项被排除了,因为我不想基本更改和重新验证巨大的Lua代码库。 我迄今为止喜欢的方法: 1)有一个二进制伙伴分配器,并牺牲内存使用效率(舍入到2的幂大小)。 -这将(据我所知)需要为每个顺序/ bin设置一个二叉树,以按内存地址排序的自由节点存储以进行快速伙伴块查找以进行重新链接。
2)为免费块有两个二叉树,一个按大小排序,一个按内存地址排序。(所有二进制树链接都存储在块本身中) -使用表格按大小最佳拟合进行分配,然后从其他树中按地址删除该块 -解除分配会查找相邻块以进行重新链接
-这两种算法都需要在分配块之前存储分配大小,并且块以2的幂减4(或8,具体取决于对齐)出去。 (除非它们在其他地方存储二进制树以按内存地址排序跟踪分配,否则我认为不是一个好的选择)
-这两种算法都需要平衡高度的二叉树代码。
-算法2不需要浪费内存来舍入为2的幂。
-无论哪种情况,我可能会通过嵌套位字段为32字节块分配一个固定的块库,这些块将免疫外部碎片化。 我的问题: -有什么理由认为方法1比方法2更免疫碎片化吗?
-我是否遗漏了任何符合要求的替代方案?
-确定性时间不重要——任何需要确定性最坏情况时间的代码部分都有自己的分配方法。
-主要要求是免疫碎片化。设备正在运行一个Lua脚本引擎,它将需要一系列分配大小(重点是32字节块)。主要要求是使该设备长时间运行而不会使其堆转变为无法使用的状态。 还请注意: -参考资料,我们谈论的是Cortex-M和PIC32部件,内存范围从128K到16MB(重点关注较低端)。
-我不想使用编译器的堆,因为1)我希望所有编译器具有一致的性能,2)它们的实现通常非常简单,并且对于碎片化来说相同或更差。
-双重间接选项被排除了,因为我不想基本更改和重新验证巨大的Lua代码库。 我迄今为止喜欢的方法: 1)有一个二进制伙伴分配器,并牺牲内存使用效率(舍入到2的幂大小)。 -这将(据我所知)需要为每个顺序/ bin设置一个二叉树,以按内存地址排序的自由节点存储以进行快速伙伴块查找以进行重新链接。
2)为免费块有两个二叉树,一个按大小排序,一个按内存地址排序。(所有二进制树链接都存储在块本身中) -使用表格按大小最佳拟合进行分配,然后从其他树中按地址删除该块 -解除分配会查找相邻块以进行重新链接
-这两种算法都需要在分配块之前存储分配大小,并且块以2的幂减4(或8,具体取决于对齐)出去。 (除非它们在其他地方存储二进制树以按内存地址排序跟踪分配,否则我认为不是一个好的选择)
-这两种算法都需要平衡高度的二叉树代码。
-算法2不需要浪费内存来舍入为2的幂。
-无论哪种情况,我可能会通过嵌套位字段为32字节块分配一个固定的块库,这些块将免疫外部碎片化。 我的问题: -有什么理由认为方法1比方法2更免疫碎片化吗?
-我是否遗漏了任何符合要求的替代方案?