我有一个单线程的嵌入式应用程序，它分配和释放大量的小块（32-64b）。基于缓存的分配器的完美场景。虽然我可以尝试编写一个，但它可能会浪费时间，并且没有像已经在前线的一些解决方案那样经过测试和调整。
那么我可以在这种情况下使用的最佳分配器是什么？
注意：我在系统中使用 Lua 虚拟机（这是 80% 以上分配的罪魁祸首），所以我不能轻易地重构我的代码以使用堆栈分配来提高分配性能。
Robert Gould
问问题
7330 次
8 回答
9
在过去的 CI 项目中，我们为在包括嵌入式系统在内的各种平台上运行的库实现了自己的内存管理例程。该库还分配和释放了大量的小缓冲区。它运行得比较好，并且不需要大量的代码来实现。如果你想自己开发一些东西，我可以给你一些关于该实现的背景知识。
基本实现包括一组管理一定大小的缓冲区的例程。这些例程被用作 malloc() 和 free() 的包装器。我们使用这些例程来管理我们经常使用的结构的分配，并管理集合大小的通用缓冲区。使用一种结构来描述所管理的每种类型的缓冲区。当分配特定类型的缓冲区时，我们会 malloc() 块中的内存（如果空闲缓冲区列表为空）。IE，如果我们管理 10 字节的缓冲区，我们可能会创建一个 malloc()，其中包含 100 个这些缓冲区的空间，以减少碎片和所需的底层 malloc 数量。
在每个缓冲区的前面是一个指针，用于链接空闲列表中的缓冲区。当分配了 100 个缓冲区时，每个缓冲区将在空闲列表中链接在一起。当缓冲区正在使用时，指针将设置为空。我们还维护了缓冲区“块”的列表，以便我们可以通过在每个实际的 malloc'd 缓冲区上调用 free() 来进行简单的清理。
为了管理动态缓冲区大小，我们还在每个缓冲区的开头添加了一个 size_t 变量，告诉缓冲区的大小。然后使用它来识别释放缓冲区时将其放回哪个缓冲区块。我们有 malloc() 和 free() 的替换例程，它们执行指针运算以获取缓冲区大小，然后将缓冲区放入空闲列表中。我们还限制了我们管理的缓冲区大小。大于此限制的缓冲区只需 malloc'd 并传递给用户。对于我们管理的结构，我们创建了用于分配和释放特定结构的包装程序。
最终，当用户请求清理未使用的内存时，我们还将系统改进为包括垃圾收集。由于我们可以控制整个系统，因此我们能够随着时间的推移进行各种优化以提高系统的性能。正如我所提到的，它确实工作得很好。
于 2008-10-07T04:30:34.643 回答
9
我参加聚会有点晚了，但我只想分享我最近发现并测试过的嵌入式系统的非常有效的内存分配器：https ://github.com/dimonomid/umm_malloc
这是一个专门设计用于 ARM7 的内存管理库，我个人在 PIC32 设备上使用它，但它应该适用于任何 16 位和 8 位设备（我计划在 16 位 PIC24 上进行测试，但我还没有测试过）
我被默认分配器的碎片严重击败：我的项目经常分配各种大小的块，从几个字节到几百个字节，有时我遇到“内存不足”错误。我的 PIC32 设备共有 32K 的 RAM，其中 8192 字节用于堆。在特定时刻有超过 5K 的可用内存，但由于碎片，默认分配器的最大非碎片内存块只有大约 700 字节。这太糟糕了，所以我决定寻找更有效的解决方案。
我已经知道一些分配器，但是它们都有一些限制（例如块大小应该是幂或 2，并且不是从 2 开始，而是从 128 字节开始），或者只是有问题。每次之前，我都必须切换回默认分配器。
但这一次，我很幸运：我找到了这个：http ://hempeldesigngroup.com/embedded/stories/memorymanager/
当我尝试这个内存分配器时，在完全相同的情况下，有 5K 的空闲内存，它有超过 3800 字节的块！这对我来说太不可思议了（与 700 字节相比），我进行了艰苦的测试：设备工作了 30 多个小时。没有内存泄漏，一切正常。我还在 FreeRTOS 存储库中找到了这个分配器：http ://svnmios.midibox.org/listing.php?repname=svn.mios32&path=%2Ftrunk%2FFreeRTOS%2FSource%2Fportable%2FMemMang%2F&rev=1041&peg=1041# ，还有这个事实是 umm_malloc 稳定性的另一个证据。所以我完全切换到 umm_malloc，我对此非常满意。
我只需要稍微改变一下：当宏 UMM_TEST_MAIN 未定义时，配置有点错误，所以，我创建了 github 存储库（链接在这篇文章的顶部）。现在，用户相关配置存储在单独的文件 umm_malloc_cfg.h
在这个分配器中应用的算法我还没有深入了解，但是它对算法的解释非常详细，所以有兴趣的人可以看一下文件的顶部 umm_malloc.c 。至少，“分箱”方法应该在减少碎片方面带来巨大的好处：http: //g.oswego.edu/dl/html/malloc.html
我相信任何需要高效微控制器内存分配器的人，至少应该尝试这个。
于 2014-04-03T11:01:37.053 回答
8
我最近对这个主题进行了一些研究，因为我们遇到了内存碎片问题。最后，我们决定继续使用 GNU libc 的实现，并在必要时添加一些应用程序级内存池。还有其他分配器具有更好的碎片行为，但我们对它们在全局范围内替换 malloc 感到不够满意。GNU 的优势在于其背后的悠久历史。
就您而言，这似乎是合理的；假设您无法修复 VM，那么这些微小的分配非常浪费。我不知道您的整个环境是什么，但您可能会考虑仅在 VM 上包装对 malloc/realloc/free 的调用，以便您可以将其传递给为小型池设计的处理程序。
于 2008-10-07T05:55:21.727 回答
6
虽然我问这个已经有一段时间了，但我的最终解决方案是使用 LoKi 的 SmallObjectAllocator，它工作得很好。摆脱了所有操作系统调用并提高了我的 Lua 引擎在嵌入式设备上的性能。非常好和简单，只需大约 5 分钟的工作！
于 2008-11-21T01:21:44.243 回答
3
即使它是一个旧线程，我也想补充一下。在嵌入式应用程序中，如果您可以分析应用程序的内存使用情况并得出不同大小的最大内存分配数量，通常最快的分配器类型是使用内存池的分配器。在我们的嵌入式应用程序中，我们可以确定运行时所需的所有分配大小。如果你能做到这一点，你就可以完全消除堆碎片并获得非常快的分配。大多数这些实现都有一个溢出池，它将为特殊情况做一个常规的 malloc，如果你的分析正确的话，希望它们之间的差距很小。
于 2009-07-04T00:39:10.477 回答
2
我在vxworks下使用'binary buddy'系统效果很好。基本上，您通过将块切成两半来分配堆，以获得两个大小块的最小功率来容纳您的请求，当块被释放时，您可以向上传递树以将块合并在一起以减少碎片。谷歌搜索应该会找到您需要的所有信息。
于 2009-07-04T01:03:20.773 回答
-1
我正在编写一个名为 tinymem 的 C 内存分配器，旨在能够对堆进行碎片整理并重新使用内存。看看这个：
https://github.com/vitiral/tinymem
注意：该项目已停止进行 rust 实施：
https://github.com/vitiral/defrag-rs
另外，我以前没有听说过 umm_malloc。不幸的是，它似乎无法处理碎片，但它确实看起来很有用。我得去看看。
于 2015-04-26T19:20:19.807 回答