操作系统 - 内存管理

核心概念

虚拟内存(virtual memory)：应用程序面向虚拟内存编写，而不是物理地址，CPU 负责将虚拟地址翻译成物理地址。

虚拟内存设计的三个目标：

  1. 高效性：不能明显降低应用程序性能，不能过多占用物理内存
  2. 安全性：保证应用程序隔离
  3. 透明性：开发者无需考虑虚拟内存实现细节

虚拟地址与物理地址

物理地址与虚拟地址

  • 物理地址：物理内存的真实地址，CPU 通过总线发送物理地址请求读写内存。
  • 虚拟地址：以应用程序自身的数据和代码为参照形成的地址，应用程序使用虚拟地址访问内存中的数据和代码。
  • 地址翻译：CPU 将虚拟地址转换为物理地址的过程。

CPU 地址翻译

使用虚拟地址访问物理内存

  • MMU：内存管理单元（Memory Management Unit），属于 CPU 中的重要部件，负责将虚拟地址转换为物理地址。
  • TLB：转址旁路缓存（Translation Lookaside Buffer），属于 MMU 的部件，用于缓存经常访问的页表项。

分段与分页机制

  • 分段机制：操作系统以段（一段连续的物理区域）管理/分配物理内存
  • 相关概念：段表、段号、段内地址、段表基址寄存器

分段机制带来外部碎片，x86-64架构后普遍采用分页机制管理虚拟内存。

分段机制

  • 分页机制：将虚拟地址空间和物理内存划分为连续、等长的虚拟页，并在页表中存储虚拟页到物理页的映射关系
  • 相关概念：虚拟页号、页内偏移量、页表基地址寄存器

分页机制下，虚拟地址空间中的任意虚拟页可被映射到任意物理页，可有效避免外部碎片。

分页机制

基于分页的虚拟内存

AArch64 架构下的 4 级页表

AArch64 的常见设置：虚拟地址低 48 位参与地址翻译，页表级数为 4 级，虚拟页大小为 4KB，页表项 8 字节。

  • 63-48 位全部置 1 或 0，应用程序置 0。
  • 47-39 位，0 级页表索引（9 位）
  • 38-30 位，1 级页表索引（9 位）
  • 29-21 位，2 级页表索引（9 位）
  • 20-12 位，3 级页表索引（9 位）
  • 11-0 位，页内偏移量
  • 使用寄存器 TTBR0_EL1 或 TTBR1_EL1

AArch64 架构下的 4 级页表

TLB（Translation Lookaside Buffer, 转址旁路缓存）

TLB 中缓存了虚拟页号到物理页号的映射关系（可以看成键值对哈希表）。

TLB 结构

  • TLB 命中：查询的页表项在 TLB 中

CPU 核心中的 TLB 缓存项通常很少，若TLB已满，则根据硬件预定的策略替换某一页。
某些体系结构（MIPS, SPARC）允许软件在地址翻译过程中对 TLB 进行管理。

  • TLB 刷新：当进行页表切换时（应用程序切换），TLB 需要主动更新

AArch64 体系结构中，系统调用不需要刷新TLB，因为采用了两个基地址寄存器 TTBR0_EL1, TTBR1_EL1。
X86-64 体系中，只有一个页表基地址 CR3，操作系统将自己映射到应用程序页表中的高地址部分。
ASID（X86 称为 PCID，Process Context IDentifier）：OS 为不同的应用程序分配不同的 ASID 作为应用程序的身份标签（TTBR0_EL1 的高 16 位），切换页表的时候不再需要清空 TLB。

换页与缺页异常

  • 换页：物理内存不够时，OS 将若干物理页的内容写入到硬盘中，同时将应用程序的页表进行修改（记录到硬盘上的位置）。
  • 缺页异常：当访问的页表项对应的物理内存不存在时（在硬盘上），触发缺页异常。
  • 页面预取：发生换入操作时，预测哪些页会被访问，并将它们写入内存。
  • 缺页异常的判定：应用程序的虚拟地址空间被分成多个 VMA（Virtual Memory Area），当缺页异常发生时，OS 通过判定页 P 是否属于某个虚拟内存区域来区分该页的状态。

换页机制

页面替换策略

MIN/OPT 策略：优先选择未来不会再访问的页

物理页访问顺序323143542343
物理内存中
存放的物理页		3
-
-		3
2
-		3
2
-		3
2
1		3
2
4		3
2
4		5
2
4		5
2
4		5
2
4		3
2
4		3
2
4		3
2
4
缺页异常（共 6 次）是是否是是否是否否是否否

FIFO 策略：优先选择最先换入的页进行换出

物理页访问顺序323143542343
（该行为队列头部）
存储物理页号
的 FIFO 队列		3
-
-		3
2
-		3
2
-		3
2
1		2
1
4		1
4
3		4
3
5		4
3
5		3
5
2		3
5
2		5
2
4		2
4
3
缺页异常（共 9 次）是是否是是是是否是否是是

Second Chance 策略：对 FIFO 的改进

OS 维护一个先进先出队列记录换入物理内存的物理页，并为每个物理页号维护一个访问标志，如果访问的页号已经在队列中，则置访问标志位。
寻找换出页时，优先查找位于队头的页号，如果其标志位没有标记，换出该页，否则将该标志清零，并将该页号挪到队尾。

物理页访问顺序323143542343
（该行为队列头部）
存储物理页号
的 FIFO 队列		3
-
-		3
2
-		3*
2
-		3*
2
1		1
3
4		1
3*
4		3*
4
5		3*
4*
5		3
4
2		3*
4
2		3*
4*
2		3*
4*
2
缺页异常（共 6 次）是是否是是否是否是否否否

LRU 策略：优先选择最久未被访问的页

OS 维护一个链表，最久未访问的页放在链表头，最近访问的页在链表尾，每次访问 OS 将刚访问的内存页调整到链表尾，每次选择换出链表首端的页。

物理页访问顺序323143542343
（该行为链表首端）
越不常访问的页号
离首端越近		3
-
-		3
2
-		2
3
-		2
3
1		3
1
4		1
4
3		4
3
5		3
5
4		5
4
2		4
2
3		2
2
4		2
4
3
缺页异常（共 7 次）是是否是是否是否是是否否

MRU 策略：优先选择最近访问的内存页

时钟算法策略（与 Second Chance 类似）：将换入物理内存的页号排成一个时钟，针臂指向新换入内存的页号的最后一个，每个页设置一个访问标志位。

  1. 换页时，若当前页号的访问位没有设置，则替换该页。
  2. 如果已经被置上，则将该访问位清空，针臂下移。

工作集模型

  • 颠簸现象：页面在内存和外存间反复调换
  • 工作集：一个程序在[t−x,t][t-x,t] 时间内的内存页的集合
  • 工作集时钟算法：每间隔一段时间启动一个跟踪函数，检查每个页面（上次访问时间、访问位），访问位为 1，则将当前系统时间赋予该内存页的上次使用时间，访问位为 0，计算该页面的年龄若超过xx 则不再属于工作集。检查完一个页的状态后，工作集追踪函数将访问位设置为 0。