c - 如何计算碎片化？

Question

想象一下，你有一些包含一堆字节的内存：

++++ ++-- ---+ +++-
-++- ++++ ++++ ----
---- ++++ +

让我们说+意味着分配和-免费。

我正在寻找如何计算碎片百分比的公式。

背景

我正在为具有静态内存的嵌入式设备实现一个微小的动态内存管理。我的目标是拥有一些可以用来存储少量数据的东西。主要是通过无线连接传入的数据包，每个大约 128 字节。

score 8 · Accepted Answer

正如 R. 所说，这完全取决于您所说的“碎片百分比”的含义——但您可以使用的一个简单公式是：

(free - freemax)
----------------   x 100%    (or 100% for free=0)
    free

在哪里

free     = total number of bytes free
freemax  = size of largest free block

这样一来，如果所有内存都在一个大块中，则碎片为0％，如果将内存全部分割成数百个小块，则将接近100％。

score 7 · Accepted Answer

计算当前内存布局可以容纳多少个 128 字节数据包。让这个数字n。

计算在内存布局中可以容纳多少个 128 字节数据包，分配的字节数与当前分配的字节数相同，但没有空洞（例如，将所有 + 移到左侧）。让这个数字N。

您的“碎片率”将是 alpha = n/N

score 4 · Accepted Answer

如果您的分配大小都大致相同，只需将您的内存分成TOTAL/MAXSIZE几块，每块由MAXSIZE字节组成。那么碎片化是无关紧要的。

一般来说，要回答您的问题，“碎片化”没有神奇的数字。你必须评估不同函数在反映内存碎片化程度方面的优点。这是我推荐的一个，作为 size 的函数n：

fragmentation(n) = -log(n * number_of_free_slots_of_size_n / total_bytes_free)

请注意，log它只是将事物映射到“0到无穷大”的比例；您实际上不应该在实践中对此进行评估。相反，您可以简单地评估：

freespace_quality(n) = n * number_of_free_slots_of_size_n / total_bytes_free

理想（1.0能够分配最大可能数量的 size 对象n）并且0.0非常糟糕（无法分配任何对象）。

score 0 · Accepted Answer

如果你有 [++++++--------++++--++-++++++++--------+++++] 并且你想测量可用空间的碎片（或任何其他分配）您可以测量平均连续块大小总块/连续块计数。

在这种情况下，它将是 4/(5 + 2 + 1 + 8) / 4 = 4

4 回答 4