操作系统内存管理 —— 虚拟内存

本篇面向已经了解以下概念的读者物理内存的分页管理什么是页框、页表、多级页表MMU 和 TLB 的基本工作原理进程地址空间的布局代码段、数据段、堆、栈如果你对这些还不太熟悉建议先翻阅《深入理解计算机系统》第9章或《现代操作系统》第3章再回来看本篇会更顺畅。为什么还要谈虚拟内存物理内存管理解决了“如何分配和回收物理页框”的问题但它有几个天生的局限碎片化即使有伙伴系统和 slab长期运行后仍可能出现外部碎片导致大块连续物理内存难以分配。进程隔离每个进程直接操作物理地址既不安全一个进程可以篡改另一个进程的数据也不灵活进程地址空间大小受限于物理内存。程序大小受限一个程序如果想运行其代码和数据必须全部加载到物理内存中否则无法执行。这在早期计算机中是一个严重瓶颈。虚拟内存正是为了解决这些问题而诞生的。它在进程和物理内存之间增加了一层抽象——虚拟地址空间让每个进程拥有独立的、连续的、大小远超物理内存的地址空间并通过按需调页和页面置换来高效利用有限的物理内存。1 基本概念1.1 传统存储管理方式特征和缺点在虚拟内存出现之前操作系统采用连续分配或非连续分配基本分页/分段​ 的方式来管理内存。这些方式有一个共同的假设一个作业必须全部装入内存才能开始运行并且一旦装入就一直驻留在内存中直到结束。传统的两种分配方式有两个根本性的问题一次性作用大小受限于物理内存容量。如果一个程序需要8GB才能运行而机器只有4GB那就无法运行——哪怕程序在实际执行中只访问了其中很小一部分代码和数据驻留性一旦作业被装入内存就会一直在内存中直至作业运行结束。这导致了严重的资源浪费——内存中有大量“冷数据”占据着宝贵的页框。面试视角传统方式的这两个缺点直接催生了虚拟内存的思想。面试官可能会问“为什么早期的操作系统不支持运行比物理内存大的程序”——答案就在“一次性”和“驻留性”上。1.2 局部性原理虚拟内存之所以可行是因为程序在执行上存在一种规律局部性原理时间局部性一条指令或者一个数据项被访问后不久很可能再次被访问。典型场景循环、递归、计数器变量空间局部性一个内存地址被访问后附近的地址也很快会被访问。典型场景数组遍历顺序执行的指令流基于局部性原理我们可以得出一个重要推论程序在任意时刻只需要访问其全部代码和数据的一小部分。也就是说没有必要把整个程序都放在内存里只要把当前正在使用的部分即“工作集”装入内存其余部分留在磁盘上用到时再调入即可。面试视角“虚拟内存的理论基础是什么”——答案是局部性原理。面试官还可能追问“如果没有局部性虚拟内存还能工作吗”——理论上可以但效率极低会频繁缺页导致系统陷入抖动。1.3 虚拟内存定义和特征虚拟内存是一种内存管理技术它将进程使用的逻辑地址与实际的物理地址分离使得每个进程都拥有一个连续的、私有的地址空间其大小可以远远超过物理内存的容量。具体来说基于局部性原理在程序装入时可以将程序中很快会用到的部分装入内存暂时用不到的部分留在外存就可以让程序执行程序执行过程中当所访问的信息不存在时由操作系统负责将所需信息从外存调入内存然后继续执行程序若内存空间不够由操作系统使用一些算法将暂时不用到的信息换出外存因此在用户看来似乎有一个比实际内存大的多的内存这就是虚拟内存虚拟内存有三个核心特征多次性无需在一次作业时一次性全部装入内存而是允许被分成多次调入内存对换性在作业运行时无需一直常驻在内存而是允许作业在运行过程中将作业换入换出虚拟性从逻辑上扩充了容量使用户看到的内存容量远大于实际的容量面试视角“虚拟内存的最大容量由什么决定”——由地址总线位数和外存容量共同决定。32 位系统最大虚拟地址空间为 4GB64 位系统理论上可达 256TB实际受硬件和操作系统限制。但如果磁盘空间不足即使地址空间足够也无法容纳那么多页面。1.4 如何实现虚拟内存技术虚拟内存的实现依赖于以下三个机制的协同工作请求分页或请求分段管理方式在基本分页的基础上增加了按需调页的能力。只有当程序访问到某个页面时才通过缺页中断将该页从磁盘加载到内存。这是虚拟内存的核心执行机制。页面置换算法当物理内存已满而又需要调入一个新页面时必须选择内存中的一个页面换出到磁盘。如何选择被换出的页面直接影响系统的缺页率和性能。常见的算法有 OPT、FIFO、LRU、CLOCK 等。页表机制扩展为了实现请求分页页表需要增加额外的标志位状态位标识该页是否已在内存中。访问位记录该页是否被访问过供置换算法参考。修改位记录该页是否被修改过脏页换出时是否需要写回磁盘。外存地址记录该页在磁盘上的存放位置。这三者的关系可以概括为一句话请求分页提供了“怎么调入”页面置换算法决定了“怎么换出”页表机制提供了“怎么知道页在哪”。后面的三章将逐一深入展开。面试视角“实现虚拟内存需要哪些硬件和软件支持”——硬件方面需要 MMU内存管理单元和 TLB软件方面需要请求分页的页表机制、缺页中断处理程序、页面置换算法以及磁盘 I/O 驱动。2 请求分页管理方式请求分页Demand Paging是实现虚拟内存的核心机制。它与基本分页管理的本质区别在于页面不是在进程创建时全部装入而是在实际访问时才通过缺页中断调入。本章围绕三个关键环节展开页表如何支持按需调页、缺页中断的处理流程、以及地址变换的全过程。2.1 页表机制基本分页的页表只需要记录页框号物理地址映射但请求分页的页表需要额外信息来支持按需调页和页面置换。每个页表项的结构如下字段作用页框号​该页对应的物理页框号仅在状态位为1时有效状态位存在位​标识该页是否在内存中。0表示不在内存需要从磁盘调入1表示在内存访问位引用位​记录该页是否被访问过用于页面置换算法如CLOCK判断使用频率修改位脏位​记录该页是否被修改过。如果为1换出时需要写回磁盘为0则可直接丢弃若磁盘副本未过期外存地址​该页在磁盘上的存放位置交换区或文件系统中的偏移量面试视角为什么需要修改位——如果页面未被修改换出时无需写回磁盘减少I/O开销。这也是CLOCK改进算法考虑修改位的原因。此外为了加速地址变换现代CPU引入了快表TLB。TLB是页表的高速缓存存储最近使用的页表项。请求分页下的TLB项也需要包含状态位等信息以便快速判断页面是否在内存。2.2 缺页中断机构缺页中断是请求分页的核心事件。当CPU试图访问一个页表项状态位为0的虚拟地址时MMU无法完成地址转换触发缺页异常Page Fault。这是一个内中断异常发生在指令执行期间并且可能在同一指令中多次发生例如跨页的指令。缺页中断的处理流程如下保护现场CPU保存当前进程的上下文程序计数器、寄存器等切换到内核态。查找外存根据页表中的外存地址确定所需页面在磁盘上的位置。分配页框在物理内存中寻找一个空闲页框。如果有空闲页框直接分配。如果没有空闲页框则调用页面置换算法选择一个牺牲页框将其换出若脏则写回磁盘。读入页面启动磁盘I/O将所需页面从磁盘读入刚分配的页框。此过程进程通常会阻塞等待I/O完成。更新页表修改页表项的状态位为1填入页框号清除访问位和修改位通常。恢复现场返回到用户态重新执行引发缺页的那条指令。注意事项缺页中断是可恢复的异常处理完成后会重新执行原指令而非下一条指令。缺页处理期间操作系统可能会调度其他进程运行因为磁盘I/O耗时较长以提高CPU利用率。面试视角“缺页中断和普通中断有什么区别”——缺页中断发生在指令执行期间而非指令结束后且同一指令可能触发多次缺页如访问跨页数据处理完成后需要重新执行原指令而非继续下一条。2.3 地址变换机构第一部分硬件地址变换流程CPU生成逻辑指令CPU执行指令计算出一个逻辑地址比如0x0804a100提取页号与页内偏移量MMU将逻辑地址分为页号P和页内偏移量W查询快表MMU首先在TLB快表中查询页号命中则直接获得对于的物理块号和权限位跳转到步骤8如果没有命中则进入步骤4查询页表页号P作为索引查找当前进程的页表其起始地址在页表寄存器PTBR中检查页表找到页表项后硬件检测其中的有效位/存在位如果为1表示该页已调入内存。页表项中存放的就是物理块号f。继续步骤6。如果为0表示该页未存在于内存中。需要硬件触发缺页中断CPU暂停当前进程转而向操作系统的缺页中断处理程序见第二部分更新页表TLB将页表查到的页号P物理块号f映射写入TLB方便下次快速访问形成物理地址将物理块号f与页内偏移W拼接得到物理地址。访问内存这个物理地址访问物理内存完成读/写操作。第二部分操作系统缺页中断处理流程保护现场硬件自动将当前进程的CPU状态程序计数器PC、寄存器等保存到内核栈。分析原因OS根据出错的逻辑地址解析出缺失的页号P并判断是否为非法访问例如访问不存在的页或权限不足。如果是非法访问则终止进程。寻址空闲页框OS试图在物理内存中找到一个空闲的物理页框。如果有则直接使用如果没有则需要页面置换算法选择内存中的页作为“牺牲页”将其换出页面换出如果需要置换检查牺牲页是否被修改过检查页表项中的修改位。如果修改位1说明该页被写过必须将其写回外存如果未0说明该页干净与磁盘一致则直接丢弃更新牺牲页的页表项将其“存在位”置为0页面换入。根据缺页页号POS从磁盘可执行文件或交换区中找到该页的数据将其读入到步骤3准备好的空闲页框中。这是一个耗时的I/O操作OS回将当前阻塞调度其他进程运行更新页表页读入完成后OS更新缺页的P的页表项物理块号设置为该空闲页框的号存在位置为1修改为置为0访问位置为1恢复并重启指令。OS将被阻塞的进程状态改为就绪。当该进程再次被调度时CPU从之前保存的现场恢复重新执行那条导致缺页的指令。这次执行硬件再次进行第一部分的地址变换。由于页已在内存TLB未命中后会查询页表此时存在位1于是成功得到物理地址指令得以完成。面试视角“为什么缺页处理后要重新执行指令而不是继续下一条”——因为引发缺页的指令还没有真正执行数据未读到必须重新执行才能完成预期的内存访问。这也意味着指令必须是“可重启的”设计CPU时要考虑这一点。请求分页通过扩展页表机制、引入缺页中断实现了“用到才加载”的按需调页。地址变换机构在TLB和慢表的配合下尽可能快地完成虚拟地址到物理地址的转换仅在缺页时才付出磁盘I/O的代价。下一章将讨论当物理内存不足时如何选择被换出的页面——即页面置换算法。3 页面置换算法3.1 最佳置换算法(OPT)思想置换在未来最长时间内不再被访问的页。是一种理想化思想无法实现但作为其他算法的benchmark操作当需要置换时查看当前内存中所有页面在未来访问序列的位置选择那个下一次访问距离当前最远的页面淘汰优点理论上缺页率最低缺点无法实现因为无法预知未来的页面访问序列作用作为性能比较的理论下届3.2 先进先出置换算法(FIFO)思想置换在内存中驻留时间最长的页面即最早进入内存的页面操作将内存中的页面按进入顺序链成一个队列。缺页时淘汰队首页面调入新页时新页加到队尾优点实现简单开销小缺点性能差与进程实际运行规律不符常访问的页面也可能被淘汰作用可能出现 Belady 异常即分配的物理块数增加时缺页率反而上升。这是FIFO独有的坏特性。3.3 最近最久未使用置换算法(LRU)思想置换最长时间没有被访问的页面。它基于“局部性原理”过去一段时间内未使用的页面在将来也可能不会使用。实现计数器/时间戳为每个页表项关联一个上次访问的时间戳。缺页时扫描所有页面选择时间戳最小的页面淘汰。开销大移位寄存器周期性将访问位右移并结合一个寄存器记录访问历史。精度较差。硬件栈理想化将访问的页号压入栈顶栈中始终保持按访问时间排序栈底即LRU页。硬件实现代价高。优点性能接近OPT是实际可用的最佳近似算法之一缺点真正的LRU需要硬件全力支持软件精确实现开销巨大3.4 时钟置换算法(CLOCK)思想LRU的低成本近似。它为每个页面设置一个访问位。当页面被访问时硬件将其访问位置1。操作系统周期性将所有访问位置0。置换时像时钟指针一样扫描页面寻找访问位为0的页面淘汰操作页面组织成一个环形链表一个“时钟指针”指向下一个候选页面。当需要置换时检查指针指向页面的访问位如果为 0则淘汰该页新页插入到此位置指针前进一步。如果为 1则将该位置 0给它一次机会指针前进一步继续检查下一个页面。改进型CLOCK考虑页面是否被修改过脏位淘汰顺序为1. (访问位0 修改位0) -2. (访问位0 修改位1) - 3. (访问位1 修改位0) - 4. (访问位1 修改位1)。优点开销小性能接近LRU是实际系统中广泛采用的算法如Linux的近似LRU4 页面分配策略前三章讨论了“页面如何调入”和“页面如何换出”但还有一个关键问题没有回答操作系统应该给每个进程分配多少个物理页框当发生缺页时应该从所有进程中选页换出还是只从缺页进程自身选​ 这就是页面分配策略要解决的问题。合理的分配策略能有效降低缺页率、防止系统性能下降抖动是多道程序环境下虚拟内存管理的关键。4.1 概念在讨论具体策略之前先明确几个核心术语驻留集Resident Set一个进程当前驻留在物理内存中的页面集合。驻留集的大小决定了该进程能同时使用的物理页框数。最小页框数保证进程正常运行所需的最少页框数。如果分配给进程的页框数少于这个值进程会因为频繁缺页而无法推进例如一条指令可能涉及多个跨页的操作数需要同时驻留多个页面。最小页框数由计算机体系结构决定如指令长度、寻址方式通常为 2~3 页。工作集Working Set进程在当前一段时间内频繁访问的页面集合。这个概念将在 4.5 节详细展开。面试视角“最小页框数和驻留集有什么区别”——最小页框数是保证进程能执行的下限由硬件决定驻留集是操作系统实际分配给进程的页框数可以动态调整但不能低于最小页框数。4.2 分配数量策略根据驻留集在进程生命周期内是否变化分配数量策略分为两类固定分配Fixed Allocation做法进程创建时分配固定数量的页框运行期间保持不变优点实现简单管理开销低缺点无法适应程序的阶段性变化。如果分配过多内存浪费分配过少缺页率高可能引发抖动适用场景早期简单系统或嵌入式环境可变分配Variable Allocation做法进程的驻留集大小随运行情况动态调整。缺页率高时增加分配内存紧张时减少分配优点更符合程序的局部性特征——程序在不同阶段的页面访问模式不同需要的内存页框数也不同缺点实现复杂需要监测缺页率并做出调整决策适用场景现代通用操作系统如 Linux、Windows面试视角“为什么可变分配优于固定分配”——程序的局部性是动态变化的例如循环阶段需要较多页框顺序执行阶段需要较少固定分配无法适应这种变化要么浪费要么不足。4.3 置换范围策略当发生缺页且内存无空闲页框时操作系统需要选择一个页面换出。这个选择范围决定了置换策略全局置换Global Replacement做法从整个系统的所有内存页面中选择一个换出不限于是缺页进程自身的页面。优点灵活性高系统可以根据整体负载动态调整内存分配。缺点一个进程的缺页可能导致其他进程的页面被换出造成进程间相互影响。极端情况下一个失控的进程可能“抢占”其他进程的内存导致系统不稳定。典型实现Linux 的页面回收机制kswapd本质上是一种全局置换。局部置换Local Replacement做法只从缺页进程自身的驻留集中选择一个页面换出。优点进程间隔离性好一个进程的缺页行为不会影响其他进程。缺点灵活性差。如果某个进程的驻留集过小它只能在自身有限的页面中反复换入换出无法借用其他进程的空闲内存。典型实现早期 Unix 系统的一些版本。面试视角“全局置换有什么潜在风险”——进程间相互影响可能导致一个进程“饿死”其他进程。例如一个内存泄漏的进程不断触发缺页持续从其他进程抢走页面导致系统整体性能下降。4.4 组合策略与对比将分配数量策略与置换范围策略组合可以得到四种可能的策略组合分配策略置换策略特点典型场景固定分配 局部置换固定局部最简单每个进程独立管理自己的页框互不影响嵌入式系统、早期 OS固定分配 全局置换固定全局矛盾组合页框数固定却允许全局置换不合理实践中罕见几乎不用可变分配 局部置换可变局部每个进程的驻留集可调但置换不出本进程范围需要操作系统持续监控并调整分配部分实时系统可变分配 全局置换可变全局最灵活也是最常用的策略。系统根据整体负载动态调整分配缺页时从全局选页换出现代通用 OSLinux、Windows为什么“可变分配 全局置换”成为主流系统可以动态平衡各进程的内存需求活跃进程的缺页率下降时可以保留更多页面不活跃进程的页面自然会被其他进程置换出去。全局置换配合工作集模型可以有效防止抖动见 4.5 节。潜在问题全局置换下如果不对进程的行为做任何限制一个高缺页率的进程可能会过度抢占内存。为此现代操作系统引入了页面老化机制和内存控制组memory cgroup​ 来限制单个进程的内存使用上限。面试视角“为什么固定分配 全局置换不合理”——固定分配意味着每个进程的页框数固定但全局置换允许从任何进程换出页面这会导致某个进程的页框数被动减少破坏了“固定”的承诺。4.5 抖动与工作集抖动Thrashing​ 是指系统中频繁发生缺页中断导致 CPU 大部分时间花费在页面换入换出上而非执行用户程序的现象。表现为CPU 利用率很低但磁盘 I/O 非常高。抖动成因抖动的根本原因是进程的驻留集小于其工作集。工作集Working Set是进程在当前一段时间内通常定义为窗口时间 Δ实际访问的页面集合。当驻留集大小小于工作集大小时进程在短时间内会反复缺页——刚换出一个页面马上又要访问它导致频繁的换入换出。举个例子一个进程在时间窗口 Δ 内需要访问页面 {A, B, C, D}工作集大小为 4但操作系统只给它分配了 3 个页框驻留集大小为 3。那么无论怎么置换总会有一个页面缺失导致进程不断缺页。如何检测抖动CPU 利用率下降由于大量时间等待磁盘 I/OCPU 空闲时间增加。磁盘 I/O 显著升高页面换入换出频繁。缺页率急剧上升可通过/proc/vmstat中的pgfault指标观察。防止抖动方法调整驻留集大小通过监测缺页率动态增加或减少进程的页框分配。缺页率高于阈值则增加分配低于阈值则回收多余页面。挂起部分进程当系统整体内存不足时选择挂起一个或多个进程将其所有页面换出释放内存给活跃进程。挂起的进程通常是优先级低或内存占用大的。工作集模型操作系统跟踪每个进程的工作集确保驻留集不小于工作集。但这需要硬件支持如引用位和定期采样实现成本较高。工作集模型由 Peter Denning 在 1968 年提出核心思想是定义一个滑动窗口 Δ如 10,000 次内存访问。统计当前窗口内访问过的页面集合即为工作集。操作系统确保每个进程的驻留集大小不低于其工作集大小。如果所有进程的工作集之和超过了物理内存总量则必须挂起部分进程。面试视角“抖动的本质是什么”——本质是进程的驻留集小于工作集导致缺页率超过临界值系统陷入“换页 → 执行一点点 → 又缺页”的死循环。面试官可能追问“如何确定工作集的大小”——通过采样页表的访问位在一个时间窗口内统计被访问的页面数。5 内存映射文件5.1 定义内存映射文件是指将一个磁盘文件或匿名内存区域的全部或部分内容映射到进程的虚拟地址空间中。映射完成后应用程序可以通过指针直接访问这段虚拟内存而无需显式调用read/write等系统调用。操作系统负责在背后完成数据的按需加载缺页时从磁盘读入和脏页的回写通过msync或内核自动刷新。在 Linux 中内存映射通过mmap系统调用实现void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);fd待映射文件的文件描述符若为 -1且指定 MAP_ANONYMOUS则为匿名映射用于分配大块内存prot保护权限PROT_READ、PROT_WRITE等flags映射类型MAP_SHARED表示对映射区的修改会写回文件MAP_PRIVATE表示写时复制修改不写回文件映射成功后mmap返回映射区域的起始虚拟地址。此后对该地址范围内的读写会触发缺页中断由内核自动从文件中读取相应页框面试视角“mmap返回后物理内存中立即有数据吗”——不一定。mmap只是建立了虚拟地址到文件的映射关系并未实际加载任何数据。只有当程序首次访问映射区域时才会触发缺页中断从磁盘读入相应的页面5.2 与传统IO对比传统文件 I/Oread/write与内存映射文件在数据路径上有本质区别传统I/O流程磁盘 → 内核缓冲区页缓存 → 用户缓冲区 → 应用程序用户调用read时数据先从磁盘读入内核的页缓存Page Cache再从页缓存拷贝到用户指定的缓冲区。这个过程涉及两次数据拷贝磁盘→内核内核→用户且上下文切换开销较大。写操作类似用户缓冲区 → 内核页缓存 → 磁盘延迟写内存映射文件的数据流磁盘 → 内核页缓存直接映射到用户地址空间 → 应用程序直接访问mmap将文件映射到进程地址空间内核页缓存中的页面直接映射到用户空间通过缺页机制。应用程序访问映射区域时直接操作内核页缓存无需额外的数据拷贝。写操作直接修改页缓存中的页面由内核在适当时机或用户调用 msync写回磁盘。维度传统 I/Oread/write内存映射文件mmap数据拷贝次数2 次磁盘→内核→用户0 次直接操作页缓存系统调用次数每次读写均需系统调用映射后无需系统调用缺页除外随机访问性能差每次随机读都需要系统调用拷贝好缺页后直接访问内存顺序读性能较好预读机制成熟可能因缺页抖动而略逊共享内存不支持需额外 IPC 机制支持MAP_SHARED多进程共享同一文件映射文件大小限制无特殊限制受虚拟地址空间大小限制32 位系统 4GB5.3 主要应用场景动态链接库/共享库加载.so/ .dll文件被映射到进程空间实现代码共享大型数据文件处理进程间通信通过映射同一个文件多个进程可以在共享的内存区域直接交换数据这是共享内存IPC的一种高效实现实现“零拷贝”网络服务器如Nginx可以用mmap将文件内容映射到内存然后直接用writev或splice等系统调用发送避免内核到用户空间的拷贝零拷贝机制传统的文件传输readwrite:4次内核/用户态切换4次拷贝零拷贝mmapwrite:4次内核/用户态切换3次拷贝零拷贝sendfile:2次内核/用户态切换3次拷贝零拷贝sendfileSG-DMA:2次内核/用户态切换2次拷贝