Appearance
虚拟内存与内存管理：分页、缺页、置换、TLB
考频 ⭐⭐⭐⭐⭐。后端 / 系统 / 基础架构 / 客户端岗必问。 主线：虚拟内存解决什么问题 → 地址怎么翻译 → 缺页怎么办 → 内存不够怎么换 → 碎片怎么治 →
malloc时到底发生了什么。 一句话：虚拟内存是操作系统最大的「善意的谎言」——它让每个进程都以为自己独占一大片连续内存。
一、为什么需要虚拟内存
三个动机（面试第一问，先答这三点）：
| 动机 | 说明 |
|---|---|
| 隔离与安全 | 每个进程有独立地址空间，A 进程无法读写 B 进程的内存；越界访问只影响自己 → 触发段错误。硬件靠 MMU + 页表 + 权限位保护。 |
| 突破物理内存限制 | 只把「当前用到的页」放进物理内存，其余放磁盘（swap）。进程可用的地址空间可以大于物理内存。 |
| 简化编程 / 链接 / 加载 / 共享 | 统一的虚拟地址视图，程序不关心物理位置；可执行文件按虚拟地址布局，加载时只做映射；同一份 libc 的物理页可被多个进程共享。 |
补充两点容易被追问的收益：
- 按需加载（lazy / demand paging）：程序没访问到的页根本不分配物理页，加快启动、节省内存。
- 共享内存 / 写时复制（COW）的基础：两个虚拟页映射到同一物理页，写时才复制，
fork的高效就靠它。
追问「没有虚拟内存会怎样？」→ 程序直接用物理地址：地址冲突、无法隔离、无法共享、内存小而碎片严重、安全灾难。
二、地址翻译：从虚拟地址到物理地址
Q1. 逻辑地址、虚拟地址、物理地址是什么关系？
答案
- 逻辑地址 / 虚拟地址：程序编译后看到的地址，也是 CPU 执行指令时使用的地址。现代系统两者基本等同（逻辑地址侧重「分段后的偏移」，虚拟地址侧重「分页前的地址」）。
- 物理地址：内存条上真正的地址。
- 翻译过程：CPU 发出虚拟地址 → MMU（Memory Management Unit，集成在 CPU 内）查页表 → 得到物理地址 → 访存。
text
虚拟地址 = [ 虚拟页号 VPN | 页内偏移 offset ]
物理地址 = [ 物理页框号 PFN | 页内偏移 offset ] ← offset 原样搬运页大小通常 4KB（2^12），因此 offset 占低 12 位，高位是 VPN。翻译只换页号，页内偏移不变，这也是「按页对齐」的根源。
Q2. 页表项（PTE）里都有哪些位？
答案
页表项记录「虚拟页 → 物理页框」的映射，外加若干控制位：
| 位 | 名称 | 作用 |
|---|---|---|
| 有效位 | Valid / Present | 该页是否在内存中（为 0 则是缺页，需从磁盘调入） |
| 保护位 | Protection / R-W-X | 只读 / 可写 / 可执行，实现权限检查 |
| 脏位 | Dirty | 页面是否被写过（决定换出时要不要写回磁盘） |
| 访问位 | Accessed / Reference | 页面是否被访问过（Clock、LRU 近似算法靠它） |
| 用户/内核位 | U/S | 用户态能否访问（防止用户访问内核页） |
| 页框号 | PFN | 物理页框号 |
另有 全局位 G（TLB 是否跨进程保留）、缓存禁用位 CD 等。
Q3. 为什么要用多级页表？
答案
结论：为了省空间、支持稀疏地址空间。
- 若单级页表：4GB 地址空间按 4KB 分页 = 2^20 个页，每项 4B → 4MB，且每个进程都要一整张，且必须连续存储。多数进程只用了很小一部分地址空间，浪费巨大。
- 多级页表：把页号再分层。x86-64 用 4 级（PML4 → PDPT → PD → PT），只有「用到的子表才存在」。未使用的巨大空洞不需要分配。
- 代价：多级页表 一次翻译要多次访存（4 级 = 4 次读页表 + 1 次读数据 = 5 次），所以必须靠 TLB 缓存来兜底，否则性能不可接受。
text
虚拟地址(x86-64, 4级) = [ PML4(9) | PDPT(9) | PD(9) | PT(9) | offset(12) ]追问「大页（Huge Page）为什么快？」→ 2MB/1GB 大页减少页表层级与 TLB 表项占用，翻译更快、miss 更少，适合大内存场景（如数据库、JVM）。
Q4. TLB 是什么？命中流程是怎样的？为什么要刷新？
答案
TLB（Translation Lookaside Buffer，快表）：MMU 内一块小容量、全相联/组相联的高速缓存，缓存最近的「VPN → PFN + 权限位」映射。命中常 1 个时钟周期，未命中要走上文的多级页表（几十到上百周期）。
命中流程：
- CPU 给出虚拟地址，拆分 VPN + offset；
- 查 TLB：命中 → 直接拿到 PFN（不访问页表），拼出物理地址；
- TLB 未命中（TLB miss）→ MMU 硬件走页表（page table walk）→ 得到 PFN → 填入 TLB；
- 若页表查到该页有效位为 0 → 触发缺页中断。
为什么上下文切换要刷新：TLB 里存的是「本进程的虚拟地址 → 物理地址」，进程切换后虚拟地址含义变了，旧条目会翻译到错误物理页，必须失效。两种做法：
- 简单粗暴：切换时
flush TLB（x86 早期），代价是切换后大量 miss； - 现代做法：ASID / PCID（地址空间标识），给 TLB 条目打进程标签，切换不必整体刷新，只切换当前 ASID。
三、分页 vs 分段 vs 段页式
Q5. 三者的区别与取舍？
答案
| 维度 | 分页 | 分段 | 段页式 |
|---|---|---|---|
| 划分依据 | 物理：固定大小（4KB） | 逻辑：按程序语义（代码段/数据段/栈） | 先分段，段内再分页 |
| 地址 | 一维（VPN + offset） | 二维（段号 + 段内偏移） | 段号 + 页号 + offset |
| 大小 | 固定 | 可变 | 固定页、可变段 |
| 碎片 | 内部碎片（页内最后不整） | 外部碎片（段间空洞难利用） | 内部碎片为主，无外部碎片 |
| 优点 | 无外部碎片、便于换页、对程序员不可见 | 逻辑清晰、便于共享和保护、动态增长 | 兼顾两者 |
| 缺点 | 页表开销、一次访问多次访存 | 外部碎片、段长受限 | 结构复杂、开销大 |
结论：现代通用 OS 以分页为主（对程序员透明），用「段」思想做权限和共享；x86-64 下分段基本被弱化，Linux 走平坦分页模型。
四、缺页中断（Page Fault）
Q6. 缺页中断的完整流程？
答案
结论：缺页 = 「页表有效位为 0」引发的一次陷入内核，由内核把页调入并更新页表，然后重执行那条指令。它与普通中断的关键区别是——缺页发生在指令执行过程中（是同步异常），返回后要重新执行同一条指令。
完整步骤：
- CPU 访存 → MMU 查页表 → 有效位为 0 → 触发缺页异常（Page Fault），陷入内核；
- 内核合法性检查：地址是否在该进程的合法 VMA（虚拟内存区域）内？不合法 → SIGSEGV（段错误），进程被杀；
- 合法但不在内存 → 找一个空闲物理页框（若无空闲 → 触发页面置换，可能写回脏页）；
- 调页：从磁盘 / swap / 可执行文件 / 零页 读入所需页（若是匿名页首次访问，直接映射一个清零页，即 COW / 零页）；
- 更新页表：填入 PFN，置有效位、权限位；同时可能要刷新 TLB；
- 返回用户态，重新执行触发缺页的那条指令，这次命中。
text
访存 → MMU查表 → 有效位0 → 缺页异常 → 内核
├─ 合法性检查失败 → SIGSEGV
└─ 合法 → 找空页/置换 → 磁盘读入 → 更新页表 → 重执行指令追问：缺页类型有「主缺页（major，需磁盘 IO，慢）」与「次缺页（minor，只在内存里建映射，如 COW、零页，快）」，/usr/bin/time -v 或 perf 能看到。
五、页面置换算法
内存满了、又发生缺页时，必须选一页换出。评价标准：缺页率最低。
Q7. OPT 与 FIFO？什么是 Belady 异常？
答案
- OPT（最优置换）：淘汰未来最长时间不再被访问的页。理论缺页率最低，但需要预知未来，无法实现，只作基准衡量其他算法。
- FIFO：淘汰最先进入内存的页。实现简单（一个队列），但性能差，且会出现 Belady 异常——物理页框增多，缺页反而增多。
- Belady 异常的根因：FIFO 不满足「栈算法（stack algorithm）」性质（页帧数 n 时驻留集不一定是 n+1 驻留集的子集），所以页框增加不保证缺页减少。LRU 和 OPT 是栈算法，不会出现 Belady 异常。
经典反例（访问串 1 2 3 4 1 2 5 1 2 3 4 5）：3 个页框缺页 9 次，4 个页框缺页 10 次。
Q8. LRU 怎么实现？如何做到 O(1)？
答案
LRU（Least Recently Used）：淘汰最久未被访问的页。基于「局部性原理」——最近用过的页，将来也更可能被用。
O(1) 实现：哈希表 + 双向链表。
- 哈希表：
key → 链表节点，O(1) 定位； - 双向链表：头部是「最近使用」，尾部是「最久未使用」；
- 每次访问
get：命中 → 把节点移到链表头；put：新插入到头部，超容量则删尾部； - 删除要能给到「双向」指针，才能 O(1) 摘除任意节点。
cpp
class LRUCache {
int cap;
std::list<std::pair<int,int>> lst; // front=MRU, back=LRU
std::unordered_map<int, std::list<std::pair<int,int>>::iterator> mp;
public:
int get(int k) {
auto it = mp.find(k);
if (it == mp.end()) return -1;
lst.splice(lst.begin(), lst, it->second); // O(1) 移到头部
return it->second->second;
}
void put(int k, int v) {
auto it = mp.find(k);
if (it != mp.end()) { it->second->second = v; lst.splice(lst.begin(), lst, it->second); return; }
if ((int)lst.size() == cap) { mp.erase(lst.back().first); lst.pop_back(); }
lst.emplace_front(k, v);
mp[k] = lst.begin();
}
};难点：LRU 需要每次访问都更新顺序，纯软件实现开销大——所以真实 OS 用近似 LRU（见 Q9）。
Q9. LFU、Clock（二次机会）、改进 Clock？
答案
- LFU（Least Frequently Used）：淘汰访问次数最少的页。问题：新页天生计数低，容易被误杀；且历史热点会「占位」，需定期衰减计数。LFU 可能实现成 LFU-Aging 防饿死。
- Clock（时钟 / 二次机会）：LRU 的近似。页表项有访问位 R。指针像钟表一样扫描：R=1 → 置 0 并跳过（给一次机会）；R=0 → 淘汰该页。只需一个环形队列 + 访问位，开销低。
- 改进 Clock：同时利用访问位 R 与脏位 D，优先淘汰「(R=0,D=0)」，再 (0,1)，再 (1,0)，最后 (1,1)，减少写回磁盘次数。（(R,D) = (0,0) 最该被换出，因为既没用过又不用写回。）
text
Clock 扫描：R=1 → 清零，跳过(二次机会)；R=0 → 淘汰Q10. 为什么实际系统用「近似 LRU」而不是精确 LRU？
答案
- 精确 LRU 要维护全局访问顺序，每次访存都要更新（移动链表节点、加锁），与硬件/多核、页表访问位机制不兼容，代价过高。
- 硬件只在页表项里提供 访问位，天然支持 Clock 这类「扫描式」近似，每页只需 1 bit。
- Linux 用双链表近似 LRU（active / inactive 两个 LRU 链表）：新页进 inactive 尾部；被访问的页提升到 active；定期把 active 头部「降级」回 inactive；淘汰发生时优先从 inactive 头部取。再用 PG_referenced 位做二次机会。
- 结论：用「访问位 + 扫描 + 分级链表」低开销逼近 LRU 效果，工程上够用。
六、抖动（Thrashing）、工作集与局部性
Q11. 什么是抖动？工作集模型怎么用？
答案
- 抖动（Thrashing）：分配给进程的物理页框太少，进程频繁缺页、频繁换入换出，CPU 大部分时间在等 IO，有效利用率暴跌。
- 局部性原理（Locality）：程序在一段时间内只集中访问一小部分页（时间局部性 + 空间局部性）。这是所有置换算法能生效的前提。
- 工作集模型（Working Set）：定义某时刻的工作集 = 「过去 Δ 时间窗口内被访问过的页集合」，大小记为 WSS。只要分配给进程的页框数 ≥ WSS，就基本不抖动。
- 对策：OS 监视缺页率，缺页率高就多给页框；页框不足则挂起（swap out）部分进程（降低多道程序度），把内存让给活跃进程。Linux 用
kswapd根据水位线回收。
追问「多道程序度 vs CPU 利用率」曲线：一开始道数增加利用率上升，超过平衡点后抖动，利用率断崖式下跌——所以不是并发越高越好。
七、内存碎片与分配器
Q12. 内部碎片 vs 外部碎片？伙伴系统、slab 分配器？
答案
- 内部碎片：分配给进程的内存内部用不完（如分页 4KB，只用了 1KB，剩 3KB 浪费）。分页产生内部碎片。
- 外部碎片：内存中存在足够总量、但不连续的空闲块，无法满足一个大请求。分段 / 早期堆分配产生外部碎片。
OS 物理内存分配：伙伴系统（Buddy System）
- 把内存按 2 的幂划分，分配时从合适大小块里不断对半劈，释放时看「伙伴块」是否也空闲，是则合并成更大块。
- 优点：合并快（伙伴地址可异或算出）、外部碎片可控（虽有内部碎片）。
- 缺点：对小块分配浪费大。
内核对象分配：slab 分配器（Slab / SLUB）
- 针对「频繁分配/释放同一类型小对象」的场景：预先从伙伴系统拿大页，切成固定大小的槽位（cache），对象释放后回收到 cache 复用，而不是还给伙伴系统。
- 好处：无外部碎片、构造快（对象内存常驻可复用）、对硬件缓存友好。
- Linux 的
kmalloc/slab是典型；用户态类似思想有 tcmalloc / jemalloc 的 thread cache。
八、malloc 如何分配内存
Q13. malloc 走 brk 还是 mmap？glibc 的 bin 机制？
答案
结论：小分配走堆（brk/sbrk），大分配走 mmap，分界阈值默认 128KB（M_MMAP_THRESHOLD）。
brk/sbrk：移动堆顶指针，扩展「堆」这一段；适合小、频繁的分配，递减时释放内存回系统。mmap(MAP_ANONYMOUS)：直接向内核映射一块匿名内存，free时munmap立即归还系统；适合大块分配（避免堆被撑大且难以回收）。
glibc ptmalloc 的空闲块管理（bins）：
| 结构 | 作用 |
|---|---|
| fastbin | 很小的块（默认 ≤ 64B，64 位系统），LIFO 单链表，不合并，分配释放极快 |
| small bin | 小于 512B 的块，按大小精确分组，双向循环链表，FIFO |
| large bin | 大于等于 512B 的块，按大小范围分组（组内排序），用于大块复用 |
| unsorted bin | 刚 free 的块先进这里，下次 malloc 先检索它，能命中就复用；再按需归入 small/large bin |
| top chunk | 堆顶剩余空间，都不满足时从 top 切分，或再向系统 brk/mmap 要内存 |
流程：malloc(n) → 先查 fastbin / small bin → 再看 unsorted bin（把能合并的合并、归位）→ 最后才向 top 切分或系统调用。free 时视大小放入 fastbin 或（尝试与相邻空闲块合并后）放 unsorted bin。
追问「为什么要区分 brk 和 mmap？」→ 小分配频繁，用 brk 减少系统调用；大分配用完能立刻 munmap 归还，避免堆碎片膨胀。可用
mallopt调整阈值。
九、内存不够了会怎样
Q14. 4GB 物理内存的机器申请 8GB 内存会成功吗？
答案
关键看是否真的读写——因为 Linux 默认超售（overcommit）。
malloc(8GB)可能立刻成功：因为malloc/mmap只是预留虚拟地址空间，并不分配物理页（按需分配）。返回的是虚拟地址，物理页在首次写入时才通过缺页中断分配。- 只有真正写入 8GB 时才会不断缺页、分配物理页；当物理内存 + swap 也扛不住 → 触发OOM，内核 OOM Killer 杀掉一个「oom_score」最高的进程（通常是内存占用大且不重要的）。
overcommit策略（/proc/sys/vm/overcommit_memory）：0启发式（默认，明显过度就拒）、1总是允许（超售）、2严格（不超过 CommitLimit，swap + 可超售比例 × RAM）。
区分两个概念：
| 概念 | 含义 |
|---|---|
| 虚拟内存（VSZ） | 进程申请的虚拟地址空间总量（含未使用的预留） |
| 驻留集（RSS） | 真正占用物理内存的页 |
追问「为什么 top 里 VSZ 远大于 RSS？」→ 就是超售 + 按需分配。数据库/JVM 会因此
malloc成功但一写就 OOM。
Q15. 物理内存真的满了，系统会发生什么？
答案
内核页回收机制按顺序应对：
- 回收干净的页：只读的文件页（page cache）可直接丢弃（数据在磁盘，需要时再读），代价最低。
- 写回脏页：脏的文件页先
writeback到磁盘，再回收。 - 换出匿名页到 swap：把进程的匿名页（堆/栈）写入 swap 分区，腾出物理页。
- 触发回收线程：
kswapd在达到低水位时开始后台回收；直接回收（direct reclaim）在紧急时同步进行。 - OOM Killer：实在回收不出内存，内核按
oom_score（结合进程 RSS、oom_score_adj、是否特权等）杀进程，先杀内存大户。可把关键进程的oom_score_adj设为-1000保护。
追问「swap 有什么用 / 该不该开？」→ swap 让「冷页」让位，避免过早 OOM；但若频繁换页则抖动。生产上常配小 swap + 监控 RSS。
十、高频 Q&A（快问快答）
Q16. 一次访存要几次内存访问？怎么优化？
答案
无 TLB 命中且 4 级页表：读 4 次页表 + 1 次数据 = 5 次。优化：TLB 命中降到 1 次，或大页减少层级与 TLB 压力。
Q17. 页表在哪里？也占用内存吗？
答案
页表由内核维护、放在物理内存里（每个进程一套），MMU 用 CR3 寄存器指向当前进程的顶级页表。TLB 只是它的缓存。
Q18. free 之后内存还给系统了吗？
答案
不一定。glibc 的 free 通常只把块放回 bin（用户态缓存） 复用，不还给内核；只有堆顶（top）超大或 mmap 的大块才会 brk 收缩 / munmap 真正归还。所以「free 后 RSS 不降」是正常的。