好友内存系统中的最坏情况外部碎片

Question

不幸的是，我无法找到任何免费可用的文本，并估计了（二进制）好友内存系统中的最坏情况（外部）碎片开销。我发现只有M（1 + lg2 m），没有任何证据。该表达式估计（？）保证分配总大小为M的内存的大小堆大小（m是最长的分配块）。 这个估计看起来太粗糙至少对于m = 2;证明也会很有趣。

我将是有关此事的任何解释或链接感谢。

Answer 1

这似乎是锻炼41电脑艺术的编程第1卷第2.5节所覆盖，由克努特。 Knuth的考虑尺寸1，2，... 2^k，其中分配的N个的总存储器的块 - 报价如下

我们可以通过感应日k证明通过这样分割块消耗的总存储从不超过KN;对于每次请求分割大小为2 ^（k + 1）的块后，我们在分割的2^k个块中至多使用kn位置，在非分割块中至多使用n个位置。所以我认为你可以看到这个，就好像你有一个内存分配器的块大小高达2 ^（k + 1），这产生了保证至多使用n（k + 1）通过使用至多n商店交付大小2 ^（K + 1）和用于更小的块延迟请求的块到感应魔法分配器，其可使用至多NK存储服务这些请求存储。如果你开始起飞（K + 1）N块池，神奇的分配从来不需要超过KN店多，所以分配的大小的块2 ^（K + 1）将始终至少有不变不分段的正店块来处理大小为2 ^（k + 1）的请求。