pm-manage-物理内存管理.md

[TOC]

物理内存管理

OS职责：分配物理内存资源

引入虚拟内存后，物理内存分配主要在以下四个场景出现：

1. 用户态应用程序触发on-demand paging（延迟映射）时
   • 此时内核需要分配物理内存页，映射到对应的虚拟页
2. 内核自己申请内存并使用时
   • 如用于内核自身的数据结构，通常通过 kmalloc() 完成
3. 内核申请用于设备的DMA缓存时
   • DMA缓存通常需要连续的物理页（一般而言设备没有页表，只能直接访问物理内存；因为MMU在CPU中，设备自己并没有MMU，也即无法进行地址翻译）
4. 发生换页（swapping）时（物理内存不够）
   • 通过磁盘来扩展物理内存的容量

• 应用调用malloc，如果不是立即映射，唯一改动的是VMA，虚拟地址对应的页表项没有发生变化，valid bit可能依然是0
• 如何找到物理页，就需要物理内存的管理！
  • alloc_page() 简单分配物理页面的实现
    • 分配时，通过bitmap查找空闲物理页，并在bitmap中标记非空闲
    • 回收时，在bitmap中，把对应的物理页标记成空闲

没有被使用 ≠ 没有被映射 （可能被内核映射）

物理内存分配需求：需要能够分配连续的4K物理页（如大页、场景-3DMA）

内存碎片（外部碎片与内部碎片）

物理内存分配器指标

1. 资源利用率
2. 分配性能

伙伴系统（buddy system）：以页为粒度的物理内存管理（最细的粒度就是一页 4K）

合适的大小是 16K，因此首先查找第2条（2^2）空闲链表，如果链表不为空， 则可以直接从链表头取出空闲块进行分配。但是，在这个例子中，该链表为空， 分配器就会依次向存储更大块的链表去查找。由于第 3 条链表不为空，分配器就从该链表头取出空闲块（32K）进行分裂操作，从而获得两个 16K 大小的 块，将其中一个用于服务请求（这里不再需要继续向下分裂），另一个依然作为空闲块插入到第 2 条链表中。若再接收到一个大小为 8K 的分配请求，分配器则会直接从第 1 条链表中取出空闲块服务请求。之后，继续接收到一个大小为 4K 的分配请求，分配器则会取出第 2 条链表中大小为 16K 的空闲块进行连续分裂，从而服务请求。释放块的过程与分配块的过程相反，分配器首先找到被释放的块的伙伴块，如果伙伴块处于非空闲状态，则将被释放的块直接插入对应大小的空闲链表中，即完成释放；如果伙伴块处于空闲状态，则将它们两个块进行合并，当成一个完整的块释放，并重复该过程。

如何定位伙伴块

高效地找到伙伴块

• 互为伙伴的两个块的物理地址仅有一位不同，而且块的大小决定是哪一位

例如：

• 块A（0-8K）和块B（8-16K）互为伙伴块

• 块A和B的物理地址分别是 0x0 和 0x2000

• 仅有第13位不同，块大小是8K（213）

• 分配物理页/连续物理页（2^n），直接映射物理页物理地址与虚拟地址
• 大大提升资源利用率，可以把外部碎片程度降低（不能保证完全没有！）

性能

分配 O(1)：在链表数组中直接找，找到就分配；否则需要split，复杂度会稍高一些

合并 O(logn)：最坏情况应该需要从底到顶

代码实现见PPT

映射与使用（细节及图见 2023.3.7 视频）

映射 ≠ 使用

• 用户态：物理内存一旦map了，一定被use；use了，不一定map了
• 内核态：物理内存map了，不一定use

一块物理内存可能有多个虚拟地址（映射了，但是没有真的使用！）

内核在任何时刻都能访问所有的memory（都映射了，但是有很多地方没有用）

triple fault：内核触发 page fault 嵌套三次之后就会 panic（人为规定）

SLAB/SLUB/SLOB**：**细粒度内存管理（内核自己数据结构等要内存的时候用，而不是用户态）

目标：快速分配小内存对象（内核中数据结构大小远小于4K，如VMA），为上层内核的 kmalloc() 接口提供实现

SLUB 分配器

**观察：**操作系统频繁分配的对象大小相对比较固定（make the common things fast）

思想：

• 从伙伴系统获得大块内存（可以是4K，8K等等，名为slab）
• 对每份大块内存进一步细分成固定大小的小块内存进行管理
• 块的大小通常是 2^n 个字节（一般来说，3 ⩽ n < 12）
• 也可为特定数据结构增加特殊大小的块，从而减小内部碎片（如经常分配60字节大小的数据结构，就增加60字节大小的块）

**设计：**不同字节大小的资源池（分不同大小如 32字节，64字节，128字节，......的池，每个池中有很多该大小的块）

• 只分配固定大小块

• 对于每个固定块大小，SLUB 分配器都会使用独立的内存资源池进行分配

• 采用 best fit 定位资源池

  • 从全部空闲内存块中找出能满足要求 且大小最小的空闲内存块

**初始化：**把从伙伴系统得到的大的连续物理页（4K或更大）划分成若干等份（slot）

**空闲链表（next_free）：**当分配时直接分配一个空闲slot

**如何区分是否空闲？**采用空闲链表（直接在 free 的内存块里面放指针 next_free，指向下一个空闲的块；刚好利用了空闲块的区域）

**分配：**分配N字节时，首先找到大小最合适的SLAB，取走Next_Free指向的第一个；释放时直接放回Next_Free后

释放：

释放时如何找到Next_Free？

SLAB大小是固定的，因此可以根据object地址计算SLAB起始地址

ADDR & ~(SLAB_SIZE-1)

上述方法在kfree(addr)接口下可行吗？

问题：没有size信息，无法判断addr是被slab分配的，还是伙伴系统分配的

解决方法：在物理页结构体中记录所属slab信息

新增SLAB：

当64字节slot的SLAB已经分配完怎么办？

再从伙伴系统分配一个SLAB（初始化成64字节的）

以前的64字节slot的SLAB有一些被释放掉，新分配的一边还没有用完，之后再malloc应该从哪分配？

• current：当前正在使用的SLAB在什么地方（分配内存时从此处分配）
• partial：指向Next_Slab链表（current所有都被分配完之后，对应SLAB会被挪到partial，partial会从里面选一个有被释放空间的SLAB挪到current；partial也都全满了就从buddy system要一个新的；partial里面某一个全是free的，就还给伙伴系统）

优势：

1.减少内部碎片（可根据开发需求额外增加特殊大小）

2.分配效率高（常数时间）：分配与释放的时间复杂度 O(1)

突破物理内存容量限制（换页）

换页 Swapping（mechanism）

• 换页的基本思想

  • 用磁盘作为物理内存的补充，且对上层应用透明
  • 应用对虚拟内存的使用，不受物理内存大小限制

• 如何实现

  • 磁盘上划分专门的Swap分区，或专门的Swap文件
  • 在处理缺页异常时，触发物理内存页的换入换出

导致缺页异常的三种可能

1. 访问非法虚拟地址【非法】
2. 按需分配（尚未分配真正的物理页）【合法】
3. 内存页数据被换出到磁盘上【合法】

OS如何区分？

• 利用VMA区分是否为合法虚拟地址（合法缺页异常）【1与2、3】

• 利用页表项内容区分是按需分配还是需要换入【2与3】

  • 通过页表项 PTE（64bit）
    • Valid bit：第一位为0，硬件知道是 page fault
    • 加一个 is_swap bit（是否是换页）
    • 后面放在磁盘中的地址（剩下62个bit）

应用进程地址空间中的虚拟页可能存在四种状态（应用进程访问某虚拟页时，操作系统会分别做什么）

1. 未分配（seg fault）
2. 已分配但尚未为其分配物理页（page fault，调用 alloc_page 从伙伴系统分配物理内存页）
3. 已分配且映射到物理页（直接访问）
4. 已分配但对应物理页被换出（换入，之后再访问）

何时进行换出操作

• 当用完所有物理页后，再按需换出

  • 回顾：alloc_page，通过伙伴系统进行内存分配
  • 问题：当内存资源紧张时，大部分物理页分配操作都需要触发换出，造成分配时延高

• 设立阈值，在空闲的物理页数量低于阈值时，操作系统择机（如系统空闲时） 换出部分页，直到空闲页数量超过阈值

  • Linux Watermark：高水位线、低水位线、 最小水位线

应用程序malloc之后，给它分配了多少内存？

没有分配！只有访问之后才会分配！！但是实际场景下可能会分配一些（接着估计就是memset等别的操作）

换页机制的代价

• 优势：突破物理内存容量限制
• 劣势：缺页异常+磁盘操作导致访问延迟增加

如何取得平衡？

• 预取机制 （Prefetching），预测接卸来进程要使用的页，提前换入；在缺页异常处理函数中，根据应用程序访存具有的空间本地性进行预取

换页策略（policy）：如何选择哪个页会被换出

• **OPT 最优策略：**优先换出未来最长时间内不会再访问的页面（先知，不可能实现，用于做性能对比的基准）

• **FIFO 策略（先进先出）：**操作系统维护一个队列用于记录换入内存的物理页号，每换入一个物理页就把其页号加到队尾，因此最先换进的物理页号总是处于队头位置

  • Belady’s Anomaly：FIFO 带来的问题，硬件资源（物理页数量）变多，某些情况下性能可能会变差！！

• Second Chance 策略（FIFO 策略的一种改进版本，多一条命）：为每一个物理页号维护一个访问标志位。如果访问的页面号已经处在队列中，则置上其访问标志位。换页时查看队头：1）无标志则换出；2）有标志则去除并放入队尾，继续寻找

  

• LRU 策略（踢走最不常用的）（很难实现）：OS维护一个链表，在每次内存访问后，OS把刚刚访问的内存页调整到链表尾端；每次都选择换出位于链表头部的页面

  

  缺点-1：对于特定的序列，效果可能非常差，如循环访问内存

  缺点-2：需要排序的内存页可能非常多，导致很高的额外负载

• 时钟算法策略（LRU 平替）：精准的LRU策略难以实现，时钟算法硬件友好

  • 物理页环形排列（类似时钟）
    • 为每个物理页维护一个访问位
    • 当物理页被访问时， 把访问位设成T
    • OS依次（如顺时针）查看每个页的“访问位”
      • 如果是T，则置成F
      • 如果是F，则驱逐该页
  • 每个物理页需要有一个“访问位”
    • MMU在页表项里面为虚拟页打上“访问位”
    • 回顾：页表项中的Access Flag
  • 实现（想要把物理页踢走，直接看物理地址）
    • OS在描述物理页的结构体里面记录页表项位置（如何根据物理页找到对应PTE？）
      • 当物理页被填写到某张页表中时，把页表项的位置记录在元数据中（在Linux中称为“反向映射”：reverse mapping）（是一个list，可能有很多PTE映射到对应物理页）
      • 根据物理页对应的页表项中的“访问位”判断是否驱逐
      • 驱逐某页时应该清空其对应的大部分页表项（例如共享内存）

替换策略评价标准

• 缺页发生的概率 （参照理想但不能实现的OPT策略）

• 策略本身的性能开销

  • 如何高效地记录物理页的使用情况？

    页表项中Access（CPU在读内存的时候写一次页表项PTE，即会写一次内存）/Dirty Bits

颠簸现象 Thrashing Problem

• 直接原因：过于频繁的缺页异常（物理内存总需求过大）（如果经常被使用的内存页被换走，会导致其频繁的刚换进又换出）

• 大部分 CPU 时间都被用来处理缺页异常

  • 等待缓慢的磁盘 I/O 操作
  • 仅剩小部分的时间用于执行真正有意义的工作

• 调度器造成问题加剧

  • 等待磁盘 I/O导致CPU利用率下降
  • 调度器载入更多的进程以期提高CPU利用率
  • 触发更多的缺页异常、进一步降低CPU利用率、导致连锁反应

工作集模型（有效避免Thrashing）

统计一段时间访问的内存都是哪些，猜测下一段时间也是用这一段内存；看这一块的使用频繁程度，换页的时候要么全部留下，要么一起换走

• 一个进程在时间t的工作集W(t, x)：
  • 其在时间段（t - x, t)内使用的内存页集合
  • 也被视为其在未来（下一个x时间内）会访问的页集合
  • 如果希望进程能够顺利进展，则需要将该集合保持在内存中
• 工作集模型：All-or-nothing
  • 进程工作集要么都在内存中，要么全都换出
  • 避免thrashing，提高系统整体性能表现