第九章 虚拟存储器管理
1、虚拟存储系统的基本概念
2、分页存储管理
3、分段存储管理
4、段页式存储管理
5、页（段）的置换算法和系统行为
6、页架分配算法
9.1 虚拟存储系统的基本概念
1、问题的提出
? 程序大于内存
? 程序暂时不执行或运行完是否还要占
用内存
2、基本思想
程序、数据的大小可以超过内存的大小，
操作系统把程序当前使用的部分保留在
主存，而把其它部分保存在辅存中，并
在需要时在主存和辅存之间动态交换 。
把辅存当作主存进行扩充，对用户来说，
计算机系统有一个容量很大的主存。
?虚存的优点,
可容纳大量的进程，提高系统多道并行
程度，提高主存和其他资源的利用率，
提高系统运行效率和系统吞吐率
?虚存的缺点,
（ 1）额外的主存开销
（ 2）地址转换增加了指令执行时间
9.2 分页存储管理
? 基本概念
? 地址转换
? 硬件支持
? 页的共享
一、分页存储管理的基本概念
? 等分主存：页架、页架号
? 用户逻辑地址空间的分页：页、页号
? 逻辑地址的表示：（页号 p,页内地址 d）
? 分配原则：以页架为基本分配单位
? 页表：页号、页架号
? 分页系统中的地址结构,
– 页号 ?最大页数
– 页内地址 ?页架的大小
? 页面尺寸应是 2的幂
基本工作原理
在程序开始运行之前，不是装入全部
页面，而是装入一个或零个页面，之
后根据程序运行的需要，动态装入其
它页面；当内存空间已满，而又需要
装入新的页面时，则根据某种算法淘
汰某个页面，以便装入新的页面
X
X
X
X
7
X
5
X
X
X
3
4
0
6
1
2
60K-64K
56K-60K
52K-56K
48K-52K
44K-48K
40K-44K
36K-40K
32K-36K
28K-32K
24K-28K
20K-24K
16K-20K
12K-16K
8K-12K
4K-8K
0K-4K
28K-32K
24K-28K
20K-24K
16K-20K
12K-16K
8K-12K
4K-8K
0K-4K
虚地址空间
物理地址空间
} 虚页
页架
二、分页系统中的地址转换
? 直接映象页地址转换
? 多级页表地址转换
? 快表的地址转换
1、直接映象页地址转换
P d
p'
+
L b
p' d
P
页表
页表地址寄存器
虚地址 v=(p,d)
实地址
b
0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0
1 1 0 0 0 0 0 0 0 0 0 0 1 0 0
110
在 /不在内存
页表
虚地址
8196
物理地址
24580
000 0 15
000 0 14
000 0 13
000 0 12
111 1 11
000 0 10
101 1 9
000 0 8
000 0 7
000 0 6
011 1 5
100 1 4
000 1 3
110 1 2
001 1 1
010 1 0
页号 页架号 状态
2、多级页表地址转换
解决页表非常大的问题
访存次数增加，增加一级页表，增加一次
访存次数。
3、快表的地址转换
页号 页内地址
页号 页架号
页架号 页内地址
虚地址
物理地址 快表
p’
页表
地址越界
l
比较
P>=1
p p’
,,,
快表
b
+
页号 p 页内地址 d
P’ d
物理地址
页表地址寄存器 页表长度寄存器 逻辑地址
举例
如果查找快表花费的时间是 50NS,访问内
存的时间是 750NS,试计算命中率为 80%,
90%时实际的访存时间。
页号在快表：存取时间为 50+750=800NS
页号在慢表：存取时间为 750+750=1500NS
命中率为 80% 存取时间为 0.8*800+0.2*1500=940NS
命中率为 90% 存取时间为 0.9*800+0.1*1500=870NS
三、硬件支持
? 主存管理单元 MMU
? 页表
? 快表
? 反向页表
1、主存管理单元 MMU
? 页表地址寄存器：页表始址，长度
? 虚地址分成虚页号和页内地址
? 判断有越界访问和保护性错误
页表中
有效位 保护权限
2、页表
实现页式管理重要的数据结构
内容：页架号
修改位
有效位
引用位
保护权限
3、快表
为加快地址转换而使用高速缓存
内容：页号
页架号
保护权限
4、反向页表
完成物理页架号到虚地址的映射
内容：虚页号
物理页架号
指向哈希链的下一项指针
有效位，修改位，引用位
保护和加锁信息
9.3 分段存储管理
? 基本概念
? 地址转换
一、分段存储管理的基本概念
? 进程的逻辑地址空间：段、段号
? 程序的地址结构：（段号 s,段内地址 w）
段号 ?最多段数 段内地址 ?最大段长
? 主存分配：以段为单位
? 段表和段表寄存器
– 段表：段号、段的长度、段在主存中的起始地
址、段的状态位、访问位、修改位、段的外存
地址
– 段表寄存器：段表起始地址、段表长度
段的动态链接
在程序开始运行时，只将主程序段装
配好并调入内存，其它各段的装配是
在主程序段的运行过程中逐步完成。
每当需要调用一个新段时，再将这个
新段装配好，并与主程序段链接。
二、分段存储管理地址转换
段表长 段表地址
段号 段内地址
+
段表
S′ l
L b
S w
b
s
+
实地址
段表地址寄存器
虚地址
Cl
Cb
+
段号 S 段内地址 d
比较
比较
b + d
段 表
S>= Cl
快表
物理地址
段表始址寄存器 段表长度寄存器 逻辑地址
l b
.,,
S l b
地址越界 d>=1
d>=1
地址映射及存储保护机制
地址越界
地址越界
比较
举例
段长 段起始地址 有效位
0 200 500 1
1 400 1000 1
2 100 1400 0
3 900 2000 1
虚地址：（ 2,250）,（ 4,470）完成实地址转换
1,缺段中断
2,越界
三、存储保护问题
? 越界保护
? 存取控制保护
四、分段存储管理的优缺点
? 优点,
– 便于处理变化的数
据结构
– 便于共享
– 提供虚存的功能
– 提供动态连接的便
利
– 便于控制存取访问
? 缺点,
– 要为存储紧缩付出处
理机机时的代价
– 分段的最大尺寸受到
主存大小的限制
– 在外存中管理可变尺
寸的分段比较困难
– 与分页一样，提高了
硬件成本
9.4 段页式存储管理
? 基本概念
? 地址转换
? 存储管理算法
? 优缺点
一、段页式存储管理的基本概念
? 等分主存：页架、页架号
? 进程的地址空间采用分段的方式
? 每一段采用分页的方法
? 逻辑地址结构：（ s,p,d）
? 主存分配：以页为单位非连续分配
? 数据结构：段表、页表、段表地址寄存器
段号
段内地址
页号 页内地址
二、段页式管理的地址转换
段表地址寄存器
段号 S 页号 P 页内地址 d
S′ S′
P
P′ 页架号 d
b
s
+
L b 虚地址
实地址
S P P′
段表
页表
快表
快表的内容
段号 虚页号 页架号 保护信息 AGE 有效位
三、段页式存储管理算法
9.5 页的置换算法
? 页面访问失效及处理
? 页面置换算法
一、页面访问失效及处理
引起失效的原因,
? 边界错误
纯分页,页号超过页表长度
纯分段,偏移量超过段长，段号超过段表长度
段页式,页号超过该段的页表长度
? 有效性错误,缺页或缺段中断
? 保护错误,访问权限错误
二、页面置换算法
? 最佳置换算法 OPT
? 先进先出置换算法 FIFO
? 最近最少使用置换算法 LRU
? 最近未使用置换算法 NUR
? 两次机会置换算法
? 时钟页面置换算法 CLOCK
1、最佳置换算法 OPT
原则：淘汰将来再也不被访问，或者是在
最远的将来才被访问的页。
举例
如果页面的引用顺序为 2,3,2,1,5,2,
4,5,3,2,5,2，而分配给它们内存页
架数为 3，用 OPT计算它的缺页次数。
2 3 2 1 5 2 4 5 3 2 5 2
2 2 2 2 2 2* 4* 4* 4* 2 2 2 3 3 3 3* 3 3 3 3 3* 3* 3*
1* 5 5 5 5 5 5 5 5 OPT
调 调 中 调 替 中 替 中 中 替 中 中
2、先进先出置换算法 FIFO
? 原则：选择最早进入主存的页面淘汰
? 缺点,
– 最早进入主存的页面可能是经常被使用的页
– 异常现象：进程所分的页架数越多，缺页次
数也越多
举例
如果页面的引用顺序为 2,3,2,1,5,2,
4,5,3,2,5,2，而分配给它们内存页
架数为 3，用 FIFO计算它的缺页次数。
2 3 2 1 5 2 4 5 3 2 5 2
2 2 2 2* 5 5 5* 5* 3 3 3 3
3 3 3 3* 2 2 2 2* 2* 5 5 1 1 1* 4 4 4 4 4* 2
调 调 中 调 替 替 替 中 替 中 替 替
FIFO
例 2：计算缺页次数
某程序在内存中分配 m页，初始为空，
页面走向为 1,2,3,4,1,2,5，
1,2,3,4,5。当 m=3,m=4时缺
页中断分别为多少？用 FIFO算法。
例子 2：计算缺页次数
m=3时，缺页中断 9次
m=4时，缺页中断 10次
当分配给进程的页架数增加时，缺页
次数反而增加。
3、最近最少使用置换算法 LRU
? 原则：选择最长时间未被访问的页面
? 基于程序的局部性原理，命中率较高
? 实现较困难
? 方法：计数法
n?n距阵法
举例
如果页面的引用顺序为 2,3,2,1,5,2,
4,5,3,2,5,2，而分配给它们内存页
架数为 3，用 LRU计算它的缺页次数。
1）计数法
设置一个计数器，一页一个，初值为 0。
每执行一条指令后，计数器自动计数 。
发生缺页中断时，选择计数器值最小
的一页淘汰
举例
如果页面的引用顺序为 2,3,2,1,5,2,
4,5,3,2,5,2，而分配给它们内存页
架数为 3，用 LRU计算它的缺页次数。（计
数法）
2 3 2 1 5 2 4 5 3 2 5 2
2 2 2 2 2* 2 2 2* 3 3 3* 3*
3 3 3* 5 5 5* 5 5 5* 5 5 1 1 1* 4 4 4* 2 2 2
调 调 中 调 替 中 替 中 替 替 中 中
LRU
2）矩阵法
设有 n个页架，系统维持一个 n ? n的
矩阵，开始时所有位均为 0。在页 j被
访问到时，首先把第 j行的所有位设
置为 1，再把第 j列的所有位设置成 0。
在任何时刻二进制值最小的行所对
应的页架就是最近最少使用的。
4、最近未使用置换算法 NUR
? 原则,1、淘汰未被访问过的页
2、淘汰未被修改过的页
? 硬件：每页增设两个硬件位,访问位，修改位
? 实现：初始：访问位, 修改位置 0；
访问位被定期清零
发生缺页中断时，系统检查访问位，修改位,
第 0类：无访问，无修改
第 1类：无访问，有修改
第 2类：有访问，无修改
第 3类：有访问，有修改
系统随机从编号最小的非空类中选择一页淘汰
5、二次机会置换算法
? 原则：按照先进先出算法选择某一页面，
检查其访问位，如果为 0，则淘汰该页；
如果为 1，则给第二次机会，将该页移至
队列末尾，并将访问位置 0。
? 命中率优于 FIFO
二次机会算法的操作
A B C D E F G H
最先装入的页面 最后装入的页面
B C D E F G H A
将 A作为刚装入页面
6、时钟页面置换算法 CLOCK
两次机会置换算法的改进。
? 实现方法：把所有的页面保存在一个类
似时钟表面的环形链表中。有一个指针
指向最老的页面。
时钟页面置换算法
A L
K
J
I
H
G
F
E
D
C
B
举例
如果页面的引用顺序为 2,3,2,1,5,2,
4,5,3,2,5,2，而分配给它们内存页
架数为 3，用 CLOCK计算它的缺页次数。
2 3 2 1 5 2 4 5 3 2 5 2
,2, 2, 2*, 2* 2 2*, 2*, 2*, 2, 2*, 2*, 2*
3 3 3 5 5 5 5* 5 5 5* 5*
1, 1, 1 4 4 3 3 3 3 CLOCK
调 调 中 调 替 中 替 中 替 中 中 中
9.6 页架分配策略
? 物理主存
? 空闲页面链表
? 页架分配中有关策略
? 分页环境中程序的行为特性
1、物理主存
非换页池 换页主存池 错误缓冲
内核代码
（常驻主存）
用户
进程
内核代码
（动态分配）
错误信息
与主存相关的数据结构,
? 主存映射图：描述物理主存
? 页表：描述虚存
? 磁盘映射图：描述交换区
? 资源映射图：实现资源（页表、交
换区）分配
2、空闲页面链表
特点,
? 用一专门的独立进程负责页面替换
工作
? 链表中的页面并非真正空闲页面
? 置换并不是页在主存中的移动
3、页架分配中有关策略
? 调入策略（提前分页，请求分页）
? 局部和全局置换，固定和可变分配
? 工作集
? 页的大小
局部和全局置换，固定和可变分配
? 固定分配：分配给进程的页架数不变。
? 可变分配：分配给进程的页架数是可变的。
? 全局置换：从整个主存中选择淘汰页。
? 局部置换：从自己以占有的页架中选择淘汰
页。
局部、全局置换与固定、可变分配之间的关系
局部置换 全局置换
（ 1）一个进程的页架数固定
固定分配 （ 2）从分配给该进程的页架中 不可能
选择被替换的页
（ 1）分配给进程的页架数不断 从主存中所有可用页
可变分配 变化 架中选择被替换的页
（ 2）从分配给进程的页架中 使进程页架数不断变
选择被替换的页 化
工作集模型
基本思想：根据程序的局部性原理，
一般情况下，进程在一段时间内总是
集中访问一些页面，这些页面称为活
跃页面，如果分配给一个进程的页架
数太少了，使该进程所需的活跃页面
不能全部装入内存，则进程在运行过
程中将频繁发生中断。
如果能为进程提供与活跃页面数相等
的页架数，则可减少缺页中断次数。
工作集
一个运行进程在 t-w到 t这个时间间隔内所
访问的页的集合称为该进程在时间 t的工作
集，记为 W（ t,w）
W（ t,w） 为工作集尺寸：工作集中包含
的页面数。
w:对于给定的访问序列选取定长的区间，
称为工作集窗口
工作集,
内容取决于页的三个因素
a 访页序列特性
b 时刻 Ti
c 窗口长度 (△ )
例,
26157775162341234443434441327
| |t1 | |t2
w(t1 ) ={1,2,5,6,7}
w(t2 ) ={3,4}
页的大小
? 大页面：页内碎片多，缺页次数多
? 小页面：页表空间大
? 大页面：可减少输入输出工作
? 大页面：解决程序局部性降低，快表命
中率降低的问题
4、分页环境中程序的行为特性
? 局部性的概念
? 分页环境中程序的行为特性
? 减少访问离散性的程序结构
（ 1）局部性的概念
? 时间局部性：某个位置最近被访问，那
么往往很快又要被访问。
? 空间局部性：某个位置最近被访问，则
它附近的位置也会被访问。
（ 3）减少访问离散性的程序结构
For j:=1 to 128
do For i:=1 to 128
do A[i,j]:=0
For i:=1 to 128
do For j:=1 to 128
do A[i,j]:=0
若以行序为主序存数
第一种编制：程序执行产
生 128*128次缺页
第二种编制：程序执行产
生 128次缺页
方法 功能 分区式 页式 段式 段页式
固定 可变 静态 动态
适用环境 多道 多道 多道 多道
重定位 静态 动态 动态 动态 动态
分配方式 分配连续区 以页为单位非连续 以段为单位非连续 以页为单位非连续
释放 执行完 全部释放 分区释放 执行完 全部释放 淘汰与执行完释放 同左 同左
保护 同左 同左 越界保护与存储键 越界保护与控制权保护
同左 同左
共享 不能 较难 方便 方便
硬件支持 保护用寄存器重定位机构 地址变换机构中断机构
保护机构
地址变换机构
中断机构保护
机构动态链接
机构
9.7 共享主存，快表一致性问题
? 主存共享
? 快表一致性问题
1、主存共享
? 内核支持相关进程间的 copy_on_write页
面级共享技术
? 支持传统的共享主存区的进程间的通讯
? 通过存储映射接口实现共享功能
2、快表一致性问题
? 概念
? 单处理机的快表一致性问题
? 多处理机的快表一致性问题
方法 功能 分区式 页式 段式 段页式
固定 可变 静态 动态
适用环境 多道 多道 多道 多道
虚拟空间 一维 一维 二维 二维
重定位 静态 动态 动态 动态 动态
分配方式 分配连续区 以页为单位非连续 以段为单位非连续 以页为单位非连续
释放 执行完全部释放 分区释放 执行完全部释放 淘汰与执行完释放 同左 同左
保护 同左 同左 越界保护与存储键
覆盖与交换
越界保护与
控制权保护
同左 同左
同左
同左
内外存统一
管理虚存 内存扩充
共享 不能 较难 方便 方便
硬件支持 保护用寄存器重定位机构 地址变换机构中断机构
保护机构
地址变换机构
中断机构保护
机构动态链接
机构
清除快表表项的三种方法
? 清除一个对应某虚页的快表表项
? 清除整个快表
? 装入一个新的快表表目
单处理器上的快表一性
需要清除快表表目的情况,
? 保护权限变化
? 被置换出去
? 进程上下文切换
? exec:进程调用 exec执行另一程序
6、页架分配算法
? 物理主存
? 空闲页面链表
? 页架分配中有关策略
? 分页环境中程序的行为特性
空闲页面链表
页架分配中有关策略
? 调入策略（预调，请调）
? 局部和全局置换，固定和可变分配
? 工作集
? 页的大小
局部和全局置换，固定和可变
分配
? 固定分配：进程的页架数不变。
? 可变分配：进程的页架数是可变的。
? 全局置换：从整个主存中选择淘汰页。
? 局部置换：从自己以占有的页架中选择
淘汰页。
工作集
一个运行进程在 t-w到 t这个时间间隔内所
访问的页的集合称为该进程在时间 t的工作
集，记为 W（ t,w）
W（ t,w） 为工作集尺寸：工作集中包含
的页面数。
页的大小
? 大页面：页内碎片多，缺页次数多
? 小页面：页表空间大
? 大页面：可减少输入输出工作
分页环境中程序的行为特性
? 局部性的概念
? 分页环境中程序的行为特性
? 减少访问离散性的程序结构
局部性的概念
? 时间局部性：某个位置最近被访问，那
么往往很快又要被访问。
? 空间局部性：某个位置最近被访问，则
它附近的位置也会被访问。
减少访问离散性的程序结构
For j:=1 to 512
do For i:=1 to 512
do A[i,j]:=0
For i:=1 to 512
do For j:=1 to 512
do A[i,j]:=0
若以行序为主序存数
第一种编制：程序执行产
生 512*512=262144次缺页
第二种编制：程序执行产
生 512次缺页
7、共享主存，快表一致性问题
? 主存共享
? 快表一致性问题
主存共享
? 内核支持相关进程间的 copy_on_write页
面级共享技术
? 支持传统的共享主存区的进程间的通讯
? 通过存储映射接口实现共享功能
快表一致性问题
? 概念
? 单处理机的快表一致性问题
? 多处理机的快表一致性问题
方法 功能 分区式 页式 段式 段页式
固定 可变 静态 动态
适用环境 多道 多道 多道 多道
虚拟空间 一维 一维 二维 二维
重定位 静态 动态 动态 动态 动态
分配方式 分配连续区 以页为单位非连续 以段为单位非连续 以页为单位非连续
释放 执行完全部释放 分区释放 执行完全部释放 淘汰与执行完释放 同左 同左
保护 同左 同左 越界保护与存储键
覆盖与交换
越界保护与
控制权保护
同左 同左
同左
同左
内外存统一
管理虚存 内存扩充
共享 不能 较难 方便 方便
硬件支持 保护用寄存器重定位机构 地址变换机构中断机构
保护机构
地址变换机构
中断机构保护
机构动态链接
机构
1、虚拟存储系统的基本概念
2、分页存储管理
3、分段存储管理
4、段页式存储管理
5、页（段）的置换算法和系统行为
6、页架分配算法
9.1 虚拟存储系统的基本概念
1、问题的提出
? 程序大于内存
? 程序暂时不执行或运行完是否还要占
用内存
2、基本思想
程序、数据的大小可以超过内存的大小，
操作系统把程序当前使用的部分保留在
主存，而把其它部分保存在辅存中，并
在需要时在主存和辅存之间动态交换 。
把辅存当作主存进行扩充，对用户来说，
计算机系统有一个容量很大的主存。
?虚存的优点,
可容纳大量的进程，提高系统多道并行
程度，提高主存和其他资源的利用率，
提高系统运行效率和系统吞吐率
?虚存的缺点,
（ 1）额外的主存开销
（ 2）地址转换增加了指令执行时间
9.2 分页存储管理
? 基本概念
? 地址转换
? 硬件支持
? 页的共享
一、分页存储管理的基本概念
? 等分主存：页架、页架号
? 用户逻辑地址空间的分页：页、页号
? 逻辑地址的表示：（页号 p,页内地址 d）
? 分配原则：以页架为基本分配单位
? 页表：页号、页架号
? 分页系统中的地址结构,
– 页号 ?最大页数
– 页内地址 ?页架的大小
? 页面尺寸应是 2的幂
基本工作原理
在程序开始运行之前，不是装入全部
页面，而是装入一个或零个页面，之
后根据程序运行的需要，动态装入其
它页面；当内存空间已满，而又需要
装入新的页面时，则根据某种算法淘
汰某个页面，以便装入新的页面
X
X
X
X
7
X
5
X
X
X
3
4
0
6
1
2
60K-64K
56K-60K
52K-56K
48K-52K
44K-48K
40K-44K
36K-40K
32K-36K
28K-32K
24K-28K
20K-24K
16K-20K
12K-16K
8K-12K
4K-8K
0K-4K
28K-32K
24K-28K
20K-24K
16K-20K
12K-16K
8K-12K
4K-8K
0K-4K
虚地址空间
物理地址空间
} 虚页
页架
二、分页系统中的地址转换
? 直接映象页地址转换
? 多级页表地址转换
? 快表的地址转换
1、直接映象页地址转换
P d
p'
+
L b
p' d
P
页表
页表地址寄存器
虚地址 v=(p,d)
实地址
b
0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0
1 1 0 0 0 0 0 0 0 0 0 0 1 0 0
110
在 /不在内存
页表
虚地址
8196
物理地址
24580
000 0 15
000 0 14
000 0 13
000 0 12
111 1 11
000 0 10
101 1 9
000 0 8
000 0 7
000 0 6
011 1 5
100 1 4
000 1 3
110 1 2
001 1 1
010 1 0
页号 页架号 状态
2、多级页表地址转换
解决页表非常大的问题
访存次数增加，增加一级页表，增加一次
访存次数。
3、快表的地址转换
页号 页内地址
页号 页架号
页架号 页内地址
虚地址
物理地址 快表
p’
页表
地址越界
l
比较
P>=1
p p’
,,,
快表
b
+
页号 p 页内地址 d
P’ d
物理地址
页表地址寄存器 页表长度寄存器 逻辑地址
举例
如果查找快表花费的时间是 50NS,访问内
存的时间是 750NS,试计算命中率为 80%,
90%时实际的访存时间。
页号在快表：存取时间为 50+750=800NS
页号在慢表：存取时间为 750+750=1500NS
命中率为 80% 存取时间为 0.8*800+0.2*1500=940NS
命中率为 90% 存取时间为 0.9*800+0.1*1500=870NS
三、硬件支持
? 主存管理单元 MMU
? 页表
? 快表
? 反向页表
1、主存管理单元 MMU
? 页表地址寄存器：页表始址，长度
? 虚地址分成虚页号和页内地址
? 判断有越界访问和保护性错误
页表中
有效位 保护权限
2、页表
实现页式管理重要的数据结构
内容：页架号
修改位
有效位
引用位
保护权限
3、快表
为加快地址转换而使用高速缓存
内容：页号
页架号
保护权限
4、反向页表
完成物理页架号到虚地址的映射
内容：虚页号
物理页架号
指向哈希链的下一项指针
有效位，修改位，引用位
保护和加锁信息
9.3 分段存储管理
? 基本概念
? 地址转换
一、分段存储管理的基本概念
? 进程的逻辑地址空间：段、段号
? 程序的地址结构：（段号 s,段内地址 w）
段号 ?最多段数 段内地址 ?最大段长
? 主存分配：以段为单位
? 段表和段表寄存器
– 段表：段号、段的长度、段在主存中的起始地
址、段的状态位、访问位、修改位、段的外存
地址
– 段表寄存器：段表起始地址、段表长度
段的动态链接
在程序开始运行时，只将主程序段装
配好并调入内存，其它各段的装配是
在主程序段的运行过程中逐步完成。
每当需要调用一个新段时，再将这个
新段装配好，并与主程序段链接。
二、分段存储管理地址转换
段表长 段表地址
段号 段内地址
+
段表
S′ l
L b
S w
b
s
+
实地址
段表地址寄存器
虚地址
Cl
Cb
+
段号 S 段内地址 d
比较
比较
b + d
段 表
S>= Cl
快表
物理地址
段表始址寄存器 段表长度寄存器 逻辑地址
l b
.,,
S l b
地址越界 d>=1
d>=1
地址映射及存储保护机制
地址越界
地址越界
比较
举例
段长 段起始地址 有效位
0 200 500 1
1 400 1000 1
2 100 1400 0
3 900 2000 1
虚地址：（ 2,250）,（ 4,470）完成实地址转换
1,缺段中断
2,越界
三、存储保护问题
? 越界保护
? 存取控制保护
四、分段存储管理的优缺点
? 优点,
– 便于处理变化的数
据结构
– 便于共享
– 提供虚存的功能
– 提供动态连接的便
利
– 便于控制存取访问
? 缺点,
– 要为存储紧缩付出处
理机机时的代价
– 分段的最大尺寸受到
主存大小的限制
– 在外存中管理可变尺
寸的分段比较困难
– 与分页一样，提高了
硬件成本
9.4 段页式存储管理
? 基本概念
? 地址转换
? 存储管理算法
? 优缺点
一、段页式存储管理的基本概念
? 等分主存：页架、页架号
? 进程的地址空间采用分段的方式
? 每一段采用分页的方法
? 逻辑地址结构：（ s,p,d）
? 主存分配：以页为单位非连续分配
? 数据结构：段表、页表、段表地址寄存器
段号
段内地址
页号 页内地址
二、段页式管理的地址转换
段表地址寄存器
段号 S 页号 P 页内地址 d
S′ S′
P
P′ 页架号 d
b
s
+
L b 虚地址
实地址
S P P′
段表
页表
快表
快表的内容
段号 虚页号 页架号 保护信息 AGE 有效位
三、段页式存储管理算法
9.5 页的置换算法
? 页面访问失效及处理
? 页面置换算法
一、页面访问失效及处理
引起失效的原因,
? 边界错误
纯分页,页号超过页表长度
纯分段,偏移量超过段长，段号超过段表长度
段页式,页号超过该段的页表长度
? 有效性错误,缺页或缺段中断
? 保护错误,访问权限错误
二、页面置换算法
? 最佳置换算法 OPT
? 先进先出置换算法 FIFO
? 最近最少使用置换算法 LRU
? 最近未使用置换算法 NUR
? 两次机会置换算法
? 时钟页面置换算法 CLOCK
1、最佳置换算法 OPT
原则：淘汰将来再也不被访问，或者是在
最远的将来才被访问的页。
举例
如果页面的引用顺序为 2,3,2,1,5,2,
4,5,3,2,5,2，而分配给它们内存页
架数为 3，用 OPT计算它的缺页次数。
2 3 2 1 5 2 4 5 3 2 5 2
2 2 2 2 2 2* 4* 4* 4* 2 2 2 3 3 3 3* 3 3 3 3 3* 3* 3*
1* 5 5 5 5 5 5 5 5 OPT
调 调 中 调 替 中 替 中 中 替 中 中
2、先进先出置换算法 FIFO
? 原则：选择最早进入主存的页面淘汰
? 缺点,
– 最早进入主存的页面可能是经常被使用的页
– 异常现象：进程所分的页架数越多，缺页次
数也越多
举例
如果页面的引用顺序为 2,3,2,1,5,2,
4,5,3,2,5,2，而分配给它们内存页
架数为 3，用 FIFO计算它的缺页次数。
2 3 2 1 5 2 4 5 3 2 5 2
2 2 2 2* 5 5 5* 5* 3 3 3 3
3 3 3 3* 2 2 2 2* 2* 5 5 1 1 1* 4 4 4 4 4* 2
调 调 中 调 替 替 替 中 替 中 替 替
FIFO
例 2：计算缺页次数
某程序在内存中分配 m页，初始为空，
页面走向为 1,2,3,4,1,2,5，
1,2,3,4,5。当 m=3,m=4时缺
页中断分别为多少？用 FIFO算法。
例子 2：计算缺页次数
m=3时，缺页中断 9次
m=4时，缺页中断 10次
当分配给进程的页架数增加时，缺页
次数反而增加。
3、最近最少使用置换算法 LRU
? 原则：选择最长时间未被访问的页面
? 基于程序的局部性原理，命中率较高
? 实现较困难
? 方法：计数法
n?n距阵法
举例
如果页面的引用顺序为 2,3,2,1,5,2,
4,5,3,2,5,2，而分配给它们内存页
架数为 3，用 LRU计算它的缺页次数。
1）计数法
设置一个计数器，一页一个，初值为 0。
每执行一条指令后，计数器自动计数 。
发生缺页中断时，选择计数器值最小
的一页淘汰
举例
如果页面的引用顺序为 2,3,2,1,5,2,
4,5,3,2,5,2，而分配给它们内存页
架数为 3，用 LRU计算它的缺页次数。（计
数法）
2 3 2 1 5 2 4 5 3 2 5 2
2 2 2 2 2* 2 2 2* 3 3 3* 3*
3 3 3* 5 5 5* 5 5 5* 5 5 1 1 1* 4 4 4* 2 2 2
调 调 中 调 替 中 替 中 替 替 中 中
LRU
2）矩阵法
设有 n个页架，系统维持一个 n ? n的
矩阵，开始时所有位均为 0。在页 j被
访问到时，首先把第 j行的所有位设
置为 1，再把第 j列的所有位设置成 0。
在任何时刻二进制值最小的行所对
应的页架就是最近最少使用的。
4、最近未使用置换算法 NUR
? 原则,1、淘汰未被访问过的页
2、淘汰未被修改过的页
? 硬件：每页增设两个硬件位,访问位，修改位
? 实现：初始：访问位, 修改位置 0；
访问位被定期清零
发生缺页中断时，系统检查访问位，修改位,
第 0类：无访问，无修改
第 1类：无访问，有修改
第 2类：有访问，无修改
第 3类：有访问，有修改
系统随机从编号最小的非空类中选择一页淘汰
5、二次机会置换算法
? 原则：按照先进先出算法选择某一页面，
检查其访问位，如果为 0，则淘汰该页；
如果为 1，则给第二次机会，将该页移至
队列末尾，并将访问位置 0。
? 命中率优于 FIFO
二次机会算法的操作
A B C D E F G H
最先装入的页面 最后装入的页面
B C D E F G H A
将 A作为刚装入页面
6、时钟页面置换算法 CLOCK
两次机会置换算法的改进。
? 实现方法：把所有的页面保存在一个类
似时钟表面的环形链表中。有一个指针
指向最老的页面。
时钟页面置换算法
A L
K
J
I
H
G
F
E
D
C
B
举例
如果页面的引用顺序为 2,3,2,1,5,2,
4,5,3,2,5,2，而分配给它们内存页
架数为 3，用 CLOCK计算它的缺页次数。
2 3 2 1 5 2 4 5 3 2 5 2
,2, 2, 2*, 2* 2 2*, 2*, 2*, 2, 2*, 2*, 2*
3 3 3 5 5 5 5* 5 5 5* 5*
1, 1, 1 4 4 3 3 3 3 CLOCK
调 调 中 调 替 中 替 中 替 中 中 中
9.6 页架分配策略
? 物理主存
? 空闲页面链表
? 页架分配中有关策略
? 分页环境中程序的行为特性
1、物理主存
非换页池 换页主存池 错误缓冲
内核代码
（常驻主存）
用户
进程
内核代码
（动态分配）
错误信息
与主存相关的数据结构,
? 主存映射图：描述物理主存
? 页表：描述虚存
? 磁盘映射图：描述交换区
? 资源映射图：实现资源（页表、交
换区）分配
2、空闲页面链表
特点,
? 用一专门的独立进程负责页面替换
工作
? 链表中的页面并非真正空闲页面
? 置换并不是页在主存中的移动
3、页架分配中有关策略
? 调入策略（提前分页，请求分页）
? 局部和全局置换，固定和可变分配
? 工作集
? 页的大小
局部和全局置换，固定和可变分配
? 固定分配：分配给进程的页架数不变。
? 可变分配：分配给进程的页架数是可变的。
? 全局置换：从整个主存中选择淘汰页。
? 局部置换：从自己以占有的页架中选择淘汰
页。
局部、全局置换与固定、可变分配之间的关系
局部置换 全局置换
（ 1）一个进程的页架数固定
固定分配 （ 2）从分配给该进程的页架中 不可能
选择被替换的页
（ 1）分配给进程的页架数不断 从主存中所有可用页
可变分配 变化 架中选择被替换的页
（ 2）从分配给进程的页架中 使进程页架数不断变
选择被替换的页 化
工作集模型
基本思想：根据程序的局部性原理，
一般情况下，进程在一段时间内总是
集中访问一些页面，这些页面称为活
跃页面，如果分配给一个进程的页架
数太少了，使该进程所需的活跃页面
不能全部装入内存，则进程在运行过
程中将频繁发生中断。
如果能为进程提供与活跃页面数相等
的页架数，则可减少缺页中断次数。
工作集
一个运行进程在 t-w到 t这个时间间隔内所
访问的页的集合称为该进程在时间 t的工作
集，记为 W（ t,w）
W（ t,w） 为工作集尺寸：工作集中包含
的页面数。
w:对于给定的访问序列选取定长的区间，
称为工作集窗口
工作集,
内容取决于页的三个因素
a 访页序列特性
b 时刻 Ti
c 窗口长度 (△ )
例,
26157775162341234443434441327
| |t1 | |t2
w(t1 ) ={1,2,5,6,7}
w(t2 ) ={3,4}
页的大小
? 大页面：页内碎片多，缺页次数多
? 小页面：页表空间大
? 大页面：可减少输入输出工作
? 大页面：解决程序局部性降低，快表命
中率降低的问题
4、分页环境中程序的行为特性
? 局部性的概念
? 分页环境中程序的行为特性
? 减少访问离散性的程序结构
（ 1）局部性的概念
? 时间局部性：某个位置最近被访问，那
么往往很快又要被访问。
? 空间局部性：某个位置最近被访问，则
它附近的位置也会被访问。
（ 3）减少访问离散性的程序结构
For j:=1 to 128
do For i:=1 to 128
do A[i,j]:=0
For i:=1 to 128
do For j:=1 to 128
do A[i,j]:=0
若以行序为主序存数
第一种编制：程序执行产
生 128*128次缺页
第二种编制：程序执行产
生 128次缺页
方法 功能 分区式 页式 段式 段页式
固定 可变 静态 动态
适用环境 多道 多道 多道 多道
重定位 静态 动态 动态 动态 动态
分配方式 分配连续区 以页为单位非连续 以段为单位非连续 以页为单位非连续
释放 执行完 全部释放 分区释放 执行完 全部释放 淘汰与执行完释放 同左 同左
保护 同左 同左 越界保护与存储键 越界保护与控制权保护
同左 同左
共享 不能 较难 方便 方便
硬件支持 保护用寄存器重定位机构 地址变换机构中断机构
保护机构
地址变换机构
中断机构保护
机构动态链接
机构
9.7 共享主存，快表一致性问题
? 主存共享
? 快表一致性问题
1、主存共享
? 内核支持相关进程间的 copy_on_write页
面级共享技术
? 支持传统的共享主存区的进程间的通讯
? 通过存储映射接口实现共享功能
2、快表一致性问题
? 概念
? 单处理机的快表一致性问题
? 多处理机的快表一致性问题
方法 功能 分区式 页式 段式 段页式
固定 可变 静态 动态
适用环境 多道 多道 多道 多道
虚拟空间 一维 一维 二维 二维
重定位 静态 动态 动态 动态 动态
分配方式 分配连续区 以页为单位非连续 以段为单位非连续 以页为单位非连续
释放 执行完全部释放 分区释放 执行完全部释放 淘汰与执行完释放 同左 同左
保护 同左 同左 越界保护与存储键
覆盖与交换
越界保护与
控制权保护
同左 同左
同左
同左
内外存统一
管理虚存 内存扩充
共享 不能 较难 方便 方便
硬件支持 保护用寄存器重定位机构 地址变换机构中断机构
保护机构
地址变换机构
中断机构保护
机构动态链接
机构
清除快表表项的三种方法
? 清除一个对应某虚页的快表表项
? 清除整个快表
? 装入一个新的快表表目
单处理器上的快表一性
需要清除快表表目的情况,
? 保护权限变化
? 被置换出去
? 进程上下文切换
? exec:进程调用 exec执行另一程序
6、页架分配算法
? 物理主存
? 空闲页面链表
? 页架分配中有关策略
? 分页环境中程序的行为特性
空闲页面链表
页架分配中有关策略
? 调入策略（预调，请调）
? 局部和全局置换，固定和可变分配
? 工作集
? 页的大小
局部和全局置换，固定和可变
分配
? 固定分配：进程的页架数不变。
? 可变分配：进程的页架数是可变的。
? 全局置换：从整个主存中选择淘汰页。
? 局部置换：从自己以占有的页架中选择
淘汰页。
工作集
一个运行进程在 t-w到 t这个时间间隔内所
访问的页的集合称为该进程在时间 t的工作
集，记为 W（ t,w）
W（ t,w） 为工作集尺寸：工作集中包含
的页面数。
页的大小
? 大页面：页内碎片多，缺页次数多
? 小页面：页表空间大
? 大页面：可减少输入输出工作
分页环境中程序的行为特性
? 局部性的概念
? 分页环境中程序的行为特性
? 减少访问离散性的程序结构
局部性的概念
? 时间局部性：某个位置最近被访问，那
么往往很快又要被访问。
? 空间局部性：某个位置最近被访问，则
它附近的位置也会被访问。
减少访问离散性的程序结构
For j:=1 to 512
do For i:=1 to 512
do A[i,j]:=0
For i:=1 to 512
do For j:=1 to 512
do A[i,j]:=0
若以行序为主序存数
第一种编制：程序执行产
生 512*512=262144次缺页
第二种编制：程序执行产
生 512次缺页
7、共享主存，快表一致性问题
? 主存共享
? 快表一致性问题
主存共享
? 内核支持相关进程间的 copy_on_write页
面级共享技术
? 支持传统的共享主存区的进程间的通讯
? 通过存储映射接口实现共享功能
快表一致性问题
? 概念
? 单处理机的快表一致性问题
? 多处理机的快表一致性问题
方法 功能 分区式 页式 段式 段页式
固定 可变 静态 动态
适用环境 多道 多道 多道 多道
虚拟空间 一维 一维 二维 二维
重定位 静态 动态 动态 动态 动态
分配方式 分配连续区 以页为单位非连续 以段为单位非连续 以页为单位非连续
释放 执行完全部释放 分区释放 执行完全部释放 淘汰与执行完释放 同左 同左
保护 同左 同左 越界保护与存储键
覆盖与交换
越界保护与
控制权保护
同左 同左
同左
同左
内外存统一
管理虚存 内存扩充
共享 不能 较难 方便 方便
硬件支持 保护用寄存器重定位机构 地址变换机构中断机构
保护机构
地址变换机构
中断机构保护
机构动态链接
机构
