虚存的引入
虚拟存储器
•（一）程序一次性装入内存带来的问题
1.单一连续分配、多道分区分配、分页和
分段存储管理的共同特点是：
都需要将程序一次性全部装入内存。
• 2.程序一次性装入带来一些问题
(1)内存总是有限的，当作业很大，内
存不足时？
OS
内存
用
户
作
业
带来的问题是：内存
空间连一个作业也无
法全部装入！
• (2)当使用固定分区管理，分页分段管
理需要装入多个作业时，每个作业只能
占用内存的一部份，但分给作业的内存
不足时？
OS
40K
内存
80K
120K
作
业
一
130K
作
业
二
180K
作
业
三
250K
带来的问题是：没有哪一个分区
能完全装入一个用户作业！
（二）程序局部性原理
1.时间局部性：一条指令被执行后，那么
它可能很快会再次执行。如循环、子程序、
堆栈、计数或累计变量等。
2.空间局部性：若某一存储单元被访问，
那么与该存储单元相邻的单元可能也会很
快被访问。如程序代码的顺序执行，对线
性数据结构的访问或处理、常用变量等。
问题：能否将部分程序装入内存后就开
始运行作业？为什么？
（三）程序局部性原理的应用
•一个程序特别是一个大型程序的一部份装
入内存是可以运行的。理由是：
•.程序中的某些部份在程序整个运行过程中可程序中的某些部份在程序整个运行过程中可
能根本不用。如：出错处理程序。能根本不用。如：出错处理程序。
•.许多表格占用固定数量的内存空间，而实际许多表格占用固定数量的内存空间，而实际
上只用到其中的一部份。上只用到其中的一部份。
•.许多程序段是顺序执行的，还有一些程序段许多程序段是顺序执行的，还有一些程序段
是互斥执行的。如菜单选择功能。是互斥执行的。如菜单选择功能。
•.在程序的一次执行过程中，有些程序执行之在程序的一次执行过程中，有些程序执行之
后，从某个时刻起不再用到。后，从某个时刻起不再用到。
（四）虚拟存储器的定义与特性
• 1.虚拟存储器是指仅把作业的一部份
装入内存便可以运行作业的存储器系统。
•也即，指具有请求调入功能和置换功
能，能从逻辑上对内存容量进行扩充的
一种存储器系统。
2.虚拟存储器的新特性
虚拟扩充。虚拟扩充。不是物理上扩大内存空间，而是逻不是物理上扩大内存空间，而是逻
辑上扩充了内存。也即是把大的逻辑地址空间映辑上扩充了内存。也即是把大的逻辑地址空间映
射到较小的物理内存上。射到较小的物理内存上。
部分装入部分装入。每个作业不是全部一次装入内存。。每个作业不是全部一次装入内存。
只将当前要运行的装入内存就开始运行。只将当前要运行的装入内存就开始运行。
离散分配。离散分配。装入内存的部份作业不必占用连续装入内存的部份作业不必占用连续
的内存空间，而是的内存空间，而是““见缝插针见缝插针””。。
多次对换。多次对换。一个作业运行时，它所需要的程序一个作业运行时，它所需要的程序
和数据分成多次调入内存。而在内存中那些暂时和数据分成多次调入内存。而在内存中那些暂时
不用的程序和数据可换出到外存对换区，以腾出不用的程序和数据可换出到外存对换区，以腾出
尽量多的内存空间供运行进程使用。尽量多的内存空间供运行进程使用。
交换区（SWAP）：进程刚建立时，页表
记录页面所在辅存位置，即程序文件所
在的外存位置。但程序文件中一般包含
有程序的二进制目标码及数据初始值和
初值为0的工作区。后两者在回写时不
能写入程序文件所在辅存区，因此引入
了交换区—临时存储区。（就绪挂起、
阻塞挂起的进程）
23
22
26
25
27
23
26
22
25
27
21
24
23
24
25
26
27
24
21
外存交换区
外存
20
21
22
换出21，换入25
换出24，换入27
内存
页表
例：内存原存放外存的21块和24
块（存放数据和初始值），现需
调入25和27块，因内存不足，需
对换。
3.虚拟存储器的容量不是无限大的。
它受两方面的限制。
一个是指令中表示的地址长度。假设
地址长度为32字节，按字节寻址，则逻辑
空间（虚存空间）大小为232个字节。（４
Ｇ个字节）
另一个是外存容量。用户的虚拟空间
不能超过硬盘中作业的存放空间。
（四）虚拟存储器的定义与特性
（五）实现虚拟存储的基本方法
可采用页式虚存管理、段式虚存管
理和段页式虚存管理。如：
页式虚存管理。在页式管理的基础上，
仅将进程的一部分页放于主存。页表项
中注明该页是否在主存。程序执行时，
如果访问的页不在主存，根据页表项的
指示，将其从外存调入主存，如果此时
无可用的内存空间，则先淘汰若干页帧。
（其他方法基本相同）
一、基本原理
页式虚拟存储管理方式是在分页
系统的基础上，增加了请求调页功能、
页面置换功能所形成的虚拟存储器系
统。
页式虚存管理
状态位：表示该页是否已经调入内存。
访问位：表示该页在内存间是否被访问过
修改位：表示该页在内存是否被修改过。
页号 内存块号 状态位状态位 访问位访问位 修改位修改位 外存地址外存地址
二、页表项结构
对页表增加了一些项目，具体如下：
三、地址变换机构
与页式管理基本相同，只是缺页时
产生缺页中断，先将该页调入内存，再
访问。见下图示。
指
令
执
行
步
骤
与
缺
页
中
断
处
理
过
程
★ 页面置换算法
一、目的与要求：
1、掌握页面替换策略中的基本概念
2、掌握驻留集固定的三种页面替换
策略。
3、掌握影响缺页中断率的主要因素
4、了解动态驻留集的页面替换策略。
二、重点与难点
1、固定驻留集算法
2、SWS等实用动态驻留集算法。
三、课时：2(90分钟)
四、教法：讲授法
五、教具
六、教学过程
1、介绍有关概念及替换策略分类
2、详细介绍驻留集固定的页面替
换策略
3、简略介绍可变驻留集替换策略
本节主要讲述的内容
一、页面替换策略中的基本概念
二、页面替换策略的分类
三、驻留集大小固定的替换策略
四、页面替换算法解题举例
五、影响缺页中断率的主要因素
六、页面替换策略应用实例
七、驻留集可变的替换策略
八、替换策略选择
一、页面替换(策略)策略中的基本概念
页面置换算法页面置换算法：：地址映射过程中，若在页面中
发现所要访问的页面不再内存中，则产生缺页
中断。当发生缺页中断时操作系统必须在内存
选择一个页面将其移出内存，以便为即将调入
的页面让出空间。而用来选择淘汰哪一页的规
则叫做页面置换算法(策略)。
一、页面替换(策略)策略中的基本概念
驻留集驻留集((工作集工作集))：：进程的合法页集合；也即系
统分给一个进程的内存可用块数。
访问串（页面走向）访问串（页面走向）：进程的存储访问序列或
进程访问虚空间的地址踪迹。页式虚存管理以
页为基本单位，只需页号即可。页面走向可合
理简化。
页面走向可合理简化原则：
（1）对于给定的页面大小，仅考虑其
页号，不关心完整的地址。
（2）如果当前对页面P进行了访问，那
么，马上又对该页访问就不会缺页。这样
连续出现的页号就简化为一个页号。
举例：某进程依次访问如下地址：
0100，0432，0101，0612，0102，0103，
0104，0101，0611，0102，0103，0104，
0101，0610，0102，0103，0104，0101，
0609，0102，0105。若页面大小为100，
上述访问串可简化为：
1，4，1，6，1，6，1，6，1，6，1
二、页面替换策略分成两类：
• 驻留集大小固定的替换策略；
• 驻留集大小可变的替换策略。
三、驻留集大小固定的替换策略
• (一)先进先出置换算法(FIFO)
• (二)最佳置换算法(OPT)
• (三)最近最少使用算法(LRU)
• (四)时钟置换算法(CLOCK)
(一) FIFO替换算法
置换策略：优先淘汰最早进入内存的
页面，亦即在内存中驻留时间最久的
页面
算法举例：驻留集大小为算法举例：驻留集大小为33，访问串为：，访问串为：
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2……
设开始三页内存为空，每调入一页均缺页。试设开始三页内存为空，每调入一页均缺页。试
列表求出列表求出FIFOFIFO算法的面页淘汰过程，淘汰的页算法的面页淘汰过程，淘汰的页
序和缺页次数？序和缺页次数？
FIFOFIFO算法页面替换过程如下表表示：算法页面替换过程如下表表示：
7 0 1 2 0 3 0 4 2 3 0 3 2
是
0 1 2 0 3 0 4 2 3 0 3 2
是 是
7 7
1 2 0 3 0 4 2 3 0 3 2
是 是
7 7 7
00
是
2 0 3 0 4 2 3 0 3 2
是 是
7 7 7
00
是
1
是
0
1
7
0 3 0 4 2 3 0 3 2
是 是
7 7 7
00
是
1
是
0
2
0
2
否 是
1
1
0 0 4 2 3 0 3 2
是 是
7 7 7
00
是
1
是
0
2
0
2
否 是
1
11
2
33
是
0 4 2 3 0 3 2
是 是
7 7 7
00
是
1
是
0
2
0
2
否 是
1
11 2
3
3
是
2
3
00
是
0 2 3 0 3 2
是 是
7 7 7
00
是
1
是
0
2
0
2
否 是
1
11 2
3
3
是
2 3
0
0
是
3
0
44
是
0 3 0 3 2
是 是
7 7 7
00
是
1
是
0
2
0
2
否 是
1
11 2
3
3
是
2 3
0
0
是
3
0
44
是
00
44
22
是
0 0 3 2
是 是
7 7 7
00
是
1
是
0
2
0
2
否 是
1
11 2
3
3
是
2 3
0
0
是
3
0
44
是
00
4
4
2
2
是
4
2
33
是
0 3 2
是 是
7 7 7
00
是
1
是
0
2
0
2
否 是
1
11 2
3
3
是
2 3
0
0
是
3
0
44
是
00
4
4
2
2
是
4
2
33
是 否 否
结果：缺页次数共结果：缺页次数共1010次。次。
（1）FIFO方法的特点：
• 实现方便。不需要额外硬件。
• 效果不好，有Belady奇异。
（2）FIFO存在Belady奇异：指替换策
略不满足随着驻留集的增大，页故障
数（缺页中断次数）一定减少的规律。
这一规律由Belady于1969年发现，
故称为Belady异常
2.对FIFO替换算法的进一步认识
（3）FIFO算法的Belady奇异现象举例
•对于如下的页面访问序列：1，2，3，4，1
，2，5，1，2，3，4，5当内存块数量分别
为3和4时，试问：使用FIFO置换算法产生的
缺页中断是多少？（所有内存开始时都是空
的，凡第一次用到的页面都产生一次缺页中
断）
–内存块为3时，缺页中断次数为9次。
–内存块为4时，缺页中断次数为10次。
–内存块为内存块为33时，缺页中断次数为时，缺页中断次数为99次。次。
–内存块为4时，缺页中断次数为10次。
(二) OPT替换算法
置换策略：当要调入一页而必须淘汰
旧页时，应该淘汰以后不再访问的页，
或距现在最长时间后要访问的页面。
1966年，Belady提出最佳(优)页面替换算
法(OPTimal replacement，OPT)。是操作系
统存储管理中的一种全局页面替换策略 。
算法举例：驻留集大小为算法举例：驻留集大小为33，访问串为：，访问串为：
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2……
设开始三页内存为空，每调入一页均缺页。试列表求出设开始三页内存为空，每调入一页均缺页。试列表求出
FIFOFIFO算法的面页淘汰过程，淘汰的页序和缺页次数？算法的面页淘汰过程，淘汰的页序和缺页次数？
7 0 1 2 0 3 0 4 2 3 0 3 2
是
7
0 1 2 0 3 0 4 2 3 0 3 2
是 是
7
OPT算法置换过程
7
1 2 0 3 0 4 2 3 0 3 2
是 是
7
0
是
7
0
OPT算法置换过程
7
1
2 0 3 0 4 2 3 0 3 2
是 是
7
0
是
7
0
7
0
1
是
OPT算法置换过程
7
1
0 3 0 4 2 3 0 3 2
是 是
7
0
是
7
0
7
0
1
是
7
0
11
0
22
否 是
OPT算法置换过程
7
1
0
3
0 4 2 3 0 3 2
是 是
7
0
是
7
0
7
0
1
是
7
0
11
0
22
否 是
22
00
3
否 是
OPT算法置换过程
7
1
0
3
0
4
2 3 0 3 2
是 是
7
0
是
7
0
7
0
1
是
7
0
11
0
22
否 是
22
00
3
否 是
22
33
否 否 是
4
OPT算法置换过程
7
1
0
3
0
4
2 3 3 2
是 是
7
0
是
7
0
7
0
1
是
7
0
11
0
22
否 是
22
00
3
否 是
22
33
否 否 是
4
否 否
OPT算法置换过程
结果：缺页次数共结果：缺页次数共77次次
2.对OPT替换算法的进一步认识
(1)是最优的页面替换策略
• OPT策略对任意一个访问串的控制均
有最小的时空积（进程所占空间与时
间的乘积）。
(2)是不可实现的策略
•由于需要预先得知整个访问串的序，
故不能用于实践,仅作为一种标准，用
以测量其他可行策略的性能。
(三) LRU替换算法
置换策略：淘汰上次使用距当前最远的
页或最近很少使用的页。
LRU LRU是是Least Recently UsedLeast Recently Used的缩写，的缩写，
即最近最少使用。即最近最少使用。
算法举例：驻留集大小为算法举例：驻留集大小为33，访问串为：，访问串为：
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2……
设开始三页内存为空，每调入一页均缺页。试列设开始三页内存为空，每调入一页均缺页。试列
表求出表求出FIFOFIFO算法的面页淘汰过程，淘汰的页序和算法的面页淘汰过程，淘汰的页序和
缺页次数？缺页次数？
7 0 1 2 0 3 0 4 2 3 0 3 2
是
LRU算法置换过程
7
0 1 2 0 3 0 4 2 3 0 3 2
是 是
7
LRU算法置换过程
7
1 2 0 3 0 4 2 3 0 3 2
是 是
7
0
是
7
0
LRU算法置换过程
7
1
2 0 3 0 4 2 3 0 3 2
是 是
7
0
是
7
0
7
0
1
是
LRU算法置换过程
7
1
0 3 0 4 2 3 0 3 2
是 是
7
0
是
7
0
7
0
1
是
7
0
11
0
22
否 是
LRU算法置换过程
7
1
0
3
0 4 2 3 0 3 2
是 是
7
0
是
7
0
7
0
1
是
7
0
11
0
22
否 是
22
00
3
否 是
LRU算法置换过程
7
1
0
3
0
4
2 3 0 3 2
是 是
7
0
是
7
0
7
0
1
是
7
0
11
0
22
否 是
22
00
3
否 是
LRU算法置换过程
4
00
33
是
7
1
0
3
0
4
2
3 0 3 2
是 是
7
0
是
7
0
7
0
1
是
7
0
11
0
22
否 是
22
00
3
否 是
LRU算法置换过程
4
00
33
是
2
00
44
是
7
1
0
3
0
4
2
3
0 3 2
是 是
7
0
是
7
0
7
0
1
是
7
0
11
0
22
否 是
22
00
3
否 是
LRU算法置换过程
4
00
33
是
2
00
44
是
3
22
44
是
7
1
0
3
0
4
2
3
3 2
是 是
7
0
是
7
0
7
0
1
是
7
0
11
0
22
否 是
22
00
3
否 是
LRU算法置换过程
4
00
33
是
2
00
44
是
3
22
44
是 否 否
结果：缺页次数共结果：缺页次数共99次次
2.对LRU算法的进一步认识到
(1)LRU没有Belady奇异。即随着驻留集
的增大,页故障一定减少。
(2)需要硬件配合，实现费用高，但效果
适中。
（3）LRU替换算法无Belady奇异现象举例：
••对于如下的页面访问序列：1，2，3，5，
2，4，5，2，1，3，2，5当内存块数量分
别为3和4时，试问：使用LRU置换算法产生
的缺页中断是多少？（所有内存开始时都
是空的，凡第一次用到的页面都产生一次
缺页中断）
–LRU算法，内存块为3时，缺页中断次数为8次。
–LRU算法，内存块为4时，缺页中断次数为7次。
（4）LRU算法的实现方法
••实现方法1：用计数器实现LRU。
••实现方法2：用栈实现LRU。
••实现方法3：用矩阵实现LRU。
••实现方法4：用寄存器实现LRU。
实现方法1—用计数器实现LRU
每页增加一个计数器，用计数器方
法记录情况。命中时，刚访问到的页
计数器清0，其余页计数器加1；淘汰
时选择页计数器值最大的页面，新换
入的页计数器清0，其余页计数器加1。
例如：
举例：若驻留集大小为3，访问串为
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2
0/7 1/7
0/0
2/7
1/0
0/1
0/2
2/0
1/1
1/2
0/0
2/1
2/2
1/0
0/3
3/2
0/0
1/3
0/4
1/0
2/3
1/4
2/0
0/2
2/4
0/3
1/2
0/0
1/3
2/2
1/0
0/3
3/2
2/0
1/3
0/2
淘汰的页序：淘汰的页序：7 1 2 3 0 47 1 2 3 0 4
缺页次数：缺页次数：99次次
实现方法2—用栈实现LRU
可用一个特殊的栈来保存当前使
用的各个页面的页面号。每当进程访
问某页面时便将该面页从栈中移出，
然后将它压入栈顶。因此，栈顶始终
是最新的页号，而栈底则是最近最久
未使用的页号。例如:
举例：驻留集大小为3，访问串为
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2
7
0
7
1
0
7
2
1
0
0
2
1
3
0
2
0
3
2
4
0
3
2
4
0
3
2
4
0
3
2
3
0
2
2
3
0
淘汰的页：7 1 2 3 0 4
缺页次数：9次
栈顶
栈底
(四)时钟置换算法(CLOCK)
CLOCK算法是LRU算法的近似算法。CLOCK
算法给每个页面设置一个访问位，标识该
页最近有没有被访问过，再将内存中的所
有页面通过一个指针链接成一个循环队列。
其算法流程图如下图所示。
开始
该页命中？
P指针不动，将
命中页的页面访
问位置为1
P指针所指页面访问位=0？
淘汰该页，换入
新页，该页页面
访问位置为1
P指针下移一个页面
置该页页面访问位为0
P指针下移一个页面
YES NO
YES
NO
CLOCK算法的流程图
读取要访问的页号读取要访问的页号
CLOCK算法举例：驻留集大小为3，访问串为
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2
淘汰页序:
O O O 7 1 2 0 3 4
1/7
0/-
0/-
1/7
1/0
1/7
1/0
1/1
0/7
0/0
0/1
1/2
0/0
0/1
1/2
1/0
0/1
1/2
1/0
1/3
0/2
0/0
0/3
1/4
0/0
0/3
1/4
1/2
0/3
1/4
1/2
1/3
0/4
0/2
1/0
1/3
0/2
1/0
1/3
1/2
1/0
0/4
0/2
0/3
1/2
0/0
0/1
1/2
0/0
1/3
0/-
0/-
0/-
初
始
注意:
若循环链表存在当前访问页(命中)时，直
接将其访问位改为1．指针不移动（命中后指针
不移动）；否则，若当前P指针指向页面的访问
位为0，则淘汰该页，调入新页．将其访问位改
为1，指针移到下一个物理块；若当前P指针指
向页面的访问位为1．则将其访问位改为0,并移
动指针到下一个物理块。
CLOCK算法的优点是:比LRU算法少了很多硬
件的支持，实现比较简单，但和FIFO算法相比，
仍需要较多的硬件支持。
四、页面替换算法解题举例
例1:在页式管理中，设给定的主存块数为三块，
已知页面走向为：4，3，2，1，4，3，5，4，3
，2，l，5。调页时分别采用FIFO算法、OPT算
法、栈结构实现的LRU算法和计数器实现的
LRU时，问：写出淘汰页序，淘汰次数和缺页
率各是多少？要求写出算法过程
1、FIFO页面置换算法
缺页次数为9次；缺页中断率f= 9/12＝75%.
2、OPT页面置换算法
缺页次数为7次，缺页中断率： f=7/12=%。
上题上题OPTOPT页面置换算法，当内存块为页面置换算法，当内存块为44块时，结果又是多少？块时，结果又是多少？
缺页次数为6次，缺页中断率： f=6/12=50%。
课堂练习
3、栈结构实现LRU页面置换算法
缺页次数为10次，缺页中断率： f=10/12=%。
课堂练习
对于如下的页面访问序列：7，1， 2， 0，3，0
，4， 2， 3， 0， 3， 2， 7， 0 。当内存块
数量为4时，试问：使用栈结构实现LRU置换算法
产生的缺页中断是多少？写出依次淘汰的页号。
（所有内存开始时都是空的，凡第一次用到的页
面都产生一次缺页中断。要求写出计算步骤。）
缺页次数为7次，缺页中断率： f=7/14=50%。
课堂练习答案
4、页计数器结构实现LRU页面置换算法
2
4
0
3
0
4
1
4
1
3
0
2
0
1
2
3
1
2
0
4
1
1
2
2
0
3
2
1
1
4
0
5
2
4
1
3
0
4
1
5
2
3
0
3
1
4
2
5
0
2
2
4
1
3
0
1
2
3
1
2
0
5
1
1
2
2
课堂练习
对于如下的页面访问序列：7，1， 2， 0，3，0
，4， 2， 3， 0， 3， 2， 7， 0 。当内存块
数量为4时，试问：使用LRU计数器置换算法产生
的缺页中断是多少？写出依次淘汰的页号。（所
有内存开始时都是空的，凡第一次用到的页面都
产生一次缺页中断。要求写出计算步骤。）
3
7
2
7
0
7
0
1
2
1
0
2
0
3
0
0
4
1
0
0
1
0
0
4
4
2
1
4
0
2
2
0
1
2
2
4
3
0
0
0
2
2
3
4
4
4
3
2
1
0
1
2
3
0
5
4
0
0
2
2
1
7
1
7
1
1
1
2
3
1
2
2
1
0
3
2
1
3
2
3
3
3 03
1
3
0
3
2
0
0
2
1
3
0
7
2
3
3
3
课堂练习答案
缺页次数为7次，缺页中断率： f=7/14=50%。
五、关于缺页中断率的讨论
（一）概念。假定一个作业共有n页，
系统分配给它的主存块是m块（m,n均是
正整数，且1<=m<=n）.因此，该作业最
多有m页可同时装入主存。如果作业执
行中访问页面的总次数为A，其中有F次
访问的页面未装入主存，故产生了F次
缺页中断。现定义：f=F/A
把f称为“缺页中断率”。
（二）影响缺页中断率的因素
1、分配给作业的主存块数
分配给作业的主存块数越多，则同
时装入主存的页面数就越多，缺页中断
的次数就越少。反之，就越高。
2、页面的大小
页面的大小取决于主存分块的大小，
块越大则页面越大，页面大则作业 的页
数就越少，一页内装入的信息量就越大，
缺页中断的次数就越少。反之，就越高。
3、编制程序的方法
程序编制的方法不同，对缺页中断
的次数有很大影响。例如：
有一个程序要把128×128的数组置
初值“0”，数组中的每一个元素为一
个字。现假定页面的尺寸为每页128个
字，数组中的每一行元素存放在一页。
能供这个程序使用的主存块只有一块，
开始时该内存块为空。若程序编制如下：
int A[127,127] ;
for (j=0 ;j<128;j++)
{ for (i=0;i<128;i++)
{ A[i,j]=0;}
}
•由于程序是按列清“0”的，所以每执
行一次A[i,j]=0(清“0”)就会产生一次缺
页中断，总共产生了（128*128）次中断。
若重新编制这个程序如下：
Int A[127,127];
for (i=0;i<128;i++)
{ for (j=0;j<128;j++)
{ A[i,j]=0;}
}
•那么，每装入一页后就对一行元素全部
清“0”后才产生缺页中断，故总共只产
生了128次缺页中断。
4、与页面调度算法有关
页面调度算法对缺页中断率的影响也很
大，调度不好就会出现“抖动”。
例：考虑下面的页访问串：1，2，3，
4，2，1，5，6，2，1，2，3，7，6，3
，2，1，2，3，6。假定分别有1，2，3
，4，5，6，7个页块，应用下面的页面
替换算法时，各会出现多少次缺页中断
？
（1）LRU；
（2） FIFO；
（3）Optimal。
由上可知：
（1）不同的调度算法，缺页中断次数有
差别，其中OPT算法最优，但无法实现，
因为谁也不能对程序的执行中要使用的
页面作出精确的断言。然而，它可以作
为一个衡量各种具体算法的标准。
（2）当驻留集增加到一定数量后，三种
算法的缺页中断次数，差别不大。
课堂练习：
考虑下述页面走向：4，3，2，1，4，
3，5，4，3，2，1，5。当内存块分别为3
和4时，试问LRU(基于栈结构算法)、FIFO、
OPT这三种置换算法的缺页次数各是多少
（假设所有内存块起初为空）？
当给定的内存块当给定的内存块=3=3时，时，LRULRU栈结构算法的置换过程如下：栈结构算法的置换过程如下：
当给定的内存块当给定的内存块=4=4时，时，LRULRU栈结构算法的置换过程如下：栈结构算法的置换过程如下：
六、一个页面替换策略的实用方法
（兼顾FIFO和LRU策略）
为页帧在页表项中增加一位使用位，硬件每访
存一次，即将对应页的使用位置1，操作系统页面
管理程序定时将所有使用位清0。淘汰时任选一个
使用位为0的页。
操作系统选择淘汰页时，尽量避免选被修改过
的页。因此，首先选择使用和修改位都为0的页；
若没有，再选修改位为1，使用位为0的页；再选
使用位为1，修改位为0的页；最后按FIFO选两者
均为1的页。
七、驻留集可变的替换策略
（一）引入原因：
1、程序访存的布局特性和阶段转换
特性。
• 局部性:一段时间内程序访存有局部
性.
• 阶段转换性:从一个局部集向另一个
局部集过渡是突然的.
• 局部集一般不超过程序总页数的20%。
2、若驻留集小于局部集时引起抖
动，而驻留集大于局部集又是浪费。同
时局部集又有大有小。
因此，应随着程序访问虚存的局部
集大小变化而改变驻留集。
若驻留集(最大为4块)中的某页有△
个访问间隔没被访问，则将其淘汰。
举例：取△=5，访问串为如下，问共
产生多少次缺页中断？，驻留集的平均大
小为多少个页帧？
(一) WS(working set)
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1
1 2 3 4 4 4 4 4 4 4 4 4 3 4 4 4 3
7
0
7
0
1
7
0
1
2
7
0
1
2
7
0
1
2
3
0
1
2
3
0
4
2
3
0
4
2
3
0
4
2
3
0
4
2
3
0
4
2
3
0
2
3
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1
0
2
1
3
0
2
1
3
0
2
1
3
2
1
0
结果：共产生7次页故障；驻留集的平均大
小为个页帧。
实现：
每一页面设一计数器。每访存一次，
将所有计数器加1，所访存的页面计数器
清0，淘汰计数器值等于△的页面。
特点：
开销太大，不实用。
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1
(二) VMIN(Variable Minimal
replacement)
若某页距下次访问的距离大于△，则
将其淘汰(不能实用)；与WS策略△相同时，
VMIN与WS的故障数相同，但VMIN的平均驻
留集要小。例：
1 1 2 2 2 3 3 4 3 3 3 3 2 3 3 2 1
7 0
1
0
2
0
2
0
2
3
0
2
3
0
2
3
4
0
2
3
0
2
3
0
2
3
0
2
3
0
2
0
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1
2
1
0
2
1
0
1
0 1
结果：共产生7次页故障；驻留集的平均大
小为个页帧。
实用OS选择动态驻留集FIFO(SWS)的变种。
• 设立两个队列：自由链表和修改链表。
• 定时作页淘汰：淘汰时不立即删除页中数据，
要根据页面是否修改挂入自由链/修改链，修改链
过长时，回写页面后改挂到自由链中。
• paging in要用空页时,选自由链的第一页帧，
这时页中数据被覆盖,改变该页帧原页面页表项状
态等信息。
• 在自由链/修改链中的页面再次被访问时，则将
该页从链中摘除,该页又能通过页表项访问到。
八、替换策略选择
预调
请调与预调的区别：
• 存储管理：用时分配调入与预分配调入；
• 替换策略：要时页淘汰与预淘汰。
固定驻留集大小时，一般驻留集未满时，
采用预调；待驻留集满即改为请调。
本讲完
