4计算机系统结构(第四讲)

1、计算机系统结构(第四讲),厦门大学计算机科学系 陆达 2004年10月18日,第三章 存储系统,3.2 虚拟存储器,1961年，Kilbrn提出 虚拟存储器，虚拟存储系统，虚拟存储体系 基本工作原理，地址映象和变换方法，页面替换算法，加速地址变换速度的方法,3.2.1 虚拟存储器工作原理,页式虚拟存储器 页（page） 图3.16：虚拟存储器中的地址组成 实页（主存储器的页） 主存地址A=实页号p+页内偏移d 虚页（虚拟存储器的页） 虚地址Av=用户号U+虚页号P+页内偏移D,图3.17：页式虚拟存储器工作原理,变换成功（命中） 变换失败（未命中） 内部地址变换：虚页号P = 实页号p 外部地

2、址变换：虚页号P = 磁盘实地址 页面替换算法（当主存储器中没有空页时）,3.2.2 地址的映象与变换,虚拟地址空间、主存地址空间、辅存地址空间 地址映象：把虚拟地址空间映象到主存地址空间，即将用户用虚拟地址编写的程序按照某种规则装入到主存储器中 地址变换：在程序被装入主存储器后，在实际运行时，把多用户虚地址变换成主存实地址（内部地址变换）或磁盘存储器地址（外部地址变换）,3.2.2.1 段式虚拟存储器,图3.18：地址映象 段表：包括段号（或段名）、段长、起始地址等 图3.19：地址变换 段表基址寄存器堆 装入位、访问方式、修改标志字段,段式虚拟存储器的主要优点： 1）、程序的模块化性能好

3、2）、便于程序和数据的共享 3）、程序的动态链接和调度比较容易 4）、便于实现信息保护 段式虚拟存储器的主要缺点： 1）、地址变换所化的时间比较长 2）、主存储器的利用率往往比较低 3）、对辅存（磁盘存储器）的管理比较困难,3.2.2.2 页式虚拟存储器,页（page）：1page=0.5KB的整倍数=1KB16KB 虚页、实页 地址映象：从虚页号到实页号的地址变换（图3.20） 页表=页号+主存页号 地址变换：将用户程序的虚拟地址变换成主存实地址（图3.21） 多用户虚地址Av=用户号U+虚页号P+页内偏移D 主存实地址A=实页号p+页内偏移d 页表基址寄存器堆 基址寄存器的内容=页表起始地

4、址 装入位、修改位、各种标志信息,页式虚拟存储器的主要优点： 1）、主存储器的利用率比较高 2）、页表相对比较简单 3）、地址映象和变换的速度比较快 4）、对辅存（磁盘存储器）的管理比较容易 页式虚拟存储器的主要缺点： 1）、程序的模块化性能不好 2）、页表很长 虚拟存储空间=4GB、1页=1KB 页表的容量=4M存储字（4GB/1KB） =4M*4B=16MB,3.2.2.3 段页式虚拟存储器,综合段式虚拟存储器在程序模块化方面的优点和页式虚拟存储器在管理主存和辅存物理空间方面的优点 基本思想是：对用户用来编写程序的虚拟存储空间采用分段的方法管理，而对主存储器的物理空间采用分页的方法管理 地

5、址映象：图3.22 段表=页表长度+页表地址 页表=主存的实页号,地址变换：图3.23 多用户虚地址Av=用户号U+段号S+虚页号P+页内偏移D 主存地址A=实页号p+页内偏移d 段表基址寄存器堆、段表、页表 IBM 370/168、Multics、Amdahl470V/6等采用段页式虚拟存储器 段页式虚拟存储器的缺点：要从主存储器中访问一个数据，需要查二次表，访问主存储器三次,3.2.2.4 外部地址变换,当发生页面失效时（未命中），必须进行外部地址变换 外部地址变换：虚地址 = 辅存的实地址 页面失效属于异常故障，保存和恢复故障点的现场的方法有三个： （1）、采用硬件的缓冲寄存器 （2）、

6、只保存部分现场（如PC、PSW等） （3）、采用指令预判技术,磁盘存储器的地址=磁盘号+柱面号+磁头号+块号（图3.24） 图3.25：外部地址变换，通常用软件实现 外页表=磁盘实地址+装入位 多级页表技术（见3.2.3小节） 外页表与内页表合并成一个页表,3.2.3 加快内部地址变换的方法,造成虚拟存储器速度降低的主要原因： （1）、要访问主存储器，必须先查段表或页表或段页表 （2）、页表或段表的容量超过一个页面时，需采用多级页表技术，从而又增加了查页表（段表）的次数 多级页表技术： g：页表的级数 Nv：虚拟存储空间的大小 Np：页面的大小 Nd：页表存储字的大小,例如： Nv=4Gb、N

7、p=1KB、Nd=4B g=3 第一级页表：1个页面，64个存储字（64*4B=256B1KB） 第二级页表：64个页面，每个页面256个存储字（256*4B=1KB），共64*256=16K存储字 第三级页表：16K个页面，每个页面256个存储字（256*4B=1KB） ，共16K*256=4M存储字，用于存放虚拟存储器的4M个页面（4M*1K=4GB） 必需加快查表（页表）的速度,3.2.3.1 目录表,基本思想是：压缩页表的存储容量，用一个容量比较小的高速存储器来存放页表，从而加快页表的查表速度 压缩页表的方法：页表只为已经装入到主存储器中的那些页面建立虚页号与实页号之间的关系。页表中的

8、每个存储字=多用户虚页号+主存储实页号+修改位+其他标志 页表采用相联访问的方式（高速小容量存储器，如Cache）：亦称相联目录表，简称目录表 图3.26：目录表（采用按内容访问的相联存储器）,3.2.3.2 快慢表,慢表是一个全表，快表只是慢表的一个部分副本，而且只存放了慢表中很少的一部分 快表和慢表也构成了一个由两级存储器组成的存储系统 快表：TLB（Translation Lookaside Buffer，地址变换后行缓冲器，或地址变换后备缓冲存储器） 快表=多用户虚页号（U，P拼接）+实页号 图3.27：慢表（按地址访问）、快表（按内容相联访问）,3.2.3.3 散列函数,当快表容量较

9、大时，必需采用按地址方式访问 散列查找方法（Hashing方法，哈希方法） Ah=H(Pv) Pv：多用户虚页号 Ah：快表的地址 图3.28：用硬件实现Hashing函数 折叠按位加散列函数 图3.29：Pv等于Pv，表示快表命中；否则，表示发生了Hashing冲突，需要去查慢表,3.2.3.4 虚拟存储器举例,例3.1：IBM370/168计算机的虚拟存储器快表结构及地址变换过程（图3.30） 二项新的措施： （1）、在快表的每一个存储字中存放二对多用户虚页号和主存实页号 （2）、用一个由6个寄存器组成的相联寄存器组，把24位的用户号U压缩成3位的ID 上述措施对应用程序员来说是透明的,例

10、3.2：Intel i486处理机的虚拟存储器的分段与分页机制 图3.31(a)：分段产生线性地址 虚拟地址=段+偏移 232=4GB 图3.31(b)：快表（TLB）操作 四种方式组织存储器系统： （1）、页式虚拟存储器 （2）、段式虚拟存储器 （3）、段页式虚拟存储器 （4）、纯物理寻址的主存储器 图3.31(c)：二级分页方案 目录：210=1024；表：210=1024；偏移：212=4KB,3.2.4 页面替换算法及其实现,什么是页面替换算法？ 当主存中所有页面都已经被占用，或者所有主存空间都已经被占用，而又要从磁盘存储器中调入新页（或新段）的情况。这时，必须从主存储器中淘汰掉一个不

11、常用的页面（或程序段），以便腾出主存空间来存放新调入的页面（或程序段）。 评价一个页面替换算法好坏的标准主要有二个： （1）、命中率要高 （2）、算法要容易实现 提高命中率： （1）、要使这种算法能正确反映程序的局部性 （2）、要能够充分利用主存中页面调度情况的历史信息，或者能够预测主存中将要发生的页面调度情况,页面替换算法所使用的地方： （1）、虚拟存储器中，主存页面（或程序段）的替换 （2）、Cache中的块替换 （3）、虚拟存储器的快慢表中，快表存储字（行）的替换 （4）、虚拟存储器中，用户基地址寄存器的替换 （5）、有些虚拟存储器中，目录表的替换,3.2.4.1 页面替换算法,常用的页

12、面替换算法有： （1）、随机算法（RAND算法，Random Algorithm） 优点：简单、容易实现；缺点：命中率比较低 （2）、先进先出算法（FIFO算法，First-In First-Out Algorithm） 优点：容易实现，利用页面调度情况的历史信息；缺点：没有反映程序的局部性 （3）、近期最少使用算法（LRU算法，Least Recently used Algorithm） 优点：既利用页面调度情况的历史信息，又正确反映程序的局部性；缺点：实现起来非常困难,（4）、最久没有使用算法（LFU算法，Least Frequently Used Algorithm） 特点：将LRU算法

13、的“多”与“少”，简化成判断“有”与“无” （5）、最优替换算法（OPT算法，Optimal Replacement Algorithm） 特点：选择将来最久不被访问的页面作为被替换的页面。是一种理想化的算法，常用来作为评价其他页面替换算法好坏的标准,例3.3：图3.32 RAND算法的命中率比较低；LRU算法实现起来特别困难；FIFO算法和LFU算法是常用的替换算法，其中LFU算法是一种比较好的算法 例3.4：图3.33 “颠簸”（Thrashing）现象。一般来说，当分配给程序的主存页面较小时，有可能发生“颠簸”现象。 命中率不仅与页地址流有关，而且也与分配给程序的主存页面数有关。,3.2

14、.4.2 堆栈型替换算法,什么是堆栈型替换算法？ P167上的定义 堆栈型替换算法的基本思想是：随着分配给主存页面数增加，主存的命中率也提高，至少不下降 LFU、LRU、OPT都属于堆栈型替换算法 FIFO不是堆栈型替换算法（图3.34） 页面失效频率法（PFF：page fault frequency）的动态页面调度方法：根据各道程序在实际运行过程中页面失效率的情况，由操作系统动态调整分配给每道程序的主存页面数。,3.2.4.3 页面替换算法的实现,一般用软件实现 主存页面表：图3.35 主存页面表是面向主存储器的；页表是面向用户程序空间的，每一个用户，或者每一道程序都有一张页表。 主存页面

15、表=（实页号）+占用位+程序号+段页号+使用位（计数器）+程序优先级+历史位Hb（未使用计数器）+其他信息,3.2.5 提高主存命中率的方法,存储系统的等效访问速度： T=H*T1+(1-H)*T2 T1指主存储器的访问周期，包括查页表和段表所需要的时间；T2是指磁盘存储器的访问速度通常很大 影响主存命中率的几个主要因素： （1）、页地址流分布情况（程序本身决定，无能为力） （2）、页面替换算法（常采用LFU算法） （3）、页面大小（3.2.5.1） （4）、主存储器的容量（ 3.2.5.2） （5）、页面调度方法（ 3.2.5.3）,3.2.5.1、页面大小的选择,图3.36： H=f（Sp

16、，S） H：命中率 Sp：页面大小 S：主存容量 为什么当Sp较小时， H随Sp增大而提高；当Sp较大时， H随Sp增大反而降低？ （P170） 页面大小Sp必须选择适中,3.2.5.2 主存容量,图3.37：主存容量S与命中率H的关系 当S增加到某一值之后，H几乎不再提高,3.2.5.3 页面调度方式,分页式页面调度方式：在程序装入主存储器之前就对程序进行链接装配，并且要在把整个程序都调入到主存储器中之后才能开始运行。 命中率=100% 请求页式页面调度方式：只在发生页面失效时，才把要访问的页面进行链接装配，并调入到主存储器中。 在程序刚开始运行时，页面失效很频繁，主存命中率很低。 预取式页

17、面调度方式：在程序被挂起之后又重新开始运行之前，先把上次停止运行前一段时间内用到的页面先调入到主存储器，然后才开始运行程序（3.3.4.3）,3.3 高速缓冲存储器（Cache）,处理机需要主存储器的速度： (1/200MHz1/500MHz)/6=0.83ns0.33ns 主存储器实际的速度=100ns200ns 通用寄存器组；指令和数据的先行缓冲存储器 一级Cache；两级 Cache（第一级在CPU内部）；三级Cache（第一级、第二级在CPU内部） 表3.4：Cache与虚拟存储器的主要区别,3.3.1 基本工作原理,图3.38：Cache工作原理 主存地址=块号B+块内地址W Cac

18、he地址=块号b+块内地址w 主存-Cache地址变换部件完成B变换成b 变换成功，称为Cache命中 变换不成功，产生Cache失效信息 将被访问字在内的一整块都从主存储器中读出来（利用程序的局部性特点，提高Cache的命中率）,3.3.2 地址映象与变换算法,什么是Cache的地址映象？ 什么是Cache的地址变换？ 以“块”为单位进行调度 需要考虑的因素： （1）、地址变换的硬件是否容易实现？ （2）、地址变换的速度是否快？ （3）、主存空间的利用率是否高？ （4）、发生块冲突的概率如何？,3.3.2.1 全相联映象及其变换,全相联映象方式是指主存中的任意一块可以映象到Cache中的任意

19、一块的位置上。 图3.39：全相联映象方式 Cb = Mb 图3.40：全相联映象方式的地址变换 主存地址=块号B+块内地址W Cache地址=块号b+块内地址w 目录表=主存块号B+Cache块号b+有效位,Cache命中 Cache没有命中（ Cache失效） 全相联映象方式的优点：块的冲突率最小，Cache的利用率也最高 全相联映象方式的缺点：需要一个相联访问速度快、容量为Cb的相联存储器，其代价很高；相联比较所花费的时间将影响Cache的访问速度,3.3.2.2 直接映象及其变换,直接映象方式：主存中一块只能映象到Cache的一个特定的块中。 b=B mod Cb B：主存的块号 b：

20、Cache的块号 Cb：Cache的块容量（个数） 图3.41：直接相联映象方式 Mb=Cb*Me Mb：主存的块容量（个数） Cb：Cache的块容量（个数） Me：主存的区容量（个数）,图3.42：直接相联地址变换 主存地址=区号E+块号B+块内地址W Cache地址=块号b+块内地址w 区表存储器=区号E（按地址访问）+有效位 四种情况： （1）、区号比较结果相等、有效位为“1”： Cache命中 （2）、区号比较结果相等、有效位为“0”： Cache没有命中；Cache中的这一块已经作废 （3）、区号比较结果不相等、有效位为“0”： Cache没有命中；Cache的这一块是空的 （4）

21、、区号比较结果不相等、有效位为“1”： Cache没有命中；原来在Cache中存放的那一块是有用的,图3.43：将区号存储器与Cache合并成一个存储器 直接相联映象方式的优点：硬件实现很简单，不需要采用相联访问的存储器，访问速度也比较快 直接相联映象方式的缺点：块的冲突率比较高。,3.3.2.3 组相联映象及其变换,介于全相联和直接相联之间的一种折中方案 图3.44：组相联映象方式 Cache： Cb=Cg*Gb Cb：Cache总的块容量（个数） Cg：Cache的组容量（个数） Gb：Cache每一组的块容量（个数） 主存储器： Mb=Gb*Cg*Me Mb：主存储器总的块容量（个数）

22、Gb：Cache每一组的块容量（个数） Cg：Cache的组容量（个数） Me：主存储器的区容量（个数）,图3.45：组相联映象方式的地址变换 主存地址=区号E+组号G+组内块号B+块内地址W Cache地址=组号g+组内块号b+块内地址w 快表存储器=（区号E，组内块号B）+组内块号b （采用按地址访问和按相联访问两种方式） 图3.46：采用多个相等比较器代替相联访问，以加快查表的速度 当一个块内的字数不多时，可以把块表与Cache合并成一个存储器。即用Cache中的数据字代替块表中的块号b字段（参见P178的图3.43）,组相联映象方式与直接映象方式相比：Cache中块的利用率能够大幅度提

23、高，Cache块的失效率能够明显降低，块的冲突概率大大降低。但是，实现的难度和造价要高。 组相联映象方式与全相联映象方式相比：实现起来容易，Cache的命中率与全相联映象方式很接近。 当Gb=1（Cache每一组的块容量（个数）时，就成了直接映象方式 当Cg=1（Cache的组容量（个数）时，就成了全相联映象方式,可以通过选择Gb和Cg，来优化Cache的性能（包括块冲突率、块的失效率、查表的速度、实现的复杂性和成本等） Gb越大，块的冲突概率和Cache的失效率就越低，但查表的速度就越慢，实现的成本也就高 表3.5：典型机器的Cache分组情况 （Cb=Cg*Gb）,3.3.2.4 位选择组

24、相联映象及其变换,图3.47：位选择组相联映象方式 （主存不再分组） Cache：Cb=Cg*Gb Cb：Cache总的块容量 Cg：Cache的组容量 Gb：Cache每个组的块容量 主存储器：Mb=Cg*Me Mb：主存总的块容量 Cg：主存每个区的块容量 Me：主存的区容量,主存中的块与Cache中的组之间是直接映象关系；而主存中的块与Cache中组内部的各个块之间是全相联映象方式 在组相联映象方式中，主存中的一个组与Cache中的一个组之间是多个块到多个块的映象 在位选择组相联映象方式中，主存中的一个块到Cache中一个组之间是一个块到多个块的映象,图3.48：位选择组相联地址变换的一

25、种实现方式 主存地址=区号E+区内块号B+块内地址W Cache地址=组号g+组内块号b+块内地址w 块表=（区号E+块号b+有效位e）+（区号E+块号b+有效位e） （共Gb个）,3.3.2.5 段相联映象及其变换,段相联映象方式：组内采用直接映象方式，而组间改用全相联映象方式 是组相联映象方式的一种变形，也是介于全相联和直接相联二种映象方式之间的一种折中方案,图3.49：段相联映象方式 Cache：Cb=Sb*Cs Cb：Cache总的块容量 Cs：Cache的段容量 Sb：Cache每个段的块容量 主存储器：Mb=Sb*Ms Mb：主存总的块容量 Ms：主存的段容量 Sb：主存每个段的块

26、容量,图3.50：段相联地址变换方式 主存地址=段号S+段内块号B+块内地址W Cache地址=段号s+段内块号b+块内地址w 段表=主存段号S+Cache段号s+有效位,段相联映象方式的优点： 段表比较简单，实现的成本相对比较低 块的冲突概率和Cache的失效率与Cache的段容量Cs有关 段相联映象方式的缺点： 当发生段失效，要把本段内各个块原来已经与主存建立起来的许多映象关系全部撤消 例子：256KB的Cache：8个段、每段2048块、每块16B（8*2048*16B=256KB）,3.3.3 Cache替换算法及其实现,什么是Cache替换算法？ 直接映象方式：不需要替换算法 全相联

27、映象方式：替换算法最复杂 组相联映象方式/位选择组相联映象方式： 需要从Cache同一组内的几个块中选择一块替换出去 虚拟存储器：采用全相联映象方式，替换算法用软件实现 Cache：替换算法用硬件实现 常用的Cache替换：随机法、轮换法、LFU算法、比较对法、堆栈法,3.3.3.1 轮换法及其实现,用于组相联映象方式 两种实现方法： （1）、每块一个计数器 （2）、每组一个计数器,1、每块一个计数器,在块表中，增加设置一个替换计数器字段，计数器字段的长度与Cache地址中的组内块号字段的长度相同 替换规则： （1）、被装入或被替换的块，它所属的计数器清为“0”，同组的其他块所属的计数器都加“

28、1” （2）、需要替换时，在同组中选择计数器的值最大的块作为被替换的块 例子：Solar-16/65，位选择组相联映象方式，每组的块容量=4，2位计数器（表3.6）,2、每组一个计数器,只为每个组设置一个计数器 替换规则： 本组有替换时，计数器加“1”，计数器的值就是要被替换出去的块号,轮换法的优点：实现比较简单，能够利用历史上的块地址流情况，把最先装入的块作为被替换的块 轮换法的缺点：也没有能够利用程序的局部性特点,3.3.3.2 LFU算法及其实现,LFU算法既利用了历史上Cache中块地址流的调度情况，又正确反映了程序的局部性特点 在块表中为每一块设置一个计数器,替换规则： （1）、被装

29、入或被替换的块，它所属的计数器清为“0”，同组的其他块所属的计数器都加“1” （2）、命中的块，其对应的计数器清为“0”，同组中其他所有计数器中，凡是计数器的值小于命中块所属计数器原来值，都加“1”，其他计数器不变 （3）、需要替换时，在同组的所有计数器中选择计数器最大（一般为全1）的计数器，它所对应的块就是要被替换的块 例子：IBM370/165，每组=4块，计数器=2位（表3.7） LFU算法的命中率比较高， LFU算法是一种堆栈型算法,3.3.3.3 比较对法,也是一种LFU算法，它不用计数器来实现，而采用硬联逻辑实现 LFU算法：将同一组内的各个块按照被访问过的时间顺序排序，从而找出最

30、久没有被访问过的块 TAB ：B块比A块更久没有被访问过 ：A块比B块更久没有被访问过,C块最久没有被访问过：A、B、C；B、A、C 图 3.51：每组3个块的比较对法 表3.8：每组块容量与所需触发器、与门及与门输入端个数的关系,当每组块容量很多时，要采用分级的办法来实现 例子：IBM 3033 ，每组=16块，分3级，第1级=4、第2级=2、第3级=2 共需6+1*4+1*2*4=18个触发器（120个触发器） 例子：IBM 370/168 ，每组=8块，分2级，第1级=4、第2级=2 共需6+1*4=10个触发器（28个触发器） 比较对法的优点：块失效率比较低，工作速度比较高 比较对法的

31、缺点：硬件实现相对比较复杂,3.3.3.4 堆栈法,用栈顶至栈底的先后次序来记录Cache同一组内的各个块被访问的先后次序。栈顶是最近被访问过的块，栈底是最久没有被访问过的块。 （图3.52） 堆栈法的管理规则： （1）、把本次访问的块号与堆栈中保存的所有块号进行相联比较。如果发现有相等的，则Cache命中； （2）、如果相联比较没有发现相等的，则Cache块失效。,图3.53：用硬件实现堆栈法的逻辑图 Cache采用组相联映象方式，每组块容量=4 堆栈法的优点：一是失效率低，采用的是LRU算法；二是硬件实现相对比较简单。 堆栈法的缺点：速度比较低，因为它需要进行相联比较 堆栈法所用触发器的个

32、数=Gb*log2Gb,对于Cache的替换算法，主要解决好以下三个问题： （1）、记录每次访问Cache的块号 （2）、管理好所记录的Cache块号 （3）、根据记录和管理的结果，采用时序逻辑判断哪个块号是将要被替换出去的块号,3.3.4 Cache的性能分析,Cache的加速比 Cache系统的一致性问题,3.3.4.1 Cache系统的加速比,T=HTc+(1-H)Tm 加速比SP=Tm/T=f（H，Tm/Tc） 图3.54：加速比SP与命中率H的关系 SP的最大值为Tm/Tc 影响Cache命中率H的几个主要因素： （1）、程序在执行过程中的地址流分布情况 （2）、Cache的替换算法

33、 （3）、Cache的容量 （4）、块的大小，分组的数目 （5）、Cache的预取算法（3.3.4.3）,1、Cache命中率与容量的关系,图3.55： Cache命中率H与容量S的关系 H=1-S-0.5,2、Cache命中率与块大小的关系,图3.56： Cache命中率与块大小的关系 当块大小非常大时，进入Cache中的许多数据可能根本用不上。而且，随着块大小的增加，程序时间局限性的作用就会逐渐减弱。最后，当块大小等于整个Cache的容量时，命中率将趋近于零,3、Cache命中率与组数的关系,随着组数的增加，Cache的命中率要降低。 当分组的数目增加时，主存中的某一块可以映象到Cache中的块数就将减少，从而导致命中率的下降,3.3.4.2 Cache的一致性问题,造成Cache与主存的不一致问题的原因：