北京大学《计算机系统结构》：第三章存储系统3

4、虚拟存储器举例 例3.7:IMB3η0/168计算机的虚拟存储器快表结构及地址变换过程。虚拟地 址长36位,页面大小为4KB,每个用户最多占用4K个页面,最多允许16G个用 户,但同时上机的用户数一般不超过6个 (书上第62页)图3.30IBM370/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—1 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 123456 8|910实际 页地址流 PIP2P1|P5P4P1|P3P4P2P41命中次数 先进先出算法_2 (F第法)影缓555*3333* 调入调入命中调入蒈换替換替换命中替换替換2次 最久没有使用算法圆才222*444444 (LN算法)(變55**3「33*[3* 调入调入命中调入蒈换命中替换命中替换命中4次 111111*3*3*33 最优替换算法圈2121 OP算法)5*[444444 调入调入命中调入匿换命中替換命中命中命中5次 三种页面替换算法对同一个页地址流的调度过程 例3.9:一个循环程序,依次使用P1,P2,P3,P4四个页面,分配给这个 程序的主存页面数为3个。FIFO、LRU和OPT三种页面替换算法对主存页面的调 度情况如下图所示。在FIFO和LRU算法中,总是发生下次就要使用的页面本次 被替换出去的情况,这就是“颠簸”现象。 时间t 23|4567|8|实阿 页地址流 PI十P2P3十p4P1P2p3p4|命中次数 先进先出算法_222*111*4 FI算法)圈333*222* 调入调入|调入替换|替换「替换「替换替换0次 4 3 最久没有使用算法影缓[2211「*4 LR算法)多「333*222 调入|调入调入替换替换|替换|替换|替换|0次 最优替换算法 OP算法)多多3*[4*44[44 调入|调入调入替换命中|命中替换命中3次 图3.33页面调度中的颠簸现象

3—2 假设分配给这个程序的主存储器共有 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)c Bt (n) 则这类算法称为堆栈型替换算法。 堆栈型算法的基本特点是:随着分配给程序的主存页面数增加,主存的命中 率也提高,至少不下降。 时间t 23456789101112|实际 页地址流P1P2P3PP1P2P5P1P2P3P4P5命中次数 4*55555*5* 主存页面数222* N=3菱333* 2222 入调入调入替换替换替换替换命中命中替换替换命中3次 1*1*55 5*4 主存页面数2 22*2*1 1|1* N=4多接33333 2222* 调入调入调入调入命中命中替换替換换替换替换替换替换2次 FIFO算法在主存页面数增加时命中率反而下降 LFU算法、LRU算法和PT算法都是堆栈型算法。 FIFO算法不是堆栈型算法 3.2.5提高主存命中率的方法 影响主存命中率的主要因素: (1)程序在执行过程中的页地址流分布情况。 (2)所采用的页面替换算法 (3)页面大小。 (4)主存储器的容量 (5)所采用的页面调度方法。 以下,对后三个因素进行分析 1、页面大小与命中率的关系 页面大小为某个值时,命中率达到最大。 解释:假设A1和A是相邻两次访问主存储器的逻辑地址,d=|At-A+1|。 如果dSp,At和A+1一定不在同一个页面内。随着Sp的增大,主存 的页面数减少,页面的替换将更加频繁。H随着Sp的增大而降低

3—3 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比较小的时候,前一种情况是主要的,H随着Sp的增大而提高 当Sp达到某一个最大值之后,后一种情况成为主要的,H随着Sp的 增大而降低 当页面大小增大时,造成的浪费也要增加 当页面大小减小时,页表和页面表在主存储器中所占的比例将增加 (书上第170页)图3.36页面大小与主存命中率的关系 2、主存容量与命中率的关系 主存命中率H随着分配给该程序的主存容量S的增加而单调上升 在S比较小的时候,H提高得非常快。随着S的逐渐增加,H提高的速度逐 渐降低。当S增加到某一个值之后,H几乎不再提髙 (书上第171页)图3.37主存命中H率与主存容量S的关系 3、页面调度方式与命中率的关系 请求式:当使用到的时候,再调入主存 预取式:在程序重新开始运行之前,把上次停止运行前一段时间内用到的页 面先调入到主存储器,然后才开始运行程序 可以避免在程序开始运行时,频繁发生页面失效的情况。 如果调入的页面用不上,浪费了调入的时间,占用了主存资源。 3.3高速缓冲存储器( Cache) 3.31基本工作原理 3.32地址映象与变换方法 3.33 Cache替换算法及其实现 334 Cache存储系统的加速比 3.35 Cache的一致性问题 336 Cache的预取算法 Cache存储系统与虚拟存储系统的比较 存储系统 ache 虚拟存储器 要达到的目标 提高(主存)速度 扩大(主存)容量 实现方法 全部硬件 软件为主,硬件为辅 两级存储器速度比 3~10倍 105倍 页(块)大小 1~16字 IKB-16KB 等效存储容量 主存储器 虚拟存储器 透明性 对系统和应用程序员 仅对应用程序员 不命中时处理方式 等待主存储器 任务切换

3—4 当 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页)图338 Cache存储系统工作原理 3.3.2地址映象与变换方法 地址映象:把存放在主存中的程序按照某种规则装入到 Cache中,并建立主 存地址与 Cache地址之间的对应关系。 地址变换:当程序已经装入到 Cache之后,在实际运行过程中,把主存地址 变换成 Cache地址 在选取地址映象方法时,要考虑的主要因素: 地址变换的硬件容易实现, 地址变换的速度快, 主存空间利用率高 发生块冲突的概率。 1、全相联映象及其变换 (书上第175页)图3.39全相联映象方式 映象规则:主存中的任意一块可以映象到 Cache中的任意一块。 如果 Cache的块数为Cb,主存的块数为Mb,映象关系共有Cb×Mb种 (书上第175页)图340全相联地址变换 2、直接映象及其变换 映象规则:主存中一块只能映象到 Cache的一个特定的块中, 计算公式:b= B mod Cb 其中:b为 Cache的块号,B是主存的块号,Cb是 Cache的块数。 整个 Cache地址与主存地址的低位部分完全相同。 (书上第176页)图341直接相联映象方式 地址变换过程: 用主存地址中的块号B去访问区号存储器 把读出来的区号与主存地址中的区号E进行比较 比较结果相等,且有效位为1,则 Cache命中。 比较结果相等,有效位为0,表示 Cache中的这一块已经作废

3—5 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,表示 比较结果不相等,有效位为1,表示 Cache I 中的这一块是空的。 中的这一块是有用的。 (书上第177页)图342直接相联地址变换 提高 Cache速度的一种方法: 把区号存储器与 Cache合并成一个存储器 (书上第178页)图343快速度的直接相联地址变换 ●直接映象方法的主要优点: 硬件实现很简单,不需要相联访问存储器 访问速度也比较快,实际上不进行地址变换 直接映象方式的主要缺点:块的冲突率比较高。 习题: 3.23.53.83.133.14

3—6 比较结果不相等，有效位为 0，表示 Cache 中的这一块是空的。 比较结果不相等，有效位为 1，表示 Cache 中的这一块是有用的。 （书上第 177 页）图 3.42 直接相联地址变换 • 提高 Cache 速度的一种方法： 把区号存储器与 Cache 合并成一个存储器 (书上第 178 页）图 3.43 快速度的直接相联地址变换 • 直接映象方法的主要优点： 硬件实现很简单，不需要相联访问存储器 访问速度也比较快，实际上不进行地址变换 • 直接映象方式的主要缺点：块的冲突率比较高。 习题： 3.2 3.5 3.8 3.13 3.14