4、虚拟存储器举例例3.7：IMB370/168计算机的虚拟存储器快表结构及地址变换过程。虚拟地址长36位，页面大小为4KB，每个用户最多占用4K个页面，最多允许16G个用户，但同时上机的用户数一般不超过6个。
（书上第62页） 图3.30 IBM370/168计算机的虚拟存储器快表结构
采用了两项新的措施：
一是采用两个相等比较器。
二是用相联寄存器组把24位用户号U压缩成3位
3.2.4 页面替换算法及其实现方法页面替换发生时间：当发生页面失效时，要从磁盘中调入一页到主存。如果主存所有页面都已经被占用，必须从主存储器中淘汰掉一个不常使用的页面，以便腾出主存空间来存放新调入的页面。
评价页面替换算法好坏的标准：一是命中率要高，二是算法要容易实现。
页面替换算法的使用场合：
(1) 虚拟存储器中，主存页面的替换，一般用软件实现。
(2) Cache中的块替换，一般用硬件实现。
(3) 虚拟存储器的快慢表中，快表存储字的替换，用硬件实现。
(4) 虚拟存储器中，用户基地址寄存器的替换，用硬件实现。
(5) 在有些虚拟存储器中，目录表的替换。
1、页面替换算法常用的页面替换算法：
(1) 随机算法（RAND Random algorithm）：
算法简单，容易实现。
没有利用历史信息，没有反映程序的局部性，命中率低。
(2) 先进先出算法（FIFO First-In First-Out algorithm）：
比较容易实现，利用了历史信息，没有反映程序的局部性。
最先调入主存的页面，很可能也是经常要使用的页面。
(3) 近期最少使用算法（LFU Least Frequently Used algorithm）：
既充分利用了历史信息，又反映了程序的局部性
实现起来非常困难。
(4) 最久没有使用算法（LRU Least Recently Used algorithm）：
它把LRU算法中的“多”与“少”简化成“有”与“无”，
实现起来比较容易。
(5) 最优替换算法（OPT OPTimal replacemant algorithm）：
是一种理想化的算法。用来作为评价其它页面替换算法好坏的标准。
在虚拟存储器中，实际上有可能采用只有FIFO和LRU两种算法。
例3.8：一个程序共有5个页面组成，分别为P1～P5。程序执行过程中的页地址流（即程序执行中依次用到的页面）如下：
P1，P2，P1，P5，P5，P1，P3，P4，P3，P4
假设分配给这个程序的主存储器共有3个页面。给出FIFO、LRU和OPT三种页面替换算法对这3页主存的使用情况，包括调入、替换和命中等。
时间t
1
2
3
4
5
6
7
8
9
10
实际
页地址流
P1
P2
P1
P5
P4
P1
P3
P4
P2
P4
命中次数
1
1
1
1*
4
4
4*
4*
2
2
先进先出算法
2
2
2
2*
1
1
1
1*
4
（FIFO算法）
5
5
5*
3
3
3
3*
调入
调入
命中
调入
替换
替换
替换
命中
替换
替换
2次
1
1
1
1
1
1
1
1*
2
2
最久没有使用算法
2
2
2*
4
4
4*
4
4
4
（LRU算法）
5
5*
5*
3
3
3*
3*
调入
调入
命中
调入
替换
命中
替换
命中
替换
命中
4次
1
1
1
1
1
1*
3*
3*
3
3
最优替换算法
2
2
2
2*
2
2
2
2
2
（OPT算法）
5*
4
4
4
4
4
4
调入
调入
命中
调入
替换
命中
替换
命中
命中
命中
5次
三种页面替换算法对同一个页地址流的调度过程
例3.9：一个循环程序，依次使用P1，P2，P3，P4四个页面，分配给这个程序的主存页面数为3个。FIFO、LRU和OPT三种页面替换算法对主存页面的调度情况如下图所示。在FIFO和LRU算法中，总是发生下次就要使用的页面本次被替换出去的情况，这就是“颠簸”现象。
时间t
1
2
3
4
5
6
7
8
实际
页地址流
P1
P2
P3
P4
P1
P2
P3
P4
命中次数
1
1
1*
4
4
4*
3
3
先进先出算法
2
2
2*
1
1
1*
4
（FIFO算法）
3
3
3*
2
2
2*
调入
调入
调入
替换
替换
替换
替换
替换
0次
1
1
1*
4
4
4*
3
3
最久没有使用算法
2
2
2*
1
1
1*
4
（LRU算法）
3
3
3*
2
2
2*
调入
调入
调入
替换
替换
替换
替换
替换
0次
1
1
1
1
1*
1
1
1
最优替换算法
2
2
2
2
2*
3*
3
（OPT算法）
3*
4*
4
4
4
4*
调入
调入
调入
替换
命中
命中
替换
命中
3次
图3.33 页面调度中的颠簸现象
2、堆栈型替换算法堆栈型替换算法的定义：
对任意一个程序的页地址流作两次主存页面数分配，分别分配m个主存页面和n个主存页面，并且有m≤n。如果在任何时刻t，主存页面数集合Bt都满足关系：
Bt（m）( Bt（n）
则这类算法称为堆栈型替换算法。
堆栈型算法的基本特点是：随着分配给程序的主存页面数增加，主存的命中率也提高，至少不下降。
时间t
1
2
3
4
5
6
7
8
9
10
11
12
实际
页地址流
P1
P2
P3
P4
P1
P2
P5
P1
P2
P3
P4
P5
命中次数
1
1
1*
4
4
4*
5
5
5
5
5*
5*
主存页面数
2
2
2*
1
1
1*
1*
1*
3
3
3
N＝3
3
3
3*
2
2
2
2
2*
4
4
调入
调入
调入
替换
替换
替换
替换
命中
命中
替换
替换
命中
3次
1
1
1
1
1*
1*
5
5
5
5*
4
4
主存页面数
2
2
2
2
2*
2*
1
1
1
1*
5
N＝4
3
3
3
3
3
3*
2
2
2
2*
4
4
4
4
4
4*
3
3
3
调入
调入
调入
调入
命中
命中
替换
替换
替换
替换
替换
替换
2次
FIFO算法在主存页面数增加时命中率反而下降
LFU算法、LRU算法和OPT算法都是堆栈型算法。
FIFO算法不是堆栈型算法
3.2.5 提高主存命中率的方法影响主存命中率的主要因素：
(1) 程序在执行过程中的页地址流分布情况。
(2) 所采用的页面替换算法。
(3) 页面大小。
(4) 主存储器的容量
(5) 所采用的页面调度方法。
以下，对后三个因素进行分析。
1、页面大小与命中率的关系页面大小为某个值时，命中率达到最大。
解释：假设At和At+1是相邻两次访问主存储器的逻辑地址，d＝｜At－At+1｜。
如果ｄ＜Sp，随着Sp的增大，At和At+1在同一页面的可能性增加，即Ｈ随着Sp的增大而提高。
如果ｄ＞Sp，At和At+1一定不在同一个页面内。随着Sp的增大，主存的页面数减少，页面的替换将更加频繁。Ｈ随着Sp的增大而降低。
当Sp比较小的时候，前一种情况是主要的，Ｈ随着Sp的增大而提高。
当Sp达到某一个最大值之后，后一种情况成为主要的，Ｈ随着Sp的增大而降低。
当页面大小增大时，造成的浪费也要增加。
当页面大小减小时，页表和页面表在主存储器中所占的比例将增加。
（书上第170页）图3.36 页面大小与主存命中率的关系
2、主存容量与命中率的关系主存命中率H随着分配给该程序的主存容量S的增加而单调上升。
在S比较小的时候，H提高得非常快。随着S的逐渐增加，H提高的速度逐渐降低。当S增加到某一个值之后，H几乎不再提高。
（书上第171页）图3.37 主存命中H率与主存容量S的关系
3、页面调度方式与命中率的关系请求式：当使用到的时候，再调入主存预取式：在程序重新开始运行之前，把上次停止运行前一段时间内用到的页面先调入到主存储器，然后才开始运行程序。
可以避免在程序开始运行时，频繁发生页面失效的情况。
如果调入的页面用不上，浪费了调入的时间，占用了主存资源。
3.3 高速缓冲存储器（Cache）
3.3.1 基本工作原理
3.3.2 地址映象与变换方法
3.3.3 Cache替换算法及其实现
3.3.4 Cache存储系统的加速比
3.3.5 Cache的一致性问题
3.3.6 Cache的预取算法
Cache存储系统与虚拟存储系统的比较存储系统
Cache
虚拟存储器
要达到的目标
提高（主存）速度
扩大（主存）容量
实现方法
全部硬件
软件为主，硬件为辅
两级存储器速度比
3～10倍
105倍
页（块）大小
1～16字
1KB～16KB
等效存储容量
主存储器
虚拟存储器
透明性
对系统和应用程序员
仅对应用程序员
不命中时处理方式
等待主存储器
任务切换
3.3.1 基本工作原理
Cache和主存储器都划分成相同大小的块。
主存地址由块号B和块内地址W两部分组成。
Cache的地址也由块号b和块内地址w组成。
（书上第173页）图3.38 Cache存储系统工作原理
3.3.2 地址映象与变换方法地址映象：把存放在主存中的程序按照某种规则装入到Cache中，并建立主存地址与Cache地址之间的对应关系。
地址变换：当程序已经装入到Cache之后，在实际运行过程中，把主存地址变换成Cache地址。
在选取地址映象方法时，要考虑的主要因素：
地址变换的硬件容易实现，
地址变换的速度快，
主存空间利用率高，
发生块冲突的概率。
1、全相联映象及其变换
（书上第175页）图3.39 全相联映象方式
映象规则：主存中的任意一块可以映象到Cache中的任意一块。
如果Cache的块数为Cb，主存的块数为Mb，映象关系共有Cb×Mb种。
（书上第175页）图3.40 全相联地址变换
2、直接映象及其变换
( 映象规则：主存中一块只能映象到Cache的一个特定的块中。
计算公式：b＝B mod Cb
其中：b为Cache的块号，B是主存的块号，Cb是Cache的块数。
整个Cache地址与主存地址的低位部分完全相同。
（书上第176页）图3.41 直接相联映象方式
( 地址变换过程：
用主存地址中的块号B去访问区号存储器把读出来的区号与主存地址中的区号E进行比较
比较结果相等，且有效位为1，则Cache命中。
比较结果相等，有效位为0，表示Cache中的这一块已经作废。
比较结果不相等，有效位为0，表示Cache中的这一块是空的。
比较结果不相等，有效位为1，表示Cache中的这一块是有用的。
（书上第177页）图3.42 直接相联地址变换
( 提高Cache速度的一种方法：
把区号存储器与Cache合并成一个存储器
(书上第178页）图3.43 快速度的直接相联地址变换
( 直接映象方法的主要优点：
硬件实现很简单，不需要相联访问存储器访问速度也比较快，实际上不进行地址变换
( 直接映象方式的主要缺点：块的冲突率比较高。
习题：
3.2 3.5 3.8 3.13 3.14
（书上第62页） 图3.30 IBM370/168计算机的虚拟存储器快表结构
采用了两项新的措施：
一是采用两个相等比较器。
二是用相联寄存器组把24位用户号U压缩成3位
3.2.4 页面替换算法及其实现方法页面替换发生时间：当发生页面失效时，要从磁盘中调入一页到主存。如果主存所有页面都已经被占用，必须从主存储器中淘汰掉一个不常使用的页面，以便腾出主存空间来存放新调入的页面。
评价页面替换算法好坏的标准：一是命中率要高，二是算法要容易实现。
页面替换算法的使用场合：
(1) 虚拟存储器中，主存页面的替换，一般用软件实现。
(2) Cache中的块替换，一般用硬件实现。
(3) 虚拟存储器的快慢表中，快表存储字的替换，用硬件实现。
(4) 虚拟存储器中，用户基地址寄存器的替换，用硬件实现。
(5) 在有些虚拟存储器中，目录表的替换。
1、页面替换算法常用的页面替换算法：
(1) 随机算法（RAND Random algorithm）：
算法简单，容易实现。
没有利用历史信息，没有反映程序的局部性，命中率低。
(2) 先进先出算法（FIFO First-In First-Out algorithm）：
比较容易实现，利用了历史信息，没有反映程序的局部性。
最先调入主存的页面，很可能也是经常要使用的页面。
(3) 近期最少使用算法（LFU Least Frequently Used algorithm）：
既充分利用了历史信息，又反映了程序的局部性
实现起来非常困难。
(4) 最久没有使用算法（LRU Least Recently Used algorithm）：
它把LRU算法中的“多”与“少”简化成“有”与“无”，
实现起来比较容易。
(5) 最优替换算法（OPT OPTimal replacemant algorithm）：
是一种理想化的算法。用来作为评价其它页面替换算法好坏的标准。
在虚拟存储器中，实际上有可能采用只有FIFO和LRU两种算法。
例3.8：一个程序共有5个页面组成，分别为P1～P5。程序执行过程中的页地址流（即程序执行中依次用到的页面）如下：
P1，P2，P1，P5，P5，P1，P3，P4，P3，P4
假设分配给这个程序的主存储器共有3个页面。给出FIFO、LRU和OPT三种页面替换算法对这3页主存的使用情况，包括调入、替换和命中等。
时间t
1
2
3
4
5
6
7
8
9
10
实际
页地址流
P1
P2
P1
P5
P4
P1
P3
P4
P2
P4
命中次数
1
1
1
1*
4
4
4*
4*
2
2
先进先出算法
2
2
2
2*
1
1
1
1*
4
（FIFO算法）
5
5
5*
3
3
3
3*
调入
调入
命中
调入
替换
替换
替换
命中
替换
替换
2次
1
1
1
1
1
1
1
1*
2
2
最久没有使用算法
2
2
2*
4
4
4*
4
4
4
（LRU算法）
5
5*
5*
3
3
3*
3*
调入
调入
命中
调入
替换
命中
替换
命中
替换
命中
4次
1
1
1
1
1
1*
3*
3*
3
3
最优替换算法
2
2
2
2*
2
2
2
2
2
（OPT算法）
5*
4
4
4
4
4
4
调入
调入
命中
调入
替换
命中
替换
命中
命中
命中
5次
三种页面替换算法对同一个页地址流的调度过程
例3.9：一个循环程序，依次使用P1，P2，P3，P4四个页面，分配给这个程序的主存页面数为3个。FIFO、LRU和OPT三种页面替换算法对主存页面的调度情况如下图所示。在FIFO和LRU算法中，总是发生下次就要使用的页面本次被替换出去的情况，这就是“颠簸”现象。
时间t
1
2
3
4
5
6
7
8
实际
页地址流
P1
P2
P3
P4
P1
P2
P3
P4
命中次数
1
1
1*
4
4
4*
3
3
先进先出算法
2
2
2*
1
1
1*
4
（FIFO算法）
3
3
3*
2
2
2*
调入
调入
调入
替换
替换
替换
替换
替换
0次
1
1
1*
4
4
4*
3
3
最久没有使用算法
2
2
2*
1
1
1*
4
（LRU算法）
3
3
3*
2
2
2*
调入
调入
调入
替换
替换
替换
替换
替换
0次
1
1
1
1
1*
1
1
1
最优替换算法
2
2
2
2
2*
3*
3
（OPT算法）
3*
4*
4
4
4
4*
调入
调入
调入
替换
命中
命中
替换
命中
3次
图3.33 页面调度中的颠簸现象
2、堆栈型替换算法堆栈型替换算法的定义：
对任意一个程序的页地址流作两次主存页面数分配，分别分配m个主存页面和n个主存页面，并且有m≤n。如果在任何时刻t，主存页面数集合Bt都满足关系：
Bt（m）( Bt（n）
则这类算法称为堆栈型替换算法。
堆栈型算法的基本特点是：随着分配给程序的主存页面数增加，主存的命中率也提高，至少不下降。
时间t
1
2
3
4
5
6
7
8
9
10
11
12
实际
页地址流
P1
P2
P3
P4
P1
P2
P5
P1
P2
P3
P4
P5
命中次数
1
1
1*
4
4
4*
5
5
5
5
5*
5*
主存页面数
2
2
2*
1
1
1*
1*
1*
3
3
3
N＝3
3
3
3*
2
2
2
2
2*
4
4
调入
调入
调入
替换
替换
替换
替换
命中
命中
替换
替换
命中
3次
1
1
1
1
1*
1*
5
5
5
5*
4
4
主存页面数
2
2
2
2
2*
2*
1
1
1
1*
5
N＝4
3
3
3
3
3
3*
2
2
2
2*
4
4
4
4
4
4*
3
3
3
调入
调入
调入
调入
命中
命中
替换
替换
替换
替换
替换
替换
2次
FIFO算法在主存页面数增加时命中率反而下降
LFU算法、LRU算法和OPT算法都是堆栈型算法。
FIFO算法不是堆栈型算法
3.2.5 提高主存命中率的方法影响主存命中率的主要因素：
(1) 程序在执行过程中的页地址流分布情况。
(2) 所采用的页面替换算法。
(3) 页面大小。
(4) 主存储器的容量
(5) 所采用的页面调度方法。
以下，对后三个因素进行分析。
1、页面大小与命中率的关系页面大小为某个值时，命中率达到最大。
解释：假设At和At+1是相邻两次访问主存储器的逻辑地址，d＝｜At－At+1｜。
如果ｄ＜Sp，随着Sp的增大，At和At+1在同一页面的可能性增加，即Ｈ随着Sp的增大而提高。
如果ｄ＞Sp，At和At+1一定不在同一个页面内。随着Sp的增大，主存的页面数减少，页面的替换将更加频繁。Ｈ随着Sp的增大而降低。
当Sp比较小的时候，前一种情况是主要的，Ｈ随着Sp的增大而提高。
当Sp达到某一个最大值之后，后一种情况成为主要的，Ｈ随着Sp的增大而降低。
当页面大小增大时，造成的浪费也要增加。
当页面大小减小时，页表和页面表在主存储器中所占的比例将增加。
（书上第170页）图3.36 页面大小与主存命中率的关系
2、主存容量与命中率的关系主存命中率H随着分配给该程序的主存容量S的增加而单调上升。
在S比较小的时候，H提高得非常快。随着S的逐渐增加，H提高的速度逐渐降低。当S增加到某一个值之后，H几乎不再提高。
（书上第171页）图3.37 主存命中H率与主存容量S的关系
3、页面调度方式与命中率的关系请求式：当使用到的时候，再调入主存预取式：在程序重新开始运行之前，把上次停止运行前一段时间内用到的页面先调入到主存储器，然后才开始运行程序。
可以避免在程序开始运行时，频繁发生页面失效的情况。
如果调入的页面用不上，浪费了调入的时间，占用了主存资源。
3.3 高速缓冲存储器（Cache）
3.3.1 基本工作原理
3.3.2 地址映象与变换方法
3.3.3 Cache替换算法及其实现
3.3.4 Cache存储系统的加速比
3.3.5 Cache的一致性问题
3.3.6 Cache的预取算法
Cache存储系统与虚拟存储系统的比较存储系统
Cache
虚拟存储器
要达到的目标
提高（主存）速度
扩大（主存）容量
实现方法
全部硬件
软件为主，硬件为辅
两级存储器速度比
3～10倍
105倍
页（块）大小
1～16字
1KB～16KB
等效存储容量
主存储器
虚拟存储器
透明性
对系统和应用程序员
仅对应用程序员
不命中时处理方式
等待主存储器
任务切换
3.3.1 基本工作原理
Cache和主存储器都划分成相同大小的块。
主存地址由块号B和块内地址W两部分组成。
Cache的地址也由块号b和块内地址w组成。
（书上第173页）图3.38 Cache存储系统工作原理
3.3.2 地址映象与变换方法地址映象：把存放在主存中的程序按照某种规则装入到Cache中，并建立主存地址与Cache地址之间的对应关系。
地址变换：当程序已经装入到Cache之后，在实际运行过程中，把主存地址变换成Cache地址。
在选取地址映象方法时，要考虑的主要因素：
地址变换的硬件容易实现，
地址变换的速度快，
主存空间利用率高，
发生块冲突的概率。
1、全相联映象及其变换
（书上第175页）图3.39 全相联映象方式
映象规则：主存中的任意一块可以映象到Cache中的任意一块。
如果Cache的块数为Cb，主存的块数为Mb，映象关系共有Cb×Mb种。
（书上第175页）图3.40 全相联地址变换
2、直接映象及其变换
( 映象规则：主存中一块只能映象到Cache的一个特定的块中。
计算公式：b＝B mod Cb
其中：b为Cache的块号，B是主存的块号，Cb是Cache的块数。
整个Cache地址与主存地址的低位部分完全相同。
（书上第176页）图3.41 直接相联映象方式
( 地址变换过程：
用主存地址中的块号B去访问区号存储器把读出来的区号与主存地址中的区号E进行比较
比较结果相等，且有效位为1，则Cache命中。
比较结果相等，有效位为0，表示Cache中的这一块已经作废。
比较结果不相等，有效位为0，表示Cache中的这一块是空的。
比较结果不相等，有效位为1，表示Cache中的这一块是有用的。
（书上第177页）图3.42 直接相联地址变换
( 提高Cache速度的一种方法：
把区号存储器与Cache合并成一个存储器
(书上第178页）图3.43 快速度的直接相联地址变换
( 直接映象方法的主要优点：
硬件实现很简单，不需要相联访问存储器访问速度也比较快，实际上不进行地址变换
( 直接映象方式的主要缺点：块的冲突率比较高。
习题：
3.2 3.5 3.8 3.13 3.14
