嗡嗡嗡

第六章：虚拟存储技术

6.1 覆盖技术

6.1.1 基本思想

覆盖段：不会同时执行的程序段共享同一内存区
覆盖结构：树状调用结构
管理方式：程序员指定覆盖结构，系统管理覆盖

6.1.2 示例

text复制下载

程序结构：
    根段A（常驻）
    ├─覆盖区0：B和C互斥
    └─覆盖区1：D、E、F互斥

6.1.3 优缺点

优点：可在小内存运行大程序
缺点：
- 程序员负担重
- 不能实现虚拟存储的透明性

6.2 交换技术

6.2.1 基本概念

交换单位：整个进程
交换时机：内存紧张时
交换位置：磁盘交换区

6.2.2 交换过程

换出：进程暂停，映像保存到磁盘
换入：从磁盘恢复映像到内存
地址重定位：换入位置可能与原位置不同

6.2.3 与覆盖对比

特性	覆盖	交换
交换单位	程序段	整个进程
控制者	程序员	操作系统
透明性	不透明	透明
灵活性	低	高

6.3 虚拟存储原理

6.3.1 局部性原理的量化

工作集模型：进程在时间窗口τ内访问的页面集合
工作集大小：随时间变化的函数W(t, τ)

6.3.2 虚拟存储特征

多次性：分多次装入程序
对换性：页面可在内存和外存间换入换出
虚拟性：逻辑内存远大于物理内存
离散性：程序不必连续存放

6.3.3 虚拟存储实现条件

硬件支持：页表/段表机制、中断机构、地址转换机构
软件支持：调入策略、置换算法、分配策略

第七章：请求分页系统

7.1 页表扩充字段

字段	作用	位数
状态位P	页面是否在内存	1位
访问位R	页面是否被访问	1位
修改位M	页面是否被修改	1位
外存地址	页面在磁盘位置	若干位
保护位	读/写/执行权限	2-3位
其他	特殊用途	可变

7.2 缺页中断处理

7.2.1 中断流程

保护现场：保存CPU状态
分析原因：确定缺页的虚拟地址
页面调入：
- 有空闲块：直接分配
- 无空闲块：执行页面置换
更新页表：修改状态位和物理块号
恢复执行：重新执行被中断指令

7.2.2 与一般中断的区别

方面	一般中断	缺页中断
时机	指令之间	指令执行中
次数	一次	可能多次
处理	简单	复杂（涉及I/O）
返回	下条指令	当前指令

7.3 调入策略

7.3.1 请求调页（Demand Paging）

策略：缺页时才调入
优点：实现简单，只调入需要页面
缺点：启动慢，缺页频繁

7.3.2 预调页（Prepaging）

策略：预测需要页面，提前调入
实现：
- 进程创建时：调入初始工作集
- 缺页时：调入缺页及邻近页面
效果：减少缺页率，提高I/O效率

7.3.3 页面来源

文件区：只读页面（代码、常量）
交换区：可修改页面（堆、栈、数据）

7.4 分配策略

7.4.1 物理块分配算法

平均分配：所有进程平分物理块
按比例分配：按进程大小比例分配text复制下载进程i分配块数 = (进程i大小 / 所有进程总大小) × 总块数
优先级分配：高优先级进程分配更多块

7.4.2 分配置换组合策略

策略	物理块分配	置换范围	特点
固定分配+局部置换	固定	本进程内部	稳定但需合理分配
可变分配+全局置换	可变	所有进程	简单但可能影响其他进程
可变分配+局部置换	可变	本进程内部	动态调整，性能好

7.4.3 缺页率与分配关系

缺页率公式：f = F / N
- F：缺页次数
- N：总访问次数
影响因素：
- 分配物理块数
- 页面置换算法
- 程序访问模式
- 页面大小

7.5 性能优化技术

7.5.1 页面缓冲技术

空闲页面链表：保留一定数量空闲页
已修改页面链表：延迟写回磁盘
未修改页面链表：可直接重用

7.5.2 负载控制

颠簸检测：监控缺页率
解决方案：
1. 挂起部分进程
2. 增加物理内存
3. 调整分配策略

第八章：页面置换算法

8.1 算法评价标准

标准	描述	重要性
缺页率	缺页次数/总访问次数	最重要
时间复杂度	选择淘汰页面的时间开销	重要
空间开销	算法需要的额外存储空间	重要
实现复杂度	软硬件实现难度	中等
适用场景	特定访问模式的适应性	中等

8.2 经典置换算法详解

8.2.1 最佳置换算法（OPT）

思想：淘汰未来最长时间不会被访问的页面
实现：需要预知未来访问序列（理论值）
特点：
- 理论最优缺页率
- 无法实际实现
- 用于算法性能上界

8.2.2 先进先出算法（FIFO）

思想：淘汰最早进入内存的页面
实现：队列管理页面进入顺序
Belady异常：增加物理块可能增加缺页率
优缺点：
- 优点：实现简单
- 缺点：性能差，可能Belady异常

8.2.3 最近最久未使用算法（LRU）

硬件实现方案：

计数器法：
- 每个页表项设置计数器
- 每次访问更新为当前时间
- 淘汰计数器最小的页面
矩阵法（n×n位矩阵）：
- 初始全0
- 访问帧k：行k置1，列k置0
- 淘汰二进制值最小的行对应帧

软件模拟方案：

NFU（最不常用）：
- 每个页面一个计数器
- 时钟中断时将R位加到计数器
- 淘汰计数器最小的页面
- 问题：不能”忘记”历史
老化算法（Aging）：
- 改进NFU：计数器右移1位，R加到最高位
- 公式：计数器 = (计数器 >> 1) | (R << (n-1))
- 示例（8位计数器）：text复制下载初始：10000000 下个时钟R=1：11000000（右移后1100000，加R得11000000）下个时钟R=0：01100000

LRU特点：

性能接近OPT
实现代价高（硬件）或近似（软件）
对访问模式变化敏感

8.2.4 时钟置换算法（Clock）

基本时钟算法：

数据结构：环形链表，指针指向最老页面
算法流程：
1. 检查指针指向页面的R位
2. R=0：淘汰该页，装入新页，指针前进
3. R=1：清R位，指针前进，继续检查

改进时钟算法（考虑修改位）：

页面分类：4类（R,M）=(0,0),(0,1),(1,0),(1,1)
淘汰顺序：优先淘汰(0,0)，最后淘汰(1,1)

时钟算法特点：

FIFO的改进，避免淘汰常用页面
实现简单，性能较好
是实际系统常用算法

8.2.5 第二次机会算法

本质：FIFO + R位检查
流程：
1. 检查最老页面的R位
2. R=0：立即淘汰
3. R=1：清R位，放到链表尾部，继续检查
退化情况：所有页面R=1时退化为FIFO

8.2.6 最近未使用算法（NRU）

基础：使用R位和M位
页面分类：
1. 类0：R=0,M=0（最佳淘汰对象）
2. 类1：R=0,M=1（次佳）
3. 类2：R=1,M=0
4. 类3：R=1,M=1
策略：随机淘汰最低非空类中页面
特点：简单高效，性能适中

8.3 工作集相关算法

8.3.1 工作集模型

定义：W(t, τ) = 时间窗口(t-τ, t]内访问的页面集合
性质：
- 随τ单调不减
- 有限（不超过地址空间）
- 随时间变化

8.3.2 工作集页面置换算法

思想：淘汰不在工作集中的页面
实现：
- 页表记录上次访问时间
- 计算页面年龄 = 当前时间 – 上次访问时间
- 淘汰年龄>τ且R=0的页面
问题：需要扫描所有页面，开销大

8.3.3 工作集时钟算法（WSClock）

数据结构：时钟环形链表，增加上次访问时间字段
算法流程：
1. 检查指针指向页面
2. R=1：清R，指针前进
3. R=0且年龄>τ：若M=0则淘汰；若M=1则调度写回
4. 扫描一周未找到淘汰页：强制淘汰任一R=0页或最早页
特点：
- 结合工作集和时钟算法优点
- 实现相对简单
- 性能良好

8.4 算法性能比较

算法	缺页率	实现开销	硬件需求	适用场景
OPT	最低（理论）	无法实现	预知未来	性能基准
FIFO	较高	很低	无	简单系统
LRU	接近OPT	高	计数器/矩阵	性能要求高
Clock	较好	低	R位	通用系统
NRU	中等	很低	R/M位	实际常用
WSClock	好	中等	R/M+时间	虚拟存储

8.5 算法选择建议

简单系统：NRU或简单Clock
通用系统：改进Clock或WSClock
高性能需求：硬件LRU或优化Clock
特殊应用：根据访问模式定制

第九章：分页系统设计问题

9.1 共享页面深入

9.1.1 共享实现方式

代码共享：
- 只读页面可安全共享
- 多个进程页表指向相同物理帧
- 示例：系统库、公共代码
数据共享：
- 需要同步机制
- 写时复制技术：
  a. 初始共享只读副本
  b. 写操作触发页面复制
  c. 每个进程有自己的可写副本
fork()中的共享：
- Unix fork：父子进程共享相同地址空间
- 写时复制优化：实际复制延迟到写入时

9.1.2 共享管理问题

引用计数：跟踪共享页面被多少进程使用
回收策略：所有进程释放后才回收页面
一致性：确保共享页面内容一致性

9.2 清除策略优化

9.2.1 分页守护进程

作用：定期检查并清理页面
工作方式：
1. 睡眠大部分时间
2. 定时唤醒检查内存状态
3. 空闲页过少时启动页面清理

9.2.2 双指针时钟算法

前指针：分页守护进程控制，清理脏页面
后指针：页面置换使用，标准时钟算法
优点：提高后指针找到干净页面的概率

9.2.3 页面缓冲技术

干净页面链表：可直接重用
脏页面链表：需要写回磁盘
空闲页面阈值：保持一定数量空闲页

9.3 页面锁定机制

9.3.1 需要锁定的场景

I/O操作中页面：避免DMA访问时页面被换出
内核关键页面：操作系统核心代码和数据
实时任务页面：保证实时性

9.3.2 实现方式

页表锁定位：防止页面被置换
内核缓冲区：I/O先到内核缓冲区，再复制到用户空间
临时锁定：I/O期间锁定，完成后释放

9.4 后备存储管理

9.4.1 交换区组织方式

静态分配：
- 进程创建时分配固定大小交换区
- 管理简单，地址计算容易
- 可能浪费空间
动态分配：
- 页面换出时分配磁盘空间
- 空间利用率高
- 管理复杂，需要记录每个页面的磁盘位置

9.4.2 交换区优化

分离存储：代码、数据、栈分开管理
预分配预留：避免频繁分配
集群分配：相邻页面分配连续磁盘空间

9.5 其他设计问题

9.5.1 分离指令和数据空间

I-space和D-space：独立地址空间
优点：
- 便于共享只读代码
- 独立保护机制
- 支持更大地址空间
实现：两个页表，独立管理

9.5.2 大页支持

目的：减少TLB失效，提高性能
大小：2MB、1GB等
应用：数据库、科学计算等

9.5.3 反置页表优化

哈希加速：虚拟地址→物理地址快速映射
链式冲突解决：哈希冲突时链表连接
TLB配合：频繁访问页面通过TLB加速

第十章：请求分段系统

10.1 段表扩展字段

字段	功能	说明
存在位	段是否在内存	1位
访问权限	读/写/执行	2-3位
修改位	段是否被修改	1位
访问位	访问频率/时间	若干位
外存地址	段在磁盘位置	磁盘地址
增长方向	段增长方向	1位（栈/堆）
段长限制	最大允许长度	长度值

10.2 缺段中断处理

10.2.1 处理流程

检查内存空间：是否有足够连续空间
空间足够：直接装入
空间不足：
a. 检查能否通过紧凑获得空间
b. 若不能，淘汰一个或多个段
c. 执行紧凑（如果需要）
装入段：从外存读入段
更新段表：设置存在位和基址

10.2.2 与缺页中断对比

单位不同：段 vs 页
空间要求：需要连续空间 vs 任意位置
置换粒度：整个段 vs 单个页面
发生频率：较低 vs 较高

10.3 分段共享详细

10.3.1 共享段表管理

text复制下载

共享段表项结构：
1. 段名/标识符
2. 段长
3. 内存基址
4. 共享进程计数
5. 进程引用列表
6. 其他管理信息

10.3.2 共享过程示例

text复制下载

进程A首次访问段S：
1. 检查共享段表，S不存在
2. 为S分配内存空间
3. 从磁盘装入S
4. 创建共享段表项，count=1
5. 更新进程A段表指向S

进程B访问段S：
1. 检查共享段表，S存在
2. 更新进程B段表指向S
3. count++

进程A释放段S：
1. 从进程A段表移除S引用
2. count--
3. 若count=0，释放S内存

10.3.3 共享同步问题

只读共享：无同步问题
可写共享：需要同步机制
- 互斥访问
- 版本控制
- 事务支持

10.4 分段保护机制

10.4.1 越界保护

段长检查：偏移量 < 段长
增长方向：栈段向下增长需特殊处理
越界处理：触发段错误（Segmentation Fault）

10.4.2 权限保护

基本权限：读(R)、写(W)、执行(X)
组合权限：RW、RX、RWX等
权限违反：触发保护异常

10.4.3 环保护机制

特权级别：通常0-3级，0为最高
访问规则：
- 高级别可访问低级别数据
- 低级别不能访问高级别数据
- 调用门机制控制跨级别调用
现代实现：用户态(3) vs 内核态(0)

10.5 分段系统优缺点总结

10.5.1 优点

逻辑结构清晰：符合程序设计习惯
易于共享：以段为单位共享
动态链接支持：运行时链接模块
动态增长：数据段、栈段可扩展
保护粒度细：段级别保护
便于调试：地址有逻辑意义

10.5.2 缺点

外部碎片：内存空间不连续
管理复杂：需要紧凑和碎片整理
内存利用率：可能较低
交换开销：整个段交换，即使只使用部分
实现复杂：硬件和软件支持复杂

10.5.3 适用场景

需要动态链接：如现代操作系统
需要精细保护：安全敏感应用
逻辑结构重要：大型复杂软件
共享需求多：多进程协作应用

于2025年12月11日2025年12月11日由Aisssky发布

第六章：虚拟存储技术

6.1 覆盖技术

6.1.1 基本思想

6.1.2 示例

6.1.3 优缺点

6.2 交换技术

6.2.1 基本概念

6.2.2 交换过程

6.2.3 与覆盖对比

6.3 虚拟存储原理

6.3.1 局部性原理的量化

6.3.2 虚拟存储特征

6.3.3 虚拟存储实现条件

第七章：请求分页系统

7.1 页表扩充字段

7.2 缺页中断处理

7.2.1 中断流程

7.2.2 与一般中断的区别

7.3 调入策略

7.3.1 请求调页（Demand Paging）

7.3.2 预调页（Prepaging）

7.3.3 页面来源

7.4 分配策略

7.4.1 物理块分配算法

7.4.2 分配置换组合策略

7.4.3 缺页率与分配关系

7.5 性能优化技术

7.5.1 页面缓冲技术

7.5.2 负载控制

第八章：页面置换算法

8.1 算法评价标准

8.2 经典置换算法详解

8.2.1 最佳置换算法（OPT）

8.2.2 先进先出算法（FIFO）

8.2.3 最近最久未使用算法（LRU）

硬件实现方案：

软件模拟方案：

LRU特点：

8.2.4 时钟置换算法（Clock）

基本时钟算法：

改进时钟算法（考虑修改位）：

时钟算法特点：

8.2.5 第二次机会算法

8.2.6 最近未使用算法（NRU）

8.3 工作集相关算法

8.3.1 工作集模型

8.3.2 工作集页面置换算法

8.3.3 工作集时钟算法（WSClock）

8.4 算法性能比较

8.5 算法选择建议

第九章：分页系统设计问题

9.1 共享页面深入

9.1.1 共享实现方式

9.1.2 共享管理问题

9.2 清除策略优化

9.2.1 分页守护进程

9.2.2 双指针时钟算法

9.2.3 页面缓冲技术

9.3 页面锁定机制

9.3.1 需要锁定的场景

9.3.2 实现方式

9.4 后备存储管理

9.4.1 交换区组织方式

9.4.2 交换区优化

9.5 其他设计问题

9.5.1 分离指令和数据空间

9.5.2 大页支持

9.5.3 反置页表优化

第十章：请求分段系统

10.1 段表扩展字段

10.2 缺段中断处理

10.2.1 处理流程

10.2.2 与缺页中断对比

10.3 分段共享详细

10.3.1 共享段表管理

10.3.2 共享过程示例

10.3.3 共享同步问题

10.4 分段保护机制