09 第九章 虚拟存储器管理技术.pptx

第1页：第九章 虚拟存储器管理技术

第九章 虚拟存储器管理技术

• 虚拟存储管理是与实存管理技术相对应的另一种管理技术
• 虚拟存储器是指一种在物理意义上实际并不存在的存储器，也称为外存或辅存，通常设置在硬盘上
• 一般地，虚拟存储器比实存要大得多，但虚存也不能是无限大（受地址场的大小与硬盘本身大小限制）
• 在存在虚存的前提下，用户可以运行比实存大得多的程序

实现虚存的代价

• 存储虚—实地址转换表等需要花费主存空间
• 地址转换增加了机时的消耗
• 进行置换操作时，要消耗硬盘的 I/O 操作时间

第2页：9.1 基本概念

9.1 基本概念

• 进程执行程序时要访问的是程序的指令和数据的逻辑地址；进程在处理机上才能运行，通过处理机实际访问指令和数据的主存地址
• 严格区分逻辑地址（相对地址）及逻辑地址空间和绝对地址（实际地址）及绝对地址空间（实存地址空间）

第3页：虚拟地址与实地址

虚拟地址

把一个运行进程访问的地址称为“虚拟地址”

虚拟地址空间

一个运行进程可访问的虚拟地址集合

实地址

处理机可直接访问的主存的地址称为“实地址”

实地址空间

计算机主存称为“实地址空间”

动态地址映象机构

实现由虚拟地址到实际地址的转换，把程序的指令和数据所在的虚拟地址放入主存实地址中去

虚拟地址空间（虚存）　>>　实地址空间（主存）。

第4页：虚存地址空间的大小

虚存地址空间大小取决于

• 指令中的地址长度
• 外存空间的大小

虚拟存储器是一个地址空间，是进程访问的逻辑地址空间，而不是物理主存空间。最大虚拟地址空间往往取决于指令中的地址长度限制（因外存空间通常大于指令地址长度所限定的范围）。

虚存管理：由 OS 自动实现，对用户是透明的

• 决定把作业虚拟地址空间的哪一部分装入主存
• 放在主存的什么位置
• 主存空间不够时把哪一部分置换出主存

第5页：常用的虚拟存储管理技术

常用的虚拟存储管理技术

• 分页（PAGING）管理技术
• 分段（SEGMENTATION）管理技术
• 段页式（SEGMENTATION WITH PAGING）管理技术

第6页：9.2 分页存储管理

9.2 分页存储管理

1. 分页存储管理的基本规则
2. 分页系统的地址转换
3. 硬件支持
4. 分页存储管理技术性能分析

第7页：分页存储管理基本规则

等分主存

把主存划分成相同大小的存储块——页架（page frame），页架大小固定不变，页架从 0 编号——页架号

用户逻辑地址空间的分页

逻辑地址空间划分成与页架大小相同的部分——页（逻辑页、虚页），不足一页的补齐一页，给页从 0 编号——页号

逻辑地址的表示

虚拟地址 A => 数对（p, d）：p 为页面号，d 为虚拟地址在页面号 p 内相对地址（页内地址）。页面大小 L，则 p＝⌊A/L⌋；d＝[A] MOD L。例：L=1000，A=3456 => 逻辑地址（3, 456）

第8页：主存分配原则与页表

主存分配原则：系统以页架为单位把主存分给作业或进程，并且分给一个作业或进程的页架不一定是相邻和连续的，即作业可以按页为单位零散地放在主存不连续的页架中。页面与页架一一对应（对应关系由页表记录）。

页表

• 页表是系统在作业装入主存、建立进程的同时建立的，记录各页面的调度情况
• 页表表目也称为页描述子（page descriptor），包括页号、状态、页架号、页面存储控制字段
• 页表起始地址 b 和表长 L 一般放在该作业进程的 PCB 中，当进程投入运行时先装入页表地址寄存器

第9页：分页系统中的地址结构

分页系统中地址结构：虚拟地址（p, d）在指令场中的物理表示。以 IBM 为例：页号 P 占 0～19 位中的前 12 位，页内地址 d 占后 12 位；p 占 12 位则页面总数为 2^12＝4K，d 占 12 位则页面大小为 4K。

页面尺寸应是 2 的幂：便于由指令地址场中给出的逻辑地址计算出其页面号 p 及页内地址 d。若页面大小 2^i，把地址场从第 i 位分成两部分，高位部分表示的数即为页面号 p，低位部分表示的数即为页内地址 d。例：L＝1K＝1024＝2^10，A＝1005H => p＝4H；d＝5H。

第10页：

第11页：分页存储管理地址转换

直接映象的地址转换（图 9.1）

1. 进程被调度：该进程页表起始地址和表长送页表寄存器 R=(L, b)
2. 进程访问虚地址 v：地址映象硬件把 v 转换成 (p, d)
3. 比较页面号 p 与页表长 L，判断是否越界
4. 页访问合法——按 p 索引页表：b + p×i => 第 p 个页面对应页表表目——页描述子（页架号 p′）（i 为表目长度）
5. 根据该表目中存储控制字段检验访问权限是否合法
6. 硬件计算实际地址：页架号 p′ 与 d 构成物理地址（p′, d）

第12页：页表放在主存中的缺点

页表放在主存中系统表格区：主存页架数 N＝主存大小／页大小；最多可存放 N 个页面，必然还有未能调入主存的页面，即所有进程页表表目数之和 ≥ N，页表所占空间＝页表表目数×每个表目长度 l ≥ N×l。

缺点：访问两次主存（页表、数据），处理机执行速度降低 1/2。

第13页：多级页表的地址转换

多级页表的地址转换

• 把页表本身按固定大小分成一个个页面
• 为了对小页表进行管理和索引查找，设置一个页表目录，为顶级目录，分别指出每个次级小页表所在物理页号和其他状态信息
• 每个进程有一个页目录，它的每一个表目映射一个页表
• 页目录本身大小是一个页面，页目录是一级页表，而每个小目录是二级页表

第14页：二级页表的地址变换

二级页表的地址变换（图 9.2）：例如十六进制数 0080300B 是虚地址，它的页目录＝2，页表＝3，偏移量＝B。地址变换时以页目录 2 索引顶级页表，查得该二级页表所在主存页架号，再以页表＝3 索引该页表，查得该虚地址的页面所在的主存页架号，与偏移量＝B 拼成主存物理地址。

通过二级页表的地址映射访问主存存取数据需要三次访问主存，所需时间是原来的三倍。

第15页：反向页表的地址转换

反向页表的地址转换（图 9.3）：表中每一个表目对应主存中一个物理页架，完成物理页架到虚地址的映射。对于进程的虚地址，存储管理单元通过哈希定位表的数据结构，把虚页号转化为哈希值，以该值为索引指向页表中的一个表目。

该表目包含以下信息

• 映射的虚页号
• 指向哈希链的下一项指针
• 有效位、引用位、修改位
• 保护和加锁信息
• 查找反向页表的索引号即为页架号

第16页：快表的地址转换

快表的地址转换（图 9.4）

• 页表放在相关存储器（关联存储器）：快表／相关页表
• 相关存储器：硬件寄存器，且有一定的判断能力，实现按内容检索
• 虚拟地址 v 由硬件截成两部分 (p, d)；用 p 与相关存储器中各表目同时比较，查得其所在表目，自动送出页架号 p′，再与 d 构成实地址（p′, d）
• 处理机执行速度提高，但高速相关存储器很贵

第17页：分页存储管理技术性能分析

优点

可提供多个大容量的虚拟存储器：作业的地址空间不再受主存大小的限制；主存利用率大大提高：作业中不常用的页不会长期驻留在主存，当前运行用不到的信息也不必调入主存；能实现多道作业同时运行；方便用户：大作业也无须考虑覆盖问题

缺点

缺页中断处理增加系统开销；页面的调入调出增加 I/O 系统的负担；此外页表等占用空间且需要管理，存在页内零头

第18页：解决：减少缺页中断次数

解决：尽可能减少缺页中断次数

• 程序质量：尽可能使编出的程序具有高度的局部性，则执行时可经常集中在几个页面上进行访问，减少缺页率
• 页面大小：页面大，页表小，省空间且查找快，缺页次数相对也少，但一次换页的时间长，页内零头空间浪费的可能性较大；页面小则相反
• 主存容量：一个程序运行时遇到缺页中断的次数，和分配给该道程序的主存容量（页架数）成反比，但当主存容量达到某个值时，缺页次数减少不再明显，多数程序都有一个确定值——拐点
• 淘汰算法：在淘汰页选择范围选择最合适的置换算法

第19页：分段存储管理导览

分段存储管理

1. 分段存储管理基本概念
2. 分段的实现
3. 虚拟存储管理中的存储保护问题
4. 分段存储管理的优缺点

第20页：9.3 分段存储管理

9.3 分段存储管理

• 方法：按程序模块来划分段，并按这些段来分配主存
• 段：定义为一组逻辑信息的集合，如子程序、数组和数据区等，通常以文件形式存于文件系统中

进程的逻辑地址空间

• 程序员为每个段给出段名 => 二维逻辑地址空间（段名，段内地址）
• 编译或汇编之后系统为每个段给出一个内部段名（段号）=> 二维虚地址空间（段号 s，段内相对地址 w）
• 程序的地址结构：（S, W）；例：S 为 0…FF，W 为 0…FFFF

第21页：主存分配与段表

• 主存分配：以段为单位，每一段分配一块连续的主存分区，一个进程的各段所分到的主存分区不要求是相邻连续的分区

段表和段表地址寄存器：每个作业一个段表

• 内容：段号、段的长度、段在主存中的起始地址、段的状态位、访问位、修改位、扩充位、段在外存的地址等
• 组织：段号从小到大排列，包含该进程的全部段
• 生命期：作业调入时为进程建立段表，撤消进程时清除此进程的段表
• 段表地址寄存器：存放运行进程的段表在主存中起始地址（调度时从 PCB 中读取）

第22页：分段的实现

分段的实现：每个虚拟地址由一个数对（段号，段内偏移量）两部分构成，每个进程有一个段表，包含段的起始地址、段长、有效位、修改位、保护和共享信息。

地址转换（图 9.5）：逻辑地址（s, w）经 b + s×l 得到该段在段表中的表目地址，读出段在主存中的起始地址 s′，再由 s′ + w 得到要访问的主存实际地址。

第23页：虚拟存储管理中的存储保护问题

虚拟存储管理中的存储保护问题（多级存储保护体系）

• 越界保护：页表长度（最大页号）／段表长度（最大段号）送入页表地址寄存器。当访问某虚拟地址时，硬件自动将其页号（段号）和页表（段表）长度进行比较；分段环境下还要将段内地址与段表中该段的长度进行比较，如果合法才进行转换，否则产生越界中断信号
• 存取控制保护：控制各种共享类型的用户的访问权限——读：允许用户对该段／页内任何信息或其副本进行读操作；写：允许用户修改该段／页内任何信息直至撤消整个段／页；执行：用户可以执行该段／页程序，数据段／页除外；增加：允许用户向该段／页添加信息

第24页：分段存储管理的优缺点

优点

便于处理变化的数据结构：段表中加一个增长标志位，0 表示该段不可增长，1 表示该段允许动态增长，由越界中断处理程序根据动态增长位来判别；便于共享：欲共享作业的段表中有相应表目指向被共享段在主存中的起始地址；提供了虚存的功能：小内存分区运行大作业（可能需要存储器紧缩）；提供了动态连接的便利；便于控制存取访问

缺点

存储紧缩；分段最大尺寸受到主存大小的限制；在外存中管理可变尺寸的分段较困难；提高了硬件成本

第25页：9.4 段页式存储管理

9.4 段页式存储管理基本概念

• 等份主存：主存划分为页架，并编号为页架号
• 进程的地址空间采用分段方式：按程序的自然逻辑关系把进程的地址空间分成若干段（外部段名，内部段名）
• 每一段采用分页方法：每一段划分成若干页，大小同页架；每一段为自己段的各页依次编以连续的页号；不足补齐
• 逻辑地址结构：V=(s, p, d)＝（段号，页号，页内地址）
• 主存分配：以页架为单位分配给每个进程
• 段表、页表、段表地址寄存器：系统为每个进程建立一个段表，为其段表中每个段建立一个页表；用段表地址寄存器指示进程段表起始地址

第26页：段页式存储管理中的地址转换

段页式存储管理中的地址转换（图 9.6）：无相关存储器——直接映象

1. 硬件：段表地址寄存器给出段表基址 b + 段号 s ==> 该段在段表中表目地址
2. 读段表表目 ==> 该段页表起始地址 s′
3. 硬件：页表基址 s′ + 页号 p ==> 该页在页表中表目地址
4. 读页表表目 ==> 该页对应的页架号 p′
5. 硬件：页架号 p′ 与页内地址 d ==> 绝对地址／主存地址

有相关存储器——相关映象

1. 以段号 s、页号 p 为索引 ==> 同时比较相关存储器的各表目
2. 匹配：判断访问合法性 ==> 不合法：停止转换，发中断信号；合法：继续转换

第27页：段页式存储管理的优缺点

进程表、段表、页表、页架的关系见图 9.7，段页式存储管理算法的地址转换见图 9.8。

优点

虚存管理功能；无紧缩问题，无页外碎片；便于处理变化的数据结构，段可动态增长；便于共享；动态连接；便于控制存取访问

缺点

增加硬件成本；增加软件复杂性和管理开销；存在页内碎片

第28页：分页存储管理策略要解决的三个问题

何时取页（取页策略）

请求取页：当用到某页而不在主存时即缺页时取页（请求式分页存储管理）；提前取页：预先装入主存一页或几页（提前页）

取来的页面装入主存中哪个页架（置页策略）

一般装入主存任一个可用的页架中

当需调入一页而主存已无可用的自由页架时如何选择或腾出一个页架

9.5 页的置换算法

第29页：页的置换算法基本概念

页的置换算法

当发生缺页，而主存中已无空闲页架时，需选一页淘汰，选取淘汰页的方法叫页的置换算法

抖动

刚被淘汰出去的页，不久又被访问，又需把它调入而将另一页淘汰出去，很可能又把刚调入的或很快要用的页淘汰出去了。如此反复更换页面，以至系统大部分机时花在页面的调度和传输上，系统的实际效率很低，这种现象称为“抖动”

缺页率

f =（缺页次数／访问页面总数）%

第30页：最佳置换算法OPT

基本原则

淘汰在将来再也不被访问，或者是在最远的将来才能被访问的页

特点

无法预测作业将用到哪些页！所以此算法是无法实现的——理论上的算法

例：某进程分配页架数为 3，其运行期间页面访问序列 A、B、C、D、A、B、E、A、B、C、D、E，分析其按照 OPT 算法进行页面置换时的缺页情况（堆栈式算法）。

第31页：最佳置换算法OPT示例

最佳置换算法 OPT 置换过程图示：本页以图示方式展示页架数为 3 时，按访问序列 A、B、C、D、A、B、E、A、B、C、D、E 进行 OPT 页面置换的过程。

注：本页为置换过程图示，源文本仅含算法标题，具体逐次置换结果建议对照原课件图片核对。

第32页：最近未使用置换算法NUR

页表扩充：为每个页面设置两个硬件位——访问位和修改位。访问位＝0 表示该页尚未被访问过，＝1 表示该页已经被访问过；修改位＝0 表示该页尚未被修改过，＝1 表示该页已经被修改过。

• 基本原则：淘汰最近未使用的页，且希望其在主存逗留期间页面内的数据未被修改过
• 过程：开始时所有页的访问位、修改位都为 0，访问／修改时再置 1
• 周期性地对访问位清零

页面描述子：页面号、页架号、状态、存储控制、访问位、修改位、外页地址。

第33页：先进先出置换算法FIFO

基本原则

选择最早进入主存的页面淘汰

理由

最早进入的页面其不再使用的可能性比最近调入的页面要大

实现简单

把进入主存的各页面按进入主存的时间次序构成队列（链表或表格），总是淘汰队头的页面

缺点

• 只有按照线性顺序访问地址空间时才是理想的，否则效率不高
• 异常现象：对于一些特定的访问序列，随分配页架数增加，缺页频率反而增加

第34页：先进先出置换算法FIFO示例

先进先出置换算法 FIFO 置换过程图示：本页以图示方式展示按页面进入主存的时间次序构成队列、每次淘汰队头页面的置换过程。

注：本页为置换过程图示，源文本仅含算法标题，具体逐次置换结果建议对照原课件图片核对。

第35页：二次机会置换算法

基本原理

将 FIFO 算法与使用页表中的访问位结合

目的

防止把最近经常使用的、最早进入的页面置换出去

实现方法

首先检查 FIFO 链上的最前面的页，如果访问位为 0，则选择该页淘汰，否则把它移到 FIFO 的链尾，作为新调入的页（访问位为 1 表示这一页虽然最早进来，但最近仍然被访问过）

是 FIFO 算法的改进，真正淘汰的是最早进来的、而最近又没有被访问的页。把访问位为 1 的处于链头的页移往链尾，需要一定开销。

第36页：时钟页面置换算法

时钟页面置换算法：对二次机会置换算法的改进，将进程所访问的页构成像一个时钟样的环形链表。

实现方法：当产生缺页中断时，先检测指针所指的页，如果它的引用位为 0，则淘汰该页，新装入的页插入到这个位置，然后指针向前一个位置；如果它的访问位为 1，则清除为 0，并将指针再向前一个位置，继续检查访问位。重复此过程，直到找到访问位为 0 的页为止（请参考图 9.13）。

第37页：最近最少使用置换算法LRU

基本原则

选择最近一段时间内最长时间没有被访问过的页面淘汰

基本理由

认为过去一段时间里不曾被访问过的页，在最近的将来也可能不再会被访问

实现困难

需为每个页设置一个特定单元，记录上次访问后到现在的时间量 t，并选择 t 最大的页淘汰；无论硬件还是软件实现开销都很大

实际应用

近似算法 NUR

第38页：最近最少使用置换算法LRU示例

最近最少使用置换算法 LRU 置换过程图示：本页以图示方式展示按各页上次访问后经过的时间量 t 选择 t 最大的页淘汰的置换过程。

注：本页为置换过程图示，源文本仅含算法标题，具体逐次置换结果建议对照原课件图片核对。

第39页：9.6 页架分配策略

提前分页

• 目的：解决当程序刚一被启动时所引起的大量的持续的缺页
• 方法：启动前提前把该进程的最初的工作集装入主存
• 问题：（1）系统有无能力主动装入某个指定的页面，而不是只能在缺页请求发生时才能将该页装入（可以）；（2）将哪些页提前装入（估计）

最少页架数

• 指为保证一条指令能完整地执行，进程应分得的起码的页架数，随计算机结构的不同而不同，取决于该机器的指令格式和寻址方式
• 例 PDP-8 单地址指令：立即寻址需要 1 个页架；直接寻址至少需要 2 个页架；间接寻址需要更多页架

第40页：页架分配（续）

局部分配／局部淘汰

仅在一个作业自己所占用的全部页架中挑选页面淘汰；所以进程所占页架数不变

全局分配／全局淘汰

对整个主存范围内的页面进行挑选

固定页面

不能被换出或某段时间不能被换出的页面——固定页标志（长期固定和短期固定）

分配算法

• 平均分配：系统中全部页架数 m 在 n 个进程间平均分配。设 m＝95，n＝6，m/n＝95/6＝15×6+5，每个进程分得 15 个页架，还有 5 个留作公用页架缓冲区
• 根据作业大小按比例分配：设每个进程的虚存大小（即作业大小）为 Si，则 S＝ΣSi，主存可用页架数 m 按比例分配

第41页：又一种页面置换算法：工作集

又一种页面置换算法：工作集

• 根据：程序行为的局部性
• 目标：降低缺页频率，缩短等待调页时间，提高系统效率
• 工作集：是进程在某段时间里实际要访问的页面的集合，保证程序有效运行，工作集必须在主存中
• 工作集的确定原则：依据程序过去的行为来估计它未来的行为，因为程序运行的局部化特点决定了工作集变化是缓慢的

进程在时间 t 的工作集：一个运行进程在 t-w 到 t 这个时间间隔内所访问的页的集合称为该进程在时间 t 的工作集，记为 W(t, w)。变量 w 称为工作集窗口尺寸，工作集所包含的页面数称为工作集尺寸，记为 |W(t, w)| 或 |W|。

第42页：工作集（续）

工作集（续）

• 工作集窗口尺寸 w 的选取：过大，甚至把整个作业地址空间全部包含在内，就失去了虚存的意义；过小，引起频繁缺页，降低了系统效率
• 工作集尺寸 |W(t, w)| 的确定：从 t1 起，将所有的页面访问位全清零（特权指令），在 t1+w＝t2 时，记下全部访问位为“1”的页面，则这些页的集合可看成 t2 时的工作集
• 结论：把缺页的间隔时间控制在合理的范围，使分给进程的页架数保持在上下限之间（拐点附近）

第43页：页面的大小

注：原课件本页关于大页面「增加缺页频率」的表述与本章「页面大则缺页次数相对也少」一节存在出入，建议对照原课件图片核对后确认。

结论：理论和实践都表明，页面尺寸以小些为好。

第44页：程序运行的局部特性

进程对主存的访问不是均匀的，而是高度地表现出其局部性。

时间局部性

指某个位置（数据或指令）最近被访问了，那么往往很快又要被再次访问，借助于循环、经常用到的变量和子程序等程序结构实现

空间局部性

指一旦某个位置最近被访问了，那么它附近的位置也要被访问，采用顺序的指令串、线性的数据结构（如数组或常用变量彼此相近存放）来实现

程序在某段时间对整个地址空间各页的访问集中在少数几页；一个页面中也不是均匀的，而是集中于页面中的较少部分。

第45页：*9.7 高速缓冲存储器

*9.7 高速缓冲存储器

• 三级存储结构：CPU、缓冲存储器、主存（图 8.18）
• 缓存／隐藏存储器 Cache：不参与主存储器编址，对用户是透明的（不属于虚拟存储技术）
• Cache 的组织：典型容量 4K、8K、16K、32K
• 读双字指令速度：主存 1100ns，高速缓存 120ns，处理机 150～300ns
• 构成：缓存、缓存目录、缓存控制器
• 缓存组织：缓存（和主存）分成若干块，每个块 64 字节；缓存空间分区——行号，每个区 2K，32 块——列号 0…31；4KB=>2 个区，8KB=>4 个区

第46页：4K缓存的缓存目录

4K 缓存的缓存目录：32 个表目／区 × 2 区

• 每个缓存块对应一个缓存目录的表目——列号 0..31
• 主存地址行号 11 bits：指示该块在主存中的行号（每一行对应缓存一个区的大小，即 2K）
• 状态 3 bits：有效位、修改位、故障位
• LRU：指示最近被访问的区号，用于选择淘汰页

第47页：有缓存的系统主存编址

有缓存的系统主存编址（图 8.20）：分成 64 字节大小的块（Intel 80386 的块大小为 32 字节）；行号为每 32 块构成一个区（2K），每行有一个编号 0、1、……；列号为区中的 32 个块编号 0…31。

注：80386 的地址格式为行号 17 位、列号 10 位、字节数 5 位。

第48页：Cache与主存的对应关系

Cache 与主存的对应关系图示：本页以图示方式展示缓存目录中区 0、区 1 两区的表目（列号 0～31）与主存中各行、各列块的对应关系。

注：本页为组织结构图示，源文本仅含目录与主存的行列标注，建议对照原课件图片核对。

第49页：高速缓冲存储器工作过程

高速缓冲存储器工作过程——取指令

1. 根据列号查找缓存目录——一列表目
2. 把各表目的主存地址行号与指令中行号比较：匹配，有效位＝0，缓存块 => 指令处理部件，LRU＝当前区号；不匹配，该块不在缓存，从主存把该块 => 指令处理部件，同时该块 => 缓存相应列的某块

写数据

• 在缓存，则写入缓存，且修改位置“1”；不在缓存，则先把该块读入缓存，然后再在缓存中修改
• Windows NT 惰性方法：修改块淘汰出缓存时才写回主存块
• IBM 370 立即存方法：对主存缓存相应块同时写
• 通道向主存写数据：写入主存的同时，缓存相应块作废

第50页：9.8 Windows NT虚存管理

9.8 Windows NT 虚存管理：二级页表地址变换，虚存空间（2^32）4GB＝2GB 系统存储区 + 2GB 用户存储区；虚拟分页：页面 4KB（2^12），进程最大页面数 1M 多（2^20）；页表不常驻内存，可换进换出；目录位移 10 bits 为一级页表（页目录），1K＝1024；页表位移 10 bits 为二级页表（页表），1K＝1024；页架号。采用高速缓存 Cache 和快表。

页面调度算法

• 取页：集群提前取页 + 请求取页
• 置换：局部置换，FIFO 置换，自动调整工作集技术
• 惰性技术

共享主存机制：段对象、视口机制。