目录
1.请求分页存储管理概述
2.请求分页页表结构（新增字段）
3.缺页中断
4.请求分页地址变换流程与细节
5.五大页面置换算法（原理 + 例题 + 优缺点）
6.页面分配与置换策略
7.页面调入时机与来源
8.抖动（颠簸）与工作集、驻留集

一、请求分页存储管理概述
1.基本定位
请求分页是在基本分页存储管理基础上拓展而来的虚拟内存技术，核心目标：逻辑上扩充内存，让进程无需全部装入内存即可运行。

2. 两大核心新增功能
相较于基本分页，系统必须实现两个关键功能：

1. 请求调页：访问页面时，若页面不在内存（缺页），自动从外存将页面调入内存。
2. 页面置换：内存无空闲物理块时，按照算法选择内存中某个页面换出到外存，腾出空间给新页面。

3. 学习重点
全程对比基本分页存储管理，区分二者异同；重点掌握页表、缺页中断、地址变换、置换算法、分配策略。

二、请求分页的页表结构
1.基础组成
继承基本分页页表的原有字段（页号、物理块号），额外新增 4 个字段，用于支撑请求调页与页面置换。

2. 新增 4 个字段及作用

3. 补充说明
该页表也称为请求页表，是实现请求调页、页面置换的核心数据结构。

三、缺页中断
1.定义
进程访问逻辑页面时，查询页表发现状态位为 0（页面不在内存），硬件触发缺页中断，由操作系统中断处理程序完成调页。

2. 缺页中断完整处理流程
分为有空闲物理块、无空闲物理块两种场景：
场景 1：内存存在空闲物理块

1. 触发缺页中断，进程阻塞，进入阻塞队列；
2. 根据页表中外存地址，启动 I/O，将目标页面从外存调入空闲物理块；
3. 修改页表：状态位置 1、更新物理块号；
4. I/O 完成，唤醒进程，放回就绪队列，重新执行被中断的指令。

场景 2：内存无空闲物理块

1. 触发缺页中断，进程阻塞；
2. 执行页面置换算法，选择一个内存页面淘汰；
3. 判断被淘汰页面的修改位：
   ￮修改位 = 0：直接丢弃，无需写回外存；
   ￮修改位 = 1：启动 I/O，将页面写回外存；
4. 把当前所需页面调入刚腾出的物理块，更新对应页表项；
5. 唤醒进程，继续执行。

3. 缺页中断的分类与特性

1. 中断类型：属于内中断（异常），由当前执行指令触发，和当前进程强相关；
2. 内中断细分：属于故障，故障可由操作系统修复，修复后指令可重新执行；
3. 特殊点：一条指令执行过程中，可能产生多次缺页中断

例：一条拷贝指令同时访问两个不同页面，若两个页面都不在内存，会触发两次缺页。

4. 关键区分：缺页 ≠ 页面置换
•只要页面不在内存，就会缺页、触发缺页中断；
•只有内存物理块全部占满时，缺页才会伴随页面置换；
•内存有空闲块：只缺页、不置换。

四、请求分页 地址变换流程 & 细节
1.整体流程（对比基本分页，新增步骤标重点）

1. 检查页号是否越界，越界则终止进程；
2. 查询快表（TLB）：
   ￮快表命中：直接取出物理块号 + 页内偏移，拼接物理地址，访问内存；
   ￮快表未命中：查询内存中的慢表（请求页表）；
3. 遍历慢表，找到对应页表项，检查状态位：
   ￮状态位 = 1（页面在内存）：更新访问字段，若为写指令则更新修改位；同时同步快表，拼接地址访问内存；
   ￮状态位 = 0（缺页）：触发缺页中断，执行前文「缺页中断处理流程」；
4. 页面调入完成后，更新慢表 + 同步写入快表，重新完成地址变换。

2.高频易错细节

1. 快表特性：快表中存在的页表项，一定代表页面在内存；页面被换出时，对应快表项会同步删除。
2. 修改位规则：仅执行写指令时才修改修改位，读指令不会改变修改位。
3. 中断现场：缺页中断会保存 CPU 现场，进程唤醒后恢复现场继续执行。
4. I/O 开销：页面换入 / 换出都需要磁盘 I/O，频繁置换会严重降低系统效率。
5. 页表同步：新页面调入内存后，必须同时更新慢表 + 快表，提升后续访问速度。

五、五大页面置换算法
核心前提
1.算法作用：内存满时，选择哪个页面换出；
2.评价标准：缺页率越低，算法性能越好；
3.缺页率计算公式：缺页率=缺页次数总页面访问次数。

算法 1：最佳置换算法（OPT / 理想算法）
1.核心思想
每次淘汰未来最长时间不会被访问的页面（或永久不再使用的页面）。
2. 优缺点
•优点：理论缺页率最低，性能最优；
•缺点：无法实际实现。操作系统无法提前预知未来的页面访问序列，仅作为评判其他算法的标杆。
3. 做题规则
从当前访问位置向后扫描，对比内存中所有页面下一次出现的位置，选择最晚出现的页面淘汰。

算法 2：先进先出置换算法（FIFO）
1.核心思想
按照页面进入内存的先后顺序淘汰，优先换出最早装入内存的页面。
2. 实现方式
用队列管理内存页面：队头 = 最早进入，队尾 = 最新进入；淘汰队头页面，新页面加入队尾。
3. 关键特性：Belady（贝拉迪）异常
唯一会出现贝拉迪异常的算法：
为进程分配的物理块数量增多，缺页次数反而增加。
4. 优缺点
•优点：逻辑简单、实现开销小；
•缺点：性能差，未考虑页面实际使用频率，经常淘汰仍会被访问的页面。

算法 3：最近最久未使用（LRU）
1.核心思想
淘汰最近一段时间最久没有被访问的页面（局部性原理：最近使用的页面，未来大概率继续使用）。
2. 做题规则
从当前访问位置逆向（向前）扫描，选择内存中最后一次出现位置最远的页面淘汰。
3. 优缺点
•优点：性能最接近最佳置换算法，实际应用广泛；
•缺点：需要专用硬件支持，软件模拟开销大、实现复杂。

算法 4：简单时钟置换算法（Clock / NRU 最近未使用）
1.核心思想
又称最近未用算法，为每个页面设置访问位：
•访问位 = 1：页面最近被访问过；
•访问位 = 0：页面最近未被访问。
2. 执行规则
1.将内存页面组织成循环队列，设置扫描指针；
2.指针循环扫描队列：
￮遇到访问位 = 0：直接淘汰该页面；
￮遇到访问位 = 1：将访问位置 0，指针继续后移；
3.最坏情况：所有页面访问位均为 1，两轮扫描后必找到可淘汰页面。
3. 优缺点
平衡性能与实现开销，介于 FIFO 和 LRU 之间，工程常用。

算法 5：改进型时钟置换算法
1.核心优化
在访问位基础上，增加修改位，优先淘汰「未修改」的页面，减少磁盘 I/O 次数。
页面状态用二元组 (访问位, 修改位) 表示，共 4 种组合。
2. 四轮扫描规则（优先级从高到低，优先淘汰靠前类型）
1.第一轮：寻找 (0, 0) → 最近未访问、未修改（最优淘汰对象，无 I/O），找到直接淘汰；
2.第二轮：寻找 (0, 1) → 最近未访问、已修改；扫描途中将所有(1,*)的访问位置 0；
3.第三轮：再次寻找 (0, 0)；
4.第四轮：寻找 (0, 1)；
最多四轮扫描，一定能选出淘汰页面。
3. 淘汰优先级总结
(0,0)>(0,1)>(1,0)>(1,1)
（越靠前，越优先被淘汰）

六、页面分配与置换策略
1.基础概念
（1）驻留集
请求分页中，分配给一个进程的物理块（页框）集合。
•驻留集过小：频繁缺页、系统效率低；
•驻留集过大：系统并发度下降、资源利用率变低。
（2）两大分类维度

1. 按物理块数量是否可变：固定分配、可变分配
2. 按置换范围：局部置换、全局置换

（3）组合策略（共 3 种，无固定分配 + 全局置换）
固定分配 + 全局置换 相互矛盾，不存在该策略。

策略 1：固定分配 局部置换
1.规则：进程运行前分配固定数量物理块，运行中数量不变；缺页时，仅能淘汰自身内存的页面。
2.特点：
￮难点：初始难以确定合理的物理块数量；
￮灵活性差，缺页率无法动态调整。

策略 2：可变分配 全局置换
1.规则：初始分配若干物理块，运行中数量可变；
2.缺页处理：优先分配系统空闲物理块；无空闲块时，淘汰系统内任意进程的页面（全局范围）；
3.特点：缺页进程一定会新增物理块，可能导致其他进程缺页率上升。

策略 3：可变分配 局部置换（综合最优）
1.规则：初始分配物理块，缺页时仅淘汰自身页面；
2.动态调整：
￮进程频繁缺页 → 增加物理块；
￮进程缺页率极低 → 适当回收物理块；
3.特点：兼顾并发度与缺页率，实际系统主流策略。

七、页面调入时机 & 调入来源
1.页面调入时机（两种策略）
（1）请求调页（主流）
•规则：仅当页面缺页时，才触发调入；
•特点：调入的页面一定会被使用；每次调页都要触发 I/O，开销大；进程运行期间使用。
（2）预调页（基于局部性原理）
•规则：提前预测页面访问顺序，一次性调入多个相邻页面；进程启动前使用；
•特点：减少 I/O 次数；预测成功率约 50%，调入无用页面会浪费内存；
•适用场景：进程首次加载，批量导入代码 / 数据。
补充：实际系统组合使用
预调页（进程启动） + 请求调页（进程运行）。

2. 页面调入来源（外存分区：文件区、兑换区）
外存分为两部分：
•文件区：离散分配，读写慢，存放原始程序 / 文件；
•兑换区：连续分配，读写快，专门用于内存页面交换。
三种调入规则
1.系统有充足兑换区
进程运行前：数据从文件区 → 兑换区；运行时：页面在内存 ↔ 兑换区之间交换（速度快）。
2.系统兑换区不足
•未修改页面：直接从文件区调入，换出时无需写回；
•已修改页面：换出到兑换区，再次使用时从兑换区调入。
3.Unix 系统方案
•页面首次使用：从文件区调入内存；
•页面换出：写入兑换区；再次访问：从兑换区调入。

八、抖动（颠簸） & 工作集
1.抖动 / 颠簸
（1）定义
页面频繁换入、换出：刚换出的页面立刻需要调入，刚调入的页面马上被换出。
（2）产生原因
分配给进程的物理块（驻留集）过小，小于进程实际频繁访问的页面数量。
（3）危害
系统绝大部分时间消耗在页面 I/O 上，进程几乎无法推进，系统性能急剧下降。
（4）解决办法
为进程分配足够的物理块，保证驻留集大小满足运行需求。

2. 工作集
（1）定义
以时间窗口为标准，进程在一段时间内实际访问的页面集合。
（2）工作集 vs 驻留集
•工作集：进程实际正在使用的页面（动态）；
•驻留集：系统分配给进程的物理块（系统分配）。
（3）核心原则
驻留集大小 ≥ 工作集大小
若驻留集 < 工作集 → 必然发生抖动。
（4）应用
系统监测进程工作集大小，以此为依据动态调整驻留集，从根源避免抖动。

九、全章节核心考点总结
1.请求分页页表：牢记 4 个新增字段（状态位、访问位、修改位、外存地址）及作用；
2.缺页中断：内中断、故障类型，区分「缺页」和「页面置换」；
3.地址变换：对比基本分页，重点记忆缺页判断、页表修改、快表同步；
4.置换算法：5 种算法规则、优缺点、贝拉迪异常、淘汰优先级（改进时钟）；
5.分配策略：3 种合法组合，理解局部 / 全局置换、固定 / 可变分配；
6.抖动与工作集：抖动成因、解决方式，驻留集与工作集的大小关系。