1. 从一次内存分配翻车说起为什么连续分配没那么简单刚接触操作系统内存管理那会儿我以为连续内存分配就是把一整块内存切给进程用简单直接。直到有一次在模拟器里跑一个多进程场景系统频繁报内存不足可实际空闲内存明明还有一大截。排查了半天才发现问题出在外部碎片上——空闲内存被切得七零八落单个进程要的连续空间凑不出来系统只能干瞪眼。这件事让我意识到连续内存分配和非连续内存分配不是两个孤立的知识点而是一条演进路线上的两个阶段。前者简单但脆弱后者复杂但灵活。理解它们之间的取舍比死记概念重要得多。这篇文章会从实际场景出发把连续分配的四种放置策略、碎片问题的来龙去脉、分页与分段的底层逻辑、以及多级页表为什么必须存在一层层拆开讲清楚。适合正在学操作系统、准备面试、或者写模拟器时被内存管理卡住的人。读完之后你至少能做到看到一道内存分配题知道该用哪种策略写代码模拟时知道页表项该放什么字段面试被问到为什么需要多级页表能从头推导出来。2. 连续内存分配四种放置策略的实战取舍2.1 首次适应、最佳适应、最坏适应、邻近适应到底怎么选连续内存分配的核心思路很朴素每个进程占一块物理地址连续的内存区域操作系统维护一张空闲分区表或空闲分区链。当进程请求内存时从空闲区域里找一块够大的切出去。问题在于空闲区域往往不止一块选哪块这就引出了四种经典策略策略选择逻辑优点缺点首次适应从低地址开始选第一个够大的实现简单高地址大空闲块保留低地址碎片多查找开销随碎片增加最佳适应选能满足要求的最小空闲块理论上浪费最小产生大量微小碎片几乎无法再利用最坏适应选最大的空闲块切分剩余块仍可能可用大块很快被消耗光后续大请求无解邻近适应从上次结束位置继续找分配更均匀高地址大块也被破坏我实测过这四种策略在同一个请求序列下的表现。假设初始空闲块为 100KB、500KB、200KB、300KB、600KB请求序列是 212KB、417KB、112KB、426KB。首次适应212KB 放进 500KB剩 288KB417KB 放进 600KB剩 183KB112KB 放进 288KB剩 176KB426KB 找不到够大的块失败。最佳适应212KB 放进 300KB剩 88KB417KB 放进 500KB剩 83KB112KB 放进 200KB剩 88KB426KB 放进 600KB剩 174KB全部成功。这个对比很直观最佳适应在这个序列下反而表现最好因为它保留了 600KB 的大块给后面的大请求。但换个序列最佳适应就可能因为切出太多小碎片而崩盘。注意没有哪种策略永远最优。实际系统里首次适应和邻近适应用得最多因为实现开销低且碎片分布相对可控。最佳适应听起来美好但碎片回收时的合并逻辑如果写得不好反而会加速内存碎片化。2.2 碎片问题内部碎片和外部碎片的本质区别碎片分两种很多人容易搞混。外部碎片空闲内存总量够但不连续凑不出一块满足请求的连续区域。这是连续分配方案的固有缺陷。比如空闲块是 50KB、30KB、40KB进程要 100KB总量 120KB 够但没有一块连续的 100KB。内部碎片分配给进程的内存块比它实际需要的大多出来的部分浪费在分区内部。比如进程要 95KB系统按 2KB 对齐分配了 96KB那 1KB 就是内部碎片。分页机制里这种碎片很常见因为页大小固定。解决外部碎片有两条路一是紧凑把已分配的内存块挪到一起腾出连续空闲区。但紧凑需要动态重定位支持而且移动内存块的开销很大不是所有场景都能接受。二是非连续分配干脆允许进程的内存分散在多个不连续的物理块里从根上绕开连续性的约束。我个人的经验是如果系统对实时性要求高紧凑操作要慎用因为移动内存时进程必须暂停。非连续分配虽然增加了地址转换的开销但换来了内存利用率的提升现代通用操作系统基本都走这条路。2.3 动态分区分配的具体实现空闲分区链怎么维护连续分配的实际实现通常用空闲分区链。每个空闲块有一个节点头记录块大小和前后指针。分配时遍历链表找合适块回收时把相邻空闲块合并。合并逻辑是这里的关键。假设回收的块地址为addr大小为size需要检查前一个块是否空闲且结束地址等于addr后一个块是否空闲且起始地址等于addr size如果前一个块空闲合并后新块起始地址变为前块的起始地址大小累加。如果后一个块也空闲继续合并。这个逻辑写起来不复杂但边界条件容易出错尤其是链表头和链表尾的处理。// 空闲块结构示意 typedef struct FreeBlock { size_t start_addr; // 起始地址 size_t size; // 块大小 struct FreeBlock* prev; struct FreeBlock* next; } FreeBlock; // 回收时的合并逻辑简化版 void free_block(FreeBlock* block) { // 检查前向合并 if (block-prev block-prev-start_addr block-prev-size block-start_addr) { block-prev-size block-size; // 从链表移除 block保留 prev block block-prev; } // 检查后向合并 if (block-next block-start_addr block-size block-next-start_addr) { block-size block-next-size; // 从链表移除 next } }提示合并时一定要先检查前向再检查后向因为前向合并会改变当前块的起始地址影响后向合并的判断条件。这个顺序搞反了合并就会漏掉相邻块。3. 非连续分配的分页机制地址转换的每一步3.1 页表项里到底存了什么从逻辑地址到物理地址的完整映射分页的核心思想是把逻辑地址空间切成固定大小的页物理内存切成同样大小的页框页可以离散地装入任意空闲页框。地址转换靠页表完成每个进程一张页表页号到页框号的映射。逻辑地址结构是高位是页号P低位是页内偏移W。假设页大小为 4KB逻辑地址 32 位那么低 12 位是偏移高 20 位是页号。转换过程从逻辑地址中提取页号P和偏移W查页表找到第P项读出页框号F物理地址 F × 页大小 W页表项通常不止存页框号还包含一些控制位字段作用页框号物理块编号有效位该页是否在内存中访问位是否被访问过供置换算法参考修改位是否被写过决定换出时是否需要写回保护位读/写/执行权限我写模拟器时踩过一个坑页表项的有效位没初始化导致访问未加载的页时没有触发缺页异常程序直接读到了垃圾数据。后来养成习惯页表创建时所有有效位清零加载页时才置 1。3.2 页大小怎么定4KB不是随便选的页大小是分页系统里最关键的参数之一它直接影响内部碎片、页表大小和地址转换开销。页太小页表项数量暴增页表占用内存大地址转换时查表次数多。页太大内部碎片增加最后一页平均浪费半个页大小。假设页大小为S进程平均大小为P那么内部碎片期望值约为S/2。如果S 4KB平均每个进程浪费 2KB。如果S 64KB平均浪费 32KB对于大量小进程来说不可接受。页表大小 页表项数 × 每项大小 (逻辑地址空间 / 页大小) × 每项字节数。32 位地址空间、4KB 页、每项 4 字节页表大小 2^20 × 4B 4MB。每个进程 4MB 页表100 个进程就是 400MB光页表就吃掉大量内存。这就是为什么 4KB 成为事实标准它在页表大小和内部碎片之间取了一个平衡点。但 64 位系统下即使 4KB 页页表也会大到无法接受所以必须引入多级页表。3.3 快表TLB为什么地址转换不能每次都查内存分页带来一个严重问题每次访存需要两次内存访问一次查页表一次取数据。如果页表本身也在内存里性能直接减半。解决方案是快表也叫TLB是一块高速缓存存放最近使用的页表项。地址转换时先查 TLB命中则直接得到页框号不命中才查内存中的页表并把结果填入 TLB。TLB 命中率对性能影响极大。假设 TLB 查找耗时 10ns内存访问 100ns命中时10ns 100ns 110ns不命中时10ns 100ns查页表 100ns取数据 210ns如果命中率 98%平均访问时间 0.98 × 110 0.02 × 210 112ns。如果命中率降到 90%平均时间 0.9 × 110 0.1 × 210 120ns。命中率每降一点性能就掉一截。TLB 通常用相联存储器实现支持并行查找。它按内容寻址不是按地址所以查找速度快。但容量有限一般几十到几百项所以置换算法很重要常用 LRU。注意进程切换时 TLB 必须刷新或标记否则新进程可能用到旧进程的页表项导致地址转换错误。有些架构用 ASID地址空间标识符来区分不同进程的 TLB 项避免每次切换都全量刷新。4. 分段与段页式更贴近程序逻辑的划分方式4.1 分段为什么按逻辑单元切代码段、数据段、栈段的实际意义分页是物理层面的划分对用户透明一个函数可能被切到两页里。分段是逻辑层面的划分按程序的自然结构切主程序段、子程序段、数据段、栈段。每个段有段名和段号段内地址连续段间不要求连续。逻辑地址结构是段号S 段内偏移W。段表每项记录段基址和段长。地址转换时先查段表检查偏移是否越界然后基址加偏移得到物理地址。分段的好处很直观逻辑清晰代码段只读、数据段可读写、栈段可增长权限管理自然共享方便多个进程可以共享同一个代码段只要段表指向同一物理区域保护灵活段级保护越界检查在段表项里完成但分段也有外部碎片问题因为段大小不固定和连续分配一样会面临空闲区碎片化。4.2 段页式结合先分段再分页的地址转换流程段页式是两者的结合先把程序按逻辑分段每个段再分页。逻辑地址变成三段段号S 页号P 页内偏移W。地址转换需要三次访存查段表找到该段的页表起始地址查页表找到页框号访问物理内存取数据加上 TLB 后如果 TLB 命中可以跳过前两步。但 TLB 需要同时缓存段号和页号信息实现更复杂。段页式的优点是兼顾了逻辑清晰和内存利用率缺点是地址转换开销大、硬件支持复杂。实际系统里纯分段用得少纯分页和段页式更常见。x86 架构早期用段页式后来 64 位模式下段机制基本被弱化以分页为主。4.3 分段和分页的对比什么时候用哪种维度分页分段划分依据物理块大小固定逻辑单元大小可变对用户透明可见碎片类型内部碎片外部碎片地址空间一维二维段号偏移共享保护页级较粗段级较细典型用途通用内存管理逻辑模块划分我个人的判断标准如果系统追求内存利用率和管理简单选分页如果需要精细的逻辑保护和共享选分段两者都要就上段页式但要做好性能开销的心理准备。5. 多级页表64位系统下页表爆炸的解法5.1 一级页表在64位下为什么不可行32 位系统下4KB 页、4 字节页表项页表大小 4MB还能接受。64 位系统下逻辑地址空间是2^64即使只考虑实际使用的 48 位地址空间页表项数 2^48 / 2^12 2^36每项 8 字节页表大小 2^36 × 8B 512GB。每个进程 512GB 页表完全不现实。而且进程实际使用的地址空间往往很稀疏大部分页表项是空的。一级页表强制为整个地址空间分配连续页表浪费极其严重。5.2 二级页表怎么省内存外层页表按需分配二级页表把页号再切一刀外层页号 内层页号。外层页表指向内层页表内层页表指向页框。以 32 位地址、4KB 页为例页号 20 位切成 10 位外层 10 位内层。外层页表有2^10 1024项每项指向一个内层页表。内层页表也有 1024 项。关键点内层页表可以按需创建。如果进程只用了低地址的几 MB 空间只有对应的几个内层页表需要分配外层页表里其余项置空。这样页表占用从 4MB 降到几十 KB。地址转换变成外层页号查外层页表 → 得到内层页表地址 → 内层页号查内层页表 → 得到页框号 → 加偏移。多了一次访存但 TLB 命中时可以抵消。5.3 多级页表的访存次数和TLB的补偿作用二级页表不命中 TLB 时需要三次访存外层页表、内层页表、数据。三级页表四次四级页表五次。访存次数随级数线性增长。TLB 在这里的作用更加关键。如果 TLB 命中率高多级页表的额外开销几乎被完全掩盖。实测数据TLB 命中率 99% 时二级页表和一级页表的平均访存时间差距不到 5%。提示多级页表的级数不是越多越好。级数增加页表占用减少但访存次数增加。实际系统里32 位通常用二级64 位用四级如 x86-64 的 PML4 → PDPT → PD → PT。选择级数时要在页表内存开销和地址转换开销之间找平衡。5.4 反置页表另一种思路反置页表不走每个进程一张页表的路子而是整个系统一张页表每个物理页框对应一项记录哪个进程的哪个虚拟页占用了它。页表项数 物理页框数而不是虚拟页数。物理内存 4GB、页 4KB页框数 2^20页表项 100 万左右每项 8 字节总共 8MB。相比每个进程 512GB 的页表节省巨大。但反置页表的缺点是查找慢。给定虚拟页号需要搜索整张表找到对应项不能直接索引。通常用哈希表加速但哈希冲突又带来新问题。而且进程共享页时一项只能记录一个进程需要额外结构处理。反置页表在实际系统里用得不多但它的思路值得了解用物理页框数而不是虚拟页数来决定页表规模在虚拟地址空间远大于物理内存时很有优势。6. 写内存分配模拟器时踩过的坑6.1 碎片统计口径不一致导致的数据对不上第一次写模拟器时我统计外部碎片用的是空闲块中无法满足当前请求的块大小之和但回收时合并逻辑有 bug导致空闲块链表里存在相邻但未合并的块。结果碎片统计偏大和预期对不上。排查过程打印每次分配和回收后的空闲链表逐块对比地址和大小。发现两个相邻块[0x1000, 0x2000)和[0x2000, 0x3000)没有合并原因是回收时只检查了前向合并后向合并的条件写错了——用了block-start_addr block-size block-next-start_addr但block-size在合并前向块后已经变了导致后向判断失效。修复方案先保存原始块的起始地址和大小再做前向合并最后用保存的值做后向判断。或者调整顺序先做后向再做前向。6.2 页表项有效位没初始化引发的随机崩溃页表模拟里我用数组表示页表但创建时没有清零有效位。程序运行时访问某些页时有效位恰好是随机值 1系统以为页在内存里直接去读页框号结果页框号也是垃圾值访问了非法物理地址程序崩溃。这个 bug 的隐蔽性在于它不总是触发取决于内存分配时数组的初始内容。有时候跑十次才崩一次很难复现。修复方案页表创建时用memset清零或者显式遍历所有项置有效位为 0。加载页时再置 1。这个习惯后来一直保留任何位图结构创建时先清零。6.3 TLB模拟中命中率统计的偏差TLB 模拟时我用一个固定大小的数组加 LRU 置换。统计命中率时发现数值偏高和理论计算对不上。检查后发现我在 TLB 查找时如果命中没有更新 LRU 顺序导致某些项长期不被置换人为提高了命中率。修复每次命中后把该项移到 LRU 链表头部。不命中时从尾部淘汰新项插入头部。这样命中率统计才准确。提示TLB 模拟里LRU 的更新时机很关键。命中不更新等于用了 FIFO 策略命中率会失真。写模拟器时置换策略的每个细节都要和理论定义对齐否则统计数据没有参考价值。7. 面试和实际工作中怎么用这些知识7.1 常见面试题的推导思路面试问为什么需要多级页表不要直接背答案。从一级页表的大小算起64 位系统、4KB 页、8 字节页表项一级页表 512GB不可行。然后引出稀疏地址空间的特点说明大部分页表项是空的按需分配内层页表可以大幅节省。最后提 TLB 补偿访存开销。这个推导链条完整面试官能看出你是真理解。问分页和分段有什么区别从划分依据、碎片类型、地址空间维度、共享保护粒度四个角度对比每个角度给一个具体例子。比如共享保护分页共享以页为单位一个函数跨两页时共享麻烦分段共享以段为单位代码段整体共享更自然。问页面置换算法FIFO、LRU、Clock、OPT 要能说出各自优缺点和适用场景。FIFO 实现简单但可能置换常用页LRU 理论好但硬件实现开销大Clock 是 LRU 的近似实际系统常用OPT 是理论最优无法实现只做基准。7.2 实际系统调优中的内存管理视角实际工作中理解内存分配机制对性能调优很有帮助。比如发现程序频繁缺页可以检查是不是工作集太大超出了物理内存发现 TLB 命中率低可以调整数据结构让热点数据集中在少数页里发现内存碎片严重可以考虑用内存池预分配减少动态分配次数。大页Huge Page是另一个实用技巧。把页大小从 4KB 提到 2MB 或 1GB页表项数大幅减少TLB 覆盖范围扩大命中率提升。数据库和虚拟化场景里大页能带来明显的性能收益。但大页的内部碎片也更大适合内存占用大、对碎片不敏感的应用。我个人的经验内存管理知识不是背出来的是在排查问题和写模拟器的过程中慢慢内化的。每次遇到缺页异常、内存碎片、地址转换错误回头翻这些原理都会有新的理解。建议你也动手写一个简单的分页模拟器把页表、TLB、缺页处理都实现一遍比看十遍书都管用。