Linux 好友页框分配和释放
Linux Buddy page frames allocation and freeing
在使用指南阅读和理解 linux 内核时-
http://www.johnchukwuma.com/training/UnderstandingTheLinuxKernel3rdEdition.pdf
我想了解 Buddy 系统中有关页面分配和释放的一些内容。
The technique adopted by Linux to solve the external fragmentation
problem is based on the well-known buddy system algorithm. All free
page frames are grouped into 11 lists of blocks that contain groups of
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, and 1024 contiguous page
frames, respectively. [chapter 8.1.7]
这非常有意义，因为现在 Linux 可以快速处理分配请求，因为有不同的块大小准备好用于不同的块大小请求。
现在，假设系统启动，并且所有可用页面都是空闲的，并且如上所述分组到那 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++;
}
所以根据这个和我的场景，顺序 1 块（第一个分配的块）将与另一个顺序 1 块合并为顺序 2 的块，尽管两个顺序 1 块尚未从在分配阶段订购 2 个块。
这样，如果我继续分配然后释放单个块，系统很快就会达到所有内存块都是最大顺序的状态，这似乎效率不高。我本以为只有当这两个伙伴之前从一个更大的订单块中分离出来时，才会合并两个伙伴，这样会尽可能地保留初始默认状态，并且整个系统将保持高效。
我错过了什么吗？这段代码有可能是错误的吗？我不知道此代码提供的另一个优势吗？
当有大量最小订单块可用时，这种 初始 状态的假设可能有点可疑。如果我没记错的话，内存块的分配应该从查看最小（相同大小）的组开始，然后查看更高阶的组以找到空闲块。如果找到的块大于需要的块，它将被拆分，并更新相应的组。这不是很明显，但是当只有最高阶块可用时，整个过程可能会从初始状态开始。
我在文献中遇到的少数几个例子描绘了几乎相同的初始状态图。 eloquent 示例可以在维基百科上找到：https://en.wikipedia.org/wiki/Buddy_memory_allocation#In_practice。图表和描述阐明了典型情况。
总而言之，我找不到任何证据证明 "initial default state" 的假设。将较小的块从较大的块中分离出来会降低效率的想法是最模糊的，可能值得单独讨论。
编辑:
从内核的角度来看，initial 状态可能与您假设的进程看到的初始状态不同。比方说，系统启动，并且在某个时刻有一大块内存。但是，您的假设过程不会是唯一的，- 当然。在进程能够开始分配和释放任何内存块之前，内存分配可能会发生很大变化。可以肯定的是，内核，或者更确切地说，它的大部分子系统在初始化期间会请求大量不同大小的内存块，并且内核会在相当长的一段时间内拥有大量的内存块（也许，在整个过程中）正常运行时间）。因此，关键是当您的进程开始时，伙伴系统可能 "warmed up" 并且确实有足够的小块可用。但是，页面的 buddies（由您的进程获取）仍将由各种子系统拥有，并且一旦您的进程决定释放 its 页面，那些 好友 将不会被批准为准备合并，即摘录中的 page_is_buddy() 将产生错误。当然，如果您的进程确实成功地获取 existing 个空闲块而不拆分高阶块，则整个场景可能是正确的。
所以，重点是您对 初始 好友分布的假设可能不是 真实初始状态 。它只能是一个 "warmed up" 状态，你确实可能有小块 但是 他们的 伙伴 会很忙，因此会阻止所描述的无法控制合并的假设过程。
P.S。这是 page_is_buddy() 的 description 的用途。
在使用指南阅读和理解 linux 内核时- http://www.johnchukwuma.com/training/UnderstandingTheLinuxKernel3rdEdition.pdf
我想了解 Buddy 系统中有关页面分配和释放的一些内容。
The technique adopted by Linux to solve the external fragmentation problem is based on the well-known buddy system algorithm. All free page frames are grouped into 11 lists of blocks that contain groups of 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, and 1024 contiguous page frames, respectively. [chapter 8.1.7]
这非常有意义，因为现在 Linux 可以快速处理分配请求，因为有不同的块大小准备好用于不同的块大小请求。
现在，假设系统启动，并且所有可用页面都是空闲的，并且如上所述分组到那 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++;
}
所以根据这个和我的场景，顺序 1 块（第一个分配的块）将与另一个顺序 1 块合并为顺序 2 的块，尽管两个顺序 1 块尚未从在分配阶段订购 2 个块。
这样，如果我继续分配然后释放单个块，系统很快就会达到所有内存块都是最大顺序的状态，这似乎效率不高。我本以为只有当这两个伙伴之前从一个更大的订单块中分离出来时，才会合并两个伙伴，这样会尽可能地保留初始默认状态，并且整个系统将保持高效。
我错过了什么吗？这段代码有可能是错误的吗？我不知道此代码提供的另一个优势吗？
当有大量最小订单块可用时，这种 初始 状态的假设可能有点可疑。如果我没记错的话，内存块的分配应该从查看最小（相同大小）的组开始，然后查看更高阶的组以找到空闲块。如果找到的块大于需要的块，它将被拆分，并更新相应的组。这不是很明显，但是当只有最高阶块可用时，整个过程可能会从初始状态开始。
我在文献中遇到的少数几个例子描绘了几乎相同的初始状态图。 eloquent 示例可以在维基百科上找到：https://en.wikipedia.org/wiki/Buddy_memory_allocation#In_practice。图表和描述阐明了典型情况。
总而言之，我找不到任何证据证明 "initial default state" 的假设。将较小的块从较大的块中分离出来会降低效率的想法是最模糊的，可能值得单独讨论。
编辑:
从内核的角度来看，initial 状态可能与您假设的进程看到的初始状态不同。比方说，系统启动，并且在某个时刻有一大块内存。但是，您的假设过程不会是唯一的，- 当然。在进程能够开始分配和释放任何内存块之前，内存分配可能会发生很大变化。可以肯定的是，内核，或者更确切地说，它的大部分子系统在初始化期间会请求大量不同大小的内存块，并且内核会在相当长的一段时间内拥有大量的内存块（也许，在整个过程中）正常运行时间）。因此，关键是当您的进程开始时，伙伴系统可能 "warmed up" 并且确实有足够的小块可用。但是，页面的 buddies（由您的进程获取）仍将由各种子系统拥有，并且一旦您的进程决定释放 its 页面，那些 好友 将不会被批准为准备合并，即摘录中的 page_is_buddy() 将产生错误。当然，如果您的进程确实成功地获取 existing 个空闲块而不拆分高阶块，则整个场景可能是正确的。
所以，重点是您对 初始 好友分布的假设可能不是 真实初始状态 。它只能是一个 "warmed up" 状态，你确实可能有小块 但是 他们的 伙伴 会很忙，因此会阻止所描述的无法控制合并的假设过程。
P.S。这是 page_is_buddy() 的 description 的用途。