目录1.请求分页存储管理概述2.请求分页页表结构新增字段3.缺页中断4.请求分页地址变换流程与细节5.五大页面置换算法原理 例题 优缺点6.页面分配与置换策略7.页面调入时机与来源8.抖动颠簸与工作集、驻留集一、请求分页存储管理概述1.基本定位请求分页是在基本分页存储管理基础上拓展而来的虚拟内存技术核心目标逻辑上扩充内存让进程无需全部装入内存即可运行。2. 两大核心新增功能相较于基本分页系统必须实现两个关键功能请求调页访问页面时若页面不在内存缺页自动从外存将页面调入内存。页面置换内存无空闲物理块时按照算法选择内存中某个页面换出到外存腾出空间给新页面。3. 学习重点全程对比基本分页存储管理区分二者异同重点掌握页表、缺页中断、地址变换、置换算法、分配策略。二、请求分页的页表结构1.基础组成继承基本分页页表的原有字段页号、物理块号额外新增 4 个字段用于支撑请求调页与页面置换。2. 新增 4 个字段及作用3. 补充说明该页表也称为请求页表是实现请求调页、页面置换的核心数据结构。三、缺页中断1.定义进程访问逻辑页面时查询页表发现状态位为 0页面不在内存硬件触发缺页中断由操作系统中断处理程序完成调页。2. 缺页中断完整处理流程分为有空闲物理块、无空闲物理块两种场景场景 1内存存在空闲物理块触发缺页中断进程阻塞进入阻塞队列根据页表中外存地址启动 I/O将目标页面从外存调入空闲物理块修改页表状态位置 1、更新物理块号I/O 完成唤醒进程放回就绪队列重新执行被中断的指令。场景 2内存无空闲物理块触发缺页中断进程阻塞执行页面置换算法选择一个内存页面淘汰判断被淘汰页面的修改位修改位 0直接丢弃无需写回外存修改位 1启动 I/O将页面写回外存把当前所需页面调入刚腾出的物理块更新对应页表项唤醒进程继续执行。3. 缺页中断的分类与特性中断类型属于内中断异常由当前执行指令触发和当前进程强相关内中断细分属于故障故障可由操作系统修复修复后指令可重新执行特殊点一条指令执行过程中可能产生多次缺页中断例一条拷贝指令同时访问两个不同页面若两个页面都不在内存会触发两次缺页。4. 关键区分缺页 ≠ 页面置换•只要页面不在内存就会缺页、触发缺页中断•只有内存物理块全部占满时缺页才会伴随页面置换•内存有空闲块只缺页、不置换。四、请求分页 地址变换流程 细节1.整体流程对比基本分页新增步骤标重点检查页号是否越界越界则终止进程查询快表TLB快表命中直接取出物理块号 页内偏移拼接物理地址访问内存快表未命中查询内存中的慢表请求页表遍历慢表找到对应页表项检查状态位状态位 1页面在内存更新访问字段若为写指令则更新修改位同时同步快表拼接地址访问内存状态位 0缺页触发缺页中断执行前文「缺页中断处理流程」页面调入完成后更新慢表 同步写入快表重新完成地址变换。2.高频易错细节快表特性快表中存在的页表项一定代表页面在内存页面被换出时对应快表项会同步删除。修改位规则仅执行写指令时才修改修改位读指令不会改变修改位。中断现场缺页中断会保存 CPU 现场进程唤醒后恢复现场继续执行。I/O 开销页面换入 / 换出都需要磁盘 I/O频繁置换会严重降低系统效率。页表同步新页面调入内存后必须同时更新慢表 快表提升后续访问速度。五、五大页面置换算法核心前提1.算法作用内存满时选择哪个页面换出2.评价标准缺页率越低算法性能越好3.缺页率计算公式缺页率缺页次数总页面访问次数。算法 1最佳置换算法OPT / 理想算法1.核心思想每次淘汰未来最长时间不会被访问的页面或永久不再使用的页面。2. 优缺点•优点理论缺页率最低性能最优•缺点无法实际实现。操作系统无法提前预知未来的页面访问序列仅作为评判其他算法的标杆。3. 做题规则从当前访问位置向后扫描对比内存中所有页面下一次出现的位置选择最晚出现的页面淘汰。算法 2先进先出置换算法FIFO1.核心思想按照页面进入内存的先后顺序淘汰优先换出最早装入内存的页面。2. 实现方式用队列管理内存页面队头 最早进入队尾 最新进入淘汰队头页面新页面加入队尾。3. 关键特性Belady贝拉迪异常唯一会出现贝拉迪异常的算法为进程分配的物理块数量增多缺页次数反而增加。4. 优缺点•优点逻辑简单、实现开销小•缺点性能差未考虑页面实际使用频率经常淘汰仍会被访问的页面。算法 3最近最久未使用LRU1.核心思想淘汰最近一段时间最久没有被访问的页面局部性原理最近使用的页面未来大概率继续使用。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,*)的访问位置 03.第三轮再次寻找 (0, 0)4.第四轮寻找 (0, 1)最多四轮扫描一定能选出淘汰页面。3. 淘汰优先级总结(0,0)(0,1)(1,0)(1,1)越靠前越优先被淘汰六、页面分配与置换策略1.基础概念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.抖动与工作集抖动成因、解决方式驻留集与工作集的大小关系。
目录1.请求分页存储管理概述2.请求分页页表结构新增字段3.缺页中断4.请求分页地址变换流程与细节5.五大页面置换算法原理 例题 优缺点6.页面分配与置换策略7.页面调入时机与来源8.抖动颠簸与工作集、驻留集一、请求分页存储管理概述1.基本定位请求分页是在基本分页存储管理基础上拓展而来的虚拟内存技术核心目标逻辑上扩充内存让进程无需全部装入内存即可运行。2. 两大核心新增功能相较于基本分页系统必须实现两个关键功能请求调页访问页面时若页面不在内存缺页自动从外存将页面调入内存。页面置换内存无空闲物理块时按照算法选择内存中某个页面换出到外存腾出空间给新页面。3. 学习重点全程对比基本分页存储管理区分二者异同重点掌握页表、缺页中断、地址变换、置换算法、分配策略。二、请求分页的页表结构1.基础组成继承基本分页页表的原有字段页号、物理块号额外新增 4 个字段用于支撑请求调页与页面置换。2. 新增 4 个字段及作用3. 补充说明该页表也称为请求页表是实现请求调页、页面置换的核心数据结构。三、缺页中断1.定义进程访问逻辑页面时查询页表发现状态位为 0页面不在内存硬件触发缺页中断由操作系统中断处理程序完成调页。2. 缺页中断完整处理流程分为有空闲物理块、无空闲物理块两种场景场景 1内存存在空闲物理块触发缺页中断进程阻塞进入阻塞队列根据页表中外存地址启动 I/O将目标页面从外存调入空闲物理块修改页表状态位置 1、更新物理块号I/O 完成唤醒进程放回就绪队列重新执行被中断的指令。场景 2内存无空闲物理块触发缺页中断进程阻塞执行页面置换算法选择一个内存页面淘汰判断被淘汰页面的修改位修改位 0直接丢弃无需写回外存修改位 1启动 I/O将页面写回外存把当前所需页面调入刚腾出的物理块更新对应页表项唤醒进程继续执行。3. 缺页中断的分类与特性中断类型属于内中断异常由当前执行指令触发和当前进程强相关内中断细分属于故障故障可由操作系统修复修复后指令可重新执行特殊点一条指令执行过程中可能产生多次缺页中断例一条拷贝指令同时访问两个不同页面若两个页面都不在内存会触发两次缺页。4. 关键区分缺页 ≠ 页面置换•只要页面不在内存就会缺页、触发缺页中断•只有内存物理块全部占满时缺页才会伴随页面置换•内存有空闲块只缺页、不置换。四、请求分页 地址变换流程 细节1.整体流程对比基本分页新增步骤标重点检查页号是否越界越界则终止进程查询快表TLB快表命中直接取出物理块号 页内偏移拼接物理地址访问内存快表未命中查询内存中的慢表请求页表遍历慢表找到对应页表项检查状态位状态位 1页面在内存更新访问字段若为写指令则更新修改位同时同步快表拼接地址访问内存状态位 0缺页触发缺页中断执行前文「缺页中断处理流程」页面调入完成后更新慢表 同步写入快表重新完成地址变换。2.高频易错细节快表特性快表中存在的页表项一定代表页面在内存页面被换出时对应快表项会同步删除。修改位规则仅执行写指令时才修改修改位读指令不会改变修改位。中断现场缺页中断会保存 CPU 现场进程唤醒后恢复现场继续执行。I/O 开销页面换入 / 换出都需要磁盘 I/O频繁置换会严重降低系统效率。页表同步新页面调入内存后必须同时更新慢表 快表提升后续访问速度。五、五大页面置换算法核心前提1.算法作用内存满时选择哪个页面换出2.评价标准缺页率越低算法性能越好3.缺页率计算公式缺页率缺页次数总页面访问次数。算法 1最佳置换算法OPT / 理想算法1.核心思想每次淘汰未来最长时间不会被访问的页面或永久不再使用的页面。2. 优缺点•优点理论缺页率最低性能最优•缺点无法实际实现。操作系统无法提前预知未来的页面访问序列仅作为评判其他算法的标杆。3. 做题规则从当前访问位置向后扫描对比内存中所有页面下一次出现的位置选择最晚出现的页面淘汰。算法 2先进先出置换算法FIFO1.核心思想按照页面进入内存的先后顺序淘汰优先换出最早装入内存的页面。2. 实现方式用队列管理内存页面队头 最早进入队尾 最新进入淘汰队头页面新页面加入队尾。3. 关键特性Belady贝拉迪异常唯一会出现贝拉迪异常的算法为进程分配的物理块数量增多缺页次数反而增加。4. 优缺点•优点逻辑简单、实现开销小•缺点性能差未考虑页面实际使用频率经常淘汰仍会被访问的页面。算法 3最近最久未使用LRU1.核心思想淘汰最近一段时间最久没有被访问的页面局部性原理最近使用的页面未来大概率继续使用。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,*)的访问位置 03.第三轮再次寻找 (0, 0)4.第四轮寻找 (0, 1)最多四轮扫描一定能选出淘汰页面。3. 淘汰优先级总结(0,0)(0,1)(1,0)(1,1)越靠前越优先被淘汰六、页面分配与置换策略1.基础概念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.抖动与工作集抖动成因、解决方式驻留集与工作集的大小关系。
