第2章存储系统

1、体系结构概念体系结构概念弗林分类法弗林分类法计算机层次结构计算机层次结构CPU 性能及计算性能及计算计算机系统结构设计及发展计算机系统结构设计及发展作业 P23 1.12 1.14冯冯 诺依曼机的改进：诺依曼机的改进：运算器为中心运算器为中心存储器为中心存储器为中心目的：目的：存放计算机系统中所需要处理的程序与数据存放计算机系统中所需要处理的程序与数据 。主存储器：主存储器：用以存放正在运行的程序与数据用以存放正在运行的程序与数据 。辅助存储器：辅助存储器：存放等待运行的程序与数据。存放等待运行的程序与数据。通用寄存器组：通用寄存器组：是存放那些最经常用到的数据。是存放那些最经常用到的数据。存

2、储系统：存储系统：两个或两个以上的速度、容量、价格不同的存两个或两个以上的速度、容量、价格不同的存储器采用硬件，软件或软、硬件结合的办法联接成一个系储器采用硬件，软件或软、硬件结合的办法联接成一个系统。统。v存储层次的概念和性能参数（命中率、平均访存储层次的概念和性能参数（命中率、平均访问时间、加速比）问时间、加速比） v存储层次的三个特性（局部性、一致性、包含存储层次的三个特性（局部性、一致性、包含性）性）vCACHE引入目的、与虚拟存储器比较的特点及引入目的、与虚拟存储器比较的特点及需要解决的问题。需要解决的问题。vCACHE-主存地址映象变换概念？几种主要方主存地址映象变换概念？几种主要

3、方式（全相联、直接、组相联）式（全相联、直接、组相联）v几种替换算法分类；简述几种替换算法分类；简述LRU替换算法替换算法vCACHE的写方法，的写方法，CACHE的性能分析讨论的性能分析讨论v存储保护几种方法存储保护几种方法作业：作业：P2-69 2.14 （1）（）（2）（）（3）（）（4）（）（6）（）（7）（）（8） P2-70 2.16 ( 1 ) ( 2 ) 以存储器为中心的计算机结构以存储器为中心的计算机结构 主主 存存 缓缓指指 存存令令 器器 缓缓读存读存 器器 缓缓写存写存 器器 I/O 部部 件件 I/O 部部 件件CPUv 存储容量存储容量S S：以字节数表示，单位为B

4、、KB、MB、GB、TB等。v 存储器速度存储器速度T T：存储器访问周期，与命中率有关。v 存储器价格存储器价格C C：表示单位容量的平均价值单位为C/bit或C/KB。计算机存储系统三个基本参数：计算机存储系统三个基本参数： 第一层第二层第三层第四层第五层存储系统的层次结构存储系统的层次结构速速 度度 提提 高高容容 量量 增增 加加 通用寄存器通用寄存器M1高速缓冲存储器高速缓冲存储器M2 主存储器主存储器M3 脱机大容量存储器脱机大容量存储器M5 辅助存储器辅助存储器M4 每级存储器的性能参数可以表示为每级存储器的性能参数可以表示为TiTi，SiSi，CiCi。存储系统的性能可表示为：

5、存储系统的性能可表示为：TiTi+1TiTi+1；SiSi+1SiCi+1CiCi+1。: baAB :BAM4M3M2段段 C段段 Dabv多个存储器并行工作，并用并行访问和交叉访多个存储器并行工作，并用并行访问和交叉访问等方法；问等方法；v设置各种缓冲存储器；设置各种缓冲存储器；v采用采用Cache存储系统。存储系统。频带宽度：单位时间内所能访问的数据量。频带宽度：单位时间内所能访问的数据量。解决频带平衡的三种方法：解决频带平衡的三种方法：并行主存系统：一个主存周期内能读写多个字的主存系统。并行主存系统：一个主存周期内能读写多个字的主存系统。数据寄存器数据寄存器数据总线数据总线地址总线地址

6、总线地址寄存器地址寄存器体号 WW1W2W3W4 m1 m2 m3 m4ba体内地址优点：优点：简单、容易。简单、容易。缺点：缺点：访问的冲突大。访问的冲突大。主要冲突：主要冲突：取指令冲突（条件转移时）取指令冲突（条件转移时）读操作数冲突（需要的多个操作数不一定都存放在读操作数冲突（需要的多个操作数不一定都存放在同一个存储字中）同一个存储字中）写数据冲突（必须凑齐写数据冲突（必须凑齐n个数才一起写入存储器）个数才一起写入存储器）读写冲突（要读出的一个字和要写入的一个字处在读写冲突（要读出的一个字和要写入的一个字处在同一个存储字内时，无法在一个存储周期内完成）。同一个存储字内时，无法在一个存储

7、周期内完成）。 模模M主存储器：主存储器：分为分为M个存储体的主存储器。个存储体的主存储器。同时访问：同时访问：采取同时启动，完全并行工作的方式；采取同时启动，完全并行工作的方式；交叉访问：交叉访问：分时启动，互相错开一个存储体存储周期的分时启动，互相错开一个存储体存储周期的1/M，交叉进行工作。，交叉进行工作。四个存储体交叉访问的时间关系四个存储体交叉访问的时间关系m=4 分时启动时间图分时启动时间图主存周期主存周期主存周期主存周期启动启动0体体启动启动1体体启动启动2体体启动启动3体体低位部分：体内地址低位部分：体内地址 b=log2n高位部分：存储体体号高位部分：存储体体号 a=log2

8、mm: 体数体数n：每个体的容量：每个体的容量数据总线地址总线 WMDR0 0 1 2 3 n-1MDR1 n n+1 n+2 n+3 2n-1MAR0MAR3MDRm-1n(m-1)n(m-1)+1n(m-1)+2n(m-1)+3 n(m-1)MARm-1译码译码 a b低位交叉存储器结构低位交叉存储器结构 低位部分：存储体体号低位部分：存储体体号 b=log2m高位部分：体内地址高位部分：体内地址 a=log2n W MDR0 0 m 2m 3m (n-1)m MDR1 1 m+1 2m+1 3m+1 (n-1)m+1MAR0MAR3 MDRm-1 m-1 2m-1 3m-1 4m-1 n

9、m-1 MARm-1译码译码 a b数据总线地址总线分时访问例如，例如，n=8 m=4多体并行低位交叉编址多体并行低位交叉编址 012345678910111213141516171819202122232425262728293031 b a09182712510304个体并行2个体并行 CPU与Cache主存的关系 CPUMMUCache MSD或或 ID或或 I存储器管理部件存储器管理部件 缓存地址缓存地址主存Cache 块号块号块内地址块内地址 MS-Cache地址变换地址变换 块号块号块内地址块内地址 Cache替换替换部件部件 ： ： ： ： ： ：主存地址主存地址替换块替换块装入

10、块装入块不命中不命中数据或指令数据或指令是指某一数据在主存中的地址与在缓存中的地址两者之间的关系。 ： B：每块大小：每块大小C：Cache容量容量M：主存容量：主存容量 块块0 块块1 ： 块块i：块块M/B-1 块块0 块块1 ：块块C/B-1Cache主存储器主存储器优点：命中率较高，Cache的存储空间利用率高；缺点：线路复杂，成本高，速度低。 块号 块内地址主存地址 块号 块内地址Cache地址 Bi bi 1 主存块号B Cache块号b 有效位 假设在某个计算机系统中Cache容量为32K字节，数据块大小是16个字节，主存容量是1M，地址映象为全相联方式。（1）主存地址多少位？如

11、何分配？（2）Cache地址多少位？如何分配？（3）目录表的格式和容量？ b=A mod C/B其中b： Cache的块号A：主存的块号C/B：Cache的块数主存储器主存储器 块块0 块块1 : : 块块C/B-1C/B-1 块块C/BC/B 块块C/B+1C/B+1 : :块块2C/B-1 : : 块块M/B-C/BM/B-C/B 块块M/B-C/B+1M/B-C/B+1 : : 块块M/B-1M/B-1区区0区区1区区M/C-1 块块0 块块1 : : 块块C/B-1cache优点：简单；缺点：命中率低。优点：简单；缺点：命中率低。目录表存储器目录表存储器块失效块失效相等比较相等比较区号

12、区号Ei 块号块号i 块内地址块内地址块号块号i 块内地址块内地址 主存地址主存地址Cache地址地址相等相等 Ei 1 区号（按地址访问）区号（按地址访问） 有效位有效位访问访问Cache 假设在某个计算机系统中Cache容量为64K字节，数据块大小是16个字节，主存容量是4M，地址映象为直接相联方式。（1）主存地址多少位？如何分配？（2）Cache地址多少位？如何分配？（3）目录表的格式和容量？主存地址格式：主存地址格式： 区号区号区内块号区内块号块内地址块内地址21 16 15 4 3 0 缓存地址格式：缓存地址格式： 块块 号号块内地址块内地址15 4 3 0 目录表的格式：目录表的格

13、式： 主存区号主存区号有效位有效位6 1 0 解：解： 容量：应与缓存块数量相同即容量：应与缓存块数量相同即212=4096 思考题：思考题： 当组相联映象的组内块数大到等于当组相联映象的组内块数大到等于Cache时，就变成什时，就变成什么映象？而当块数小到只有一块时就变成了什么映象？么映象？而当块数小到只有一块时就变成了什么映象？区区0区区Me1组组1组组0组组C/B1 块块0 块块B1 块块B 块块2B1 Cache块块0块块B1 块块B 块块2B1组组1组组C/B1组组0组组C/B(Me1)组组C/BMeC/B+1组组C/BMe1优点：速度快，命中率高；优点：速度快，命中率高；相等相等不

14、等不等Cache地址地址区号区号 组号组号 组内块号组内块号 块内地址块内地址主存地址主存地址 组号组号 组内块号组内块号 块内地址块内地址相联比较相联比较区号区号E 组内块号组内块号 组内块号组内块号 EiBi bi块表块表请写出：请写出： （1）主存与）主存与Cache的格式；的格式； （2）相关存储器的格式与容量）相关存储器的格式与容量解：解：主存地址：主存地址： 区号区号组号组号块号块号块内地址块内地址19 15 14 8 7 6 5 0 缓存地址：缓存地址： 组号组号块号块号块内地址块内地址14 8 7 6 5 0 区号区号Ei块号块号Bi缓存块号缓存块号bi装入位装入位9 5 4

15、3 2 1 0 相关存储器的格式：相关存储器的格式：相关存储器的容量，应与缓存的块数相同，即相关存储器的容量，应与缓存的块数相同，即: 组数组数组内块数组内块数=1284=512 随机法：随机法：(Random,RAND法法) 先进先出法先进先出法(First-In First-Out,FIFO法法) 近期最少使用法近期最少使用法(Least Recently Used,LRU法法)最久没有使用法（最久没有使用法（Least Frequently Used,LFU） 设有一道程序，有设有一道程序，有1至至5共五页，执行时的页地址流共五页，执行时的页地址流（即执行时依次用到的程序页页号）为：（即

16、执行时依次用到的程序页页号）为： 2，3，2，1，5，2，4，5，3，2，5，2若分配给该道程序的主存有若分配给该道程序的主存有3页，分别采用页，分别采用FIFO和和LRU替替换算法表示这换算法表示这3页的使用和替换过程。页的使用和替换过程。说明：说明： （1）随机算法：用随机数确定要替换的块；）随机算法：用随机数确定要替换的块； （2）FIFO算法：替换最早装入主存的页；算法：替换最早装入主存的页； （3）LRU算法：依据各块使用的情况，选择最近最少使算法：依据各块使用的情况，选择最近最少使用的块替换。用的块替换。时间时间t 1 2 3 4 5 6 7 8 9 10 11 12页地址流页地址

17、流 2 3 2 1 5 2 4 5 3 2 5 2先进先出先进先出 FIFO调调进进调调进进调调进进命命中中替替换换替替换换替替换换替替换换命命中中命命中中替替换换替替换换2232322*313*1551*25*24245*2*43342*34*53*52命命中中命命中中命命中中命中命中3次次近期最少近期最少使用使用LRU2调调进进23调调进进232命命中中23*1调调进进2*15替替换换51*2命命中中25*4替替换换2*45命命中中54*3替替换换35*2替替换换3*25命命中中523*命命中中命命中中命命中中命命中中命命中中命命中中命中命中5次次2v LRU也不是理想的方法，它仅仅是根据

18、过去访存的频率也不是理想的方法，它仅仅是根据过去访存的频率估计未来的访存情况，因而只是推测的方法；估计未来的访存情况，因而只是推测的方法；v 块命中率与地址流、块的大小和块的数量有关，应具体问块命中率与地址流、块的大小和块的数量有关，应具体问题具体分析，选择适当的算法；题具体分析，选择适当的算法； v 存储单元替换时应注意防止出现颠簸现象，即调入一块时存储单元替换时应注意防止出现颠簸现象，即调入一块时将另一块调出，紧接着又需要访问刚刚调出块的数据，而将将另一块调出，紧接着又需要访问刚刚调出块的数据，而将该块调入时又将上一块调出，即颠簸。该块调入时又将上一块调出，即颠簸。 对于一个容量为对于一个

19、容量为3个块的全相联个块的全相联Cache，假定访问的，假定访问的地址块号序列为地址块号序列为 1，2，3，4，1，2，3，4，分别用，分别用FIFO算法和算法和LRU算法，写出其队列变化情况，并得出结算法，写出其队列变化情况，并得出结论。论。练习练习2 对于一个全相联对于一个全相联Cache，假定访问的地址块号序列，假定访问的地址块号序列为为 1，2，3，4，1，2，5，1，2，3，4，5，在先进，在先进先出替换方式下，分别写出分配给程序的主存页面是先出替换方式下，分别写出分配给程序的主存页面是3页页和和4页的情况下，其队列的变化情况，并得出结论。页的情况下，其队列的变化情况，并得出结论。结

20、论：产生颠簸现象，说明命中率结论：产生颠簸现象，说明命中率与页地址流有关。与页地址流有关。结论：结论：FIFO算法不是堆栈型算法，主存算法不是堆栈型算法，主存页数增加，命中率反而下降。页数增加，命中率反而下降。计数器方法计数器方法主存访问主存访问块地址块地址 块块4 块块2 块块3 块块5 块号块号计数计数器器块块号号计数计数器器块块号号计数计数器器块块号号计数计数器器Cache块块0110111111500Cache块块1301310300301Cache块块2400401410411Cache块块3空空200201210操作操作 起始状态起始状态 调入调入命中命中替换替换比较对法比较对法

21、缓存操作缓存操作初始状态初始状态调入调入2命中块命中块4替换块替换块1寄存器寄存器03245寄存器寄存器14324寄存器寄存器21432寄存器寄存器3空空1134231T12T24T34T13T14T23v Cache存储器的地址变换和块替换算法全由硬存储器的地址变换和块替换算法全由硬件实现；件实现；一、一、Cache透明性分析透明性分析vCache-主存存储层次对应用程序员和系统程序主存存储层次对应用程序员和系统程序员都是透明的；员都是透明的；vCache对处理机和主存之间的信息交往是对处理机和主存之间的信息交往是透明的。透明的。1. Cache的容量对命中率的影响 2.Cache块的大小对

22、命中率的影响3.地址映象方式对命中率的影响 命中率H命中率H容量S1块大小初始最佳Cache命中率命中率H与容量与容量S的关系的关系Cache命中率命中率H与块大小的关系与块大小的关系 mcccTHTHT)1 ( )1 (1)1 (cmccmcccmmpHTTHTHTHTTTS cmpTTSTc ：Cache的访问周期；的访问周期；Tm：主存储器的访问周期；：主存储器的访问周期；Hc：Cache的命中率的命中率 cmcccTTHHTTe)1 (1Sp的期望值的期望值Spmax=Tm/TcSp102468命中率H 不直接将数据写入主存，直接将数据写入主存，不调入缓存不调入缓存数据写入主存，并将该

23、数据写入主存，并将该数据调入数据调入 Cache一、一、Cache的分体的分体 多体存储器：多体存储器：分为数据体分为数据体Cache与指令体与指令体Cache。原因：原因：q 数据与指令不在一体可以减少多个访问源访问存储数据与指令不在一体可以减少多个访问源访问存储器的冲突器的冲突 ；q 两个体的访问操作不完全相同，数据体有读操作和写两个体的访问操作不完全相同，数据体有读操作和写操作，而指令体只有读操作。因此在替换时，只有数据操作，而指令体只有读操作。因此在替换时，只有数据体有写回的问题。在体有写回的问题。在Cache容量相等的情况下，指令与容量相等的情况下，指令与数据分体的数据分体的Cach

24、e比一体化的比一体化的Cache命中率要高。命中率要高。 112 11420微缓存地址微缓存地址 组号组号 双字双字 字节字节5组内块号组内块号 数据数据 数据数据 数据数据0101位位 标记标记 M 标记标记 E 标记标记 S组号组号 0 1127 标记标记 I 标记标记 S 标记标记 E 数据数据 数据数据 数据数据目录目录1路路120位位 2位位32字节字节32字节字节路路020位位 2位位目录目录0主存地址：主存地址：虚空间：虚空间：程序所能利用的空间。程序所能利用的空间。实地址：实地址：主存物理空间的编址；主存物理空间的编址；虚地址：虚地址：编程序时程序员所用的地址，在编译程序中由处

25、编程序时程序员所用的地址，在编译程序中由处理机生成。理机生成。CPU存储存储管理管理主主存存 辅辅 存存I或或DI或或DVAPA外存地址外存地址虚拟存储器中虚拟存储器中CPU、MS、辅存间关系、辅存间关系 1.1.段式管理段式管理 2.2.页式管理页式管理 3.3.段页式管理段页式管理 Cache虚拟存储器虚拟存储器提高了主存储提高了主存储器的速度器的速度 扩大了主存储扩大了主存储器的容量器的容量 硬件硬件 以软件为主以软件为主 透明透明 不透明不透明 简单简单 复杂、速度慢复杂、速度慢 地址映象：地址映象：将虚存空间分段，主存的空间按这种段来分将虚存空间分段，主存的空间按这种段来分配和管理配

26、和管理 。段：段：按程序的逻辑功能来划分，一个用户的程序按程序的逻辑功能来划分，一个用户的程序(或一个进或一个进程程)可以包含多个功能不同的程序段可以包含多个功能不同的程序段 地址转换：地址转换：主存地址格式：主存地址格式：段号段号段内地址段内地址虚存地址格式：虚存地址格式：用户号用户号段号段号段地址段地址程序模块化的性能好，各段在功能上是相互独程序模块化的性能好，各段在功能上是相互独立的；立的； 便于程序与数据的共享；便于程序与数据的共享； 程序的动态链接比较容易；程序的动态链接比较容易； 便于实现存储保护。便于实现存储保护。地址变换所需的时间比较长。地址变换所需的时间比较长。 主存的空间利

27、用不充分。主存的空间利用不充分。对辅存对辅存(磁盘磁盘)的管理比较困难。的管理比较困难。段式管理的主要缺点：段式管理的主要缺点： 页：页：将主存空间与虚存空间按固定的大小划分成块，每块称为一页。虚页：虚页：虚存中的页；虚存中的页；实页：实页：实存中的页。实存中的页。虚页与实页之间按全相联方式映象。虚页与实页之间按全相联方式映象。虚存地址格式：虚存地址格式： 虚页号虚页号页内地址页内地址主存地址格式：主存地址格式： 实页号实页号页内地址页内地址主存储器的空间利用率比较高。主存储器的空间利用率比较高。页表的管理比较简单，可以不考虑程序的长短，按固页表的管理比较简单，可以不考虑程序的长短，按固定块长

28、分配，管理，调度。定块长分配，管理，调度。 地址映象与地址转换速度比较快。地址映象与地址转换速度比较快。 按页的管理方式，与对辅存的地址格式是一致的，因按页的管理方式，与对辅存的地址格式是一致的，因而管理起来比较容易。而管理起来比较容易。 缺点：缺点：占用很大的存储空间。占用很大的存储空间。 程序的模块化性能不好。程序的模块化性能不好。虚存地址格式：虚存地址格式： 用户号用户号段号段号段内虚页号段内虚页号页内地址页内地址主存地址格式主存地址格式 ：实页号实页号页内地址页内地址地址转换：地址转换：需要三层表，记录相关信息，包括段表基地址表、段表、页段表基地址表、段表、页表。表。快表快表TLB(translation lookaside buffer)：采用一个小容量的、高采用一个小容量的、高速的相关存储部件，用来存放当前最经常用到的那一部分页表，速的相关存储部件，用来存放当前最经常用到的那一部分页表，采取按内容相联方式进行访问。采取按内容相联方式进行访问。 快表的内容包括两部分即虚地址与实地址的对应关系。快表的内容包括两部分即虚地址与实地址的对应关系。 优点：优点：速度快。速度快。缺点：缺点：随着主存容量的增加，目录表的容