OS07 虚拟内存

虚拟内存1:地址翻译和虚拟内存

引入

• 复用CPU：调度，scheduling

• 复用内存：虚拟内存

• 复用磁盘和设备

• 进程/内核的工作状态完全由其内存中的数据和寄存器中的数据决定

• 不能让不同的线程同时使用同一片内存

• 阻止用户程序访问其他进程的内存、访问内核的内存

• 给不同内存页面赋予不同的权限

• k比特的地址可以访问2^k比特的地址空间

• 可能正常访存

• 可能导致I/O操作

• 可能导致错误甚至终止

• 可能导致和其他程序通信

• 介入I/O：所有的I/O通过syscall实现

• 介入CPU使用：中断使得内核可以抢占线程

• 介入访存：
• 内核若介入每次访存，效率太低
• 翻译：在硬件层面给予支持
• 页错误：陷入内核态来处理、调页；不常发生

虚拟内存发展历程

虚拟内存2: 多级页表、cache和TLB

页表 Page Table

• 本质上是一个从虚拟地址到物理地址的映射（实际上是虚拟页号到物理页号，VPN-PPN）

• 两个设计指标：算得快、存得少

• 对于单级页表，由于只要访问一次页表项，时间开销低；但空间开销巨大

• 可能的优化方法：使用树实现多级页表；使用哈希表实现稀疏页表

多级页表

• 例如32比特虚拟地址，拆分成10+10+12bit，分别作为一级页表索引（P1）、二级页表索引（P2）、页偏移（VPO）

• 首先根据P1和PTBR（CR3 in x86）从一级页表中提取出页表项，查得对应二级页表的起始物理位置；再根据P2从二级页表中提取出页表项，查得PPN；最后PPN与VPO组合得PP

• 一张页表存放1024个页表项，每个页表项占用32bit（4byte），一张页表共4096B（4KB），刚好存放在一页里

• 页表项（PTE）除了存放20bit的物理地址（指向下一级页表或实际物理页），其他比特位还可以存放各种标志位，例如valid、read-only，read-write，write-only

• PTE无效时，可能对应的页表/页没有建立映射，或者是暂存在磁盘上。需要通过按需调页机制

• 需要额外的两次访存来进行地址翻译，但内存需求更低了。

• 页机制和段机制可以灵活组合，例如一级分段+二级分页

按需调页 Demand Paging

• 核心思想：只在内存上保留活跃的页；将不活跃或未被访问的页放在磁盘中，并标记相应的PTE的invalid

• 例如copy-on-write（COW）机制，当进程fork时，复制一份父进程的页表作为子进程的页表，并标记为read-only（COW），而不用进行任何页的复制。若子进程想要修改相应的页，触发页错误，进而复制一份页分配给子进程。

• 再如分配一张新的空白页时，可将对应PTE设置为invalid并指向磁盘的一块特殊的匿名（anonymous）页，其内容全为0

内存共享

• 两个进程共享一个物理页时，可将它们对应的二级页表项都指向同一个物理页。

• 若两个进程需要共享更大的物理内存，可将它们的一个一级页表项指向同一个二级页表

x86-64的页表

• 地址格式：48bit=9+9+9+9+12

• 每级页表存储2^9=512个页表项，每个页表项占用8字节，总共4KB，刚好占用一个页

1. 节省内存：仅需为实际使用的地址空间分配页表项，减少无效内存占用（对比单级页表）。方便实现稀疏的地址空间。

2. 灵活扩展：支持大地址空间（如64位系统），通过分级避免线性页表的爆炸式增长。未访问的页表层级可不驻留内存，降低初始化开销。

3. 方便共享：可以在页一级、也可以在段（segment）一级进行共享

1. 访问开销增加：每次地址翻译需多次访存（如4级页表需4次查表），可能引发TLB未命中惩罚。

2. 复杂度提升：需硬件（MMU）和操作系统协同管理多级结构，设计/调试更复杂。

3. 需要为每个页维护一个指针（物理内存指针）

4. 一张页表内的页表项需要连续存储。但通过将一张页表刚好放入一个页，可以解决此问题。

回忆：双模式 Dual-Mode

• 硬件层面支持至少两种模式：内核态和用户态。模式用控制寄存器中的一个比特维护。这个比特仅在内核模式下可访问。

• 因此，内核态容易切换到用户态；而用户程序必须要触发某种异常才能切换到内核态

• 事实上，x86架构有不止两个模式。模式也被称为“当前特权级别”（Current Privilege Level，CPL）

• 某些特定的操作只能在内核态下完成：
• 修改页表基指针（PTBR）
• 修改段描述符表（Segment Descriptor Table）
• 映射页表页

倒置页表 Inverted Page Table

动机

• 传统的页表（Page Table）采用进程视角，每个进程维护一张页表，记录其虚拟页号（VPN）到物理页框号（PFN）的映射。这种方式存在两个主要问题：
• 空间开销大：每个进程的页表需要存储所有虚拟页的映射，即使许多页未被使用。
• 多级页表复杂性：为减少内存占用，现代系统采用多级页表（如x86的4级页表），但增加了地址转换的开销。

• 在某些设备上，物理地址空间可能远小于虚拟地址空间；许多进程页表中维护的页可能都存放在磁盘中或者未被使用

倒置页表

• 倒置页表（IPT）是一种物理内存视角的页表设计，通过全局共享的哈希表来优化内存占用。

• 核心思想：仅维护一张全局页表，其条目数量等于物理内存的页框数（与虚拟地址空间大小无关）。每个条目记录：
• 进程ID（PID）：标识占用该物理页框的进程。
• 虚拟页号（VPN）：进程的虚拟页映射到当前物理页框。

• 结构示例：

物理页框号（PFN）	进程ID（PID）	虚拟页号（VPN）	其他标志位（如脏位、访问位等）
0	100	0x1234	R/W, Valid
1	101	0x5678	R, Valid

优缺点分析

• 内存高效：条目数仅与物理内存大小相关，与进程数量或虚拟地址空间无关。对使用64位虚拟地址空间的架构十分有用。

• 多进程共享：所有进程共享同一张表，减少重复存储。

• 查找速度慢：需遍历或哈希查找，比传统页表的直接索引更耗时（可通过TLB缓解）。尤其是翻译机制往往需要通过硬件实现，硬件开发成本高

• 共享内存处理复杂：多个进程共享同一物理页时，需额外机制（如反向映射）。

• 不能很好地利用缓存局部性。

总结：不同地址翻译机制的优缺点

翻译过程与MMU

• MMU（内存管理单元）需要在CPU每次取指/load/store时进行地址翻译

• 使用页表时，MMU依次进行：
• 按照PTBR从物理内存中读取页表项
• 检查页表项valid位
• 组合PPN与VPO
• 设置页表项的access标志位；store时设置dirty标志位
• （多级页表时还需要进行多次的读取、检查、更新）

• 实际上是进行了页表树的“周游”

• CPU — MMU - Caches - Physical Meomory

TLB

• 每次翻译过程均需（多次）查表，时间开销大，可以通过caching来降低平均开销

• 此即TLB（Translation Lookaside Buffer），也即快表，用于存储最近的翻译过程。实际上TLB是一个键值对，从VPN映射到PPN（及其页表项）

• MMU收到CPU的翻译请求时，首先在TLB中查询VPN，若查到则直接从TLB中读取并修改对应页表项即可。

• 由于页局部性（程序通常频繁地访问同一页或固定的几页），TLB可以发挥作用

缓存：未命中原因

• 强制性（Compulsory）未命中（冷启动，首次引用）：首次访问一个数据块。如果运行极多条指令，强制性未命中可以忽略不计

• 容量（Capacity）未命中：缓存无法包含程序访问的所有数据块。解决方案：增加缓存大小

• 冲突（Conflict）未命中（碰撞）：多个内存位置映射到同一个缓存位置，导致缓存抖动。解决方案：增加缓存大小；增加关联性。

• 一致性（Coherence）未命中（失效）：其他进程（例如，I/O）更新了内存

缓存：组织形式

• 地址在缓存中从高到低被切分为：Tag+Index+Offset。该地址所在的块只会被缓存在标号为Index的set中。一个set中存放的各个line，使用Tag来标识它们对应哪个具体的块

• 缓存映射机制（块可以被放入哪些line）：
• 直接映射：关联度E=1，一个set只包含一个line
• N路组相连映射：关联度E=N，一个set包含N个line
• 全相连映射：每个块都可以被映射到任意缓存line上。没有Index位。

• 替换策略（如何选择victim）：
• 随机替换
• LRU（Least recently used）替换

• 写机制（对缓存块写入会发生什么）：
• 写穿透（Write Through）：同时写入缓存中的块和主存中的块。优点：替换出缓存块时不会引发写主存；缺点：写入缓存时还要访问主存，CPU会被阻塞。
• 写回（Write Back）：只写入缓存中的块并设置dirty位。块要被替换出缓存时，若其dirty位为1，则写回主存。优点：写入缓存时不需要访问主存；缺点：实现更复杂

TLB应使用的缓存架构

• 动机：
• TLB是地址翻译中的关键路径，因此其需要做的足够小（128-512 entries）；
• 作为cache，其hit time与miss time的差距极大（hit时仅需几个时钟周期；miss时需多次访存（Page Table Traverse））
• 其至少需要支持对code、data、stack的访问，为了避免cache slashing（缓存抖动），需要尽可能高的相连度

• 架构：
• TLB比较小，约128-512个缓存行
• 使用全相连映射、LRU替换
• 不支持写入操作；当页表被修改时，应由操作系统将TLB中的对应条目设置为invalid

• 上下文切换时TLB应如何工作
• 朴素方法：上下文切换时，将所有TLB条目设置为invalid
• 更好方法：在TLB条目中加入PID部分；查找时同时使用VPN和PID作为唯一Tag；需要硬件支持

物理索引缓存 vs 虚拟索引缓存

物理索引缓存（Physically-Indexed Caches）

• 地址在转换后传递给缓存（即先查页表，再用物理地址访问缓存，缓存按物理地址组织）

• 页表存储物理地址

• 优点：：每个数据在缓存中仅有一个存储位置（避免别名问题）；上下文切换时无需刷新缓存

• 挑战：：TLB位于查找的关键路径上（可能导致延迟）

虚拟索引缓存（Virtually-Indexed Caches）

• 地址在转换前传递给缓存（即直接用虚拟地址访问缓存）

• 页表存储虚拟地址

• 优点：：TLB 不在查找的关键路径上，因此可能更快

• 挑战：：同一数据可能映射到缓存中的多个位置（别名问题）；上下文切换时可能需要刷新缓存

结论

TLB&cache的同时运行

• 地址的切分：
• VA=VPN+VPO，VPN=TLB Tag
• PA=PPN+PPO，PPO=VPO（Virtual Index Physical Tag，VIPT）
• 可以适当安排cache的配置（例如，令IndexBit+OffsetBit<=12），使cacheIndex可以直接从VPO中提取

• CPU给出访存的VA时，TLB和cache同时运作：
• TLB获取VPN，将其作为Tag查找对应的TLB条目，得到PPN
• cache获取VPO，从中获取Index，提取出对应set
• TLB将PPN传递给cache，cache将其作为Tag在set中查找条目

• 若TLB miss，MMU进行Page Table Traverse，多次查询页表得到PPN

• 若cache miss，直接将PPN和PPO组合成PA，从主存中访存

Page Fault

• 可能的原因：
• PTE中标记为invalid（未被分配/映射，或对应的Page在磁盘中）
• Privilege Level Violation（CPL过低的用户态执行内核指令、访问内核空间）
• Access Violation（空指针、野指针、已释放的内存、只读内存）
• PTE不存在
• PTE被标记为private-COW（Copy-On-Write）

• 对于两个violation，通常会直接中止程序并报错；对于其他选项，内核启动Page Fault Handler进行调页/swap/COW

PTE格式

页状态对应的PTE状态

不同状态下的 Page Fault 处理

页表项（PTE）各 Bit 位

一些标志位的细节

(1) Present (Bit 0)

• 触发 Page Fault：当 P=0 时，访问该页会触发缺页异常。

• 处理方式：
• 若页在磁盘（Swap/File），加载到内存后设置 P=1。
• 若页未分配，可能终止进程（非法访问）或分配新页。

(2) Dirty (Bit 6)

• 写回优化：若页被修改（D=1），换出时需写回磁盘；否则可直接丢弃。

(3) Accessed (Bit 5)

• 页面替换算法：操作系统通过 A 位统计活跃页（如 Clock 算法）。

(4) NX/XD (Bit 63)

• 安全防护：防止数据页（如栈、堆）被恶意执行（防范 Shellcode 攻击）。

虚拟内存3:按需调页

Demand Paging

• 程序被加载进内存时，通常只是设置对应的PTE为invalid，并将PTE的swap/disk位置1

• 程序真正访问内存时，MMU触发Page Fault陷入内核态，PF handler发现对应的页在磁盘中，从memory中选择一个替换页清除（若其dirty则要写入磁盘中），将磁盘中的页真正加载入内存，更新页表项，并return-from-trap重新执行访存指令

• 实际上可以视为一种caching机制：
• “memory”为磁盘；“cache”为内存
• block size为页的大小
• 配置：全相连映射；写回（write-back）
• 查找页：首先查询TLB，TLB miss则PT Traversal
• miss：从下一级存储结构（disk）中调页

• Transparent Level of Indirection（透明层）
• 支持物理数据的灵活存储位置：物理内存、磁盘甚至网络
• 对用户程序而言，访问数据的存储位置并不影响访问操作，只影响访问性能

Page Fault的用途

• 拓展堆或者栈时，触发page fault分配一个新的匿名（anonymous）页，映射到磁盘中的全0页

• 进程fork时，只需要复制页表并设置为COW；共享的只读页继续共享；父子进程需要写入时，触发COW

• 程序被加载进内存时，只需要设置页表而不用拷贝所有页（lazy paging）

Demand paging 的 Back Store 机制

1. Swap Space（交换空间）
• 存储匿名页（Anonymous Pages），如堆、栈等动态分配的内存。
• 通常是一个专用分区或文件（如 Linux 的 /swapfile）。

2. File-Backed Storage（文件后备存储）
• 存储映射文件（Memory-Mapped Files），如代码段、共享库。
• 直接关联到磁盘上的文件（如 libc.so）。

(1) 页面换出（Page Out）

1. 选择牺牲页：通过页面替换算法（如 LRU）选择待换出的页。

2. 写入磁盘：
• 匿名页（如使用过的堆栈）：写入 Swap Space。
• 文件映射页：若未被修改（Clean），直接丢弃；若已修改（Dirty），写回原文件。

3. 更新页表项（PTE）：
• 标记 Present=0，并记录磁盘位置（Swap Offset 或文件位置）。

(2) 页面换入（Page In）

1. 触发 Page Fault：MMU 发现 Present=0，CPU 陷入内核。

2. 检查 PTE：
• 若 PTE 指向 Swap Space，从交换区读取数据。
• 若 PTE 指向文件，从文件系统读取数据。

3. 加载到内存：
• 分配物理页帧，将数据从磁盘读入。
• 更新 PTE：Present=1，并关联物理页帧号（PFN）。

4. 恢复执行：重新执行触发 Page Fault 的指令。

Swap 管理

• Swap 分区 vs. Swap 文件：Swap在磁盘中的不同组织形式
• 分区：性能更高（连续磁盘空间），但需提前分配。
• 文件：灵活调整大小（如 Linux 的 swapon 命令）。

• Swap 映射策略：维护PTE中地址到对应swap在磁盘中的地址的映射
• 可直接存储对于swap分区的偏移量
• 可维护swap表，存储指向表中条目的指针
• 也可以使用类似倒置页表的哈希表方法

• 交换策略：
• 全局交换：所有进程共享 Swap 空间（可能引发抖动）。
• 局部交换：限制单个进程的 Swap 使用（如 cgroups）。

demand paging的性能评估

性能评估指标

• (1) Miss Rate影响因素：
• 工作集大小（Working Set Size）：若进程活跃页集超过物理内存容量，Miss Rate 急剧上升。
• 页面替换算法：LRU 通常优于 FIFO，但受访问模式影响。
• 预取（Preloading）：提前加载可能访问的页可降低 Compulsory Miss。

• (2) Miss Penalty优化方向：
• 使用更快的存储（如 SSD/NVMe 作为 Swap）。
• 减少磁盘寻道（如 Swap 分区连续分配）。

Cache Miss 在 Demand Paging 中

• Demand Paging 中的表现：
• 进程启动时加载代码/数据页。
• 访问新分配的堆/栈页。

• 解决方案：
• 预取（Preloading）：提前加载可能需要的页（如程序启动时预加载库文件）。
• 大页（Huge Pages）：减少缺页次数（但需权衡内存碎片）。

• Demand Paging 中的表现：
• 物理内存不足，频繁触发页面置换（如 vm.swappiness 过高时）。
• Thrashing（抖动）：极端情况下，系统忙于换页，实际吞吐量骤降。

• 解决方案：
• 增加物理内存。
• 优化工作集（如减少内存泄漏，调整进程优先级）。
• 使用更高效的置换算法（如 Clock 算法近似 LRU）。

• Demand Paging 中的表现：
• 较少见：Demand Paging 通常采用全相联（Fully-Associative）策略，无固定映射限制。

• Demand Paging 中的表现：
• 共享内存页被其他进程修改，需无效化本地 TLB/页表。
• 写时复制（COW）场景下，父/子进程分离共享页。

• 解决方案：
• TLB Shootdown：多核间同步 TLB 无效化。
• 原子操作：如 mmap 共享内存时使用 MAP_SHARED 标志。

核心优化方向

• 降低 Miss Rate → 优化工作集和预取。

• 减少 Miss Penalty → 加速磁盘 I/O 和并行化。

• 结合硬件特性 → 利用 SSD、PMem、ZRAM 等新技术。

虚拟内存4:按需调页的置换策略

demand paging的替换策略

• FIFO：换出最老的页。十分公平但效率不高，可能换出被频繁使用的页而不是被使用得少的页

• Random：随机换出一个页。硬件设计最简单、开销最小；难以对性能给出保证

• MIN：换出距离下一次访问最久的页。性能最好（可证明最理想），但难以准确预知未来（硬件开销大）

• LRU：换出距离上一次访问最久的页。由于局部性，性能较好（接近MIN？）可以通过链表实现，每次访问一个页时，从链表中移出并加在链表头部。但硬件实现开销大。

• 当N+1个虚拟页需要占N个页帧，且完全按序访问时，LRU策略每次reference都会造成Page Fault；但MIN表现好很多。

Stack-Property

• 当增加物理内存容量时，访存的miss-rate会下降

• LRU和MIN符合该性质，即：对于任意访存序列，物理内存容量增加时，miss-rate不增；平均而言，miss-rate降低

• FIFO不符合该性质；存在访存序列使得，物理内存容量增加时，miss-rate反而增加

LRU的实现

• 若实现严格的LRU，每次访存时需要遍历整个表找到对应的页，将其移出表并加到表头，时间开销太大

• 时钟算法（clock algorithm）：
• 首先将所有物理页围成一个环；维护一个时钟指针；
• 对每个物理页，在PTE中维护一个use bit（Intel架构称为access bit）；每次访问时都将access bit置为1；（不需要陷入内核软件，由硬件完成）
• 只有发生Page Fault时，陷入内核态由软件（PF handler）执行。时钟指针在物理页中移动，遇到use bit=1的物理页，说明最近访问过，将其bit置为0；遇到use bit=0的物理页，说明最近没有被访问过，则将其选为victim移出物理内存
• 这里的“最近”可以严格表示为时钟指针转一圈的时间。某页的use bit为0说明在指针转动一圈的这段时间内，该页没有被访问。

• 时钟算法的分析：
• 不考虑进入PF handler时发生中断，时钟算法总是能找到一个victim页（不会陷入死循环）；在非常极端的情况下（每次线程A的PF handler将一个物理页bit置0，就切换到线程B访问该物理页，将bit置1），可能陷入死循环
• 时钟转动的速度可以反映内存的空闲程度。转动越慢，要么是产生的PF很少，要么是有很多空闲的物理页，容易找到victim

• N次机会版本（Nth Chance Version of）时钟算法
• OS为每个物理页维护一个计数器
• 每次PF时，OS通过时钟指针的旋转，依次检查其他物理页。若use bit=1，重置use bit和计数器；若use bit=0，将计数器加一，如果计数器达到N，将其设为victim页
• 意味着OS选中物理页A作为victim，当且仅当在时钟转动N圈这一时间段内，A没有被访问。
• 考虑到dirty page的置换成本高，更希望将其留在物理内存中，因此dirty bit的N可以设的比较大。例如N设为2，当N=1时将其写回硬盘，N=2是替换出物理内存。
• N设置的越大，越接近理想化的LRU，但空间开销更大、选择victim页的时间越长。

• Second-Chance List Algorithm（VAX/VMS）
• 将所有物理页分成两类：Active List（标记为valid）和SC（Second Chance）list（标记为invalid），两个List均使用FIFO组织
• 页面刚从磁盘被载入内存时，进入Active List
• 对Active List中页的访问只在硬件层面上完成
• 对SC list中页的访问会触发PF，将该页移入Active list的队首，将Active List的队尾页移入SC list的队首。
• 对不在两个List中页的访问，新页进入Active List队首，将Active List的队尾页移入SC list的队首，从SC list队尾移出victim页
• SC list的容量恒定。若为0则是FIFO，若为无穷则LRU（但每次访存均为触发PF）
• 优点：更少访问硬盘，物理页只有在很长时间内不使用（在SC list中下沉到队尾）才会被换入硬盘。
• 缺点：增加了陷入内核的开销（更频繁陷入内核）

• Free List：将对SC list的填充移至后台。
• 维护一个Free List，PF时handler可直接从中取得victim页，加快了PF时的访存速度
• Free List通过时钟算法在后台填充（页换出守护进程，Pageout Daemon），页进入Free List时被标记为invalid，但未被重新分配；若页为Dirty则会预先写入磁盘。当Free List中的页被访问，触发PF，会被移出Free List。
• 优势：加快PF时访存速度；后台访问磁盘。

Reverse Page Mapping 反向页映射

• 动机：当OS选中一个victim页，要将其换入磁盘中，应快速找到该物理页对应的PTE并将其标记为无效。反向映射机制必须高效。

• 方案1:为每个物理页维护一个链表，存储所有指向它的PTE。存储开销大、链表操作影响性能

• 方案2:每个物理页只维护一个指针，指向一块地址空间（address space），一块地址空间中维护一棵红黑树，记录所有指向该空间文件的VMA（vm-area-struct）。回收页面时，先找到对应地址空间，再从红黑树中查询映射这个页的VMA，再找到对应的页表。粒度更粗（许多物理页共用一棵红黑树），减少开销。

页帧在进程间的分配

• 每个进程至少需要最低限度的页。

• 两种替换范围：当PF时需要选择物理页换入磁盘时：
• Global Replacement：victim页可以从所有进程的所有页中选取
• Local Replacement：只能从当前进程的页中选取

• Equal Allocation：每个进程都得到相同数量的物理页配额

• Proportional Allocation：根据进程的大小按比例分配

• Priority Allocation：为每个进程维护优先级，进程PF时victim页能从所有更低优先级的进程的页中选取。优先级或许可以根据PF rate动态调整。

• PF Frequency Allocation：设定一个PF rate的合理范围，PF更多的进程分配到更多页帧，PF更少的失去一些页帧。合理范围难以设定。

Thrashing 抖动

• 当进程没有足够的物理页空间时，会频繁地进行换入换出，而实际的进展缓慢，称为进程Thrashing

• 工作集Working Set：进程进展良好所需要的最少页面数。当实际物理页空间小于工作集时会发生Thrashing

• 可能的解决方案：将一些进程挂起并整个换出物理内存。降低总工作集大小，从而降低对物理页的需求

Compulsory Miss

• 强制性miss，当页面第一次被访问，或者进程开始运行后第一次被访问

• 降低Compulsory Miss：

• Clustering：PF时将需要换入的页周围的页也加载入内存。类似Prefetch。

• Working Set Tracking：使用算法追踪进程的工作集；当进程被换入执行时，将所有工作集也换入。