8

我对heapand感到困惑free list。我有几个问题，我对 malloc 在 C 中的工作方式有自己的理解。如果我错了，请纠正我。

  • 堆内存是否组织为数据块的链表（空闲列表）？
  • 堆内存和空闲列表有区别吗？

我对存储分配的理解（有待改进）：- 当我们调用 malloc 时，它会在堆中分配内存，它是通过从中选择合适大小的数据块来实现的free list，对吧？

当 malloc 返回某个内存块时，它会从空闲列表中删除，并且该内存块的物理地址会在页表中更新。

当内存被释放free()时，数据块被插入到空闲列表中，并且可能为了减少碎片，与相邻块结合，并且present页表条目中的位被清除。

所以整个堆是一个空闲列表（空闲块的链表）+分配的数据块。

这是存储分配的全面情况吗？

编辑：来自 Linux Kernel Development (Robert Love) Chapter on memory Management , Slab allocation

“一个空闲列表包含一个可用的、已分配的数据结构块。当代码需要一个数据结构的新实例时，它可以从空闲列表中抓取其中一个结构，而不是分配足够的内存并设置它用于数据结构。后来，当不再需要数据结构时，将其返回到空闲列表而不是释放。从这个意义上说，空闲列表充当对象缓存，缓存经常使用的对象类型。

空闲列表被称为“可用的、已分配的数据结构块”。

  • 当它在空闲列表中时，它是如何分配的？
  • 以及如何将一块内存返回到空闲列表_不_与释放该块相同？
  • 平板分配与存储分配有何不同
4

3 回答 3

8

malloc()与页表无关；它分配虚拟地址，内核负责跟踪页面实际存储在物理 RAM 或磁盘中的位置。

malloc()通过brk()系统调用与内核交互，系统调用要求内核为进程分配更多页面，或者将页面释放回内核。所以实际上有两个级别的内存分配：

  • 内核将页面分配给一个进程，使这些页面不能被其他进程使用。从内核的角度来看，页面可以位于任何地方，并且它们的位置由页表跟踪，但从进程的角度来看，它是一个连续的虚拟地址空间。操作的“程序中断”brk()是内核允许您访问的地址（因为它们对应于分配的页面）与如果您尝试访问它们将导致分段错误的地址之间的边界。
  • malloc()分配程序数据段的可变大小部分以供程序使用。当数据段的当前大小内没有足够的可用空间时，它brk()会从内核中获取更多的页面，从而使数据段更大。当它发现数据段末尾的一些空间未使用时，它会使用brk()将未使用的页面还给内核，使数据段更小。

请注意，即使在该进程中运行的程序实际上并未将页面用于任何事情，页面也可以（由内核）分配给进程。如果您free()的内存块位于数据段的中间，free()则无法使用的实现brk()来缩小数据段，因为在更高地址处还有其他分配的块。因此，从内核的角度来看，这些页面仍然分配给您的程序，即使从角度来看它们是“可用空间” malloc()。

您对空闲列表如何工作的描述对我来说听起来很正确，尽管我不是如何实现内存分配器的专家。但是您从 Robert Love 发表的引述听起来像是在谈论 Linux 内核中的内存分配，这与malloc()用户空间进程中的内存分配无关。这种免费列表的工作方式可能不同。

于 2012-04-12T01:40:25.990 回答
3

您要做的第一件事是区分内核分配和程序分配。就像@Wyzard 所说，malloc 使用 brk (sbrk 有时是 mmap) 从内核获取更多页面。我对 malloc 的理解非常好，但它跟踪你可能称之为竞技场的东西。它调解对内存的访问，并根据需要进行适当的系统调用来分配内存。

空闲列表是管理内存的一种方式。每次需要从内核获得更多内存时调用 mmap 或 brk 是缓慢且低效的。这两者都需要上下文切换到内核模式，并将分配数据结构来跟踪哪个进程拥有内存。用户级别的空闲列表是一种优化，不会不断地向内核请求和返回内存。用户程序的目标是完成它的工作，而不是等待内核完成它的工作。

现在回答您的其他问题：

  • 当它在空闲列表中时，它是如何分配的？

考虑空闲列表的另一种方式是缓存。程序会发出请求，内核会尝试按需而不是一次性完成。然而，当一个程序用完一块内存时，快速的方法不是把它返回给内核，而是把它放在一个安全的地方以便再次分配。特别是，空闲列表可以跟踪分配器可以从中提取的内存区域，但这样做的方式（具有内存保护）用户代码不能只是选择它并开始覆盖所有区域.

  • 将一块内存返回到空闲列表与释放该块有何不同？

如果我们假设真正释放一个块需要将其返回给内核并让它更新其内部页表，那么区别实际上在于控制底层物理页（或帧）的是什么。实际上，释放内存并将其返回给内核意味着现在内核可以从这些页面中提取，而将其返回到用户级别的空闲列表意味着程序的某些部分仍然控制着该内存。

  • 平板分配与存储分配有何不同？

这开始得到一些不同的领域（我不是很熟悉）。平板分配器是内核管理内存分配的一种方式。从我所见，slab 尝试将分配分组为不同的大小，并有一个页面池来满足这些请求。我相信常见的 x86 架构将允许分配从 16 字节到 4 MB 的 2 次幂的连续物理内存（尽管我在 64 位机器上）。我相信在这个级别有一些自由列表的概念，以及有效升级或降级分配大小以适应不同系统需求的方法。

另一方面，存储分配听起来像是确保硬盘上有空间。我实际上没有听说过这个词，所以我只能推测。

于 2012-04-12T02:25:49.130 回答
1

在这里，您指的是两个不同的分配器，

  1. Buddy系统分配器，用于将页面分配给Zone，使用free_list来存储空闲页面，分配它们，在释放之后，如果可能的话，将它们组合回一个更大的更高阶的连续页面大小。
  2. Slab 分配器，适用于已分配的数据结构，如 keme_cache、kmalloc 调用。

请参阅C 编程中的堆内存以获取堆。

对于用户空间中的 ac 程序，我们在 malloc 发生的 call_stack 中有堆内存。这由 _break 标记，当需要更多内存时由 sbrk() 推进。

在 Linux 内核中，每个进程都有 task_struct，它有自己的堆栈和指向它使用的页面列表的指针。

于 2016-10-04T07:34:17.743 回答