第六课 虚拟 存储器
(Virtual Memory)
教学目的,
为了在内存空间运行超过内存总容量的大作业，或
者同时运行大量作业，解决的方法是从逻辑上扩充
内存容量，这正是虚拟存储技术所要解决的主要问
题。 本课要介绍虚拟存储技术实现的各种方案，每
种方案所需的硬件和软件支持。
教学要求：
? 掌握 虚拟存储器的 理论基础和定义,熟悉虚拟存
储 器 实现方式和 特征。
? 掌握请求分页的页表机制、缺页中断机构和地址
变换机构,熟悉 页面的分配和置换策略、页面的
分配的算法。
? 熟练掌握最佳置换算法、先进先出（ FIFO）置换
算法、最近最久未使用置换算法 LRU，掌握 Clock
置换算法和 页面缓冲算法； 掌握有效访问时间计
算,熟悉 工作集概念。
? 掌握请求分段的段表机制、缺段中断机构和地址
变换机构,熟悉 分段的共享和保护。
（ 一）虚拟存储器的基本概念
（ 1） 虚拟存储器的引入
1,局部性原理
早在 1968年 P,Denning就指出过, 程序在执行时将呈现出 局
部性 规律, 即在一段时间内, 程序的执行仅局限于某个部分；
相应地, 它所访问的存储空间也局限于某个区域内 。 那么程
序为什么会出现局部性规律呢？ 原因可以归结为以下几点：
? 程序在执行时, 除了少部分的转移和过程调用指令外, 大多
数仍是顺序执行的 。
? 子程序调用将会使程序的执行由一部分内存区域转至另一部
分区域 。 但在大多数情况下, 过程调用的深度都不超过 5。
? 程序中存在许多循环结构, 循环体中的指令被多次执行 。
? 程序中还包括许多对数据结构的处理, 如对连续的存储空
间 ——数组的访问, 往往局限于很小的范围内 。
虚拟存储器的引入 -1
所以局限性表现为：
?时间局限性,如果程序中的某条指令一旦执行，则不久的
将来该指令可能再次被执行；如果某个存储单元被访问，则
不久以后该存储单元可能再次被访问。产生时间局限性的典
型原因是在程序中存在着大量的循环操作。
?空间局限性,一旦程序访问了某个存储单元，则在不久的
将来，其附近的存储单元也最有可能被访问。 即程序在一
段时间内所访问的地址，可能集中在一定的范围内，其典型
原因是程序是顺序执行的。
2。 虚拟存储器的定义
根据局部性原理，一个作业在运行之前，没有必要把全部作
业装入内存，而仅将那些当前要运行的那部分页面或段，先
装入内存便可启动运行，其余部分暂时留在磁盘上。
虚拟存储器的引入 -2
程序在运行时如果它所要访问的页（段）已调入内存，便可
继续执行下去；但如果程序所要访问的页（段）尚未调入内
存（称为缺页或缺段），此时程序应利用 OS所提供的请求调
页（段）功能，将它们调入内存，以使进程能继续执行下去。
? 如果此时内存已满, 无法再装入新的页 （ 段 ）, 则还须再利
用页 （ 段 ） 的置换功能, 将内存中暂时不用的页 （ 段 ） 调出
至磁盘上, 腾出足够的内存空间后, 再将所要访问的页 （ 段 ）
调入内存, 使程序继续执行下去 。 这样, 便可使一个大的用
户程序在较小的内存空间中运行；也可使内存中同时装入更
多的进程并发执行 。 从用户角度看, 该系统所具有的内存容
量, 将比实际内存容量大得多, 人们把这样的存储器称为虚
拟存储器 。
虚拟存储器的引入 -3
? 虚拟存储器 是采用请求调入和置换功能，将内存和
外存统一管理,把作业的一部分装入内存便可运行，
从逻辑上对内存容量进行扩充的一种虚拟的存储器
系统。 其逻辑容量由内存和外存容量之和, 计算机的地址
结构 二者 所决定，其运行速度接近于内存速度，而每位的成
本却又接近于外存。可见，虚拟存储技术是一种性能非常优
越的存储器管理技术，故被广泛地应用于大、中、小型机器
外
存
内
存
虚拟存储器逻
辑
地
址
（ 2）虚拟存储 器 实现方式
1。 请求分页系统,
它是在分页系统的基础上, 增加了请求调页功能和页面置换
功能所形成的页式虚拟存储系统 。 它允许只装入若干页 （ 而
非全部程序 ） 的用户程序和数据, 就可以启动运行, 以后再
通过调页功能和页面置换功能, 陆续把将要运行的页面调入
内存, 同时把暂不运行的页面置换到外存上, 置换时以页面
为单位 。
2。 请求分段系统：
它是在分段系统的基础上, 增加了请求调段和分段置换功能
所形成的段式虚拟存储系统 。 它允许只装入若干段 （ 而非全
部段 ） 的用户程序和数据, 就可以启动运行, 以后再通过调
段功能和置换功能将不运行的段调出, 同时调入将要运行的
段, 置换以段为单位 。
3。 请求段页式系统：它是在段页式系统的基础上, 增加了请求
调页和页面置换功能所形成的段页式虚拟存储系统 。
虚拟存储 器 实现方式 -1
（ 3） 虚拟存储器的特征
? 离散性, 指在内存分配时采用离散的分配方式，它是虚拟存
储器的最基本的特征。
? 多次性：指一个作业被分成多次调入内存运行，即在作业运
行时没有必要将其全部装入，只须将当前要运行的那部分程
序和数据装入内存即可。多次性是虚拟存储器最重要的特征。
? 对换性：指允许在作业的运行过程中在内存和外存的对换区
之间换进、换出。
? 虚拟性：指能够从逻辑上扩充内存容量，使用户所看到的内
存容量远大于实际内存容量。
（二） 请求分页存储管理方式
（ 1） 请求分页中的硬件支持
它是在纯分页系统的基础上, 增加了请求调页功能, 页面置
换功能所形成的页式虚拟存储系统, 它是目前常用的一种虚
拟存储器的方式 。
1,请求分页的页表机制
它是在纯分页的页表机制上形成的, 由于只将应用程序的一
部分调入内存, 还有一部分仍在磁盘上, 故需在页表中再增
加若干项, 供程序 (数据 )在换进, 换出时参考 。 在请求分页
系统中的每个页表项如图所示 。
页号 物理块号 状态位 P 访问字段 A 修改位 M 外存地址
请求分页中的硬件支持 -1
其中各字段说明如下：
? 状态位（存在位 P）：用于指示该页是否已调入内存，供程
序访问时参考。
? 访问字段 A：用于记录本页在一段时间内被访问的次数，或
最近已有多长时间未被访问，提供给置换算法选择换出页面
时参考。
? 修改位 M：表示该页在调入内存后是否被修改过。由于内存
中的每一页都在外存上保留一份副本，因此，若未被修改，
在置换该页时就不需将该页写回到外存上，以减少系统的开
销和启动磁盘的次数；若已被修改，则必须将该页重写到外
存上，以保证外存中所保留的始终是最新副本。
? 外存地址：用于指出该页在外存上的地址，通常是物理块号，
供调入该页时使用。
请求分页中的硬件支持 -2
2,缺页中断机构
在请求分页系统中, 每当所要访问的页面不在内存时, 便要产
生一缺页中断, 请求 OS将所缺页调入内存 。 与一般中断的主
要区别在于：
? 缺页中断在指令执行期间产生和处理中断信号, 而一般中断
在一条指令执行完后检查和处理中断信号 。
? 缺页中断返回到该指令的开始重新执行该指令, 而一般中断
返回到该指令的下一条指令执行 。
? 一条指令在执行期间, 可能产生多次缺页中断 。
3,地址变换机构
请求分页系统中的地址变换机构, 是在分页系统的地址变换
机构的基础上, 再为实现虚拟存储器而增加了某些功能所形
成的, 如产生和处理缺页中断, 以及从内存中换出一页的功
能等等, 下图 给 出了请求分页系统的地址变换过程 。
缺页中断处理
是
否
否
是
是 否
产生缺页中 否
是 断请求调页 是
开始 （ 程序请求访问一页 )
越界中断
CPU检索快表
页表项是否在快表中？
访问页表
页是否在内存中？
修改快表
修改访问位和修改位
形成物理地址
地址变换结束
保留 CPU现场
从外存中找到缺
页
页号 > 页 表长
度？
内存满否？
选择一页换出
该页是否被修改？
将该页写回外存
将一页从外存换入内存
修改页表
CPU从外存读缺页
启动 I/O硬件
（ 2）页面分配
1.最少物理块数
在为进程分配物理块时, 首先应该考虑的问题是：能保证进
程能正常运行所需的最少物理块数 （ 称为最小物理块数 ） 。
若系统为某进程所分配的物理块数少于此值时, 进程将无法
运行, 这取决于指令的格式, 功能和寻址方式 。
2,页面的分配和置换策略
在请求分页系统中, 可采取两种分配策略 ——固定和可变分
配策略 。 在进行置换时, 也可采取两种策略 ——全局置换和
局部置换 。 于是可组合成以下三种策略 。
? 固定分配局部置换策略：它基于进程的类型 （ 交互型或批处
理型等 ）, 或根据程序员, 系统管理员的建议, 为每个进程
分配一固定页数的内存空间, 在整个运行期间都不再改变 。
如果进程在运行中发现缺页, 则只能从该进程在内存的固定
页面中选出一页换出, 然后再调入另一页, 保证分配给该进
程的内存空间不变 。
页面分配 -1
? 可变分配全局置换策略：系统为每个进程分配一定数目的物
理块，而 OS本身也保持一个空闲物理块队列。当某进程发现
缺页时，由系统从空闲物理块队列中，取出一物理块分配给
该进程，并将欲调入的缺页装入其中。当空闲物理块队列中
的物理块用完时,OS才能从内存中选择一页调出，该页可能
是系统中任一进程的页。
? 可变分配局部置换：根据进程的类型或程序员的要求，为每
个进程分配一定数目的内存空间；但当某进程发生缺页时，
只允许从该进程在内存的页面中选出一页换出，而不影响其
它进程的运行。
页面分配 -2
? 3．页面分配算法
在采用固定分配策略时, 可采用以下几种物理块分配方法：
? 平均分配算法：将系统中所有可供分配的物理块, 平均分配
给各个进程 。
? 按比例分配算法：这是根据进程的大小按比例分配物理块 。
? 考虑优先权的分配算法：该方法是把内存中可供分配的所有
物理块分成两部分：一部分按比例分配给各进程；另一部分
则根据各进程的优先权, 适当地增加其相应份额后, 分配给
各进程 。
(3)页面调入策略
为能使进程运行, 必须事先将一部分要执行的程序和数据调入
内存 。
1,调入页面的时机
为了将进程运行时所缺的页面调入内存, 可采取策略有：
? 预调页策略是一种主动的缺页调入策略, 即将那些预计在不
久的将来会被访问的程序或数据所在的页面, 预先调入内存 。
由于预测的准确率不高 （ 50%）, 所以这种策略主要用于进程
的首次调入 。 有的系统将预调页策略用于请求调页, 例如在
VAX/VMS操作系统中, 采用了一种称为群页式的调页策略, 当
系统将进程所请求的页面调入内存时, 也同时将其相邻的几
个页面调入内存 。
? 请求调页策略是指当进程在运行中发生缺页时, 就立即提出
请求, 由系统将缺页调入内存 。 目前的虚拟存储器中, 大多
采用此策略 。 但这种策略在调页时须花费较大的系统开销,
如需频繁启动磁盘 I/O。
页面调入策略 -1
2。从何处调入页面
在虚拟存储系统中，外存（硬盘）常常被分成两部分；
文件区（用于存放文件）和对换区（用于存放对换页
面）。通常，对换区的磁盘 I/O速度比文件区要高。
每当进程发出缺页请求时，系统应从何处将缺页调入
内存呢？在 UNIX系统中，对于从未运行过的页面，都
应从硬盘文件区调入；对于曾经运行过而又被换出的
页面，可以从对换区调入；对于共享页面，该页面可
能已由其它进程调入内存，此时就无须再从对换区调
入。
（三）页面置换算法
（ Page Replacement Algorithms）
在进程运行过程中，如果发生缺页，此时内存中又无空闲
块时，为了保证进程能正常运行，就必须从内存中调出一页
程序或数据送磁盘的对换区。但将哪个页面调出，则须根据
一定的页面置换算法来确定。置换算法的好坏将直接影响系
统的性能，不适当的算法可能会导致进程发生, 抖动,
（ Thrashing)。即刚被换出的页很快又被访问，需重新调入，
导致系统频繁地更换页面，以致一个进程在运行中把大部分
时间花费在完成页面置换的工作上，我们称该进程发生了
,抖动, 。
从理论上讲，应将那些以后不再被访问的页面换出，或把那
些在较长时间内不会再被访问的页面换出。下面介绍几种常
用的置换算法。
页面置换算法 -1
（ 1）最佳（ Optimal）置换算法
它是一种理想化的算法，性能最好，但在实际上难于实现。即
选择那些永不使用的，或者是在最长时间内不再被访问的页
面置换出去。但是要确定哪一个页面是未来最长时间内不再
被访问的，目前来说是很难估计的，所以该算法通常用来评
价其它算法。
? 例：假定系统为某进程分配了三个物理块，并考虑有以下的
页面号引用串,7,0,l,2,0,3,0,4,2,3,0,3,2，
l,2,0,l,7,0,1。如下图 所示,进程运行时先将 7,0，
1三个页面装入内存。当进程访问页面 2时，产生缺页中断，
此时 OS根据最佳置换算法，页面 7将在第 18次才被访问，是三
页中将最久不被访问的页面，所以被淘汰。接着访问页面 0时，
发现已在内存中，而不会产生缺页中断，以此类推。 从 图可
以看出，采用最佳置换算法，只发生了 6次页面置换,9次缺
页中断。
最佳（ Optimal）置换算法 -1
页面
引用
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
7 7 7 2 2 2 2 2 2 2 2 2 2 2 2 2 2 7 7 7
0 0 0 0 0 0 4 4 4 0 0 0 0 0 0 0 0 0 0
物理
块
1 1 1 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1
缺页 x x x x x x x x x
发生了 6 次面置换,9 次缺页 中断。
(2)先进先出（ FIFO）置换算法
该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久
的页面予以淘汰。该算法实现简单，只须把一个进程已调入内存的页
面，按先后次序链接成一个队列，并设置一个指针即可。它是一种最
直观，性能最差的算法，它有 B E L A D Y 异常现象：对页面访问序列 A B
C D A B E A B C D E,物理块从 3 块增加到 4 块，缺页次数增加。
表中物理块的页号按调入内存先后次序排序
页面
引用
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
7 0 1 2 2 3 0 4 2 3 0 0 0 1 2 2 2 7 0 1
7 0 1 1 2 3 0 4 2 3 3 3 0 1 1 1 2 7 0
物理
块
7 0 0 1 2 3 0 4 2 2 2 3 0 0 0 1 2 7
缺页 x x x x x x x x x x x x x x x
发生了 12 次页面置换,缺页次数 15 次。
FIFO Illustrating Belady’s Anamoly
（ 3）最近最久未使用置换算法
LRU（ Least Recently Used）
该算法是选择最近最久未使用的页面予以淘汰，系统在每个页
面设置一个访问字段，用以记录这个页面自上次被访问以来所
经 历 的 时 间 T,当 要 淘 汰 一 个 页 面 时,选 择 T 最 大 的 页 面 。但 在
实 现 时 需 要 硬 件 的 支 持 （ 寄 存 器 或 栈 ）。 利 用 L R U 算 法 对 上 例 进
行页面置换的结果如下：表中 物理块的页号按访问先后次序排
序
页面
引用
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0
物理
块
7 0 1 2 2 3 0 4 2 2 0 3 3 1 2 0 1 7
缺页 x x x x x x x x x x x x
发生了 9 次面置换,缺页次数 12 次
(4)Clock置换算法
（最近未用算法 NRU（ Not Recently Used）
二次机会 (Second-Chance)
? 这是一种 LRU的近似算法。该算法为每个页面设置一位访问
位，将内存中的所有页面都通过链接指针链成一个循环队
列。当某页被访问时，其访问位置, 1”。在选择一页淘汰
时，就检查其访问位，如果是, 0”，就选择该页换出；若
为, 1”，则重新置为, 0”，暂不换出该页，在循环队列中
检查下一个页面，直到访问位为, 0”的页面为止。由于该
算法只有一位访问位，只能用它表示该页是否已经使用过，
而置换时是将未使用过的页面换出去，所以把该算法称为
最近未用算法。
? 物理块中页号按 访问 先后次序排序规则,上面为最近调入内
存页的页号，下面为最久调入内存页的页号。
Clock置换算法 -1
块号 页号 访问位 指针 替换指针
0
1
2 4 0 4
3
4 2 1 → 0 6
5
6 5 → 6 0 → 1 7
7 1 1 2
指向 最近被替
换的 4 号页所
在块的块号 2
2 → 6
被调入 页的页
号为 6
简单 C l oc k 置换算法的数据结构—存储器分 块表
（ 5） 页面缓冲算法
（ Page Buffering Algorithm）
? 该算法在页面分配时，采用可变分配和局部置换的方式 。 首
先为每个作业分配一个工作集（进程在一段时间内运行，要
用到的部分页面的集合），每个工作集的块数相对固定的
（在一段时间内），块号是可变的。系统自己也保留一部分
存储块作为页面缓冲，并把页面缓冲组织成两个队列：空闲
队列和已修改的页面队列。
? 经过一段时间的运行,OS把一些暂时不访问的页面（在每
个工作集采用 FIFO算法进行选择）放入页面缓冲，如果页面
未被修改，就将它直接放入空闲队列中；否则，便放入已修
改的页面队列中。注意，这时页面在内存中并未做物理上的
移动，而只是将页表中的表项移到上述两个队列之一中。图
中是页面缓冲算法的某个状态，有三个作业（ A,B,C）的
工作集和页面缓冲的两个队列。
页面缓冲算法 -1
? 当进程要访问页面时, 先到工作集中去找, 如果找到就可以
直接访问 。 否则, 到页面缓冲的两个队列中去找, 如果找到
也可以直接访问, 并将该页在页表中的表项链接到工作集队
列的末尾, 而把工作集队列的队首的页表表项链入页面缓冲
的两个队列中 。
40 3 19 22 61 20
24 41 5 23
7 12 13 30 10
1 32 14 9 43 39 8 16
工
作
集
已修改的页面队列 空闲队列
页面修改位 =“1” 页面修改位 =“0”
页面缓冲
A
B
C
页面缓冲算法 -2
? 如果还是没找到, 则启动磁盘 I/O,将缺页读入空闲队列第
一个物理块中 （ 利用 FIFO）, 并将该页在页表中的表项链接
到工作集队列的末尾 。
? 利用这种方法可使已修改的页面和未修改的页面, 都仍留在
内存中 。 当该进程要再次访问这些页面时, 便只须花较小的
开销就可以使这些页面又返回到该进程的工作集中 。 当在页
面缓冲的已修改页面达到一定数量时, 例如 64个页面, 可以
将它们一起写回到磁盘, 从而显著地减少了磁盘 I/O的操作
次数 。
? 页面缓冲算法是一个较简单的近似于 LRU页面缓冲算法, 它
与 LRU和 Clock置换算法相比, 无需硬件的支持, 又大大减少
了页面置换的开销 。 在性能上又比 FIFO要好, 有效地改善了
请求式分页系统的性能 。 著名的 VAX／ VMS和 Windows NT便是
使用这种算法, 而在 MACH操作系统实现中, 只是它没有区
分已修改页面和末修改页面 。
(6)性能分析
1.缺页率对有效访问时间的影响
在请求分页系统中, 假设存储器的访问时间 ma为 100ns（ 一般
为 10ns～几百 ns）, 缺页率为 p,缺页中断时间为 25ms,则有
效访问时间就可以表示为：
有效访问时间 =（ 1一 p） × ma十 p× 缺页中断时间
=（ 1一 p） × 0.1十 p× 25000 = 0.1十 24999.9 p
由上式可以看出, 有效访问时间与缺页率成正比 。 如果缺页
率为 0.1%,则有效访问时间约为 25μ s,与直接访问存储器的
有效访问时间 （ 0.1μ s ） 相比的时间, 程序执行的性能将受
到严重的影响 。 如果希望在缺页时, 仅使有效访问时间延长
不超过 10%,则可计算出缺页率 p=0.0000004,由此得出, 要
求在 2500000次的访问中才发生一页缺页, 即请求分页方式应
保持非常低的缺页率；否则, 将使程序执行速度受到严重影
响 。 此外, 提高磁盘 I/O的速度, 对改善请求分页系统的性能
至关重要 。 为此, 应选用高速磁盘和高速磁盘接口 。
性能分析 -1
2,工作集
? 程序在运行中所产生的缺页情况，会影响程序的运行速度及
系统性能，而缺页率的高低又将是与每个进程所占用的物理
块数目有关。这里我们简单地分析一下应为每个进程分配多
少个物理块，才能把缺页率保持在一个合理的水平上。
缺页率与进程所分得的物理块数目有密切关系。下图 说明了
的缺页率与进程分得的物理块数目 N之间的关系曲线。从图中
可以看出，缺页率随着所分得的物理块数目的减少而递增，
并在所分到的物理块数目较少处，出现一个拐点。在拐点下
限以左时，随着分到的物理块数目的增加，缺页率明显地减
少；而过了拐点，在下限以右时，随着分到的物理块数目的
增加，却对缺页率的改善并不明显。所以，为进程分配的物
理块数，应取在该曲线的拐点左右。
性能分析 -2
? 工作集的理论是在 1968年由 Denning提出来的 。 他认为, 程
序在运行时对页面的访问是不均匀的, 即往往在某段时间内
的访问仅局限于较少的若干个页面, 如果能够预知程序在某
段时间间隔内要访问哪些页面, 并能将它们提前调入内存,
将会大大地降低缺页率, 从而减少置换工作, 提高 CPU的利
用率 。
缺页率
拐点
所分得的物理块数
下限
上限
性能分析 -3
? 所谓工作集是指，在某段时间间隔（ Δ ）里，进程实际要
访问的页面的集合。 Denning认为，虽然程序只需有少量的
几页在内存就可以运行，但为了使程序能够有效地运行，较
少地产生缺页、就必须使程序的工作集全部在内存中。把某
进程在时间 t的工作集记为 w（ t,Δ ），把变量 Δ 称为工作集
,窗口尺寸, （ Windows Size）。正确选择工作集窗口（ Δ ）
的大小，对存储器的有效利用和系统吞吐量的提高，都将产
生重要的影响。
? 在 Windows NT中，虚拟存储管理程序（ Virtual Memory
Manager)为每一个进程分配固定数量的页面，并且这个数目
可以进行动态的调整。那么这个数量如何确定？又如何进行
动态的调整呢？这个数目就是由每个进程的工作集来确定，
并且根据主存的负荷和进程的缺页情况动态地调整其工作集。
性能分析 -4
? 其具体的作法是：一个进程在创建时就指定了一个最小工
作集, 该工作集的大小是保证进程运行在主存中应有的最小
页面数 。 但在主存负荷不太大 （ 页面不太满 ） 时, 虚存管理
程序还允许进程拥有尽可能多的页面作为其最大工作集 。 当
主存负荷发生变化时, 如空闲页架 （ 块 ） 不多了, 虚存管理
程序就使用, 自动调整工作集, 的技术来增加主存中可用的
自由页架 。 方法是检查主存中的每个进程, 将它当前工作集
大小与其最小工作集进行比较 。 如果大于最小值, 则从它们
的工作集中移去一些页面作为主存自由页面, 可为其它进程
所使用 。 若主存自由页面仍然太小, 则不断进行检查, 直到
每个进程的工作集都达到最小值为止 。
当每个工作集都已达到最小值时, 虚存管理程序跟踪进程的
缺页数量, 根据内存中自由页面数量可以适当增加其工作集
的大小 。
（四）请求分段存储管理方式
请求分段系统在分段系统的基础上实现的虚拟存储器, 是以分
段为单位进行换入, 换出的 。 在程序运行之前只要先调入若
干个分段 （ 不必调入所有的分段 ）, 便可启动运行 。 当所访
问的段不在内存时可请求 OS将所缺的段调入内存 。 为实现请
求分段存储管理方式, 同样需要一定的硬件支持和相应的软
件, 有段表机制, 缺段中断机构以及地址变换机构 。
（ 1） 请求分段中的硬件支持
1,段表机制
在请求分段式管理中在段表中增加若干项, 以供程序在调进,
调出时参考 。 请求分段的段表项如下：
段 段 段的 存取 访问 修改 存在 增补 外存
名 长 基址 方式 字段 A 位 M 位 P 位 起址
请求分段中的硬件支持 -1
在段表项中，除了段名 (号 )、段长、段在内存的起始地址外，
还增加了以下几项：
? 存取方式：用于标识本分段的存取属性是只执行、只读，还
是允许读／写。
? 访问字段 A：用于记录该段被访问的频繁程度。
? 修改位 M：用于表示该段进入内存后，是否已被修改过。
? 存在位 P：说明本段是否已调入内存。
? 增补位：用于表示本段在运行过程中，是否进行过动态增长。
? 外存起址：指示本段在外存中的起始地址，即起始盘块号。
2.缺段中断机构
在请求分段系统中，采用的是请求调段策略。即当进程所要
访问的段未调入内存时，便由缺段中断机构产生一缺段中断
信号，由缺断中断处理程序将所需的段调入内存。缺段中断
的处理过程如下图：
请求分段中的硬件支持 -1
拼接后形成合适
大小的空闲区
淘汰一个或几个段
以形成合适大小的
空闲区
虚段不在内存中
阻塞请求的进程
内存中有合适的空闲区？
从外存读入段
修改段表和内存空闲链
唤醒请求进程
返回
空闲区大小总和能否满足？
N
N
请求分段中的硬件支持 -2
3。 地址变换机构
请求分段系统中的地址变换机构, 是在分段系统地址
变换机构的基础上形成的 。 由于被访问的段并非全
在内存, 所以在地址变换时, 若发现所要访问的段
不在内存时, 必须先将所缺的段调入内存, 并修改
了段表之后, 才能再利用段表进行地址变换 。 为此,
在地址变换机制中又增加了某些功能, 如缺段中断
的请求及其处理等 。
请求分段中的硬件支持 -3
4。段的动态链接
经过编释或汇编得到的一组目标程序需经链接程序，连接
装配成一个一维的线性连续地址空间，这一过程称为静态链
接，但是这种连接装配过程既复杂又费时，还经常发生许多
被连接好的摸块在作业运行过程中根本不用，而造成连接时
的机时和主存空间的浪费，所以最好能采用什么时候用到那
一段责连接该段的方法，这种方法称为动态连接方法。段的
动态链接是指“在一个程序运行开始时，只将主程序装配好
并调入主存，其它各段的装配是在主程序段运行过程中逐步
进行的，每当需要调用一个新段时，再将该段装配好，并与
主程序段连接。在分段存储管理环境中，由于逻辑地址空间
是二维的，每段有自己的段名，因而实现动态连接比较容易。
5。 请求段页 式地址变换机构如下图：
允 许 动 态
增
长吗？
启动要处理指令
计算有效地址
访问地址 v= (s,p,d)
S≤ 段表长吗？
段连接了吗？
段在主存吗？
P≤ 页表长吗？
访问类型合
法吗？
页在主存吗？
缺页中断处理
执行下一条指令
访问该地址
完成指令
形成主存地址
出错处理
越界中断处理
连接中断处理
缺段中断处理
出错处理
N
N
N
N
N
N
N
（ 2） 分段共享与保护
分段保护,
1.越界保护：段表长和段长
在段式系统存储管理方案中, 设置了段表寄存器,
存放段表始址 Cb和段表长 Cl,在进行地址变换时,
系统将逻辑地址中的段号 S与段表长度 Cl进行比
较, 若 S≥C l访问越界, 产生越界中断信号 。 未
越界, 根据段表的始址 Cb和段号 S,计算出该段
对应段表项的位置, 从中读出该段在内存中的起
始地址 b。 如增补位为 0,再检查段内地址 d是否
超过该段的段长 l,超过, 产生越界中断, 否则,
将该段的基址 b与段内地址 d相加, 得到要访问的
内存物理地址 。
ClCb
+
段号 S 段内地址 d
比较
比较
b + d
比较
段 表 快表
物理地址
段表始址寄存器 段表长度寄存器 逻辑地址
地址越界
d>=1
地址越界
地址越界
l b
S l b
.,.
d>=1
分段地址映射及存储保护机制
S>= Cl
MULTICS Address Translation Scheme
Segmentation Hardware
分段共享与保护 -1
2.存取保护：存取权 (R,W,E)
分段存储管理方式实现分段的共享和保护只须在每
个进程的段表中, 用相应的表项来指向共享段在内
存中的 起始地址 。 为了实现请求分段共享, 减少共
享段的置换, 应配置相应的共享段表, 用来对共享
段进行操作 。
在系统中, 用共享段表来记录了每一个共享段的段
号和段长, 内存始址, 存在位等信息, 并记录共享
此分段的每个进程的情况 。 共享段表如下图所示 。
分段共享与保护 -1
其中：
? 共享进程计数 器 COUNT：记录有多少个进程需要共享该分段。
? 存取控制字段：说明不同的进程对该分段不同的存取权限。
? 段号：对于同一个共享段，不同的进程可以使用不同的段号
去共享该段。
段名 段长 内存起址 状态 外存起址
共享进程计数器 COUNT
状态 进程名 进程号 段号 存取控制
分段共享与保护 -2
? 共享段的分配和 回收：
共享段的分配, count=count+1;
共享段的 回收,count=count-1;
if count==0 then 回收 ;
（五） Windows98虚拟存储技术
（ 1） Intel80386提供的存储管理方式
在 Inte180386芯片中, 包含了存储管理部件 MMU（ Memory
Management Unit）, 由它来提供实现虚拟存储器所需的硬件
支持, 即请求段表 （ 页表 ） 机制, 缺段 （ 页 ） 机构, 地址变
换机构 。 其地址变换过程分两步进行, 第一步由分段部件将
逻辑地址转换为线性地址, 并将该地址送分页部件；第二步
由分页部件将线性地址变换为物理地址 。 如果仅用分段存储
管理方式, 其分页部件将被旁路 （ 失效 ）, 此时分段部件送
出的线性地址便是物理地址, 直接送内存地址寄存器 。 为了
提高分段和分页的地址变换速度, 在分段和分页部件中, 都
配置了高速缓冲存储器, 作为快速段表和页表 。
80386既支持分段, 也支持分页, 可根据需要构成以下四种存
储管理方式：
1,不分段也不分页的存储管理方式 。
Windows98虚拟存储技术 -1
2,分页不分段存储管理方式（ UNIX／ 386系统）。
3．分段不分页存储管理方式。
4．分段分页存储管理方式。
（ 2）分段存储管理
1,段描述符表
80386为每个用户任务所配置的段表, 称为局部描述符表 LDT
（ Local Descriptor Table） 。 其中, 每个表项为一个段的
描述符, 共 8个字节长 。 此外, 还配置了一张对系统任务都有
用的全局描述符表 GDT（ Global Descriptor Table） 。 在任
一时刻 GDT和某一个 LDT是可被访问的, 在分段部件中, 还配
置了全局描述符表寄存器 GDTR和局部描述符表寄存器 LDTR。
它们都是 6个字节长, 分别指向当前的 GDT和 LDT。 两个描述符
的格式基本上相同 。 如图 所示 。
各字段说明如下：
Windows98虚拟存储技术 -2
?段的基址,32位，定义了段在 4GB线性地址空间中的始址。
?段界限值：规定了段的最大长度。其单位可以是字节或页
（ 4KB），这取决于粒度单位 G。当 G为 1时，表示段长是以页
为单位；当 G为 0时，表示段长以字节为单位。由于段长为 20
位，故当 G为 1时，最大段长为 4 GB。
段的基址 15…… 0 段界限值 15…… 0
段基址 G D 0 0 界限值 P DPL S TYPE A 段基址
31… 24 19… 16 23… 16
31 23 19 1615 12 8 7 0
Segmentation with Paging,Pentium(2)
? Pentium code segment descriptor
? Data segments differ slightly
Windows98虚拟存储技术 -3
2,分段的地址变换机构
?段寄存器
在 80386处理器中, 共有 6个段寄存器 。 它们是：代码段寄存器
CS,栈段寄存器 SS,四个数据段寄存器 DS,ES,FS和 GS。 段
寄存器和 8086一样仍为 16位 。 在实方式时, 段中存放段的基
址的高 16位 。 因此, 将它左移 4位后与偏移量相加, 便形成 20
位的物理地址 。 但在保护方式下, 16位的段寄存器已不足以
用来存放 32位的段的基址, 所以在段寄存器中所存放的是指
向描述符表中某个描述符的指针 。 此时, 段寄存器中的 TI（ l
位 ） 用来指示描述符表的类型, 即或者指示选择全局描述符
表, 或者指示选择局部描述符表 。 RPL（ 2位 )为请求者的特权
级 。 描述符表项索引 Index（ 13位 ） 可用来在 8K个描述符中任
选其一 。
?虚地址结构和地址变换
Segmentation with Paging,Pentium (1)
A Pentium selector
Windows98虚拟存储技术 -4
在 80386中的虚地址结构如下：
其中,TI为描述符表类型； RPL是请求者特权级； S为段号 Index
项，用来选择描述符。其前 16位实际上是放在段寄存器中的。
分段部件中，是将逻辑地址变换为线性地址，在进行地址变
换时，首先是从相应的段寄存器中取得段号 S，即获得指向段
描述符表的指针 Index，如果此时 TI=0，则从 GDT中选择一描
述符；否则（ TI=1），从 LDT中选择一描述符。从所获得的
描述符中可得到段的基址，然后将段的基址与偏移量相加，
得到线性地址。对于只分段、不分页的存储管理方式，此线
性地址就是内存的物理地址；若是既分段、又分页的存储管
理方式，则还须将此线性地址送分页部件，再形成物理地址。
段号 S TI RPL 偏移量
13位 1位 2位 32位
＋
＋
8B
基地址
限长
其它字段
8B
8B
。
。
页目录号 P1 外部页内地址 P2 页内位移 D
外部页表寄存器
（ 索引 ）
段号 S TI RPT 偏移量
CS代码段寄存器 DS数据段寄存器
GDTR全局描述符寄存器 LDTR局部描述寄存器
＋
＋
＋
块号 页内位移 D
A page table entry for a mapped page on
the Pentium
Windows98虚拟存储技术 -5
(3)Windows98系统地址空间的划分
Intel386以后的 CPU有了 32位或 64位的内存寻址范围, 所以系
统的地址空间可达 4GB或更大 。 在 Windows98系统提供了
4GB虚拟的 32位的地址空间, 给每个进程分配 2GB的专用地
址空间, 而把剩余的 2GB地址空间分成系统空间 （ 1GB） 和
用于所有的共享内存区域的单个共享的用户空间 （ 1GB） 。
这个 1GB的共享区域对于用户态是可写的, 所以任何 Win32应
用程序都可以写共享内存区和映象文件 （ 映象文件是指把驻
留在盘上的文件看成是虚拟主存的一部分 ） 。 MS-DOS应用
程序和 Win16应用程序也都在这个共享的空间中 。 Windows
NT将共享内存区域放在专用进程地址空间内 。
每一个基于 MS-DOS的程序和 32位 Windows程序都有各自的
4GB虚拟地址空间 。 16位 Windows应用程序共享单个的 4GB
地址空间 。 4GB的地址空间分为两部分,2GB用于用户应用
程序, 2GB用于操作系统组件 。 程序以如下方式使用虚拟地
址空间里的地址：
Windows98虚拟存储技术 -6
? 0~1MB：基于 MS-DOS的程序就像真的在 MS-DOS环境中运
行那样使用这些地址，所有其它程序将忽略这些地址。这些
地址仍可为程序加载的实模式设备驱动程序所使用。
? 1~4MB：由于 Windows NT在这些地址空间上加载，为了维
护与 NT的兼容性,Windows98与 32位程序也不使用这一段
地址空间。但由于向下兼容的缘故,16位程序使用这些地址。
? 4MB~2GB,WIN32应用程序使用。
? 2GB~3GB：由 DLL（动态链接库）和其它共享组件使用。
? 3GB~4CB：低层的内存管理、文件系统、驱动程序（ VxD）
使用。这些地址一般是 Ring0组件使用。
Windows98虚拟存储技术 -7
（ 4） VMM——虚拟存储管理程序
Windows98用虚拟存储管理程序 （ Virtual Memory Manager）
来实现请求调页的虚拟存储技术, 把系统 4GB的虚拟地址空间
映射到机器的物理内存上 （ 32MB或 64MB） 。
Windows98的虚拟存储管理程序通过两个内存管理进程向应用
程序提供虚拟内存：一个是页面调度 （ paging） ——负责在
物理内存和硬盘的交换文件之间交换数据；另一个是地址转
换 ——负责物理地址和虚拟地址空间的地址或映象文件 I/O之
间的转换 。
VMM将物理内存分成一个个大小为 4KB页面 （ 或称为块 ） 。 将虚
拟地址空间 （ 应用程序所在的空间 ） 也划分成 4KB大小的页 。
当程序要运行时, 一部分页面被装入物理内存, 另一部分则
放在硬盘的虚似内存交换文件 （ 或称为页交换文件 ） 中 。 交
换文件是指位于硬盘上用来模拟物理内存的文件, 它由 VMM专
门用来保存内存页面, 作为虚拟内存空间使用 。
Windows98虚拟存储技术 -8
当程序访问那些不在内存中的页面时,CPU会产生页面出错
（ Page Fault）,VMM便会从交换文件中将相应的页面换入
内存。
Windows98交换文件（ Win386.swp）是动态的，它可根据系统
内存的负荷和可利用的磁盘空间大小而增大或减小。动态交
换文件可以对硬盘进行有效的利用，因为它可占用硬盘的一
个已成碎片的区域，而不引起重大的性能下降。注意：保证
交换文件高质量运行的一条最好的途径是：确保包含交换文
件的磁盘有足够的可利用的空间，以便交换文件的大小可以
根据需要增大或减小。一般情况下，可以让 Windows98自动
管理虚拟内存。如果用户想要把交换文件设置在特定的硬盘
上，或者由于磁盘空间有限想把交换文件的大小限制在一定
范围，就要修改设置。但是在设置时，特别要注意：交换文
件太小会严重影响系统的性能。
Windows98虚拟存储技术 -9
交换文件（ Win386.Swp）存放在 C,\Window目录下。用户不
应把交换文件安置在压缩硬盘上，因为这样做将影响其性能。
交换文件的运行速度应当尽可能地快，应当定期对硬盘空间
进行整理，以使交换文件能使用连续的存储区，这也有助于
提高交换文件访问的速度。在 Windows NT中，交换文件可跨
越多个驱动器，其名为 Pagefile.sys。
（ 5）页面置换算法
Windows95/98虚拟内存管理器置换算法如下：
1。 调页算法：当某个线程试图访问一无效页面而产生页面出
错 （ Page Fault） 时, VMM采用群集技术将其邻近的页面与页
面目录一起装入内存的空闲块中 。 所谓群集技术是指当需要
调一页时, 将包括该页在内的一个页面集合取入内存的空闲
块中, 这样可以减小页面出错和磁盘操作的次数 。
Windows98虚拟存储技术 -10
2。 淘汰算法：如果内存中没有空闲块, VMM会使用淘汰算法将
页面从内存移到交换文件中 。 每个进程在内存中都有一组有
效的页面 ——工作集, 以保证进程的有效运行 。 为简化起见,
VMM使用先进先出的算法 （ FIFO） 。 即当需要进行页面淘汰时,
VMM将工作页面集中存在时间最长的页面从内存中移到交换文
件中, 为新页面腾出空间 。 由于淘汰页是当前进程的工作页
面集, 所以可以保证该进程的页面不会被另外的进程所替代 。
（ 6） 页表结构
Windows95/98/NT支持的虚拟地址空间达 4GB,都采用二级页表
机构来管理虚拟存储空间 。 见 第五 课 。
Windows98虚拟存储技术 -11
（ 7） 映象文件 I/O
当应用程序将要装入的文件大小比 RAM和交换文件合起来还要
大时, VMM的映象文件 I/O服务功能可以将虚拟内存地址映射
到一个大文件中, 并通知应用程序此文件可用, 然后仅将应
用程序实际需要访问的那部分装入内存 。 由于整个大文件中
只有一部分装入内存 （ RAM或交换文件 ）, 极大地减少了文件
装入时间, 提高了系统资源的使用 。 这对于那些经常需要访
问巨型文件的数据库应用程序来说是一个非常有用的服务 。
（ 8） 页面锁定
对有特殊要求的应用程序和系统核心的页面, VMM可授予进程
特殊权限, 以将选定的虚拟内存页面锁定在工作页面集中,
这样关键页面在使用过程中便不会被换出内存 。
Windows 2000/XP内存布局
应用程序代码
全程变量
每个线程堆栈
DLL代码 3GB用户空间
1GB系统空间
7FFFFFFF
80000000 内核和执行体
HAL
引导驱动程序
C0000000 进程页表 BFFFFFFF
超空间 C0000000
C0800000 系统高速缓存
分页缓冲池
未分页缓冲池
FFFFFFFF FFFFFFFF
系统代码 (Ntoskrnl,HAL) 和一些系统中
初始的未分页缓冲池
系统映射视图（例如,Win32k.sys)或者
会话空间
超空间和进程工作集列表
进程的页表和页目录
附加的系统 PTE（高速缓存可以扩展到
这）
没有使用,不可访问
HAL使用
故障转储信息
未分页缓冲池扩充
系统 PTE
分页缓冲池
系统高速缓存
系统工作集列表
80000000
C0800000
C0400000
C0000000
A4000000
A0000000
FFBE0000
EB000000(min)
E1000000
C1000000
C0C00000
FFC00000
进程的 系统页表与进程私有页表
.
.
.
.
.
.
.
.
.
进程 1
的页表
进程 2
的页表
PTE 0
进程 1的
页目录
进程 2的
页目录
PTE 0
PDE 0 PDE 0
System PTE 0
PDE 511
PDE 512
PDE n PDE n
PDE 512
PDE 511
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
System PTE n
.
.
.
系统页表
进 程 仍
然 没 有
访 问 系
统页表
各进程
私有
物理地址扩展 (PAE,Physical Address Extension)
每个 PDE和 PTE表项都是 8个字节，物理页面号为
24Bit，可访问的物理地址空间可达 64GB。
例题
某虚拟存贮器的用户编程空间共 32个页面, 每页 1KB,主存为
16KB。 假定某时刻用户页表中已调入主存的页面的虚拟页号
和物理页表对照表为表一, 则下表中与虚拟地址相对应的物
理地址为表二 （ 如果主存找不到, 即为该页失效 ） 。 虚拟存
贮存的功能是由 ﹎﹎ C﹎﹎ 完成的 。 在虚拟存贮系统中, 采用
﹎﹎ D﹎﹎ 提高 ﹎﹎ E﹎﹎ 的速度 。
表一 虚页号 物理页号
0 5
1 10
2 4
8 7
表二 虚地址 物理地址
0A5C（ H） ﹎﹎ A﹎﹎
1A5C（ H） ﹎﹎ B﹎﹎
例题 -1
供选择的答案：
A,B：① 页失效 ② 1E5C（ H）
③ 2A5C（ H） ④ 165C（ H）
⑤ 125C（ H） ⑥ 1A5C（ H）
C,① 硬件 ② 软件 ③ 软、硬件结合
D,① 高速辅助存贮器 ② 高速光盘存贮器
③ 快速通道 ④ 高速缓冲存贮器
E,① 连接编辑 ②虚地址分配
③ 动态地址翻译 ④动态连接
例题 -2
解,每页大小 1KB,用 16进制表示为 400H,由虚地址通过直接
映象的地址转换成物理地址步骤如下：
? 将虚地址分离成页号 p和页内地址 d：
页号 p＝ （ 虚地址／页大小 ） 取整＝ （ 0A5CH/400H） 取整＝ 2
页内地址 d＝虚地址－页号 p× 每页大小＝ 0A5C(H)－ 2× 400(H)
＝ 25C(H)
? 根据页号查页表, 由页号 p＝ 2查页表得物理页号为 4
? 将物理页号和页内地址构成物理地址＝物理页号 × 页大小＋
页内地址＝ 4× 400(H)＋ 25C(H)＝ 125C(H)
同理虚拟地址 1A5CH分离成页号 P＝ 6和页内位移 15CH.
查页表知该页不在内存, 页失效产生缺页中断调入内存 。
习题
1,虚拟存贮管理系统的基础是程序的局部性理论 。 此理论的基
本含义是 ﹎﹎ A﹎﹎ 。 局部性有两种表现形式：时间局限性和
﹎﹎ B﹎﹎ 。 它们的意义分别为 ﹎﹎ C﹎﹎ 和 ﹎﹎ D﹎﹎ 。 根据
局部性理论, Denning提出了 ﹎﹎ E﹎﹎ 。
A,B,① 程序执行时对主存和访问是不均匀的 ② 代码的顺
序执行 ③ 变量的连续访问 ④ 指令的局部性
⑤ 数据的局部性 ⑥ 空间局部性
C,D,① 最近被访问的单元, 很可能在不久的将来还要被访问
② 最近被访问的单元, 很可能在它附近的单元也即将被访问
③ 结构化程序设计, 很少出现转移语句
④ 程序中循环语句的执行时间一般很长
⑤ 程序中使用的数据局部于各子程序
E,① Cache结构的思想 ② 工作集理论
③ 最近最少使用 （ LRU） 页面置换算法 ④ 先进先出页
面置换算法
习题 -1
2.什么叫虚拟存贮器?试述虚拟存贮器的实现原理和它的物质基
础 。
3,在请求分页内存管理的页表表项中, 其中状态位供 ﹎﹎ A﹎
﹎ 时参考；修改位供 ﹎﹎ B﹎﹎ 时参考；访问位供 ﹎﹎ C﹎﹎
时参考；外存始址供 ﹎﹎ D﹎﹎ 时参考 。
A,B,C,D,（ l） 分配页面； （ 2） 置换算法； （ 3） 程序访
问； （ 4） 换出页面； （ 5） 调入页面 。
4.在请求调页系统中, 凡未装入过内存的页都应从 ﹎﹎ A﹎﹎ 调
入；已运行过的页主要是从 ﹎﹎ B﹎﹎ 调入, 有时也可以从 ﹎
﹎ C﹎﹎ 调入 。
A,B,C,（ 1） 系统区； （ 2） 文件区； （ 3） 对换区； （ 4）
页面缓冲池 。
5.详述在设有快表的请求分页存储管理系统中, 一个虚地址转
换成物理内存地址的过程 。
习题 -2
6．在请求调页系统中有着多种置换算法：（ 1）选择最先进入
内存的页面予以淘汰的算法称为 ﹎﹎ A﹎﹎ ；（ 2）选择在以
后不再使用的页面予以淘汰的算法称为 ﹎﹎ B﹎﹎ ；（ 3）选
择自上次访问以来所经历时间最长的页面予以淘汰的算法称
为 ﹎﹎ C﹎﹎ ；（ 4）选择自某时刻开始以来，访问次数最少
的页面予以淘汰的算法称为 ﹎﹎ D﹎﹎ 。
A,B,C,D：（ 1） FIFO算法；（ 2） OPT算法；（ 3）
LRU算法；（ 4） NRU算法；（ 5） LFU算法。
7,在一个请求分页系统中，采用 FIFO页面置换算法时，假如
一个作业的页面访问顺序为 4,3,2,1,4,3,5,4,3,2，
l,5，当分配给该作业的物理块数 M分别为 3和 4时，试计算访
问过程中所发生的缺页次数分别为 ﹎﹎ A﹎﹎ 和 ﹎﹎ B﹎﹎,
缺页率分别为 A/C和 B/C，其中 ﹎﹎ C﹎﹎ 为访问次数。比较所
得的结果为 ﹎﹎ D﹎﹎ 。
A,B,C,D,见 6题
习题 -3
8,在一个请求分页系统中, 采用 LRU页面置换算法时, 假如一
个作业的页面访问顺序为 4,3,2,1,4,3,5,4,3,2，
l,5,当分配给该作业的物理块数 M分别为 3和 4时, 试计算访
问过程中所发生的缺页次数 ﹎﹎ A﹎﹎ 和 ﹎﹎ B﹎﹎, 缺页率
分别为 A/C和 B/C,其中 ﹎﹎ C﹎﹎ 为访问次数 。 比较所得的结
果为 ﹎﹎ D﹎﹎ 。
A,B,C,（ 1） 5； （ 2） 6； （ 3） 7； （ 4） 8； (5)9； (6)10；
(7)11； (8)12。
D,(1) 正常现象, 即存储块增加, 缺页次数减少；
(2) 存在奇异现象, 即存储块增加, 缺页次数反而增加；
(3) 存储块增加, 缺页次数不变 。
9.试述 Windows NT页面置换算法 -页面缓冲算法的原理和特点 。
10.试述 clock页面置换算法的原理和特点 。
习题 -4
11,静态链接是程序在 ﹎﹎ A﹎﹎ 时进行的，而动态链接是程序
在 ﹎﹎ B﹎﹎ 时进行的。
A,B：（ 1）编译；（ 2）装入；（ 3）调用；（ 4）紧凑。
12.巳知一个有快表的请求分页系统,内存读写周期为 Tr(1us)
内外存之间传送一个页面的时间 Tt(5ms),快表的命中率为 p
(80%),页面失效率为 f (10%)。 计算快表命中时存取时间为
﹎﹎ A﹎﹎, 快表不命中, 内存中页表查到时存取时间为 ﹎
﹎ B﹎﹎, 页面失效时存取时间为 ﹎﹎ C﹎﹎ 。 求系统和内存
有效存取周期 EAT(平均存取时间 )。
A,B,C,（ 1） 1μ s； （ 2） 2μ s； （ 3） 3μ s； （ 4） 500μ s；
(5) 501μ s； (6)5ms。
? 快表命中时存取时间为 Tr,快表的命中率为 p (80%)
? 快表不命中, 内存中页表查到时存取时间为 Tr+ Tr
? 页面失效时存取时间为 Tt,页面失效率为 f (10%)
? 求系统和内存有效存取周期 EAT(平均存取时间 )为
EAT = Tr*p + Tt*f + 2Tr*(1-p-f)
= 1*80% + 5000*10% + 2*10%
= 501 μ s
(Virtual Memory)
教学目的,
为了在内存空间运行超过内存总容量的大作业，或
者同时运行大量作业，解决的方法是从逻辑上扩充
内存容量，这正是虚拟存储技术所要解决的主要问
题。 本课要介绍虚拟存储技术实现的各种方案，每
种方案所需的硬件和软件支持。
教学要求：
? 掌握 虚拟存储器的 理论基础和定义,熟悉虚拟存
储 器 实现方式和 特征。
? 掌握请求分页的页表机制、缺页中断机构和地址
变换机构,熟悉 页面的分配和置换策略、页面的
分配的算法。
? 熟练掌握最佳置换算法、先进先出（ FIFO）置换
算法、最近最久未使用置换算法 LRU，掌握 Clock
置换算法和 页面缓冲算法； 掌握有效访问时间计
算,熟悉 工作集概念。
? 掌握请求分段的段表机制、缺段中断机构和地址
变换机构,熟悉 分段的共享和保护。
（ 一）虚拟存储器的基本概念
（ 1） 虚拟存储器的引入
1,局部性原理
早在 1968年 P,Denning就指出过, 程序在执行时将呈现出 局
部性 规律, 即在一段时间内, 程序的执行仅局限于某个部分；
相应地, 它所访问的存储空间也局限于某个区域内 。 那么程
序为什么会出现局部性规律呢？ 原因可以归结为以下几点：
? 程序在执行时, 除了少部分的转移和过程调用指令外, 大多
数仍是顺序执行的 。
? 子程序调用将会使程序的执行由一部分内存区域转至另一部
分区域 。 但在大多数情况下, 过程调用的深度都不超过 5。
? 程序中存在许多循环结构, 循环体中的指令被多次执行 。
? 程序中还包括许多对数据结构的处理, 如对连续的存储空
间 ——数组的访问, 往往局限于很小的范围内 。
虚拟存储器的引入 -1
所以局限性表现为：
?时间局限性,如果程序中的某条指令一旦执行，则不久的
将来该指令可能再次被执行；如果某个存储单元被访问，则
不久以后该存储单元可能再次被访问。产生时间局限性的典
型原因是在程序中存在着大量的循环操作。
?空间局限性,一旦程序访问了某个存储单元，则在不久的
将来，其附近的存储单元也最有可能被访问。 即程序在一
段时间内所访问的地址，可能集中在一定的范围内，其典型
原因是程序是顺序执行的。
2。 虚拟存储器的定义
根据局部性原理，一个作业在运行之前，没有必要把全部作
业装入内存，而仅将那些当前要运行的那部分页面或段，先
装入内存便可启动运行，其余部分暂时留在磁盘上。
虚拟存储器的引入 -2
程序在运行时如果它所要访问的页（段）已调入内存，便可
继续执行下去；但如果程序所要访问的页（段）尚未调入内
存（称为缺页或缺段），此时程序应利用 OS所提供的请求调
页（段）功能，将它们调入内存，以使进程能继续执行下去。
? 如果此时内存已满, 无法再装入新的页 （ 段 ）, 则还须再利
用页 （ 段 ） 的置换功能, 将内存中暂时不用的页 （ 段 ） 调出
至磁盘上, 腾出足够的内存空间后, 再将所要访问的页 （ 段 ）
调入内存, 使程序继续执行下去 。 这样, 便可使一个大的用
户程序在较小的内存空间中运行；也可使内存中同时装入更
多的进程并发执行 。 从用户角度看, 该系统所具有的内存容
量, 将比实际内存容量大得多, 人们把这样的存储器称为虚
拟存储器 。
虚拟存储器的引入 -3
? 虚拟存储器 是采用请求调入和置换功能，将内存和
外存统一管理,把作业的一部分装入内存便可运行，
从逻辑上对内存容量进行扩充的一种虚拟的存储器
系统。 其逻辑容量由内存和外存容量之和, 计算机的地址
结构 二者 所决定，其运行速度接近于内存速度，而每位的成
本却又接近于外存。可见，虚拟存储技术是一种性能非常优
越的存储器管理技术，故被广泛地应用于大、中、小型机器
外
存
内
存
虚拟存储器逻
辑
地
址
（ 2）虚拟存储 器 实现方式
1。 请求分页系统,
它是在分页系统的基础上, 增加了请求调页功能和页面置换
功能所形成的页式虚拟存储系统 。 它允许只装入若干页 （ 而
非全部程序 ） 的用户程序和数据, 就可以启动运行, 以后再
通过调页功能和页面置换功能, 陆续把将要运行的页面调入
内存, 同时把暂不运行的页面置换到外存上, 置换时以页面
为单位 。
2。 请求分段系统：
它是在分段系统的基础上, 增加了请求调段和分段置换功能
所形成的段式虚拟存储系统 。 它允许只装入若干段 （ 而非全
部段 ） 的用户程序和数据, 就可以启动运行, 以后再通过调
段功能和置换功能将不运行的段调出, 同时调入将要运行的
段, 置换以段为单位 。
3。 请求段页式系统：它是在段页式系统的基础上, 增加了请求
调页和页面置换功能所形成的段页式虚拟存储系统 。
虚拟存储 器 实现方式 -1
（ 3） 虚拟存储器的特征
? 离散性, 指在内存分配时采用离散的分配方式，它是虚拟存
储器的最基本的特征。
? 多次性：指一个作业被分成多次调入内存运行，即在作业运
行时没有必要将其全部装入，只须将当前要运行的那部分程
序和数据装入内存即可。多次性是虚拟存储器最重要的特征。
? 对换性：指允许在作业的运行过程中在内存和外存的对换区
之间换进、换出。
? 虚拟性：指能够从逻辑上扩充内存容量，使用户所看到的内
存容量远大于实际内存容量。
（二） 请求分页存储管理方式
（ 1） 请求分页中的硬件支持
它是在纯分页系统的基础上, 增加了请求调页功能, 页面置
换功能所形成的页式虚拟存储系统, 它是目前常用的一种虚
拟存储器的方式 。
1,请求分页的页表机制
它是在纯分页的页表机制上形成的, 由于只将应用程序的一
部分调入内存, 还有一部分仍在磁盘上, 故需在页表中再增
加若干项, 供程序 (数据 )在换进, 换出时参考 。 在请求分页
系统中的每个页表项如图所示 。
页号 物理块号 状态位 P 访问字段 A 修改位 M 外存地址
请求分页中的硬件支持 -1
其中各字段说明如下：
? 状态位（存在位 P）：用于指示该页是否已调入内存，供程
序访问时参考。
? 访问字段 A：用于记录本页在一段时间内被访问的次数，或
最近已有多长时间未被访问，提供给置换算法选择换出页面
时参考。
? 修改位 M：表示该页在调入内存后是否被修改过。由于内存
中的每一页都在外存上保留一份副本，因此，若未被修改，
在置换该页时就不需将该页写回到外存上，以减少系统的开
销和启动磁盘的次数；若已被修改，则必须将该页重写到外
存上，以保证外存中所保留的始终是最新副本。
? 外存地址：用于指出该页在外存上的地址，通常是物理块号，
供调入该页时使用。
请求分页中的硬件支持 -2
2,缺页中断机构
在请求分页系统中, 每当所要访问的页面不在内存时, 便要产
生一缺页中断, 请求 OS将所缺页调入内存 。 与一般中断的主
要区别在于：
? 缺页中断在指令执行期间产生和处理中断信号, 而一般中断
在一条指令执行完后检查和处理中断信号 。
? 缺页中断返回到该指令的开始重新执行该指令, 而一般中断
返回到该指令的下一条指令执行 。
? 一条指令在执行期间, 可能产生多次缺页中断 。
3,地址变换机构
请求分页系统中的地址变换机构, 是在分页系统的地址变换
机构的基础上, 再为实现虚拟存储器而增加了某些功能所形
成的, 如产生和处理缺页中断, 以及从内存中换出一页的功
能等等, 下图 给 出了请求分页系统的地址变换过程 。
缺页中断处理
是
否
否
是
是 否
产生缺页中 否
是 断请求调页 是
开始 （ 程序请求访问一页 )
越界中断
CPU检索快表
页表项是否在快表中？
访问页表
页是否在内存中？
修改快表
修改访问位和修改位
形成物理地址
地址变换结束
保留 CPU现场
从外存中找到缺
页
页号 > 页 表长
度？
内存满否？
选择一页换出
该页是否被修改？
将该页写回外存
将一页从外存换入内存
修改页表
CPU从外存读缺页
启动 I/O硬件
（ 2）页面分配
1.最少物理块数
在为进程分配物理块时, 首先应该考虑的问题是：能保证进
程能正常运行所需的最少物理块数 （ 称为最小物理块数 ） 。
若系统为某进程所分配的物理块数少于此值时, 进程将无法
运行, 这取决于指令的格式, 功能和寻址方式 。
2,页面的分配和置换策略
在请求分页系统中, 可采取两种分配策略 ——固定和可变分
配策略 。 在进行置换时, 也可采取两种策略 ——全局置换和
局部置换 。 于是可组合成以下三种策略 。
? 固定分配局部置换策略：它基于进程的类型 （ 交互型或批处
理型等 ）, 或根据程序员, 系统管理员的建议, 为每个进程
分配一固定页数的内存空间, 在整个运行期间都不再改变 。
如果进程在运行中发现缺页, 则只能从该进程在内存的固定
页面中选出一页换出, 然后再调入另一页, 保证分配给该进
程的内存空间不变 。
页面分配 -1
? 可变分配全局置换策略：系统为每个进程分配一定数目的物
理块，而 OS本身也保持一个空闲物理块队列。当某进程发现
缺页时，由系统从空闲物理块队列中，取出一物理块分配给
该进程，并将欲调入的缺页装入其中。当空闲物理块队列中
的物理块用完时,OS才能从内存中选择一页调出，该页可能
是系统中任一进程的页。
? 可变分配局部置换：根据进程的类型或程序员的要求，为每
个进程分配一定数目的内存空间；但当某进程发生缺页时，
只允许从该进程在内存的页面中选出一页换出，而不影响其
它进程的运行。
页面分配 -2
? 3．页面分配算法
在采用固定分配策略时, 可采用以下几种物理块分配方法：
? 平均分配算法：将系统中所有可供分配的物理块, 平均分配
给各个进程 。
? 按比例分配算法：这是根据进程的大小按比例分配物理块 。
? 考虑优先权的分配算法：该方法是把内存中可供分配的所有
物理块分成两部分：一部分按比例分配给各进程；另一部分
则根据各进程的优先权, 适当地增加其相应份额后, 分配给
各进程 。
(3)页面调入策略
为能使进程运行, 必须事先将一部分要执行的程序和数据调入
内存 。
1,调入页面的时机
为了将进程运行时所缺的页面调入内存, 可采取策略有：
? 预调页策略是一种主动的缺页调入策略, 即将那些预计在不
久的将来会被访问的程序或数据所在的页面, 预先调入内存 。
由于预测的准确率不高 （ 50%）, 所以这种策略主要用于进程
的首次调入 。 有的系统将预调页策略用于请求调页, 例如在
VAX/VMS操作系统中, 采用了一种称为群页式的调页策略, 当
系统将进程所请求的页面调入内存时, 也同时将其相邻的几
个页面调入内存 。
? 请求调页策略是指当进程在运行中发生缺页时, 就立即提出
请求, 由系统将缺页调入内存 。 目前的虚拟存储器中, 大多
采用此策略 。 但这种策略在调页时须花费较大的系统开销,
如需频繁启动磁盘 I/O。
页面调入策略 -1
2。从何处调入页面
在虚拟存储系统中，外存（硬盘）常常被分成两部分；
文件区（用于存放文件）和对换区（用于存放对换页
面）。通常，对换区的磁盘 I/O速度比文件区要高。
每当进程发出缺页请求时，系统应从何处将缺页调入
内存呢？在 UNIX系统中，对于从未运行过的页面，都
应从硬盘文件区调入；对于曾经运行过而又被换出的
页面，可以从对换区调入；对于共享页面，该页面可
能已由其它进程调入内存，此时就无须再从对换区调
入。
（三）页面置换算法
（ Page Replacement Algorithms）
在进程运行过程中，如果发生缺页，此时内存中又无空闲
块时，为了保证进程能正常运行，就必须从内存中调出一页
程序或数据送磁盘的对换区。但将哪个页面调出，则须根据
一定的页面置换算法来确定。置换算法的好坏将直接影响系
统的性能，不适当的算法可能会导致进程发生, 抖动,
（ Thrashing)。即刚被换出的页很快又被访问，需重新调入，
导致系统频繁地更换页面，以致一个进程在运行中把大部分
时间花费在完成页面置换的工作上，我们称该进程发生了
,抖动, 。
从理论上讲，应将那些以后不再被访问的页面换出，或把那
些在较长时间内不会再被访问的页面换出。下面介绍几种常
用的置换算法。
页面置换算法 -1
（ 1）最佳（ Optimal）置换算法
它是一种理想化的算法，性能最好，但在实际上难于实现。即
选择那些永不使用的，或者是在最长时间内不再被访问的页
面置换出去。但是要确定哪一个页面是未来最长时间内不再
被访问的，目前来说是很难估计的，所以该算法通常用来评
价其它算法。
? 例：假定系统为某进程分配了三个物理块，并考虑有以下的
页面号引用串,7,0,l,2,0,3,0,4,2,3,0,3,2，
l,2,0,l,7,0,1。如下图 所示,进程运行时先将 7,0，
1三个页面装入内存。当进程访问页面 2时，产生缺页中断，
此时 OS根据最佳置换算法，页面 7将在第 18次才被访问，是三
页中将最久不被访问的页面，所以被淘汰。接着访问页面 0时，
发现已在内存中，而不会产生缺页中断，以此类推。 从 图可
以看出，采用最佳置换算法，只发生了 6次页面置换,9次缺
页中断。
最佳（ Optimal）置换算法 -1
页面
引用
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
7 7 7 2 2 2 2 2 2 2 2 2 2 2 2 2 2 7 7 7
0 0 0 0 0 0 4 4 4 0 0 0 0 0 0 0 0 0 0
物理
块
1 1 1 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1
缺页 x x x x x x x x x
发生了 6 次面置换,9 次缺页 中断。
(2)先进先出（ FIFO）置换算法
该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久
的页面予以淘汰。该算法实现简单，只须把一个进程已调入内存的页
面，按先后次序链接成一个队列，并设置一个指针即可。它是一种最
直观，性能最差的算法，它有 B E L A D Y 异常现象：对页面访问序列 A B
C D A B E A B C D E,物理块从 3 块增加到 4 块，缺页次数增加。
表中物理块的页号按调入内存先后次序排序
页面
引用
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
7 0 1 2 2 3 0 4 2 3 0 0 0 1 2 2 2 7 0 1
7 0 1 1 2 3 0 4 2 3 3 3 0 1 1 1 2 7 0
物理
块
7 0 0 1 2 3 0 4 2 2 2 3 0 0 0 1 2 7
缺页 x x x x x x x x x x x x x x x
发生了 12 次页面置换,缺页次数 15 次。
FIFO Illustrating Belady’s Anamoly
（ 3）最近最久未使用置换算法
LRU（ Least Recently Used）
该算法是选择最近最久未使用的页面予以淘汰，系统在每个页
面设置一个访问字段，用以记录这个页面自上次被访问以来所
经 历 的 时 间 T,当 要 淘 汰 一 个 页 面 时,选 择 T 最 大 的 页 面 。但 在
实 现 时 需 要 硬 件 的 支 持 （ 寄 存 器 或 栈 ）。 利 用 L R U 算 法 对 上 例 进
行页面置换的结果如下：表中 物理块的页号按访问先后次序排
序
页面
引用
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0
物理
块
7 0 1 2 2 3 0 4 2 2 0 3 3 1 2 0 1 7
缺页 x x x x x x x x x x x x
发生了 9 次面置换,缺页次数 12 次
(4)Clock置换算法
（最近未用算法 NRU（ Not Recently Used）
二次机会 (Second-Chance)
? 这是一种 LRU的近似算法。该算法为每个页面设置一位访问
位，将内存中的所有页面都通过链接指针链成一个循环队
列。当某页被访问时，其访问位置, 1”。在选择一页淘汰
时，就检查其访问位，如果是, 0”，就选择该页换出；若
为, 1”，则重新置为, 0”，暂不换出该页，在循环队列中
检查下一个页面，直到访问位为, 0”的页面为止。由于该
算法只有一位访问位，只能用它表示该页是否已经使用过，
而置换时是将未使用过的页面换出去，所以把该算法称为
最近未用算法。
? 物理块中页号按 访问 先后次序排序规则,上面为最近调入内
存页的页号，下面为最久调入内存页的页号。
Clock置换算法 -1
块号 页号 访问位 指针 替换指针
0
1
2 4 0 4
3
4 2 1 → 0 6
5
6 5 → 6 0 → 1 7
7 1 1 2
指向 最近被替
换的 4 号页所
在块的块号 2
2 → 6
被调入 页的页
号为 6
简单 C l oc k 置换算法的数据结构—存储器分 块表
（ 5） 页面缓冲算法
（ Page Buffering Algorithm）
? 该算法在页面分配时，采用可变分配和局部置换的方式 。 首
先为每个作业分配一个工作集（进程在一段时间内运行，要
用到的部分页面的集合），每个工作集的块数相对固定的
（在一段时间内），块号是可变的。系统自己也保留一部分
存储块作为页面缓冲，并把页面缓冲组织成两个队列：空闲
队列和已修改的页面队列。
? 经过一段时间的运行,OS把一些暂时不访问的页面（在每
个工作集采用 FIFO算法进行选择）放入页面缓冲，如果页面
未被修改，就将它直接放入空闲队列中；否则，便放入已修
改的页面队列中。注意，这时页面在内存中并未做物理上的
移动，而只是将页表中的表项移到上述两个队列之一中。图
中是页面缓冲算法的某个状态，有三个作业（ A,B,C）的
工作集和页面缓冲的两个队列。
页面缓冲算法 -1
? 当进程要访问页面时, 先到工作集中去找, 如果找到就可以
直接访问 。 否则, 到页面缓冲的两个队列中去找, 如果找到
也可以直接访问, 并将该页在页表中的表项链接到工作集队
列的末尾, 而把工作集队列的队首的页表表项链入页面缓冲
的两个队列中 。
40 3 19 22 61 20
24 41 5 23
7 12 13 30 10
1 32 14 9 43 39 8 16
工
作
集
已修改的页面队列 空闲队列
页面修改位 =“1” 页面修改位 =“0”
页面缓冲
A
B
C
页面缓冲算法 -2
? 如果还是没找到, 则启动磁盘 I/O,将缺页读入空闲队列第
一个物理块中 （ 利用 FIFO）, 并将该页在页表中的表项链接
到工作集队列的末尾 。
? 利用这种方法可使已修改的页面和未修改的页面, 都仍留在
内存中 。 当该进程要再次访问这些页面时, 便只须花较小的
开销就可以使这些页面又返回到该进程的工作集中 。 当在页
面缓冲的已修改页面达到一定数量时, 例如 64个页面, 可以
将它们一起写回到磁盘, 从而显著地减少了磁盘 I/O的操作
次数 。
? 页面缓冲算法是一个较简单的近似于 LRU页面缓冲算法, 它
与 LRU和 Clock置换算法相比, 无需硬件的支持, 又大大减少
了页面置换的开销 。 在性能上又比 FIFO要好, 有效地改善了
请求式分页系统的性能 。 著名的 VAX／ VMS和 Windows NT便是
使用这种算法, 而在 MACH操作系统实现中, 只是它没有区
分已修改页面和末修改页面 。
(6)性能分析
1.缺页率对有效访问时间的影响
在请求分页系统中, 假设存储器的访问时间 ma为 100ns（ 一般
为 10ns～几百 ns）, 缺页率为 p,缺页中断时间为 25ms,则有
效访问时间就可以表示为：
有效访问时间 =（ 1一 p） × ma十 p× 缺页中断时间
=（ 1一 p） × 0.1十 p× 25000 = 0.1十 24999.9 p
由上式可以看出, 有效访问时间与缺页率成正比 。 如果缺页
率为 0.1%,则有效访问时间约为 25μ s,与直接访问存储器的
有效访问时间 （ 0.1μ s ） 相比的时间, 程序执行的性能将受
到严重的影响 。 如果希望在缺页时, 仅使有效访问时间延长
不超过 10%,则可计算出缺页率 p=0.0000004,由此得出, 要
求在 2500000次的访问中才发生一页缺页, 即请求分页方式应
保持非常低的缺页率；否则, 将使程序执行速度受到严重影
响 。 此外, 提高磁盘 I/O的速度, 对改善请求分页系统的性能
至关重要 。 为此, 应选用高速磁盘和高速磁盘接口 。
性能分析 -1
2,工作集
? 程序在运行中所产生的缺页情况，会影响程序的运行速度及
系统性能，而缺页率的高低又将是与每个进程所占用的物理
块数目有关。这里我们简单地分析一下应为每个进程分配多
少个物理块，才能把缺页率保持在一个合理的水平上。
缺页率与进程所分得的物理块数目有密切关系。下图 说明了
的缺页率与进程分得的物理块数目 N之间的关系曲线。从图中
可以看出，缺页率随着所分得的物理块数目的减少而递增，
并在所分到的物理块数目较少处，出现一个拐点。在拐点下
限以左时，随着分到的物理块数目的增加，缺页率明显地减
少；而过了拐点，在下限以右时，随着分到的物理块数目的
增加，却对缺页率的改善并不明显。所以，为进程分配的物
理块数，应取在该曲线的拐点左右。
性能分析 -2
? 工作集的理论是在 1968年由 Denning提出来的 。 他认为, 程
序在运行时对页面的访问是不均匀的, 即往往在某段时间内
的访问仅局限于较少的若干个页面, 如果能够预知程序在某
段时间间隔内要访问哪些页面, 并能将它们提前调入内存,
将会大大地降低缺页率, 从而减少置换工作, 提高 CPU的利
用率 。
缺页率
拐点
所分得的物理块数
下限
上限
性能分析 -3
? 所谓工作集是指，在某段时间间隔（ Δ ）里，进程实际要
访问的页面的集合。 Denning认为，虽然程序只需有少量的
几页在内存就可以运行，但为了使程序能够有效地运行，较
少地产生缺页、就必须使程序的工作集全部在内存中。把某
进程在时间 t的工作集记为 w（ t,Δ ），把变量 Δ 称为工作集
,窗口尺寸, （ Windows Size）。正确选择工作集窗口（ Δ ）
的大小，对存储器的有效利用和系统吞吐量的提高，都将产
生重要的影响。
? 在 Windows NT中，虚拟存储管理程序（ Virtual Memory
Manager)为每一个进程分配固定数量的页面，并且这个数目
可以进行动态的调整。那么这个数量如何确定？又如何进行
动态的调整呢？这个数目就是由每个进程的工作集来确定，
并且根据主存的负荷和进程的缺页情况动态地调整其工作集。
性能分析 -4
? 其具体的作法是：一个进程在创建时就指定了一个最小工
作集, 该工作集的大小是保证进程运行在主存中应有的最小
页面数 。 但在主存负荷不太大 （ 页面不太满 ） 时, 虚存管理
程序还允许进程拥有尽可能多的页面作为其最大工作集 。 当
主存负荷发生变化时, 如空闲页架 （ 块 ） 不多了, 虚存管理
程序就使用, 自动调整工作集, 的技术来增加主存中可用的
自由页架 。 方法是检查主存中的每个进程, 将它当前工作集
大小与其最小工作集进行比较 。 如果大于最小值, 则从它们
的工作集中移去一些页面作为主存自由页面, 可为其它进程
所使用 。 若主存自由页面仍然太小, 则不断进行检查, 直到
每个进程的工作集都达到最小值为止 。
当每个工作集都已达到最小值时, 虚存管理程序跟踪进程的
缺页数量, 根据内存中自由页面数量可以适当增加其工作集
的大小 。
（四）请求分段存储管理方式
请求分段系统在分段系统的基础上实现的虚拟存储器, 是以分
段为单位进行换入, 换出的 。 在程序运行之前只要先调入若
干个分段 （ 不必调入所有的分段 ）, 便可启动运行 。 当所访
问的段不在内存时可请求 OS将所缺的段调入内存 。 为实现请
求分段存储管理方式, 同样需要一定的硬件支持和相应的软
件, 有段表机制, 缺段中断机构以及地址变换机构 。
（ 1） 请求分段中的硬件支持
1,段表机制
在请求分段式管理中在段表中增加若干项, 以供程序在调进,
调出时参考 。 请求分段的段表项如下：
段 段 段的 存取 访问 修改 存在 增补 外存
名 长 基址 方式 字段 A 位 M 位 P 位 起址
请求分段中的硬件支持 -1
在段表项中，除了段名 (号 )、段长、段在内存的起始地址外，
还增加了以下几项：
? 存取方式：用于标识本分段的存取属性是只执行、只读，还
是允许读／写。
? 访问字段 A：用于记录该段被访问的频繁程度。
? 修改位 M：用于表示该段进入内存后，是否已被修改过。
? 存在位 P：说明本段是否已调入内存。
? 增补位：用于表示本段在运行过程中，是否进行过动态增长。
? 外存起址：指示本段在外存中的起始地址，即起始盘块号。
2.缺段中断机构
在请求分段系统中，采用的是请求调段策略。即当进程所要
访问的段未调入内存时，便由缺段中断机构产生一缺段中断
信号，由缺断中断处理程序将所需的段调入内存。缺段中断
的处理过程如下图：
请求分段中的硬件支持 -1
拼接后形成合适
大小的空闲区
淘汰一个或几个段
以形成合适大小的
空闲区
虚段不在内存中
阻塞请求的进程
内存中有合适的空闲区？
从外存读入段
修改段表和内存空闲链
唤醒请求进程
返回
空闲区大小总和能否满足？
N
N
请求分段中的硬件支持 -2
3。 地址变换机构
请求分段系统中的地址变换机构, 是在分段系统地址
变换机构的基础上形成的 。 由于被访问的段并非全
在内存, 所以在地址变换时, 若发现所要访问的段
不在内存时, 必须先将所缺的段调入内存, 并修改
了段表之后, 才能再利用段表进行地址变换 。 为此,
在地址变换机制中又增加了某些功能, 如缺段中断
的请求及其处理等 。
请求分段中的硬件支持 -3
4。段的动态链接
经过编释或汇编得到的一组目标程序需经链接程序，连接
装配成一个一维的线性连续地址空间，这一过程称为静态链
接，但是这种连接装配过程既复杂又费时，还经常发生许多
被连接好的摸块在作业运行过程中根本不用，而造成连接时
的机时和主存空间的浪费，所以最好能采用什么时候用到那
一段责连接该段的方法，这种方法称为动态连接方法。段的
动态链接是指“在一个程序运行开始时，只将主程序装配好
并调入主存，其它各段的装配是在主程序段运行过程中逐步
进行的，每当需要调用一个新段时，再将该段装配好，并与
主程序段连接。在分段存储管理环境中，由于逻辑地址空间
是二维的，每段有自己的段名，因而实现动态连接比较容易。
5。 请求段页 式地址变换机构如下图：
允 许 动 态
增
长吗？
启动要处理指令
计算有效地址
访问地址 v= (s,p,d)
S≤ 段表长吗？
段连接了吗？
段在主存吗？
P≤ 页表长吗？
访问类型合
法吗？
页在主存吗？
缺页中断处理
执行下一条指令
访问该地址
完成指令
形成主存地址
出错处理
越界中断处理
连接中断处理
缺段中断处理
出错处理
N
N
N
N
N
N
N
（ 2） 分段共享与保护
分段保护,
1.越界保护：段表长和段长
在段式系统存储管理方案中, 设置了段表寄存器,
存放段表始址 Cb和段表长 Cl,在进行地址变换时,
系统将逻辑地址中的段号 S与段表长度 Cl进行比
较, 若 S≥C l访问越界, 产生越界中断信号 。 未
越界, 根据段表的始址 Cb和段号 S,计算出该段
对应段表项的位置, 从中读出该段在内存中的起
始地址 b。 如增补位为 0,再检查段内地址 d是否
超过该段的段长 l,超过, 产生越界中断, 否则,
将该段的基址 b与段内地址 d相加, 得到要访问的
内存物理地址 。
ClCb
+
段号 S 段内地址 d
比较
比较
b + d
比较
段 表 快表
物理地址
段表始址寄存器 段表长度寄存器 逻辑地址
地址越界
d>=1
地址越界
地址越界
l b
S l b
.,.
d>=1
分段地址映射及存储保护机制
S>= Cl
MULTICS Address Translation Scheme
Segmentation Hardware
分段共享与保护 -1
2.存取保护：存取权 (R,W,E)
分段存储管理方式实现分段的共享和保护只须在每
个进程的段表中, 用相应的表项来指向共享段在内
存中的 起始地址 。 为了实现请求分段共享, 减少共
享段的置换, 应配置相应的共享段表, 用来对共享
段进行操作 。
在系统中, 用共享段表来记录了每一个共享段的段
号和段长, 内存始址, 存在位等信息, 并记录共享
此分段的每个进程的情况 。 共享段表如下图所示 。
分段共享与保护 -1
其中：
? 共享进程计数 器 COUNT：记录有多少个进程需要共享该分段。
? 存取控制字段：说明不同的进程对该分段不同的存取权限。
? 段号：对于同一个共享段，不同的进程可以使用不同的段号
去共享该段。
段名 段长 内存起址 状态 外存起址
共享进程计数器 COUNT
状态 进程名 进程号 段号 存取控制
分段共享与保护 -2
? 共享段的分配和 回收：
共享段的分配, count=count+1;
共享段的 回收,count=count-1;
if count==0 then 回收 ;
（五） Windows98虚拟存储技术
（ 1） Intel80386提供的存储管理方式
在 Inte180386芯片中, 包含了存储管理部件 MMU（ Memory
Management Unit）, 由它来提供实现虚拟存储器所需的硬件
支持, 即请求段表 （ 页表 ） 机制, 缺段 （ 页 ） 机构, 地址变
换机构 。 其地址变换过程分两步进行, 第一步由分段部件将
逻辑地址转换为线性地址, 并将该地址送分页部件；第二步
由分页部件将线性地址变换为物理地址 。 如果仅用分段存储
管理方式, 其分页部件将被旁路 （ 失效 ）, 此时分段部件送
出的线性地址便是物理地址, 直接送内存地址寄存器 。 为了
提高分段和分页的地址变换速度, 在分段和分页部件中, 都
配置了高速缓冲存储器, 作为快速段表和页表 。
80386既支持分段, 也支持分页, 可根据需要构成以下四种存
储管理方式：
1,不分段也不分页的存储管理方式 。
Windows98虚拟存储技术 -1
2,分页不分段存储管理方式（ UNIX／ 386系统）。
3．分段不分页存储管理方式。
4．分段分页存储管理方式。
（ 2）分段存储管理
1,段描述符表
80386为每个用户任务所配置的段表, 称为局部描述符表 LDT
（ Local Descriptor Table） 。 其中, 每个表项为一个段的
描述符, 共 8个字节长 。 此外, 还配置了一张对系统任务都有
用的全局描述符表 GDT（ Global Descriptor Table） 。 在任
一时刻 GDT和某一个 LDT是可被访问的, 在分段部件中, 还配
置了全局描述符表寄存器 GDTR和局部描述符表寄存器 LDTR。
它们都是 6个字节长, 分别指向当前的 GDT和 LDT。 两个描述符
的格式基本上相同 。 如图 所示 。
各字段说明如下：
Windows98虚拟存储技术 -2
?段的基址,32位，定义了段在 4GB线性地址空间中的始址。
?段界限值：规定了段的最大长度。其单位可以是字节或页
（ 4KB），这取决于粒度单位 G。当 G为 1时，表示段长是以页
为单位；当 G为 0时，表示段长以字节为单位。由于段长为 20
位，故当 G为 1时，最大段长为 4 GB。
段的基址 15…… 0 段界限值 15…… 0
段基址 G D 0 0 界限值 P DPL S TYPE A 段基址
31… 24 19… 16 23… 16
31 23 19 1615 12 8 7 0
Segmentation with Paging,Pentium(2)
? Pentium code segment descriptor
? Data segments differ slightly
Windows98虚拟存储技术 -3
2,分段的地址变换机构
?段寄存器
在 80386处理器中, 共有 6个段寄存器 。 它们是：代码段寄存器
CS,栈段寄存器 SS,四个数据段寄存器 DS,ES,FS和 GS。 段
寄存器和 8086一样仍为 16位 。 在实方式时, 段中存放段的基
址的高 16位 。 因此, 将它左移 4位后与偏移量相加, 便形成 20
位的物理地址 。 但在保护方式下, 16位的段寄存器已不足以
用来存放 32位的段的基址, 所以在段寄存器中所存放的是指
向描述符表中某个描述符的指针 。 此时, 段寄存器中的 TI（ l
位 ） 用来指示描述符表的类型, 即或者指示选择全局描述符
表, 或者指示选择局部描述符表 。 RPL（ 2位 )为请求者的特权
级 。 描述符表项索引 Index（ 13位 ） 可用来在 8K个描述符中任
选其一 。
?虚地址结构和地址变换
Segmentation with Paging,Pentium (1)
A Pentium selector
Windows98虚拟存储技术 -4
在 80386中的虚地址结构如下：
其中,TI为描述符表类型； RPL是请求者特权级； S为段号 Index
项，用来选择描述符。其前 16位实际上是放在段寄存器中的。
分段部件中，是将逻辑地址变换为线性地址，在进行地址变
换时，首先是从相应的段寄存器中取得段号 S，即获得指向段
描述符表的指针 Index，如果此时 TI=0，则从 GDT中选择一描
述符；否则（ TI=1），从 LDT中选择一描述符。从所获得的
描述符中可得到段的基址，然后将段的基址与偏移量相加，
得到线性地址。对于只分段、不分页的存储管理方式，此线
性地址就是内存的物理地址；若是既分段、又分页的存储管
理方式，则还须将此线性地址送分页部件，再形成物理地址。
段号 S TI RPL 偏移量
13位 1位 2位 32位
＋
＋
8B
基地址
限长
其它字段
8B
8B
。
。
页目录号 P1 外部页内地址 P2 页内位移 D
外部页表寄存器
（ 索引 ）
段号 S TI RPT 偏移量
CS代码段寄存器 DS数据段寄存器
GDTR全局描述符寄存器 LDTR局部描述寄存器
＋
＋
＋
块号 页内位移 D
A page table entry for a mapped page on
the Pentium
Windows98虚拟存储技术 -5
(3)Windows98系统地址空间的划分
Intel386以后的 CPU有了 32位或 64位的内存寻址范围, 所以系
统的地址空间可达 4GB或更大 。 在 Windows98系统提供了
4GB虚拟的 32位的地址空间, 给每个进程分配 2GB的专用地
址空间, 而把剩余的 2GB地址空间分成系统空间 （ 1GB） 和
用于所有的共享内存区域的单个共享的用户空间 （ 1GB） 。
这个 1GB的共享区域对于用户态是可写的, 所以任何 Win32应
用程序都可以写共享内存区和映象文件 （ 映象文件是指把驻
留在盘上的文件看成是虚拟主存的一部分 ） 。 MS-DOS应用
程序和 Win16应用程序也都在这个共享的空间中 。 Windows
NT将共享内存区域放在专用进程地址空间内 。
每一个基于 MS-DOS的程序和 32位 Windows程序都有各自的
4GB虚拟地址空间 。 16位 Windows应用程序共享单个的 4GB
地址空间 。 4GB的地址空间分为两部分,2GB用于用户应用
程序, 2GB用于操作系统组件 。 程序以如下方式使用虚拟地
址空间里的地址：
Windows98虚拟存储技术 -6
? 0~1MB：基于 MS-DOS的程序就像真的在 MS-DOS环境中运
行那样使用这些地址，所有其它程序将忽略这些地址。这些
地址仍可为程序加载的实模式设备驱动程序所使用。
? 1~4MB：由于 Windows NT在这些地址空间上加载，为了维
护与 NT的兼容性,Windows98与 32位程序也不使用这一段
地址空间。但由于向下兼容的缘故,16位程序使用这些地址。
? 4MB~2GB,WIN32应用程序使用。
? 2GB~3GB：由 DLL（动态链接库）和其它共享组件使用。
? 3GB~4CB：低层的内存管理、文件系统、驱动程序（ VxD）
使用。这些地址一般是 Ring0组件使用。
Windows98虚拟存储技术 -7
（ 4） VMM——虚拟存储管理程序
Windows98用虚拟存储管理程序 （ Virtual Memory Manager）
来实现请求调页的虚拟存储技术, 把系统 4GB的虚拟地址空间
映射到机器的物理内存上 （ 32MB或 64MB） 。
Windows98的虚拟存储管理程序通过两个内存管理进程向应用
程序提供虚拟内存：一个是页面调度 （ paging） ——负责在
物理内存和硬盘的交换文件之间交换数据；另一个是地址转
换 ——负责物理地址和虚拟地址空间的地址或映象文件 I/O之
间的转换 。
VMM将物理内存分成一个个大小为 4KB页面 （ 或称为块 ） 。 将虚
拟地址空间 （ 应用程序所在的空间 ） 也划分成 4KB大小的页 。
当程序要运行时, 一部分页面被装入物理内存, 另一部分则
放在硬盘的虚似内存交换文件 （ 或称为页交换文件 ） 中 。 交
换文件是指位于硬盘上用来模拟物理内存的文件, 它由 VMM专
门用来保存内存页面, 作为虚拟内存空间使用 。
Windows98虚拟存储技术 -8
当程序访问那些不在内存中的页面时,CPU会产生页面出错
（ Page Fault）,VMM便会从交换文件中将相应的页面换入
内存。
Windows98交换文件（ Win386.swp）是动态的，它可根据系统
内存的负荷和可利用的磁盘空间大小而增大或减小。动态交
换文件可以对硬盘进行有效的利用，因为它可占用硬盘的一
个已成碎片的区域，而不引起重大的性能下降。注意：保证
交换文件高质量运行的一条最好的途径是：确保包含交换文
件的磁盘有足够的可利用的空间，以便交换文件的大小可以
根据需要增大或减小。一般情况下，可以让 Windows98自动
管理虚拟内存。如果用户想要把交换文件设置在特定的硬盘
上，或者由于磁盘空间有限想把交换文件的大小限制在一定
范围，就要修改设置。但是在设置时，特别要注意：交换文
件太小会严重影响系统的性能。
Windows98虚拟存储技术 -9
交换文件（ Win386.Swp）存放在 C,\Window目录下。用户不
应把交换文件安置在压缩硬盘上，因为这样做将影响其性能。
交换文件的运行速度应当尽可能地快，应当定期对硬盘空间
进行整理，以使交换文件能使用连续的存储区，这也有助于
提高交换文件访问的速度。在 Windows NT中，交换文件可跨
越多个驱动器，其名为 Pagefile.sys。
（ 5）页面置换算法
Windows95/98虚拟内存管理器置换算法如下：
1。 调页算法：当某个线程试图访问一无效页面而产生页面出
错 （ Page Fault） 时, VMM采用群集技术将其邻近的页面与页
面目录一起装入内存的空闲块中 。 所谓群集技术是指当需要
调一页时, 将包括该页在内的一个页面集合取入内存的空闲
块中, 这样可以减小页面出错和磁盘操作的次数 。
Windows98虚拟存储技术 -10
2。 淘汰算法：如果内存中没有空闲块, VMM会使用淘汰算法将
页面从内存移到交换文件中 。 每个进程在内存中都有一组有
效的页面 ——工作集, 以保证进程的有效运行 。 为简化起见,
VMM使用先进先出的算法 （ FIFO） 。 即当需要进行页面淘汰时,
VMM将工作页面集中存在时间最长的页面从内存中移到交换文
件中, 为新页面腾出空间 。 由于淘汰页是当前进程的工作页
面集, 所以可以保证该进程的页面不会被另外的进程所替代 。
（ 6） 页表结构
Windows95/98/NT支持的虚拟地址空间达 4GB,都采用二级页表
机构来管理虚拟存储空间 。 见 第五 课 。
Windows98虚拟存储技术 -11
（ 7） 映象文件 I/O
当应用程序将要装入的文件大小比 RAM和交换文件合起来还要
大时, VMM的映象文件 I/O服务功能可以将虚拟内存地址映射
到一个大文件中, 并通知应用程序此文件可用, 然后仅将应
用程序实际需要访问的那部分装入内存 。 由于整个大文件中
只有一部分装入内存 （ RAM或交换文件 ）, 极大地减少了文件
装入时间, 提高了系统资源的使用 。 这对于那些经常需要访
问巨型文件的数据库应用程序来说是一个非常有用的服务 。
（ 8） 页面锁定
对有特殊要求的应用程序和系统核心的页面, VMM可授予进程
特殊权限, 以将选定的虚拟内存页面锁定在工作页面集中,
这样关键页面在使用过程中便不会被换出内存 。
Windows 2000/XP内存布局
应用程序代码
全程变量
每个线程堆栈
DLL代码 3GB用户空间
1GB系统空间
7FFFFFFF
80000000 内核和执行体
HAL
引导驱动程序
C0000000 进程页表 BFFFFFFF
超空间 C0000000
C0800000 系统高速缓存
分页缓冲池
未分页缓冲池
FFFFFFFF FFFFFFFF
系统代码 (Ntoskrnl,HAL) 和一些系统中
初始的未分页缓冲池
系统映射视图（例如,Win32k.sys)或者
会话空间
超空间和进程工作集列表
进程的页表和页目录
附加的系统 PTE（高速缓存可以扩展到
这）
没有使用,不可访问
HAL使用
故障转储信息
未分页缓冲池扩充
系统 PTE
分页缓冲池
系统高速缓存
系统工作集列表
80000000
C0800000
C0400000
C0000000
A4000000
A0000000
FFBE0000
EB000000(min)
E1000000
C1000000
C0C00000
FFC00000
进程的 系统页表与进程私有页表
.
.
.
.
.
.
.
.
.
进程 1
的页表
进程 2
的页表
PTE 0
进程 1的
页目录
进程 2的
页目录
PTE 0
PDE 0 PDE 0
System PTE 0
PDE 511
PDE 512
PDE n PDE n
PDE 512
PDE 511
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
System PTE n
.
.
.
系统页表
进 程 仍
然 没 有
访 问 系
统页表
各进程
私有
物理地址扩展 (PAE,Physical Address Extension)
每个 PDE和 PTE表项都是 8个字节，物理页面号为
24Bit，可访问的物理地址空间可达 64GB。
例题
某虚拟存贮器的用户编程空间共 32个页面, 每页 1KB,主存为
16KB。 假定某时刻用户页表中已调入主存的页面的虚拟页号
和物理页表对照表为表一, 则下表中与虚拟地址相对应的物
理地址为表二 （ 如果主存找不到, 即为该页失效 ） 。 虚拟存
贮存的功能是由 ﹎﹎ C﹎﹎ 完成的 。 在虚拟存贮系统中, 采用
﹎﹎ D﹎﹎ 提高 ﹎﹎ E﹎﹎ 的速度 。
表一 虚页号 物理页号
0 5
1 10
2 4
8 7
表二 虚地址 物理地址
0A5C（ H） ﹎﹎ A﹎﹎
1A5C（ H） ﹎﹎ B﹎﹎
例题 -1
供选择的答案：
A,B：① 页失效 ② 1E5C（ H）
③ 2A5C（ H） ④ 165C（ H）
⑤ 125C（ H） ⑥ 1A5C（ H）
C,① 硬件 ② 软件 ③ 软、硬件结合
D,① 高速辅助存贮器 ② 高速光盘存贮器
③ 快速通道 ④ 高速缓冲存贮器
E,① 连接编辑 ②虚地址分配
③ 动态地址翻译 ④动态连接
例题 -2
解,每页大小 1KB,用 16进制表示为 400H,由虚地址通过直接
映象的地址转换成物理地址步骤如下：
? 将虚地址分离成页号 p和页内地址 d：
页号 p＝ （ 虚地址／页大小 ） 取整＝ （ 0A5CH/400H） 取整＝ 2
页内地址 d＝虚地址－页号 p× 每页大小＝ 0A5C(H)－ 2× 400(H)
＝ 25C(H)
? 根据页号查页表, 由页号 p＝ 2查页表得物理页号为 4
? 将物理页号和页内地址构成物理地址＝物理页号 × 页大小＋
页内地址＝ 4× 400(H)＋ 25C(H)＝ 125C(H)
同理虚拟地址 1A5CH分离成页号 P＝ 6和页内位移 15CH.
查页表知该页不在内存, 页失效产生缺页中断调入内存 。
习题
1,虚拟存贮管理系统的基础是程序的局部性理论 。 此理论的基
本含义是 ﹎﹎ A﹎﹎ 。 局部性有两种表现形式：时间局限性和
﹎﹎ B﹎﹎ 。 它们的意义分别为 ﹎﹎ C﹎﹎ 和 ﹎﹎ D﹎﹎ 。 根据
局部性理论, Denning提出了 ﹎﹎ E﹎﹎ 。
A,B,① 程序执行时对主存和访问是不均匀的 ② 代码的顺
序执行 ③ 变量的连续访问 ④ 指令的局部性
⑤ 数据的局部性 ⑥ 空间局部性
C,D,① 最近被访问的单元, 很可能在不久的将来还要被访问
② 最近被访问的单元, 很可能在它附近的单元也即将被访问
③ 结构化程序设计, 很少出现转移语句
④ 程序中循环语句的执行时间一般很长
⑤ 程序中使用的数据局部于各子程序
E,① Cache结构的思想 ② 工作集理论
③ 最近最少使用 （ LRU） 页面置换算法 ④ 先进先出页
面置换算法
习题 -1
2.什么叫虚拟存贮器?试述虚拟存贮器的实现原理和它的物质基
础 。
3,在请求分页内存管理的页表表项中, 其中状态位供 ﹎﹎ A﹎
﹎ 时参考；修改位供 ﹎﹎ B﹎﹎ 时参考；访问位供 ﹎﹎ C﹎﹎
时参考；外存始址供 ﹎﹎ D﹎﹎ 时参考 。
A,B,C,D,（ l） 分配页面； （ 2） 置换算法； （ 3） 程序访
问； （ 4） 换出页面； （ 5） 调入页面 。
4.在请求调页系统中, 凡未装入过内存的页都应从 ﹎﹎ A﹎﹎ 调
入；已运行过的页主要是从 ﹎﹎ B﹎﹎ 调入, 有时也可以从 ﹎
﹎ C﹎﹎ 调入 。
A,B,C,（ 1） 系统区； （ 2） 文件区； （ 3） 对换区； （ 4）
页面缓冲池 。
5.详述在设有快表的请求分页存储管理系统中, 一个虚地址转
换成物理内存地址的过程 。
习题 -2
6．在请求调页系统中有着多种置换算法：（ 1）选择最先进入
内存的页面予以淘汰的算法称为 ﹎﹎ A﹎﹎ ；（ 2）选择在以
后不再使用的页面予以淘汰的算法称为 ﹎﹎ B﹎﹎ ；（ 3）选
择自上次访问以来所经历时间最长的页面予以淘汰的算法称
为 ﹎﹎ C﹎﹎ ；（ 4）选择自某时刻开始以来，访问次数最少
的页面予以淘汰的算法称为 ﹎﹎ D﹎﹎ 。
A,B,C,D：（ 1） FIFO算法；（ 2） OPT算法；（ 3）
LRU算法；（ 4） NRU算法；（ 5） LFU算法。
7,在一个请求分页系统中，采用 FIFO页面置换算法时，假如
一个作业的页面访问顺序为 4,3,2,1,4,3,5,4,3,2，
l,5，当分配给该作业的物理块数 M分别为 3和 4时，试计算访
问过程中所发生的缺页次数分别为 ﹎﹎ A﹎﹎ 和 ﹎﹎ B﹎﹎,
缺页率分别为 A/C和 B/C，其中 ﹎﹎ C﹎﹎ 为访问次数。比较所
得的结果为 ﹎﹎ D﹎﹎ 。
A,B,C,D,见 6题
习题 -3
8,在一个请求分页系统中, 采用 LRU页面置换算法时, 假如一
个作业的页面访问顺序为 4,3,2,1,4,3,5,4,3,2，
l,5,当分配给该作业的物理块数 M分别为 3和 4时, 试计算访
问过程中所发生的缺页次数 ﹎﹎ A﹎﹎ 和 ﹎﹎ B﹎﹎, 缺页率
分别为 A/C和 B/C,其中 ﹎﹎ C﹎﹎ 为访问次数 。 比较所得的结
果为 ﹎﹎ D﹎﹎ 。
A,B,C,（ 1） 5； （ 2） 6； （ 3） 7； （ 4） 8； (5)9； (6)10；
(7)11； (8)12。
D,(1) 正常现象, 即存储块增加, 缺页次数减少；
(2) 存在奇异现象, 即存储块增加, 缺页次数反而增加；
(3) 存储块增加, 缺页次数不变 。
9.试述 Windows NT页面置换算法 -页面缓冲算法的原理和特点 。
10.试述 clock页面置换算法的原理和特点 。
习题 -4
11,静态链接是程序在 ﹎﹎ A﹎﹎ 时进行的，而动态链接是程序
在 ﹎﹎ B﹎﹎ 时进行的。
A,B：（ 1）编译；（ 2）装入；（ 3）调用；（ 4）紧凑。
12.巳知一个有快表的请求分页系统,内存读写周期为 Tr(1us)
内外存之间传送一个页面的时间 Tt(5ms),快表的命中率为 p
(80%),页面失效率为 f (10%)。 计算快表命中时存取时间为
﹎﹎ A﹎﹎, 快表不命中, 内存中页表查到时存取时间为 ﹎
﹎ B﹎﹎, 页面失效时存取时间为 ﹎﹎ C﹎﹎ 。 求系统和内存
有效存取周期 EAT(平均存取时间 )。
A,B,C,（ 1） 1μ s； （ 2） 2μ s； （ 3） 3μ s； （ 4） 500μ s；
(5) 501μ s； (6)5ms。
? 快表命中时存取时间为 Tr,快表的命中率为 p (80%)
? 快表不命中, 内存中页表查到时存取时间为 Tr+ Tr
? 页面失效时存取时间为 Tt,页面失效率为 f (10%)
? 求系统和内存有效存取周期 EAT(平均存取时间 )为
EAT = Tr*p + Tt*f + 2Tr*(1-p-f)
= 1*80% + 5000*10% + 2*10%
= 501 μ s
