🧠 内存管理
地址转换 · 分页/分段/段页式 · 页面置换算法 · TLB快表
🗺️ 进程内存布局
从低地址到高地址：代码段 → 数据段 → 堆 → 共享库 → 栈
各段说明：
· 代码段（text）：存放程序机器指令，只读、可共享
· 数据段（data）：存放已初始化的全局变量和静态变量
· BSS段：未初始化的全局变量（初始化为0，不占磁盘空间）
· 堆（heap）：动态分配内存（malloc/new），向高地址增长
· 共享库：动态链接库映射区域
· 栈（stack）：函数调用栈帧，存放局部变量、返回地址，向低地址增长
⚡ 堆与栈的增长方向：堆↑（高地址）、栈↓（低地址），中间是"空洞"→ 可以动态扩大。
📥 装入与链接（程序执行的准备阶段）
程序从源代码到内存执行，经历编译→汇编→链接→装入四个阶段
📖 完整流程：
源代码（.c）→ 编译（编译器）→ 汇编代码（.s）→ 汇编（汇编器）→ 目标模块（.o）→ 链接（链接器）→ 装入模块（a.out/exe）→ 装入（加载器）→ 内存执行
① 绝对装入（Absolute Loading）
编译时就知道程序将驻留在内存的绝对地址，装入时直接放入该地址。
✅ 优点：简单、装入快
❌ 缺点：只适用于单道程序系统（内存地址固定）
② 可重定位装入（Relocation Loading）
装入时，对指令中的逻辑地址加上装入起始地址（重定位因子）。
✅ 优点：可以装入到内存的任何位置
❌ 缺点：装入后地址就固定了，不能再移动
③ 动态运行时链接（Dynamic Run-time Linking）
程序执行过程中需要某个模块时，才将它装入内存并链接。
✅ 优点：不用的模块不装入（节省内存）、易于更新（替换文件即可）
❌ 缺点：实现复杂（需要操作系统支持）
📝 408高频考点：
① "编译时重定位和装入时重定位的区别？" → 编译时：地址在编译阶段确定；装入时：地址在装入阶段确定（更灵活）
② "动态链接相比静态链接的优点？" → 节省内存（多个进程共享同一动态库）、易于更新
📦 连续分配管理（单一/固定/动态分区）
内存分为系统区（低地址）和用户区（高地址），用户区采用连续分配方式
📖 连续分配：每个进程占用内存中一块连续的区域。分为三种方式：
① 单一连续分配：内存只有一道用户程序（如DOS），简单但内存利用率极低
② 固定分区分配：把内存分成若干个大小固定的分区，每个分区放一个进程
③ 动态分区分配：分区大小不固定，根据进程需要动态分配（最常用）
动态分区分配算法（409-416页重点！）
① 首次适应（First Fit）：从低地址开始找，第一个足够大的空闲分区就分配
· 优点：简单、高地址保留大空闲块
· 缺点：低地址产生很多小碎片
② 最佳适应（Best Fit）：找大小最接近的空闲分区（需要把空闲区按大小排序）
· 优点：避免大材小用
· 缺点：产生很多难以利用的小碎片
③ 最坏适应（Worst Fit）：找最大的空闲分区（需要把空闲区按大小排序）
· 优点：产生碎片较小
· 缺点：大进程可能没有足够大的空闲区
④ 邻近适应（Next Fit）：从上次查找的结束位置开始找（不是每次都从低地址开始）
碎片问题（连续分配的最大缺点）
外部碎片（External Fragmentation）
所有空闲分区的总和足够，但没有一个单独的分区足够大。
解决方法：
· 紧凑（Compaction）：把已占用分区移到一起，腾出连续空间（需要动态重定位支持）
· 分区对换（Swapping）：把暂时不运行的进程换出到外存
内部碎片（Internal Fragmentation）
分配给进程的内存区域比进程实际需要的大，多出来的部分就叫内部碎片。
典型场景：固定分区分配（分区大小固定，进程不一定用得完）
⚡ 分页/分段可以解决碎片问题：分页无外部碎片但有内部碎片；分段无内部碎片但有外部碎片。
📝 408高频考点：
① "首次适应 vs 最佳适应 vs 最坏适应" → 记住它们各自的优缺点
② "紧凑技术需要什么支持？" → 需要动态重定位（地址可以动态修改）
③ "内部碎片 vs 外部碎片" → 内部：分配给进程但进程用不完；外部：所有空闲区总和够，但没有单独一个够大
🔢 分页地址转换
逻辑地址 = 页号 + 页内偏移 · 通过页表转换为物理地址
转换步骤：
1. 逻辑地址拆分为 页号p 和 页内偏移w（页大小2ⁿ，低n位为偏移）
2. 查页表：页号p → 内存块号f
3. 物理地址 = f × 页大小 + w
逻辑地址（十进制）：
（页大小=4KB）
页表（Page Table）：每个进程一张，存放在内存中。
逻辑页号是索引，通过页表映射到物理内存中的内存块号。
多级页表：32位系统，页大小4KB → 页号占20位 → 需要2²⁰个页表项 → 页表太大！
解决：把页表再分页（二级页表），顶级页表常驻内存。
| 页号p | 内存块号f | 有效位 |
|---|
| 0 | 5 | ✅ |
| 1 | 2 | ✅ |
| 2 | 8 | ✅ |
| 3 | — | ❌ 缺页 |
| 4 | 6 | ✅ |
| 5 | 3 | ✅ |
| 6 | — | ❌ 缺页 |
| 7 | 4 | ✅ |
📐 分段与段页式
分段按逻辑段划分 · 段页式结合两者优点
分段存储管理：
逻辑地址 = 段号s + 段内偏移w
通过段表：段号s → 段基址b + 段长l
物理地址 = b + w（需检查 0≤w<l，否则越界中断）
优点：方便共享（共享段只需一段）、方便保护
缺点：外部碎片（类似动态分区）
段页式存储管理：
先分段、每段内再分页。
逻辑地址 = 段号s + 段内页号p + 页内偏移w
地址转换需要两次查表：
1. 查段表 → 该段的页表起始地址
2. 查页表 → 内存块号f
3. 物理地址 = f×页大小 + w
优点：无外部碎片 + 方便共享/保护
⚡ TLB快表（地址转换高速缓存）
TLB命中率直接影响有效访问时间EAT
TLB（Translation Lookaside Buffer）：CPU内部的高速缓存，存放最近访问过的页表项（页号→内存块号的映射）。
访问内存耗时 ma（通常50~200ns），TLB查找耗时 ϵ（≈1ns）。
EAT = (1-h)×ma + h×ϵ + [(1-h)×(ma+ma)] + h×(ma)
简化（ϵ 可忽略）：EAT ≈ (2-h)×ma（其中h为命中率）
EAT = 105ns
🔄 页面置换算法
缺页中断时选择换出哪个页面 · 对比FIFO/LRU/OPT/Clock/LFU
🎭 虚拟内存（Virtual Memory）
让内存比实际大 —— 虚拟内存的核心思想
📖 什么是虚拟内存？
虚拟内存是指从逻辑上扩充内存容量的技术（用户感觉内存比实际大）。它利用局部性原理，把暂时不用的页面换出到外存，需要时再换入。
⚡ 局部性原理（408超高频考点！）：
· 时间局部性：最近访问过的指令/数据，很快会再次被访问（如循环、变量复用）
· 空间局部性：最近访问过的地址，其邻近的地址也会很快被访问（如数组、顺序执行）
虚拟内存的三大实现方式
① 请求分页（Demand Paging）：最常用，以页为单位换入换出
② 请求分段（Demand Segmentation）：以段为单位换入换出
③ 请求段页式：先按段换入，段内再按页换入
虚拟内存带来的好处
✅ 大程序可运行：程序可以比实际内存大（部分在内存，部分在外存）
✅ 内存利用率高：多个进程可以共享同一份代码（COP）
✅ 简化编程：程序员不需要考虑内存容量限制
📝 408综合题考点：
① "虚拟内存的容量由什么决定？" → 地址寄存器的位数（即CPU的寻址空间，如32位系统最多4GB虚拟内存）
② "虚拟内存需要什么硬件支持？" → 地址转换机构（页表/段表）+ 外存（存放换出的页面）
③ "虚拟内存一定比实际内存大吗？" → 是的，但受限于CPU寻址空间
🔃 请求分页流程（缺页中断处理）
当访问的页面不在内存时，触发缺页中断，OS负责换入页面
📖 请求分页 vs 纯分页：
· 纯分页（传统分页）：进程的所有页面在运行前必须全部装入内存
· 请求分页（虚拟内存）：进程运行时，只装入少部分页面，缺页时再动态装入
⚡ 缺页中断（Page Fault）：访问的页面不在内存时，触发一个特殊的中断（不是在指令执行完毕时检查，而是在指令执行期间检查）
缺页中断处理详细步骤（408标准答案版）
Step 1：CPU执行指令，访问逻辑地址，通过页表查询发现有效位=0（页面不在内存）→ 触发缺页中断
Step 2：OS保存当前进程的CPU上下文（陷入内核态）
Step 3：查找外存中的页面位置（通常在PCB或页表的辅存地址字段）
Step 4：如果内存有空闲页框 → 直接装入；否则调用页面置换算法换出一个页面（如果脏则写回外存）
Step 5：把所需页面从外存读入内存页框
Step 6：更新页表（有效位设为1，内存块号填入）
Step 7：恢复进程CPU上下文，重新执行那条触发缺页的指令（这次页面在内存了，访问成功！）
📝 考点："缺页中断和一般中断的区别？" → 缺页中断发生在指令执行期间（不是指令执行完毕），并且中断处理完后需要重新执行原指令（而一般中断处理完后执行下一条指令）。
🌪️ 工作集与抖动（Thrashing）
当缺页率太高时，CPU大部分时间都在换页，导致系统吞吐量骤降
📖 工作集（Working Set）：
某进程在某段时间Δ内，实际访问的页面集合。如果把这些页面都放在内存，进程就几乎不会缺页。
⚡ 工作集模型：OS统计每个进程的工作集，保证所有进程的工作集之和 ≤ 内存容量，这样就不会抖动。
抖动（Thrashing）现象
当缺页率过高时，CPU大量时间用于页面换入换出，几乎不执行用户程序。
原因：进程数太多，每个进程分到的页框数 < 工作集大小
现象：CPU利用率断崖式下跌，磁盘I/O爆满
防止抖动的方法
① 工作集模型：保证每个进程的工作集都在内存
② 缺页率反馈调整：缺页率高 → 增加页框分配；缺页率低 → 减少页框分配
③ Lettice-Nagle算法：限制并发I/O的进程数（防止所有人都来抢磁盘）
📝 408综合题考点：
① "什么是抖动？如何防止？" → 缺页率过高导致CPU利用率暴跌；防止方法：工作集模型、缺页率反馈调整
② "缺页率达到多少时需要增加内存分配？" → 通常缺页率 > 50% 就需要增加页框分配
③ "Belady异常（Belady's Anomaly）" → FIFO页面置换算法可能出现：分配页框越多，缺页率反而越高（LRU/OPT没有这个异常）
📦 页框分配策略（如何给进程分配内存？）
多道程序系统中，如何把有限的内存页框分配给多个进程？
📖 分配策略的核心矛盾：
给每个进程多分配页框 → 缺页率低，但能并发的进程数少
给每个进程少分配页框 → 能并发的进程数多，但缺页率高（容易抖动）
① 平均分配
把所有页框平均分配给各个进程。
❌ 缺点：忽略了进程大小的差异（大进程还是容易缺页）
② 按比例分配
按进程的大小比例分配页框（大进程分得多）。
✅ 优点：比平均分配更公平
③ 优先权分配
给重要进程多分配页框（如实时进程）。还可以设置保留页框（重要进程保留最低限度的页框，不会被全部换出）。
✅ 优点：保证关键进程的响应时间
LRU栈算法（计算不同页框数下的缺页次数）
思想：维护一个LRU栈（栈顶是最近访问的页号），当分配m个页框时，只需要看栈中前m个页面是否覆盖所有访问序列。
用法：对于给定的页面访问序列，建立LRU栈，然后对于任意页框数m，缺页次数 = 访问序列长度 - 不需要缺页的次数（即那些在栈中前m个位置的页面）。
📝 408计算题考点：给你一个页面访问序列，问"分配3个页框和4个页框，缺页次数分别是多少？" → 用LRU栈算法可以一次性算出所有m的缺页次数（不需要对每个m重新模拟）。
📝 408高频考点总结：
① "页框分配需要考虑哪些因素？" → 进程总页数、进程优先级、内存总量、工作集大小
② "什么是保留页框（Reservation）？" → 给重要进程保留最低限度的页框，防止被全部换出
③ "分配页框数 < 工作集大小时会发生什么？" → 抖动！