想象一下,你有一些包含一堆字节的内存:
++++ ++-- ---+ +++-
-++- ++++ ++++ ----
---- ++++ +
让我们说+
意味着分配和-
免费。
我正在寻找如何计算碎片百分比的公式。
背景
我正在为具有静态内存的嵌入式设备实现一个微小的动态内存管理。我的目标是拥有一些可以用来存储少量数据的东西。主要是通过无线连接传入的数据包,每个大约 128 字节。
想象一下,你有一些包含一堆字节的内存:
++++ ++-- ---+ +++-
-++- ++++ ++++ ----
---- ++++ +
让我们说+
意味着分配和-
免费。
我正在寻找如何计算碎片百分比的公式。
背景
我正在为具有静态内存的嵌入式设备实现一个微小的动态内存管理。我的目标是拥有一些可以用来存储少量数据的东西。主要是通过无线连接传入的数据包,每个大约 128 字节。
正如 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%。
计算当前内存布局可以容纳多少个 128 字节数据包。让这个数字n。
计算在内存布局中可以容纳多少个 128 字节数据包,分配的字节数与当前分配的字节数相同,但没有空洞(例如,将所有 + 移到左侧)。让这个数字N。
您的“碎片率”将是 alpha = n/N
如果您的分配大小都大致相同,只需将您的内存分成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
非常糟糕(无法分配任何对象)。
如果你有 [++++++--------++++--++-++++++++--------+++++] 并且你想测量可用空间的碎片(或任何其他分配)您可以测量平均连续块大小总块/连续块计数。
在这种情况下,它将是 4/(5 + 2 + 1 + 8) / 4 = 4