§2 虚拟存储器 1961年英国曼彻斯特大学Kilbrn等人提出 70年代广泛地应用于大中型计算机系统中 目前许多微型机也开始使用虚拟存储器 §2 虚拟存储器 1961年英国曼彻斯特大学Kilbrn等人提出 70年代广泛地应用于大中型计算机系统中 目前许多微型机也开始使用虚拟存储器 是进一步完善主存-辅存存储层次，解决主存容量提出的。

虚拟存储器的特点 多个进程可以共享主存空间 程序员不必做存储管理工作 采用动态再定位，简化了程序的装入

目录 不同的虚拟存储管理方式 页式虚拟存储器构成 页式虚拟存储器实现中的问题

虚拟地址空间 实际地址空间 压缩 映射

不同的虚拟存储管理方式 通过增设地址映像表机构来实现程序在主存中的定位。这种定位技术是将程序分割成若干较小的段或页，用相应的映像表机构来指明程序的某段或某页是否已装入内存。 段式管理 页式管理 段页式管理

段式管理 段为程序的逻辑单位 段表，本身也是段，常驻内存，也可以在辅存，需要时调入主存。 能使大程序分模块编制，并行编程，缩短时间 段表结构： 段名、地址、装入位、段长、访问方式。 段表基址寄存器：指明段表的启始地址。 能使大程序分模块编制，并行编程，缩短时间 便于几道程序共用已在内存内的程序和数据； 各段是按其逻辑特点组合的，容易以段为单位实现存储保护。人工建立。

+ 3k A 4 1.5k 0段 1段 2段 3段 4段 5段 6段 1k 2k 4k a 7 1 6 5 3 2 5k 段名 地址 装入位 1 + 6 5 3 2 5k 段名 地址 装入位 段长 访问方式 已装入 段表长度 段表基地址 段表基址寄存器 实主存空间 A道程序的 程序空间 A道程序的段表 2.5k

段号 段长 起址 主程序 (0段) 1k 8k 8k 1k 1 500 16k 9k 1段 2 200 9k 500 3 200 30k 16k 2段 200 30k 3段 程序 空间 200 主存储器

地址映象方法：每个程序段都从0地址开始编址，长度可长可短，可以在程序执行过程中动态改变程序段的长度。 地址变换方法： 由用户号找到基址寄存器 从基址寄存器中读出段表的起始地址 把起始地址与多用户虚地址中段号相加得到段表地址 把段表中给出的起始地址与段内偏移D相加就能得到主存实地址

多用户 虚地址 用户号U 段号S 段内偏移D 主存实地址 As 1 6 As 2 1 3 n-1 4 段表 长度 段表 基址 段名 起始 地址 装入 位 段长 访问 方式 段表基址寄存器 一个用户（一道作业）的段表

段式管理优缺点 优点 缺点 程序的模块化性能好 便于程序和数据的共享 程序的动态链接和调度比较容易 便于实现信息保护 地址变换所花费的时间比较长，做两次加法运算 主存储器的利用率往往比较低 对辅存（磁盘存储器）的管理比较困难

段分配算法 首先分配：顺序扫描可用区域表，当找到第一个不小于调 入段长度的可用区时，立即分配。 最佳分配：先扫描全部可用区域表，然后寻找一个可用区进行分配，使之分配后段间可用区零头最小。

举例 主存 程序 (a)需依次调入 D、E、F段 (b)首先分配法 D、E、F段全被调入 （c)最佳分配法 F段无法调入 C B A D E 0.5k 3k 7k 8k 10k C B A D E F 1k 2.5k 2k 主存 程序 4k 6.5k 5.5k 9k (a)需依次调入 D、E、F段 (b)首先分配法 D、E、F段全被调入 （c)最佳分配法 F段无法调入

页式管理 页式虚拟存储器把虚拟地址空间划分成一个个固定大小的块,每块称为一页,把主存储器的地址空间也按虚拟地址空间同样的大小划分为页。页是一种逻辑上的划分，它可以由系统软件任意指定。 虚拟地址空间中的页称为虚页，主存地址空间中的页称为实页。 每个用户使用一个基址寄存器（在CPU内），通过用户号U可以直接找到与这个用户程序相对应的基址寄存器，从这个基址寄存器中读出页表起始地址。访问这个页表地址，把得到的主存页号p与虚地址中的页内偏移直接拼接起来得到主存实地址。

页式管理 把主存空间和程序空间机械地等分成固定大小的页，按顺序编号； 页表。如下图。 特点： 页表项简单，查找速度快； 页面大小固定不利于系统的效率， 有些系统可调整其大小。例：MC88200 应用程序 4kb 系统程序512kb 页式管理在存储空间较大时，由于页表过大，效率降低。 存储空间的保护困难。

D b Nv Nr nr nv 7 6 D道程序页表 2 7 1 6 D道程序页表 A B C 4k-1 32k-1 程序标志号 A B C 1 2 4k D道程序 程序空间 虚存页号 A B C 4k-1 32k-1 D 程序标志号 b Nv Nr nr nv 7 6 D道程序页表 虚存 页号 主存 起点 装如 位 访问 方式 专用 基号 虚页号 页内偏移 实页号 1 2 4k D道程序 程序空间 虚存页号 A B C 4k-1 32k-1 2 7 1 6 D道程序页表 虚存 页号 主存 起点 装如 位 访问 方式 专用

X Nv Nr x nv nr 由u转换成基号b 1 多用户 虚地址 用户标志u 用户虚页号 页内位移 多用户虚页号 某道程序的地址 页表基址寄存器 nv nr 实页号 装入位 1 已装入 主存 主存地址寄存器

举例 虚地址空间32位，页面大小为1kb（10位） 页表地址段将达22位， 32-10=22 页表的长度为4兆行(222 =4096k=4M) 如主存容量为8MB 则页表字段为13位，每行为2+1字节 则页表容量为 4MB*3=12MB＞主存容量

页号 主存页号 0页 1 1页 2 2页 3 页表 3页 用户程序 主存储器 页式虚拟存储器的地址映象

用户号U 虚页号P 页内偏移D 实页号p 页内偏移d Pa Pa 2 p 装入 修改 主存页号 标志 页表基址 页表

页式管理的优缺点 优点 缺点 主存储器的利用率比较高 页表相对比较简单 地址变换的速度比较快 对磁盘的管理比较容易 程序的模块化性能不好 页表很长，需要占用很大的存储空间。

段页式管理 页式：对应用程序员完全透明，由系统划分. 硬件较少，地址变换速度快， 调入操作简单，静态连接程序； 段式：段独立，有利于程序员灵活实现段的连接、段的扩大/缩小和修改，而不影响其他段，易于针对其特定类型实现保护，把共享的程序或数据单独构成一个段，从而易于实现多个用户、进程对共用段的管理，动态连接程序； 特点：访存两次。 段页式：把实存机械地等分成固定大小的页，程序按模块分段，每个段又分成与主存页面大小相同的页。

地址变换方法： 先查段表，得到该程序段的页表起始地址和页表长度 再查页表找到要访问的主存实页号 最后把实页号p与页内偏移d拼接得到主存的实地址。

用户号U 段号S 虚页号P 页内偏移 实页号p 页内偏移 As A As 1 0/1 Ap 1 p 0/1 装入 修改 页表 地址 装入 实页号 修改 标志

页式虚拟存储器构成

u Nv’ Nr nr nv 虚存总空间 多用户虚地址Ns 2Nr 直接 实存地址np 2Nv页包括2u个 实存空间 用户，每个用户

地址映象和变换 地址映象：是将每个虚存单元按某种规则（算法）装入（定位于）实存，即建立多用户虚地址Ns与实存地址np之间的对应关系。 页面争用（实页冲突）：发生两个以上的虚页想要进入主存中同一个页面位置的现象。

地址变换的原则 减少实页冲突 硬件少、成本低 实现方便、变换速度快。 由于虚存空间远远大于实存空间，因此页式虚拟存储器常采用全相联映像。

全相联映像 任何虚页可以映象装入到任何实页位置。冲突概率最低。 虚存 主存 每道程序任何 虚页可映像到 任何实页位置 页0 页1 页2 页面位置0 页面位置1

全相联映像的页表法 页表法 nv 装入位 2u+Nv行

全相联映像的相联目录表法 相联目录表法 u+Nv nv 2nv行 相联比较

页表法与相联目录表法的比较   页表法 相联目录表法 访问方式 地址 内容 存储容量 存取速度 慢 快 入口个数 入口宽度

替换算法 页面替换发生时间： 当发生页面失效时，要从磁盘中调入一页到主存。如果主存所有页面都已经被占用，必须从主存储器中淘汰掉一个不常使用的页面，以便腾出主存空间来存放新调入的页面。 替换算法的确定 主存的命中率 是否便于实现，软、硬件成本

页面替换算法的使用场合 虚拟存储器中，主存页面的替换，一般用软件实现 Cache块替换一般用硬件实现 虚拟存储器的快慢表中，快表存储字的替换，用硬件实现 虚拟存储器中，用户基地址寄存器的替换，用硬件实现 在有些虚拟存储器中目录表的替换

替换算法（续） 随机算法（Random ，RAND）：用软的或硬的随机数产生器来形成主存重要被替换页的页号。 简单，易于实现 没有利用历史信息 命中率低，很少使用 先进先出算法（First-In First-Out ，FIFO）：选择最早装入主存的页作为被替换的页。 配置计数器字段 虽然利用历史信息，但不一定反映出程序的局部性

替换算法（续） 近期最少使用算法（Least Recently Used ，LRU）：选择近期最少访问的页作为被替换的页。 配有计数器字段。 比较正确反映程序的局部性。 优化替换算法（Optimal Replacement Algorithm， OPT）:是在时刻t找出主存中每个页将要用到时刻ti，然后选择其中ti-t最大的那一页作为替换页。 理想化算法

举例1 设有一道程序，有1至5共5页，执行时的地址流为： 2，3，2，1，5，2，4，5，3，2，5，2 分别采用FIFO、LRU、OPT算法。

说明 命中率与地址流有关 命中率与分配给程序的主存页数有关。 例如：一个循环程序，FIFO、LRU的命中率明显低于OPT。（下一张） 颠簸现象：连续不断出现页面失效。 命中率与分配给程序的主存页数有关。 主存页数增加，LRU命中率提高，至少不会下降，而FIFO不一定。(P115,图4.17)

举例 一个循环程序，依次使用P1，P2，P3，P4四个页面，分配给这个程序的主存页面数为3个。FIFO、LRU和OPT三种页面替换算法对主存页面的调度情况如下图所示。在FIFO和LRU算法中，总是发生下次就要使用的页面本次被替换出去的情况，这就是“颠簸”现象。

举例2 一个程序共有5个页面组成，程序执行过程中的页地址流如下： P1, P2, P1, P5, P5, P1, P3, P4, P3, P4 假设分配给这个程序的主存储器共有3个页面。给出FIFO、LRU、OPT 三种页面替换算法对这3页主存的使用情况，包括调入、替换和命中等。

堆栈型替换算法的定义 对任意一个程序的页地址流作两次主存页面数分配，分别分配m个主存页面和n个主存页面，并且有m≤n。如果在任何时刻t，主存页面数集合Bt都满足关系：Bt(m)Í Bt(n)，则这类算法称为堆栈型替换算法。

堆栈型算法的基本特点 随着分配给程序的主存页面数增加，主存的命中率也提高，至少不下降。 提出使系统性能可以更优的动态算法。 LRU、OPT都是堆栈型算法 FIFO是非堆栈型算法 提出使系统性能可以更优的动态算法。 由操作系统来动态调节分配给每道程序的实页数。

虚拟存储器工作的全过程 书中 P117-118

页式虚拟存储器实现中的问题 页面失效的处理 页面失效会在一条指令的分析或执行过程中发出。 页面失效时一种故障，不是一般的中断； 注意保护现场,采用后援寄存器技术、预判技术； 选择合适的替换算法；

页式虚拟存储器实现中的问题 提高虚拟存储器等效访问速度的措施 要求：提高命中率，加快访存时间； 命中率受很多因素影响，如：地址流、页面调度策略、替换算法、页面大小、主存容量等。 访存时间，解决Ns-np的转换。 快表：相联目录表，慢表：页表 快表-慢表存储层次的替换算法一般采用LRU法。

实页号 用户号U 页内偏移D p 虚页号P 多用户 虚地址 快表（按内容相联访问） 页内偏移d 实页号p 多用户虚页号 U, P 主存实地址 装入 1 慢表

散列函数 目的：把相联访问变成按地址访问，从而加大快表容量 散列（Hashing）函数：Ah＝H(Pv), 20位左右  5~8位 采用散列变换实现快表按地址访问 避免散列冲突：采用相等比较器 地址变换过程：相等比较与访问存储器同时进行

实页号 用户号U 页内偏移D p 虚页号P 多用户 虚地址 按地址访问的快表 页内偏移d 实页号p 多用户虚页号 Pv 主存实地址 散列变 换（硬 件实现） 相等比较 查慢表 快表地址 Ah 快表 命中

虚拟存储器举例 I BM370/168计算机的虚拟存储器快表结构及地址变换过程。虚拟地址长36位，页面大小为4KB，每个用户最多占用4K个页面，最多允许16个用户，但同时上机的用户数一般不超过6个。 采用了两项新的措施： 采用两个相等比较器 用相联寄存器组把24位用户号U压缩成3位

页式虚拟存储器实现中的问题 影响主存命中率CPU效率的某些因素 程序地址流、替换算法、实页数、页面调度策略 页面大小通常为1KB到4KB。 H S1：某道程序的主存容量 Sp：页面大小 S1一定时： Sp由小增大，H逐渐增大 增达到最大值，下降。 增大S1可增大Sp。 2S1 S1 页面大小Sp

主存容量与命中率的关系 1.0 命中率 H 主存容量S 主存命中率H随着分配给该程序的主存容量S的增加而单调上升。 在S比较小的时候，H提高得非常快。随着S的逐渐增，H提高的速度逐渐降低。当S增加到某一个值之后，H几乎不再提高。 命中率 H 主存容量S 1.0

页面调度方式与命中率的关系 请求式： 预取式： 当使用到的时候，再调入主存 在程序重新开始运行之前，把上次停止运行前一段时间内用到的页面先调入到主存储器，然后才开始运行程序。 可以避免在程序开始运行时，频繁发生页面失效的情况。 如果调入的页面用不上，浪费了调入的时间，占用了主存资源。