如何计算碎片？
想象一下，您有一些内存包含一堆字节：
++++ ++-- ---+ +++-
-++- ++++ ++++ ----
---- ++++ +
让我们说 + 表示已分配，- 表示空闲。
我正在寻找如何计算碎片百分比的公式。
背景
我正在为具有静态内存的嵌入式设备实现小型动态内存管理。我的目标是拥有可以用来存储少量数据的东西。大多数是通过无线连接传入的数据包，每个数据包大约 128 字节。
Imagine you have some memory containing a bunch of bytes:
++++ ++-- ---+ +++-
-++- ++++ ++++ ----
---- ++++ +
Let us say + means allocated and - means free.
I'm searching for the formula of how to calculate the percentage of fragmentation.
Background
I'm implementing a tiny dynamic memory management for an embedded device with static memory. My goal is to have something I can use for storing small amounts of data. Mostly incoming packets over a wireless connection, at about 128 Bytes each.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
正如 R. 所说，这完全取决于您所说的“碎片百分比”的含义 - 但您可以使用一个简单的公式：
其中
这样，如果所有内存都在一个大块中，则碎片为 0%，并且如果内存全部被分割成数百个小块，就会接近100%。
As R. says, it depends exactly what you mean by "percentage of fragmentation" - but one simple formula you could use would be:
where
That way, if all memory is in one big block, the fragmentation is 0%, and if memory is all carved up into hundreds of tiny blocks, it will be close to 100%.
计算当前内存布局可以容纳多少个 128 字节数据包。
设该数字为n。
计算在内存布局中可以容纳多少个 128 字节数据包，该内存布局具有与当前分配的字节数相同的字节数，但没有空洞（例如，将所有 + 移至左侧）。
设该数字为 N。
您的“碎片率”将为 alpha = n/N
Calculate how many 128 bytes packets you could fit in the current memory layout.
Let be that number n.
Calculate how many 128 bytes packets you could fit in a memory layout with the same number of bytes allocated than the current one, but with no holes (that is, move all the + to the left for example).
Let be that number N.
Your "fragmentation ratio" would be alpha = n/N
如果您的分配大小大致相同，只需将内存分成
TOTAL/MAXSIZE块，每个块由MAXSIZE字节组成。那么碎片化就无关紧要了。一般来说，回答你的问题，“碎片”没有神奇的数字。您必须评估不同函数在反映内存碎片程度方面的优点。这是我推荐的一个，作为大小 n 的函数：
请注意，log 只是将事物映射到“0 到无穷大”的范围；您不应该在实践中实际评估这一点。相反，您可以简单地评估：
1.0是理想的（能够分配最大可能数量的大小为n的对象），0.0非常糟糕（无法分配任何）。If your allocations are all roughly the same size, just split your memory up into
TOTAL/MAXSIZEpieces each consisting ofMAXSIZEbytes. Then fragmentation is irrelevant.To answer your question in general, there is no magic number for "fragmentation". You have to evaluate the merits of different functions in reflecting how fragmented memory is. Here is one I would recommend, as a function of a size
n:Note that the
logis just there to map things to a "0 to infinity" scale; you should not actually evaluate that in practice. Instead you might simply evaluate:with
1.0being ideal (able to allocate the maximum possible number of objects of sizen) and0.0being very bad (unable to allocate any).如果您有 [++++++-----++++--++-++++++++--------+++++] 并且您想要测量可用空间（或任何其他分配）的碎片
您可以测量平均连续块大小
总块数/连续块数。
在这种情况下，它将是
4/(5 + 2 + 1 + 8) / 4 = 4
If you had [++++++-----++++--++-++++++++--------+++++] and you wanted to measure the fragmentation of the free space (or any other allocation)
You could measure the average contiguous block size
Total blocks / Count of contiguous blocks.
In this case it would be
4/(5 + 2 + 1 + 8) / 4 = 4
基于 R.. GitHub STOP HELPING ICE 的回答，我想出了以下将碎片计算为单个百分比数字的方法:
其中：
n是空闲块的总数FreeSlots(i)表示可用空闲内存空间中可以容纳多少个i大小的插槽IdealFreeSlots(i)表示有多少i大小的插槽适合大小为n的完美未碎片内存。这是一个简单的计算：IdealFreeSlots(i) = Floor(n / i)。我是如何想出这个公式的：
我正在考虑如何组合所有
freespace_quality(i)值来获得单个碎片百分比，但我对此函数的结果不是很满意。即使在理想情况下，如果可用空间大小n不能被i整除，您也可能会得到freespace_quality(i) != 1。例如，如果n=10和i=3，则freespace_quality(3) = 9/10 = 0.9。因此，我创建了一个派生函数
freespace_relative_quality(i)，如下所示：< img src="https://i.sstatic.net/2qHVc.gif" alt="freespace_relative_quality(i) = freespace_quality(i) / Ideal_freespace_quality(i)">
这总是有输出
1在理想的“完全不碎片化”的场景中。计算后：
要得出最终碎片公式，现在剩下要做的就是计算所有
i值的平均自由空间质量（来自1到n），然后通过执行1 - 平均质量反转范围，这样 0 表示完全未碎片（最高质量），1 表示碎片最多（最低质量）。Based on R.. GitHub STOP HELPING ICE's answer, I came up with the following way of computing fragmentation as a single percentage number:
Where:
nis the total number of free blocksFreeSlots(i)means how manyi-sized slots you can fit in the available free memory spaceIdealFreeSlots(i)means how manyi-sized slots would fit in a perfectly unfragmented memory of sizen. This is a simple calculation:IdealFreeSlots(i) = floor(n / i).How I came up with this formula:
I was thinking about how I could combine all the
freespace_quality(i)values to get a single fragmentation percentage, but I wasn't very happy with the result of this function. Even in an ideal scenario, you could havefreespace_quality(i) != 1if the free space sizenis not divisible byi. For example, ifn=10andi=3,freespace_quality(3) = 9/10 = 0.9.So, I created a derived function
freespace_relative_quality(i)which looks like this:This would always have the output
1in the ideal "perfectly unfragmented" scenario.After doing the math:
All that's left to do now to get to the final fragmentation formula is to calculate the average freespace quality for all values of
i(from1ton), and then invert the range by doing1 - the average qualityso that 0 means completely unfragmented (maximum quality) and 1 means most fragmented (minimum quality).