操作系统 | 内存管理之物理内存管理【思维导图版】

下面是程序锅在寒假期间根据《现代操作系统原理和实现》做的一个思维导图，完整、详细、清晰的文字版本后头会出，因为自己也想出整一套出来。

以下内容是由 XMind 根据上述思维导图的内容自动转换而来。

物理内存

分配与管理

• 目标

  • 内存资源利用率要高，减少资源浪费

    • 外部碎片（分段）
    • 内部碎片（分页）

  • 性能要好，尽可能降低分配延迟和节约 CPU 资源

• 伙伴系统-用于分配连续的物理内存页

  • 基本思想

    • 将物理内存划分为连续的块，以块作为基本单位进行分配。每个块都由一个或多个连续的物理页组成，每个块的物理页的数量必须是 2 的 n 次幂（0<=n<预设的最大值），预设的最大值一般根据实际由开发者指定。
    • 当一个请求需要分配 m 个物理页的时候，伙伴系统会寻找一个合适的块，该块包含 2^{n 个物理页，且满足 2}(n-1)<m<= 2^n。当不存在这么大的块的时候，大的块可以分裂成两半，分裂出来的两个块互为伙伴。分裂的出来块还可以继续分裂，直到得到一个大小合适的块去服务相应的分配请求。
    • 在一个块被释放后，分配器会找到其伙伴块，若伙伴块也处于空闲的状态，则将这两个伙伴块合并，形成一个大一号的伙空闲块。以此类推，可以继续向上合并。

  • 实现应用

    • 使用空闲链表数组来实现伙伴系统

  • 优缺点

    • 由于分裂和合并都是级联的，就是都是连续的物理页，所以可以很好地缓解外部碎片问题。
    • 确定一个伙伴块十分简单，互为伙伴的两个块的物理地址仅仅有一位不同，且该位由块的大小决定。比如块 A（0-8KB）和块B（8-16KB）互为伙伴块，块大小为 8KB，它们仅在 13 位不同。因此，伙伴系统能高效、有效地管理物理内存页。

• SLAB 分配器

  • Motivaion

    • 伙伴系统最小的分配单位是 4KB，但是大多数情况下，内核需要分配的内存大小通常是几十字节的或者几百字节的，如果使用伙伴系统会出现严重的内存碎片，导致内存资源利用率降低。

  • 发展

    • 20 世纪 90 年代，Solaris 2.4 内核中设计并实现了 SLAB 分配器。
    • 21 世纪初，内核开发人员发现 SLAB 存在一些问题，比如维护太多的队列、实现日趋复杂、存储开销增大。于是在 SLAB 分配器的基础上设计了 SLUB 分配器。

SLUB 分配器极大简化了 SLAB 分配器的设计和数据结构，在降低复杂度的同时依然能够提供与原来相当甚至更好的性能，同时也继承了 SLAB 分配器的接口。
- SLAB 分配器家族中，还有一种最简单的分配器称为 SLOB 分配器，主要是为了满足内存稀缺场景的需求，具有最小的存储开销，但在内存碎片处理上比不上 SLUB、SLAB 分配器。
- Linux 2.6.23 之后，SLUB 分配器成为 Linux 内核默认使用的分配器

- 基本思想

	- SLUB 分配器为了满足操作系统分配小对象的要求，其依赖于伙伴系统对物理页的分配。就是把伙伴系统分配的大块内存进一步细化成小块内存进行管理。
	- SLUB 只分配固定大小的内存块（这是因为内核分配的对象大小相对比较固定，也为了避免外部碎片），块的大小通常是 2^n 个字节（一般 3<=n<12）。
	- 对于每种块大小，SLUB 分配器都会使用独立的内存资源池进行分配，如图所示就是一种块大小对应的资源池。

SLUB 分配器会向伙伴系统申请一定大小的物理内存块，并将物理内存块作为一个 slab。slab 会被划分成等长的小块内存，内部的小块内存会被组织成空闲链表的形式。

一个内存资源池还有 current 和 partial 两个指针，current 仅指向一个 slab，所有的分配请求都将从这个指针指向的 slab 中获取空闲内存块。partial 指针指向由所有拥有空闲内存块的 slab 组成的链表。
- 当 SLUB 分配器接收到一个分配请求之后，SLUB 会先定位到能够满足请求大小且最接近的内存资源池（每个内存块大小都有一个内存资源池）。然后从 current 指向的 slab 中拿出一个空闲块返回即可。如果 current 指向的 slab 在取出一个空闲块之后，不再拥有空闲块了，则从 partial 指针指向的链表中取出一个 slab 交给 current 指针。如果 partial 指针指向的链表为空，那么 SLUB 分配器就会向伙伴系统申请分配新的物理内存块作为新的 slab。
- 当 SLUB 分配器收到一个释放请求之后，它将释放的块放入相应的 slab 空闲链表中。如果该 slab 原本已经没有空闲块了，也就是全部分配完了，那么会将这个 slab 添加到 partial 指向的链表中。如果该 slab 变成所有内存块都是空闲的，那么这个 slab 就可以被释放，还给伙伴系统。

- 优缺点

	- SLUB 的好处在于避免了外部碎片，并且分配速度很快。

• 其他基于不同空闲链表的内存分配方案（在用户态的内存分配器，比如对堆分配器中经常用到）

  • 隐式空闲链表

    • 链表里的每个元素代表了一块内存区域，空闲（白色）和非空闲（彩色）的内存块混杂在同一个链表里。每个内存块头部存储了关于该块是否空闲、块大小的信息。通过块大小可以定位到下一个块的位置。
    • 在分配空闲块的时候，分配器在这条链表上依此查询，找到第一块大小足够的空闲内存块。如果空闲内存块的大小不仅仅能够满足分配请求，还有足量剩余，则将该块进行分裂，一部分用于服务请求，剩余部分留作新的空闲块，从而缓解内存碎片问题。
    • 在释放内存块的时候，为了尽可能避免外部碎片的问题，分配器会检查该内存块紧邻的前后两个内存块是否空闲，如果有空闲块则合并。

  • 显式空闲链表

    • 显式空闲链表仅仅把空闲的内存块放在链表中。每个空闲块需要额外维护两个指针（prev 和 next）分别指向前后空闲块。
      不过分配器，只需要在空闲块中维护指针（已分配的不用了），因此可以复用该块的数据部分，从而不占用额外空间（就是不需要额外内存，直接用空闲块的）。
    • 分配和释放过程与隐式空闲链表类似。但是显式空闲链表在分配速度上更有优势，因为它的分配时间仅与空闲块数量成正相关，而隐式空闲链表的分配时间与所有块的数量成正相关。这个优势在内存使用率高的情况下更加明显。

  • 分离空闲链表

    • 在显式空闲链表的基础上构建。就是维护多条不同的显式空闲链表，每个链表服务固定范围大小的分配请求（和伙伴系统和 SLAB 分配器相似）。
    • 当分配内存块的时候，首先找到块大小对应的显式空闲链表，从中取出一个空闲块。若满足分配大小后有剩余，则将剩余部分插入相应大小的空闲链表。如果在块大小对应的显式链表中找不到合适的空闲块，就去找更大的块大小对应的链表。
    • 当释放块的时候，分配器依然可以采用单条显式空闲链表中的合并策略，然后将合并产生的空闲块插入对应大小的空闲链表中。
    • 相比普通的显式空闲链表，分离空闲链表可以获得更好的性能，一是分配空闲块所需时间变得很小，二是多条空闲链表可以更好地支持并发操作。

此外，分离空闲链表中采用 first-fit 即找到第一个空闲块即返回，能够近似地达到 best-fit 策略（最优策略，即找到大小最接近的空闲块）的内存利用率。如果分离空闲链表为每一种块大小都分配一条空闲链表，那么采用 first-fit 策略实际上也就是采用 best-fit 策略。

物理内存与CPU缓存-如何控制数据在 CPU 缓存中的位置（物理内存中的数据会根据物理地址以缓存行（cache line）为粒度放入 CPU 缓存中。但是在缓存满或者存在冲突的时候，冲突也就是不同物理页会被放到相同的缓存位置了。为了减少冲突，内核需要尽量分配不会造成缓存冲突的物理页，那么这样缓存中就可以存放更多物理页，从而利用缓存来提高性能）

• 软件方案：染色机制

  • 基本思想

    • 把能够存放到缓存中不同位置的物理页标记上不同的颜色，在为连续虚拟内存分配物理页的时候，优先选择不同颜色的物理页进行分配。这是因为连续的虚拟内存页通常可能会在短时间内被相继访问，分配不同颜色的物理页可以让被访问的数据都处于缓存中，不引起冲突。
    • 假设缓存可以放下 4 个连续的物理页，该地址则会把 1-4 的物理页染上四种不同的颜色，5-8 再染上与前面 4 个页一致的颜色。

  • 优缺点

    • 导致物理页的分配变得复杂，但如果能够明确地得知应用对内存的访问模式，则可以有效提高内存访问的性能，FreeBSD、Solaris 等操作系统就使用了这种机制。

• 硬件方案：Intel CAT（Cache Allocation Technology）

  • Motivaion

    • CPU 的最末级缓存（Last Level Cache，LLC）会被多个 CPU core 共享。由于多个 CPU core 可以同时运行不同的应用程序，这些应用程序会竞争 LLC，从而可能由于互相影响导致应用程序产生性能抖动，甚至造成系统整体性能的下降。

  • 基本思想

    • 允许操作系统设置应用程序所能使用的 LLC 大小和区域，从而实现 LLC 在不同应用程序间的隔离。

  • 具体

    • CAT 提供若干服务类（Class of Service，CLOS），每个 CLOS 有一个容量位掩码（Capacity Bitmask，CBM），标记着该 CLOS 所能使用的 LLC：CBM 中设置为 1 的位即 CLOS 能够使用 LLC。CAT 按照比例限制每个 CLOS 可以使用的 LLC，不同 CLOS 所对应的 LLC 既可以完全隔离的，也可以是部分重合的。
    • 通过设置特殊寄存器把应用程序划分到某个 CLOS 中。
    • 假设硬件支持 4 个 CLOS，每个 CLOS 有一个总长位 8 位的 CBM。

在容量大小上，CLOS-3 的应用程序由于 CBM 的所有位都为 1，所以能够使用全部的 LLC，而 CLOS-2 的应用程序由于仅有高 4 位被置为 1，故只能占用 50%的 LLC，剩下的 CLOS-0 和 CLOS-1 仅被分配到 25% 的 LLC。

在区域隔离上，CLOS-0 和 CLOS-1 由于不存在重叠位，所以使用的 LLC 是完全隔离的；CLOS-3 有 25% 的独占区域，剩下的区域可能被不同的 CLOS 竞争。

• 硬件方案：ARMv8-A MPAM（Memory System Resource Partitioning and Monitoring）

  • 基本思想

    • 与 CAT 类似，MPAM 支持配置多个分区 ID（Partition ID，PARTID），并且限制每个 PARTID 能够使用的缓存资源。内核把应用程序划分到某个 PARTID，从而限制该应用程序能够使用的缓存资源。

  • 具体（在限制每个 PARTID 所能使用的缓存资源的方式）

    • 缓存局部划分

      • MPAM 同样使用位图（bitmap）来按比例划分属于不同 PARTID 的可用缓存资源

    • 缓存最大容量划分

      • 通过配置 MPARCFG_CMAX 寄存器的值来设定一个 PARTID 所能使用的最大缓存资源比例。

    • 这两种划分方案可以结合使用，比如三组应用程序（对应三个 PARTID），用户通过局部划分使得组 A 独占 50% 的缓存资源，而剩下的两组共享剩余的 50%。但是为了保证剩下的两组不会造成过度的资源抢占，可以利用最大容量划分使得这两组应用程序均不能占用超过共享资源的 75%，也就是总缓存资源的 50%*75%=37.5%