第九章 虚拟存储管理
第 9章 虚拟存储管理
? 9.1虚拟存储系统的基本概念
? 9.2 分页存储管理
? 9.3 分段存储管理
? 9.4 段页式存储管理
? 9.5 页的置换算法
? 9.6页架的分配策略
? 9.7 主存共享、快表一致性问题
第九章 虚拟存储管理
9.1 虚拟存储系统的基本概念
? 虚拟存储器
? 指一种实际上并不以物理形式存在的虚假的存储器
? 虚拟地址
? 一个运行进程访问的地址
? 实地址
? 处理器可直接访问的地址
? 虚拟存储技术
? 在逻辑上把内存的容量扩大，利用硬盘空间作为虚
拟内存。
第九章 虚拟存储管理
9.1 虚拟存储系统的基本概念
? 局部性原理 (principle of locality),
? 指程序在执行过程中的一个较短时期，所
执行的指令地址和指令的操作数地址，分
别局限于一定区域。还可以表现为,
? 时间局部性：一条指令的一次执行和下次执行，
一个数据的一次访问和下次访问都集中在一个
较短时期内；
? 空间局部性：当前指令和邻近的几条指令，当
前访问的数据和邻近的数据都集中在一个较小
区域内。
第九章 虚拟存储管理
9.1 虚拟存储系统的基本概念
? 局部性原理的具体体现
? 程序在执行时，大部分是顺序执行的指令，
少部分是转移和过程调用指令。
? 过程调用的嵌套深度一般不超过 5，因此执
行的范围不超过这组嵌套的过程。
? 程序中存在相当多的循环结构，它们由少量
指令组成，而被多次执行。
? 程序中存在相当多对一定数据结构的操作，
如数组操作，往往局限在较小范围内。
第九章 虚拟存储管理
9.1 虚拟存储系统的基本概念
? 虚拟存储原理
? 在程序装入时，不必将其全部读入到内存，而只需
将当前需要执行的部分页或段读入到内存，就可让
程序开始执行。
? 在程序执行过程中，如果需执行的指令或访问的数
据尚未在内存（称为缺页或缺段），则由处理器通
知操作系统将相应的页或段调入到内存，然后继续
执行程序。
? 另一方面，操作系统将内存中暂时不使用的页或段
调出保存在外存上，从而腾出空间存放将要装入的
程序以及将要调入的页或段。只需程序的一部分在
内存就可执行。
第九章 虚拟存储管理
9.1 虚拟存储系统的基本概念
? 引入虚拟存储技术的好处
? 大程序：可在较小的可用内存中执行较大的
用户程序；
? 大的用户空间：提供给用户可用的虚拟内存
空间通常大于物理内存 (real memory)
? 并发：可在内存中容纳更多程序并发执行；
? 易于开发：与覆盖技术比较，不必影响编程
时的程序结构
第九章 虚拟存储管理
9.1 虚拟存储系统的基本概念
? 虚拟存储技术的特征
? 不连续性：物理内存分配的不连续，虚拟地
址空间使用的不连续（数据段和栈段之间的
空闲空间，共享段和动态链接库占用的空间）
? 部分交换：与交换技术相比较，虚拟存储的
调入和调出是对部分虚拟地址空间进行的；
? 大空间：通过物理内存和快速外存相结合，
提供大范围的虚拟地址空间
? 总容量不超过物理内存和外存交换区容量之和
第九章 虚拟存储管理
9.2 分页存储管理
? 在简单页式存储管理的基础上，增加请求
调页和页面置换功能。
? 分页系统中的地址转换
? 硬件支持
第九章 虚拟存储管理
9.2 分页存储管理
? 分页系统中的地址转换（直接地址转换）
页表始址 页表长度
页表寄存器
2
页号 页内偏移量
100
+
2 0
4 1
5 2
3
页架 页号
页表 +
10340
物理地址
2
4
5
内存空间
第九章 虚拟存储管理
9.2 分页存储管理
? 分页系统中的地址转换（多级页表）
? 当内存增大时，页表也会很大，如果页表全
部放进主存，也要占用很大的空间
? 对页表分页，为了管理这些页表，设置一个
页表目录（顶级页表）
? 随着内存的增大，也可以使用三级、四级页
表
第九章 虚拟存储管理
d p2 p1
页目录号 页号 页内地址
31 22 21 12 11 0
逻辑
地址
页目录表寄存器 +
页目录
+
页表 物理地址
第九章 虚拟存储管理
9.2 分页存储管理
? 直接转换和多级页表地址转换的一个主
要问题：访问速度
? 一级页表：取一条指令需要访问内存 2次
? 二级页表：取一条指令需要访问内存 3次
? ……
第九章 虚拟存储管理
9.2 分页存储管理
? 页表的结构
? 页表是一个二维数组，每个表目对应一个虚
页
? 虚拟页号：进程虚地址空间划分的页；
? 物理页架号；
? 修改位：表示该页是否被修改过；
? 有效位：表示该页是否在主存中；
? 引用位：表示该页是否被访问过，用于页面调度；
? 保护权限：说明该页允许什么样的访问。
第九章 虚拟存储管理
9.2 分页存储管理
? 反向页表地址转换
? 以上策略为每个进程配置一张页表，进程的逻辑空
间每一页在页表中一个表项 — 页表非常庞大。
? 反置页表,为每一物理块 (页框 )分配一个表项，按
物理块号排序，表项的内容是页号及所属的进程标
识符。
? 反置页表的优缺点,
? 页表的大小与物理空间有关。
? 只包含调入内存的页面，没有包括未调入内存的进程页面。
? 利用进程 ID和页号检索很费时，要通过 Hash表进行检索。
第九章 虚拟存储管理
CPU pid p d
…… i
i d
d
第 i帧
物理地址
逻辑地址
页表
反置页表地址转换过程
物理帧号 PID 页号
外部页表
第九章 虚拟存储管理
9.2 分页存储管理
? 反向页表的结构
? 物理页架号：每一个表目对应一个物理页架；
? 虚拟页号：该物理页架对应的虚页；
? 指向 Hash链的下一项指针；
? 修改位、引用位和有效位；
? 保护和加锁信息。
第九章 虚拟存储管理
9.2 分页存储管理
? 快表的地址转换
? 在地址变换机构中增设一个具有并行查询能力的特
殊高速缓冲存储器 — 联想存储器 /快表。工作原理,
? CPU给出有效地址；
? 如果地址, 快表, 中，直接读出对应的物理块号，送往物
理地址寄存器；再访问内存。
? 如果快表没有对应的地址，从内存, 页表, 读取地址送往
物理地址寄存器，访问内存；把页表项存入快表或把老的
页表项换出。
? 如不设联想存储器：访问时间延长一倍。
第九章 虚拟存储管理
具有快表的地址变换机构
页表寄存器
页表始址 页表长度
逻辑地址
页号 页内地址
0 0
页号 块号
1 1
2 4
3 5
…… ……
+
4
内存
页表
(慢表 )
>
越界中断
物理地址
页号 块号
2 4
输
入
寄
存
器
快表
第九章 虚拟存储管理
9.2 分页存储管理
? 快表的结构
? 虚拟页号；
? 物理页架号；
? 保护权限；
? 数据快表；
? 指令快表。
第九章 虚拟存储管理
9.2 分页存储管理
? 虚拟分页系统的硬件支持
? 主存管理单元 (Memory Management Unit:MMU)
? 功能
? 管理硬件的页表基址寄存器；
? 将虚拟地址分为序页号和页内偏移量；
? 当出现缺页、页面访问越界或其它保护性错误时，发出页面
失效异常，请求内核处理；
? 设置页表中相应页的引用位、修改位、检查有效位和保护权
限等。
? 页表
? 快表
? 反向页表
第九章 虚拟存储管理
9.3 分段存储管理
? 虚拟分段和简单分段的区别
? 简单分段 —— 全部装入
? 虚拟分段 —— 部分装入
第九章 虚拟存储管理
9.3 分段存储管理
? 虚拟分段的优点
? 简化了对任意增长和收缩的数据段的管理；
? 分别编译的段连接简单；
? 一个段被修改并重新编译，不影响其它段；
? 便于在进程之间共享过程和数据；
? 对不同的段可以安排不同的保护类型。
第九章 虚拟存储管理
9.3 分段存储管理
? 虚拟分段的实现
段表始址 段表长度
段表寄存器
2
段号 段内偏移量
100
+
6K 1K 0
4K 600 1
8K 500 2
9200 200 3
基址 段长 段号
段表
+
越界中断
+
8292
物理地址
0
1
2
内存空间
8K
第九章 虚拟存储管理
9.4 段页式存储管理
? 结合分页系统和分段系统的优点
? 实现
? 主存分页
? 进程地址空间分段
? 段内分页
? 逻辑地址结构：（段号：页号：页内偏移）
? 主存以页架为单位分配
? 段表、页表、段表地址寄存器
第九章 虚拟存储管理
9.4 段页式存储管理
? 地址转换（图）
第九章 虚拟存储管理
9.4 段页式存储管理
? 优点
? 虚拟存储；
? 以页面位单位分配，无页内碎片；
? 段可动态增长；
? 便于共享；
? 便于控制存取访问。
? 缺点
? 增加了硬件成本；
? 增加了软件复杂性和管理成本；
? 存在页内碎片。
第九章 虚拟存储管理
9.5 页面置换
? 页面访问失效
? 边界错误
? 访问的虚地址不在进程地址空间之内
? 有效性错误
? 页不在主存内
? 保护错误
? 页面不允许某些权限的访问
? 解决方法 —— 分给一个空闲页面
第九章 虚拟存储管理
9.5 页面置换
? 当内存中没有空闲的页面可用时，解决
方法是从内存中挑选一个页面淘汰出去
? 问题
? 挑选什么样的页面来淘汰
? 从那些页面中选择被淘汰地页面
第九章 虚拟存储管理
9.5 页面置换
? 页面置换算法
? 最佳置换算法 (OPT)
? 最近未使用置换算法 (NUR)
? 先进先出置换算法 (FIFO)
? 二次机会置换算法
? 时钟页面置换算法
? 最近最少使用置换算法 (LRU)
第九章 虚拟存储管理
9.5 页面置换
? 最佳置换算法 (OPT)
? 淘汰将来再也不会访问的页面，或者在最远
的将来才被访问的页面
? 理论上最理想，但是实际上无法实现
? OPT算法用来对比其它算法的效率
第九章 虚拟存储管理
9.5 页面置换
? 最近未使用置换算法 (NUR)
? 被淘汰的页是最近未使用的页，而且是在驻
留主存期间未被修改的页
? 根据访问位和修改位确定淘汰的页面
? 访问位周期性的归零
第九章 虚拟存储管理
9.5 页面置换
? 先进先出置换算法
? 选择最早进入主存的页面淘汰
? 先进先出的异常现象 —— 随分给的页架数增
多，缺页频率也增加
第九章 虚拟存储管理
9.5 页面置换
? 二次机会置换算法
? 在先进先出算法基础上，参考访问位，如果
第一个进入主存的页面访问位为 0，则淘汰
它；如果为 1则把它放在链尾作为新调入的
页面看待。
第九章 虚拟存储管理
9.5 页面置换
? 时钟页面置换算法
? 对二次机会算法的改进。把页面组织成环形
链，每次检查链指针指向的页面，如果该页
的访问位为 0，则淘汰它，指针向后移动一
个页面；否则修改它的访问位为 0，指针向
后移动一个页面。
第九章 虚拟存储管理
9.5 页面置换
? 最近最少使用置换算法
? 选择最近一段时间内最长时间未被访问的页
淘汰
? 实现
? 使用计数器
? 使用矩阵
第九章 虚拟存储管理
9.5 页面置换
? 各种算法效率评价
? 评价参数：缺页率
? 例：内存中有 4个页架，分别编号为 0,1,2、
3，页面访问序列为 012310123231
第九章 虚拟存储管理
9.6 页架分配策略
? 各种算法效率评价
? 评价参数：缺页率
? 例：内存中有 4个页架，分别编号为 0,1,2、
3，页面访问序列为 012310123231
第九章 虚拟存储管理
课后作业
? Page 147上交时间：下周
? 8.9
? 8.17
? 思考题
? 8.5
第 9章 虚拟存储管理
? 9.1虚拟存储系统的基本概念
? 9.2 分页存储管理
? 9.3 分段存储管理
? 9.4 段页式存储管理
? 9.5 页的置换算法
? 9.6页架的分配策略
? 9.7 主存共享、快表一致性问题
第九章 虚拟存储管理
9.1 虚拟存储系统的基本概念
? 虚拟存储器
? 指一种实际上并不以物理形式存在的虚假的存储器
? 虚拟地址
? 一个运行进程访问的地址
? 实地址
? 处理器可直接访问的地址
? 虚拟存储技术
? 在逻辑上把内存的容量扩大，利用硬盘空间作为虚
拟内存。
第九章 虚拟存储管理
9.1 虚拟存储系统的基本概念
? 局部性原理 (principle of locality),
? 指程序在执行过程中的一个较短时期，所
执行的指令地址和指令的操作数地址，分
别局限于一定区域。还可以表现为,
? 时间局部性：一条指令的一次执行和下次执行，
一个数据的一次访问和下次访问都集中在一个
较短时期内；
? 空间局部性：当前指令和邻近的几条指令，当
前访问的数据和邻近的数据都集中在一个较小
区域内。
第九章 虚拟存储管理
9.1 虚拟存储系统的基本概念
? 局部性原理的具体体现
? 程序在执行时，大部分是顺序执行的指令，
少部分是转移和过程调用指令。
? 过程调用的嵌套深度一般不超过 5，因此执
行的范围不超过这组嵌套的过程。
? 程序中存在相当多的循环结构，它们由少量
指令组成，而被多次执行。
? 程序中存在相当多对一定数据结构的操作，
如数组操作，往往局限在较小范围内。
第九章 虚拟存储管理
9.1 虚拟存储系统的基本概念
? 虚拟存储原理
? 在程序装入时，不必将其全部读入到内存，而只需
将当前需要执行的部分页或段读入到内存，就可让
程序开始执行。
? 在程序执行过程中，如果需执行的指令或访问的数
据尚未在内存（称为缺页或缺段），则由处理器通
知操作系统将相应的页或段调入到内存，然后继续
执行程序。
? 另一方面，操作系统将内存中暂时不使用的页或段
调出保存在外存上，从而腾出空间存放将要装入的
程序以及将要调入的页或段。只需程序的一部分在
内存就可执行。
第九章 虚拟存储管理
9.1 虚拟存储系统的基本概念
? 引入虚拟存储技术的好处
? 大程序：可在较小的可用内存中执行较大的
用户程序；
? 大的用户空间：提供给用户可用的虚拟内存
空间通常大于物理内存 (real memory)
? 并发：可在内存中容纳更多程序并发执行；
? 易于开发：与覆盖技术比较，不必影响编程
时的程序结构
第九章 虚拟存储管理
9.1 虚拟存储系统的基本概念
? 虚拟存储技术的特征
? 不连续性：物理内存分配的不连续，虚拟地
址空间使用的不连续（数据段和栈段之间的
空闲空间，共享段和动态链接库占用的空间）
? 部分交换：与交换技术相比较，虚拟存储的
调入和调出是对部分虚拟地址空间进行的；
? 大空间：通过物理内存和快速外存相结合，
提供大范围的虚拟地址空间
? 总容量不超过物理内存和外存交换区容量之和
第九章 虚拟存储管理
9.2 分页存储管理
? 在简单页式存储管理的基础上，增加请求
调页和页面置换功能。
? 分页系统中的地址转换
? 硬件支持
第九章 虚拟存储管理
9.2 分页存储管理
? 分页系统中的地址转换（直接地址转换）
页表始址 页表长度
页表寄存器
2
页号 页内偏移量
100
+
2 0
4 1
5 2
3
页架 页号
页表 +
10340
物理地址
2
4
5
内存空间
第九章 虚拟存储管理
9.2 分页存储管理
? 分页系统中的地址转换（多级页表）
? 当内存增大时，页表也会很大，如果页表全
部放进主存，也要占用很大的空间
? 对页表分页，为了管理这些页表，设置一个
页表目录（顶级页表）
? 随着内存的增大，也可以使用三级、四级页
表
第九章 虚拟存储管理
d p2 p1
页目录号 页号 页内地址
31 22 21 12 11 0
逻辑
地址
页目录表寄存器 +
页目录
+
页表 物理地址
第九章 虚拟存储管理
9.2 分页存储管理
? 直接转换和多级页表地址转换的一个主
要问题：访问速度
? 一级页表：取一条指令需要访问内存 2次
? 二级页表：取一条指令需要访问内存 3次
? ……
第九章 虚拟存储管理
9.2 分页存储管理
? 页表的结构
? 页表是一个二维数组，每个表目对应一个虚
页
? 虚拟页号：进程虚地址空间划分的页；
? 物理页架号；
? 修改位：表示该页是否被修改过；
? 有效位：表示该页是否在主存中；
? 引用位：表示该页是否被访问过，用于页面调度；
? 保护权限：说明该页允许什么样的访问。
第九章 虚拟存储管理
9.2 分页存储管理
? 反向页表地址转换
? 以上策略为每个进程配置一张页表，进程的逻辑空
间每一页在页表中一个表项 — 页表非常庞大。
? 反置页表,为每一物理块 (页框 )分配一个表项，按
物理块号排序，表项的内容是页号及所属的进程标
识符。
? 反置页表的优缺点,
? 页表的大小与物理空间有关。
? 只包含调入内存的页面，没有包括未调入内存的进程页面。
? 利用进程 ID和页号检索很费时，要通过 Hash表进行检索。
第九章 虚拟存储管理
CPU pid p d
…… i
i d
d
第 i帧
物理地址
逻辑地址
页表
反置页表地址转换过程
物理帧号 PID 页号
外部页表
第九章 虚拟存储管理
9.2 分页存储管理
? 反向页表的结构
? 物理页架号：每一个表目对应一个物理页架；
? 虚拟页号：该物理页架对应的虚页；
? 指向 Hash链的下一项指针；
? 修改位、引用位和有效位；
? 保护和加锁信息。
第九章 虚拟存储管理
9.2 分页存储管理
? 快表的地址转换
? 在地址变换机构中增设一个具有并行查询能力的特
殊高速缓冲存储器 — 联想存储器 /快表。工作原理,
? CPU给出有效地址；
? 如果地址, 快表, 中，直接读出对应的物理块号，送往物
理地址寄存器；再访问内存。
? 如果快表没有对应的地址，从内存, 页表, 读取地址送往
物理地址寄存器，访问内存；把页表项存入快表或把老的
页表项换出。
? 如不设联想存储器：访问时间延长一倍。
第九章 虚拟存储管理
具有快表的地址变换机构
页表寄存器
页表始址 页表长度
逻辑地址
页号 页内地址
0 0
页号 块号
1 1
2 4
3 5
…… ……
+
4
内存
页表
(慢表 )
>
越界中断
物理地址
页号 块号
2 4
输
入
寄
存
器
快表
第九章 虚拟存储管理
9.2 分页存储管理
? 快表的结构
? 虚拟页号；
? 物理页架号；
? 保护权限；
? 数据快表；
? 指令快表。
第九章 虚拟存储管理
9.2 分页存储管理
? 虚拟分页系统的硬件支持
? 主存管理单元 (Memory Management Unit:MMU)
? 功能
? 管理硬件的页表基址寄存器；
? 将虚拟地址分为序页号和页内偏移量；
? 当出现缺页、页面访问越界或其它保护性错误时，发出页面
失效异常，请求内核处理；
? 设置页表中相应页的引用位、修改位、检查有效位和保护权
限等。
? 页表
? 快表
? 反向页表
第九章 虚拟存储管理
9.3 分段存储管理
? 虚拟分段和简单分段的区别
? 简单分段 —— 全部装入
? 虚拟分段 —— 部分装入
第九章 虚拟存储管理
9.3 分段存储管理
? 虚拟分段的优点
? 简化了对任意增长和收缩的数据段的管理；
? 分别编译的段连接简单；
? 一个段被修改并重新编译，不影响其它段；
? 便于在进程之间共享过程和数据；
? 对不同的段可以安排不同的保护类型。
第九章 虚拟存储管理
9.3 分段存储管理
? 虚拟分段的实现
段表始址 段表长度
段表寄存器
2
段号 段内偏移量
100
+
6K 1K 0
4K 600 1
8K 500 2
9200 200 3
基址 段长 段号
段表
+
越界中断
+
8292
物理地址
0
1
2
内存空间
8K
第九章 虚拟存储管理
9.4 段页式存储管理
? 结合分页系统和分段系统的优点
? 实现
? 主存分页
? 进程地址空间分段
? 段内分页
? 逻辑地址结构：（段号：页号：页内偏移）
? 主存以页架为单位分配
? 段表、页表、段表地址寄存器
第九章 虚拟存储管理
9.4 段页式存储管理
? 地址转换（图）
第九章 虚拟存储管理
9.4 段页式存储管理
? 优点
? 虚拟存储；
? 以页面位单位分配，无页内碎片；
? 段可动态增长；
? 便于共享；
? 便于控制存取访问。
? 缺点
? 增加了硬件成本；
? 增加了软件复杂性和管理成本；
? 存在页内碎片。
第九章 虚拟存储管理
9.5 页面置换
? 页面访问失效
? 边界错误
? 访问的虚地址不在进程地址空间之内
? 有效性错误
? 页不在主存内
? 保护错误
? 页面不允许某些权限的访问
? 解决方法 —— 分给一个空闲页面
第九章 虚拟存储管理
9.5 页面置换
? 当内存中没有空闲的页面可用时，解决
方法是从内存中挑选一个页面淘汰出去
? 问题
? 挑选什么样的页面来淘汰
? 从那些页面中选择被淘汰地页面
第九章 虚拟存储管理
9.5 页面置换
? 页面置换算法
? 最佳置换算法 (OPT)
? 最近未使用置换算法 (NUR)
? 先进先出置换算法 (FIFO)
? 二次机会置换算法
? 时钟页面置换算法
? 最近最少使用置换算法 (LRU)
第九章 虚拟存储管理
9.5 页面置换
? 最佳置换算法 (OPT)
? 淘汰将来再也不会访问的页面，或者在最远
的将来才被访问的页面
? 理论上最理想，但是实际上无法实现
? OPT算法用来对比其它算法的效率
第九章 虚拟存储管理
9.5 页面置换
? 最近未使用置换算法 (NUR)
? 被淘汰的页是最近未使用的页，而且是在驻
留主存期间未被修改的页
? 根据访问位和修改位确定淘汰的页面
? 访问位周期性的归零
第九章 虚拟存储管理
9.5 页面置换
? 先进先出置换算法
? 选择最早进入主存的页面淘汰
? 先进先出的异常现象 —— 随分给的页架数增
多，缺页频率也增加
第九章 虚拟存储管理
9.5 页面置换
? 二次机会置换算法
? 在先进先出算法基础上，参考访问位，如果
第一个进入主存的页面访问位为 0，则淘汰
它；如果为 1则把它放在链尾作为新调入的
页面看待。
第九章 虚拟存储管理
9.5 页面置换
? 时钟页面置换算法
? 对二次机会算法的改进。把页面组织成环形
链，每次检查链指针指向的页面，如果该页
的访问位为 0，则淘汰它，指针向后移动一
个页面；否则修改它的访问位为 0，指针向
后移动一个页面。
第九章 虚拟存储管理
9.5 页面置换
? 最近最少使用置换算法
? 选择最近一段时间内最长时间未被访问的页
淘汰
? 实现
? 使用计数器
? 使用矩阵
第九章 虚拟存储管理
9.5 页面置换
? 各种算法效率评价
? 评价参数：缺页率
? 例：内存中有 4个页架，分别编号为 0,1,2、
3，页面访问序列为 012310123231
第九章 虚拟存储管理
9.6 页架分配策略
? 各种算法效率评价
? 评价参数：缺页率
? 例：内存中有 4个页架，分别编号为 0,1,2、
3，页面访问序列为 012310123231
第九章 虚拟存储管理
课后作业
? Page 147上交时间：下周
? 8.9
? 8.17
? 思考题
? 8.5
