Linux Buddy 页框分配和释放

Question

在使用指南阅读和理解 linux 内核时- http://www.johnchukwuma.com/training/UnderstandingTheLinuxKernel3rdEdition.pdf

我想了解 Buddy 系统中有关页面分配和释放的一些内容。

The technique adopted by Linux to solve the external fragmentationproblem is based on the well-known buddy system algorithm. All freepage frames are grouped into 11 lists of blocks that contain groups of1, 2, 4, 8, 16, 32, 64, 128, 256, 512, and 1024 contiguous pageframes, respectively. [chapter 8.1.7]

这非常有意义，因为现在 Linux 可以快速处理分配请求，因为有不同的 block 大小准备好用于不同的 block 大小请求。

现在，假设系统启动，并且所有可用页面都是空闲的，并且如上所述分组到那 11 个组。现在让我们考虑一个场景，其中一个进程需要一个订单 1 的页面，然后释放它。根据免费算法-

while (order < 10)
{ 
     buddy_idx = page_idx ^ (1 << order);
     buddy = base + buddy_idx;
     if (!page_is_buddy(buddy, order))
         break;
     list_del(&buddy->lru);
     zone->free_area[order].nr_free--;
     ClearPagePrivate(buddy);
     buddy->private = 0;
     page_idx &= buddy_idx;
     order++;
 }

所以根据这个和我的场景，order 1 block (第一个分配的 block )将与另一个 order 1 block 合并为一个 order 2 block ，尽管这两个 order 1 block 还没有从 order 2 中分离出来 block 在分配阶段。

这样，如果我继续分配然后释放单个 block ，系统很快就会达到所有内存块都是最大顺序的状态，这似乎效率不高。我原以为只有当这两个伙伴之前从一个更大的订单 block 中分离出来时，才会合并两个伙伴，这样会尽可能多地保留初始默认状态，并使整个系统保持高效。

我错过了什么吗？这段代码有可能是错误的吗？我不知道此代码提供的另一个优势吗？

Answer 1

当有大量最小订单 block 可用时，这种初始状态的假设可能有点可疑。如果我没记错的话，内存块的分配应该从查看最小(相同大小)的组开始，然后查看更高阶的组以找到空闲 block 。如果找到的 block 大于需要的 block ，它将被拆分，并更新相应的组。这不是很明显，但是当只有最高阶 block 可用时，整个过程可能会从初始状态开始。

我在文献中遇到的一些例子描绘了几乎相同的初始状态图。可以在维基百科上找到一个 Eloquent 例子:https://en.wikipedia.org/wiki/Buddy_memory_allocation#In_practice .图表和描述阐明了典型情况。

总而言之，我找不到“初始默认状态”假设的任何证据。将较小的 block 从较大的 block 中分离出来会降低效率的想法是最模糊的，可能值得单独讨论。

编辑:

从内核的角度来看，初始 状态可能与您假设的进程看到的初始状态不同。比方说，系统启动，并且在某个时刻有一大块内存。但是，您的假设过程不会是唯一的，- 当然。在进程能够开始分配和释放任何内存块之前，内存分配可能会发生很大变化。。可以肯定的是，内核，或者更确切地说，它的大部分子系统在初始化期间会请求大量不同大小的内存块，并且内核会在相当长的一段时间内拥有大量的内存块(也许，在整个过程中)正常运行时间)。所以，重点是当您的进程开始时，伙伴系统可能会“预热”，并且确实有足够的小块可用。但是，页面的伙伴(由您的进程获取)仍将由各种子系统拥有，并且，一旦您的进程决定释放它的页面，那些< em>buddies 不会被批准为合并准备就绪，即摘录中的 page_is_buddy() 将产生 false。当然，如果您的进程确实成功地获取现有 空闲 block 而不拆分高阶 block ，则整个场景可能是正确的。

因此，重点是您对初始 好友分布的假设可能不是真实的初始状态。它可能只是一个“预热”状态，您确实可能有小块但是它们的伙伴会很忙，因此会阻止所描述的不可控合并的假设过程。

附言这是 description page_is_buddy() 的用途。