Aisssky‘s BLOG

第一章：存储管理基础
第二章：程序装入与链接
第三章：连续分配存储管理
第四章：分页存储管理
第五章：分段存储管理
第六章：虚拟存储技术
第七章：请求分页系统
第八章：页面置换算法

第一章：存储管理基础

1.1 存储管理的四大功能

功能	描述	关键技术
主存分配与回收	管理内存空间的分配和释放	分配策略（首次适应、最佳适应等）、分配结构（位示图、空闲链表）
地址映射（重定位）	将逻辑地址转换为物理地址	静态重定位、动态重定位
存储保护	防止进程越界访问和非法操作	界地址寄存器、访问权限控制
主存扩充（虚拟内存）	逻辑上扩展内存容量	请求分页、请求分段

1.2 地址重定位详解

1.2.1 地址类型

逻辑地址（虚地址）：编译链接后生成的地址，从0开始编址
物理地址（实地址）：内存单元的实际地址

1.2.2 重定位方式对比

特性	静态重定位	动态重定位
时机	程序装入时一次性完成	程序执行期间动态进行
硬件需求	不需要特殊硬件	需要重定位寄存器
程序移动性	装入后不能移动	可以移动，支持内存紧凑
实现复杂度	简单	复杂
适用场景	早期多道系统	现代虚拟存储系统

1.2.3 动态重定位实现

基址寄存器：存放程序在内存中的起始地址
地址转换公式：物理地址 = 基址 + 逻辑地址
越界检查：逻辑地址 < 限长寄存器值

1.3 存储保护机制

1.3.1 保护目的

保护操作系统不被用户程序破坏
保护用户进程之间互不干扰
保护共享数据的完整性和一致性

1.3.2 硬件支持方案

界地址寄存器方案：基址寄存器 + 限长寄存器
存储键方案：为每个内存块设置保护键
环保护机制：多级特权保护（如0环为内核，3环为用户）

1.3.3 保护实现

越界检查：硬件自动比较，越界则触发中断
权限检查：通过页表/段表中的保护位实现

1.4 虚拟内存原理

1.4.1 局部性原理

时间局部性：刚被访问的存储单元很可能近期再次被访问
空间局部性：被访问存储单元的邻近单元很可能被访问

1.4.2 虚拟存储基本思想

部分装入：只将当前需要的部分装入内存
按需调页：访问不在内存的页面时产生缺页中断，调入所需页面
页面置换：内存满时选择合适的页面换出到外存

第二章：程序装入与链接

2.1 程序执行三步骤

编译：源程序 → 多个目标模块
链接：目标模块 + 库函数 → 装入模块
装入：装入模块 → 内存

2.2 装入方式详解

2.2.1 绝对装入方式

特点：程序必须装入指定内存位置
适用：单道程序系统
缺点：不灵活，不支持多道程序

2.2.2 可重定位装入方式

重定位表：记录需要修改的地址位置
装入时修改：根据实际装入地址修改所有重定位项
优缺点：
- 优点：支持多道程序
- 缺点：程序不能移动，需要连续存储空间

2.2.3 动态运行时装入方式

重定位寄存器：运行时动态计算物理地址
支持特性：
- 程序可移动
- 支持不连续存储
- 支持虚拟存储
硬件需求：地址转换硬件（MMU）

2.3 链接方式对比

2.3.1 静态链接

时机：运行前
特点：生成完整的可执行文件
缺点：
- 占用内存大
- 更新困难
- 共享困难

2.3.2 动态链接

装入时动态链接：
- 装入时完成链接
- 支持代码共享
- 便于更新
运行时动态链接：
- 需要时再链接
- 节省内存
- 支持插件式功能扩展

2.3.3 动态链接库（DLL）

优点：
- 多进程共享，节省内存
- 便于升级（接口不变即可）
- 支持模块化开发
缺点：
- 增加运行时开销
- 存在DLL版本冲突问题

第三章：连续分配存储管理

3.1 四种连续分配方式

方式	分区特点	分配特点	适用场景
单一连续	系统区+用户区	全部装入	单用户系统
固定分区	固定大小分区	按分区分配	早期多道系统
动态分区	动态划分分区	按需分配	多道批处理
可重定位分区	动态分区+紧凑	可移动程序	需要解决碎片

3.2 动态分区分配算法

3.2.1 分配算法比较

算法	策略	优点	缺点
首次适应	从低地址找第一个满足的空闲区	简单、快速	低地址碎片多
最佳适应	找大小最接近需求的空闲区	减少大空闲区被切割	产生小碎片
最坏适应	找最大的空闲区	减少小碎片	大分区被破坏

3.2.2 数据结构

空闲分区表：记录空闲分区信息
空闲分区链：双向链表组织空闲区

3.3 碎片问题与解决

3.3.1 碎片类型

内部碎片：分配给进程但未使用的部分（固定分区）
外部碎片：太小而无法分配的空闲区（动态分区）

3.3.2 解决方案

紧凑技术：移动程序合并空闲区
- 需要动态重定位支持
- 系统开销大
可重定位分区：定期紧凑碎片
离散分配：分页/分段从根本上避免外部碎片

第四章：分页存储管理

4.1 基本概念

4.1.1 地址划分

逻辑地址 = 页号P + 页内偏移W
物理地址 = 块号b + 页内偏移W
页大小：通常为2的幂（如4KB）

4.1.2 关键数据结构

页表：每个进程一个，存储页号到块号的映射
物理块表：系统全局，记录物理块使用情况

4.2 地址映射过程

4.2.1 基本映射步骤

分离逻辑地址为页号P和页内偏移W
以P为索引查页表，得物理块号b
物理地址 = b × 页大小 + W

4.2.2 地址映射实例

text复制下载

例：页大小1KB，逻辑地址2500
2500 / 1024 = 2余452 → P=2, W=452
若页表显示2号页对应7号块
物理地址 = 7×1024 + 452 = 7620

4.3 快表（TLB）技术

4.3.1 TLB原理

作用：缓存最近使用的页表项
组成：页号、块号、有效位等
查找方式：并行查找，速度快

4.3.2 性能分析

有效访问时间公式：text复制下载EAT = λ + (2 – a) × t 其中：λ为TLB访问时间，a为命中率，t为内存访问时间
实例计算：text复制下载给定：t=1μs，λ=0.2μs，a=85% EAT = 0.2 + (2-0.85)×1 = 0.2 + 1.15 = 1.35μs

4.3.3 TLB管理

替换算法：LRU、随机等
一致性：当页表项修改时需要更新或无效化TLB

4.4 多级页表

4.4.1 解决大页表问题

问题：32位系统，4KB页 → 2²⁰个页表项，每个进程需4MB页表
解决方案：页表分页，建立页目录

4.4.2 二级页表示例

text复制下载

32位地址：10位页目录索引 + 10位页表索引 + 12位页内偏移
访问过程：
1. 用页目录索引查页目录表，得页表物理地址
2. 用页表索引查页表，得物理块号
3. 合成物理地址

4.4.3 多级页表优缺点

优点：
- 页表不必连续存储
- 可以只分配需要的部分
缺点：
- 增加访存次数
- 地址转换复杂

4.5 倒排页表

4.5.1 设计思想

传统页表：每个虚拟页一个表项
倒排页表：每个物理帧一个表项
表项内容：进程ID + 虚拟页号

4.5.2 地址转换

根据进程ID和虚拟页号在倒排页表中查找
找到对应表项即得物理帧号
未找到则产生缺页异常

4.5.3 优化技术

哈希表加速：用虚拟地址哈希快速定位
TLB配合：频繁访问页面通过TLB直接转换

4.5.4 优缺点对比

方面	传统页表	倒排页表
表项数	虚拟页数	物理帧数
空间开销	大（尤其64位）	小（与物理内存成比例）
查找速度	快（直接索引）	慢（需要搜索）
实现复杂度	简单	复杂

4.6 页大小选择

4.6.1 影响因素

内部碎片：页越大，内部碎片可能越大
页表大小：页越小，页表越大
局部性：页大小影响空间局部性利用
I/O效率：大页减少缺页次数但增加传输时间

4.6.2 典型页大小

早期系统：512字节、1KB
现代系统：4KB（x86）、8KB（SPARC）、16KB（ARM）
大页支持：2MB、1GB（用于数据库等特殊应用）

4.7 分页系统的保护与共享

4.7.1 保护机制

越界保护：检查页号是否有效
权限保护：通过页表项中的保护位控制
- R（读）、W（写）、X（执行）
- U/S（用户/系统）权限

4.7.2 共享实现

代码共享：只读页面可多进程共享
写时复制：
1. 初始时共享同一物理页（只读）
2. 任一进程写入时触发保护异常
3. 操作系统复制页面，修改权限为可写
共享数据结构：页表指向相同物理帧

第五章：分段存储管理

5.1 基本概念

5.1.1 分段与分页对比

特性	分页	分段
划分单位	固定大小页	逻辑意义段
用户透明性	透明	可见
地址空间	一维	二维（段号+段内偏移）
碎片类型	内部碎片	外部碎片
共享难度	困难	容易
动态链接	不支持	支持
保护粒度	页级别	段级别

5.1.2 分段优势

逻辑清晰：按功能模块组织
便于共享：以段为单位共享
动态链接：需要时再链接模块
动态增长：数据段、栈段可动态扩展

5.2 地址映射

5.2.1 段表结构

段基址：段在内存中的起始地址
段长度：段的长度限制
保护位：读/写/执行权限
状态位：是否在内存、是否被修改等

5.2.2 映射过程

从逻辑地址提取段号S和段内偏移D
以S为索引查段表，得段基址B和段长L
检查D < L（越界检查）
物理地址 = B + D

5.2.3 保护机制

越界检查：D必须小于段长L
权限检查：根据保护位检查访问合法性
环保护：多级特权保护机制

5.3 分段系统的共享

5.3.1 共享段表

系统维护：全局共享段表
表项内容：
- 段名/段号
- 段长
- 内存地址
- 共享进程计数
- 其他管理信息

5.3.2 共享过程

首次共享：
- 分配内存空间
- 创建共享段表项
- count=1
后续共享：
- 不分配新空间
- 修改进程段表指向共享段
- count++
回收共享：
- count–
- 若count=0，释放内存

5.4 段页式存储管理

5.4.1 设计思想

用户视角：分段（二维地址）
系统视角：每段再分页（一维管理）
地址结构：段号S + 页号P + 页内偏移W

5.4.2 地址映射过程

根据段号S查段表，得页表基址
根据页号P查页表，得物理块号
物理地址 = 物理块号 × 页大小 + W

5.4.3 访存次数分析

无快表：3次访存（段表→页表→数据）
有快表：
- 命中：1次访存
- 未命中：3次访存

5.4.4 优缺点

优点：
- 结合分段和分页优点
- 便于共享和保护
- 无外部碎片
缺点：
- 地址转换复杂
- 管理开销大

第六章：虚拟存储技术

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
特殊应用：根据访问模式定制

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

第一章：存储管理基础

1.1 存储管理的四大功能

1.2 地址重定位详解

1.2.1 地址类型

1.2.2 重定位方式对比

1.2.3 动态重定位实现

1.3 存储保护机制

1.3.1 保护目的

1.3.2 硬件支持方案

1.3.3 保护实现

1.4 虚拟内存原理

1.4.1 局部性原理

1.4.2 虚拟存储基本思想

第二章：程序装入与链接

2.1 程序执行三步骤

2.2 装入方式详解

2.2.1 绝对装入方式

2.2.2 可重定位装入方式

2.2.3 动态运行时装入方式

2.3 链接方式对比

2.3.1 静态链接

2.3.2 动态链接

2.3.3 动态链接库（DLL）

第三章：连续分配存储管理

3.1 四种连续分配方式

3.2 动态分区分配算法

3.2.1 分配算法比较

3.2.2 数据结构

3.3 碎片问题与解决

3.3.1 碎片类型

3.3.2 解决方案

第四章：分页存储管理

4.1 基本概念

4.1.1 地址划分

4.1.2 关键数据结构

4.2 地址映射过程

4.2.1 基本映射步骤

4.2.2 地址映射实例

4.3 快表（TLB）技术

4.3.1 TLB原理

4.3.2 性能分析

4.3.3 TLB管理

4.4 多级页表

4.4.1 解决大页表问题

4.4.2 二级页表示例

4.4.3 多级页表优缺点

4.5 倒排页表

4.5.1 设计思想

4.5.2 地址转换

4.5.3 优化技术

4.5.4 优缺点对比

4.6 页大小选择

4.6.1 影响因素

4.6.2 典型页大小

4.7 分页系统的保护与共享

4.7.1 保护机制

4.7.2 共享实现

第五章：分段存储管理

5.1 基本概念

5.1.1 分段与分页对比

5.1.2 分段优势

5.2 地址映射

5.2.1 段表结构

5.2.2 映射过程

5.2.3 保护机制

5.3 分段系统的共享

5.3.1 共享段表

5.3.2 共享过程

5.4 段页式存储管理

5.4.1 设计思想

5.4.2 地址映射过程

5.4.3 访存次数分析

5.4.4 优缺点

第六章：虚拟存储技术

6.1 覆盖技术

6.1.1 基本思想

6.1.2 示例

6.1.3 优缺点

6.2 交换技术