计算机系统结构第四章

1、第四章 存储体系概 述本章着重讲述存贮体系的基本概念并行主存系统的组成虚拟存贮器的原理Cache存贮器的原理虚实地址的映象和变换替换算法影响性能的因素分析及软硬件功能分配中的某些问题本章的基本要求并行主存系统的基本要求：领会发展存贮体系的必要性及存贮体系的两个分支。了解并行主存系统的各种组织形式。掌握并行主存系统的极限频宽和实际频宽的关系与计算。领会并行主存局限性以及发展存贮体系的必要性。了解有关存贮体系的性能参数及相关结论。4本章的基本要求虚拟存储器的基本要求：理解虚拟存贮器的工作原理；掌握页式虚拟存贮器的虚、实地址字段对应关系和地址映象规则。熟练掌握在页式虚拟存贮器中，页面装入和替换的过程

2、，并能计算出页面命中率。理解堆栈型替换算法的定义。领会在虚拟存贮器中对页面失效的处理及内部地址映象表中的快慢表机构。 5本章的基本要求高速缓存存储器的基本要求：了解Cache存贮器的组成、工作原理。掌握Cache存贮器中的组相联地址映象规则，相应的映象表机构和虚、实地址变换过程。给出主存的块地址流后，采用组相联或直接映象、LRU或FIFO替换算法时，能 熟练画出各主存块装入Cache和其被替换的过程示意图，并计算出Cache块的命中率。6一、存贮体系的概念与并行主存系统1 存贮系统的基本要求 对存贮系统的基本要求是：大容量、高速度、低价格。 存储器容量SM=WLm 存储器速度可以用存储周期TM

3、和频宽Bm来描述。 TM是存贮器连续访问时所需要的间隔时间； Bm是指存贮器连续访问时能提供的数据传送速率： Bm=Wm/ TM7一、存贮体系的概念与并行主存系统2 发展存储体系的必要性 存在的问题： 1） 容量增大，速度会下降，价格会升高； 2）速度升高，价格也会升高。 解决问题的思路： 1）改进工艺、提高技术、降低成本； 2）配置多种性能价格不同的存贮器组成系统，使所有信息以各种方式分布于不同的存储器上。8一、存贮体系的概念与并行主存系统单体单字单体多字多体单字9一、存贮体系的概念与并行主存系统单体单字单体多字多体单字10一、存贮体系的概念与并行主存系统单体单字单体多字多体单字BM=W/T

4、M11一、存贮体系的概念与并行主存系统单体单字单体多字多体单字BM=W/TM12一、存贮体系的概念与并行主存系统单体单字单体多字多体单字BM=W/TMBM=4W/TM一、存贮体系的概念与并行主存系统单体单字单体多字多体单字BM=W/TMBM=4W/TM一、存贮体系的概念与并行主存系统单体单字单体多字多体单字BM=W/TMBM=4W/TMBM=4W/TM一、存贮体系的概念与并行主存系统单体多字存储器主要缺点：（访问冲突大）1）取指冲突；2）读操作数冲突；3）写数据冲突；4）读写冲突；单体多字一、存贮体系的概念与并行主存系统单体多字存储器与多体单字存储器的区别：1）前者并行读出的数据其地址必须是连

5、续的且在同一单元内；2）后者并行读出的数据可以分属不同的分体，地址无需连续，因为每个存储体均有自己的地址译码、读写驱动等外围电路。一、存贮体系的概念与并行主存系统一、存贮体系的概念与并行主存系统4 并行主存系统的局限性主要缺点：分体冲突；5 存储体系的形成与分支 所谓存贮体系指的是构成存贮系统的n种不同的存贮器(M1Mn)之间，配上辅助软硬件或辅助硬件，使之从应用程序员来看，他们在逻辑上是一个整体。让存贮层次的等效访问速度接近于最高层M1的，容量是最低层 Mn 的，每位价格是接近于 Mn 的。典型的两级存贮体系是虚拟存贮器和Cache存贮器。一、存贮体系的概念与并行主存系统 虚拟存贮器是从主存

6、容量满足不了要求提出来的。在主存和辅存之间，增加辅助的软硬件，让它们构成一个整体。从CPU看，速度接近于主存的，容量是辅存的，每位价格接近于辅存的。主存辅存一、存贮体系的概念与并行主存系统Cache存贮器是从主存速度满足不了要求提出来的。在物理Cache和主存之间，加设辅助硬件，让它们构成一个整体。从CPU看，速度接近于物理Cache的，容量是主存的，每位价格接近于主存的。Cache主存一、存贮体系的概念与并行主存系统6 存储体系的性能参数C=（C1SM1+C2SM2）/（SM1+SM2）T=HT1+（1-H）T2 在设计存贮体系时，需要在选择高命中率的算法、层次化相邻两级存贮器之间的容量差和

7、速度差，以及所增设的辅助软硬件价格等多个因素之间进行综合权衡。C1、SM1、T1C2、SM2、T2C、SM、TM1M2一、存贮体系的概念与并行主存系统 7 存贮体系依据于程序的局部性 程序的局部性表现在 时间和空间两个方面。时间上的局部性是因为程序存在着循环。空间上的局部性是因为程序中大部分指令是顺序存贮和顺序被取出来执行的，数据一般也是以向量、数组、树、表等形式簇聚地存贮在一起的。最近的未来要用的指令和数据大多局限于正在用的指令和数据，或是与这些指令和数据位置上邻近的单元。这样，就可以把目前常用或将要用到的信息预先放在容量较小的第一级存贮器M1中，从而使CPU的访问速度可接近于M1的。一、存

8、贮体系的概念与并行主存系统8 存贮体系的透明性 虚拟存贮器和Cache存贮器对应用程序员都是透明的，不需要对应用程序做任何修改就可以在系统上运行。由于CPU与主存的速度差只有一个数量级，主存与辅存之间的速度差却有3至4个数量级，所以，Cache存贮器只能全部采用硬件来实现。这样，Cache存贮器对系统程序员也是透明的，操作系统不参予对Cache存贮器的管理。而在虚拟存贮器中，为了降低系统的成本，让不少功能依靠操作系统中的虚拟存贮管理软件来实现。因此，虚拟存贮器对系统程序员则是不透明的。二、虚拟存贮器段式存贮管理 根据所用的存贮映象算法不同，虚拟存贮器可以有段式、页式和段页式三种不同的存贮管理方

9、式。1 段式存贮管理方式： 在系统工作时，根据所给的某道程序虚地址，由该道程序的程序号经硬件自动到段表基址寄存器组中取出相应该程序的段表起始地址。将段表起始地址与程序地址中给出的段号相加后，到该程序段表中读出相应行中的装入位。若装入位为“0”，就发生段失效故障。此时，程序自动换道，由I/O处理机去调段，而CPU转去执行另一道程序。若装入位为“1”，就读出段映象表中该行的地址字段的值。将此地址字段的值与程序虚地址的段内位移相加，就形成访存的物理地址。按此物理地址就可以访问所需要的物理存贮单元。利用段表中的段长字段可以判断出该段的地址是否越界。利用段表中的访问方式字段可以判断出这次访问是否会发生访

10、问方式保护。 二、虚拟存贮器段式存贮管理 将程序按逻辑意义分成段，各段顺序编号；各段程序都以该段的起点为0相对编址。 设置段表，程序分几段，段表有几行，行与段顺序对应；地址字段记录、装入位、段长。 如果系统有N道程序，就有N个段映象表。用N个段表基址寄存器分别记录各道程序的段表在主存中的起始地址。二、虚拟存贮器段式存贮管理段表二、虚拟存贮器段式存贮管理 段式存贮管理方式为了对实主存的空间进行分配和回收，段式存贮器需要为操作系统配备一个实主存空间管理表，进行存贮管理。它包括占用区域表和可用区域表两部分。在分配主存空间时，可采用下述两种方法：二、虚拟存贮器段式存贮管理首先分配法：扫描可用区域表，找

11、到可用区域立即分配；二、虚拟存贮器段式存贮管理最佳分配法：扫描全部可用区域表，分配找到可用区域，使的分配后段间可用区零头最小；二、虚拟存贮器段式存贮管理段式存贮管理的优点是：支持了程序的模块化设计和并行编程的要求，缩短了程序的编制时间；各个程序段的修改相互不会有影响；便于多道程序共享主存中某些段，不必将它们在物理主存中重复存放；段式存贮管理最主要的问题是：段映象表机构太庞大，其地址字段和段长字段都太长；查表进行地址变换的速度太慢；对主存各区域的存贮管理十分麻烦；存贮器内部的段间零头浪费大，有时难以利用。结论：单纯的段式存贮管理在实际的系统中无法采用。 将程序和内存分称大小相等的页，分别按页顺序

12、编号；虚页号和实页号。让程序的起点必须处在主存中某一个页面位置的起点上。 设置页表，程序分几页，页表有几行，行与页顺序对应；虚页号、实页号、装入位。 如果系统有N道程序，就有N个页映象表。用N个页表基址寄存器分别记录各道程序的页表在主存中的起始地址。二、虚拟存贮器页式存贮管理二、虚拟存贮器页式存贮管理页表二、虚拟存贮器页式存贮管理页式存贮管理的优点：所用映象表的硬件量少；地址变换的速度快；主存空间的分配和管理简便得多。页式存贮管理最主要的不足是：缺乏段式存贮管理的优点。结论：页式存贮管理在实际中使用较多。将段式存贮管理和页式存贮管理加以结合，取长补短，引出了段页式的存贮管理。二、虚拟存贮器段页

13、式存贮管理3段页式存贮管理方式：分主存为大小相等的页，并顺序编号；将程序按逻辑意义先分成段，并顺序编号；各段再分成与实页相同大小的页，各段的页单独顺序编号；每道程序通过一个段表和相应的一组页表来进行程序在主存空间中的定位；段表和页表一般在主存中，段表的起始地址在段表基址寄存器中，页表的起始地址在段表中；段（页）表中的每一行对应一个段页）；二、虚拟存贮器地址映象与变换全相联映象：让每道程序的任何一个虚页均可以映象装入到主存中任何一个实页位置上。地址映象：建立虚页和实页的对应关系；地址变换：根据多用户虚地址计算实地址。实地址=实页号*每页字数+页内偏移虚页号=Int（虚地址/每页字数）页内偏移=M

14、od（虚地址，每页字数）二、虚拟存贮器地址映象与变换页面失效：CPU按虚地址访存时未找到所需的程序页，称为页面失效。页面争用：两个以上的虚页要想进入主存中同一个实页位置时，就会产生实页冲突，或称发生了页面争用。地址映象方式的选择应尽量能降低实页冲突发生的概率。因此，虚拟存贮器都采用全相联的映象规则，实页冲突发生的概率必将是最低的。二、虚拟存贮器页面替换算法4 页面替换算法当页面失效后，从辅存中将一个虚页调入主存时又发生了实页冲突，这就要启用替换算法，选出主存中的一个页，将其替换出去。替换算法的选择应当尽可能使主存的命中率高些，算法的实现要方便，所需的软硬件要少，成本要低。二、虚拟存贮器页面替换

15、算法1）随机(RAND)替换算法是用软件或硬件的随机数生成器产生出一个待替换页的页号。 此替换算法虽然简单，容易实现，但由于未反映出程序的局部性特点，命中率很低，所以无法实用。2）先进先出(FIFO)替换算法是选择其中最早装入主存的虚页，将其替换出去。 这种算法实现起来不复杂，但不能很好地反映出程序的局部性，因此主存的命中率不一定很高。由于实现成本低，目前仍有不少系统在用。二、虚拟存贮器页面替换算法3）近期最少使用(LRU)替换算法是选择近期使用得最少的页，将其替换出去。 这种算法能比较确切地反映出程序的局部性特点。也称为近期最久未用过的替换算法。4）优化(OPT)替换算法是选择未来的近期里不

16、用或很久才用的页面，将其替换出去。 这种算法虽然不实用，但它可作为评价所用替换算法好坏的一个标准，哪种替换算法的主存命中率能接近于OPT法的，它就是好的替换算法。二、虚拟存贮器页面替换算法例1有一个虚拟存贮器，主存有03四页位置，程序有07八个虚页，采用全相联映象和LRU替换算法。给出如下程序页地址流：2,3,5,2,4,0,1,2,4,6。 (1) 分配给程序3个实页，请画出上述页地址流工作过程中，主存各页位置上所装程序各页页号的变化过程图，标出命中时刻。 (2) 分配给程序4个实页，请画出上述页地址流工作过程中，主存各页位置上所装程序各页页号的变化过程图，求此时命中率。二、虚拟存贮器页面替

17、换算法5）堆栈型替换算法对任一程序的页地址流作两次主存页面分配，分别分配给m个和n个页面，并且有mn，如果在任何时刻t，主存中的虚页集合Bt都满足关系： Bt（m） Bt（ n）则这类替换算法称为堆栈型替换算法。通俗地讲，凡属堆栈型替换算法，当增加分配给程序的实页数目时，其命中率一般会提高，至少不会下降。二、虚拟存贮器页面替换算法例3 页式虚拟存贮器共有9页空间准备分配给A、B两道程序。已知B道程序若给其分配4页时，命中率为8/15；而若分配5页时，命中率可达10/15。现给出A道程序的页地址流为2，3，2，1，5，2，4，5，3，2，5，2，1，4，5。 (1)画出用堆栈对A道程序页地址流的

18、模拟处理过程图，统计给其分配4页和5页时的命中率。 (2)根据已知条件和上述统计结果，给A、B两道程序各分配多少实页，可使系统总的命中率最高？系统总的命中率是多少？二、虚拟存贮器影响H的主要因素6 影响H的主要因素（1）页面替换算法（2）页地址流（3）所分配到的实页数（4）页面的大小（5）主存容量等多种因素有关。二、虚拟存贮器提高虚拟存储器等效访问速度的措施理论依据：程序的局部性特点。硬件支持：小容量快速存储器。那些地方还可继续改进？ 24 12 12 二、虚拟存贮器提高虚拟存储器等效访问速度的措施理论依据：一段时间内快表对应一个用户或任务。1 有什么缺陷？2 如何改进？ 24 12 12 二

19、、虚拟存贮器提高虚拟存储器等效访问速度的措施第三步：改进快表1 有什么缺陷？ 如何改进？2那些地方还可继续改进？二、虚拟存贮器提高虚拟存储器等效访问速度的措施三、高速缓冲存贮器 Cache存贮器和虚拟存贮器在工作原理上并没有本质上的区别，只是因为Cache存贮器的访问速度要求很高，所以在虚实地址字段的对应关系、信息块大小的划分、虚实地址映象规则、映象表机构、地址的变换和替换算法的实现、透明性及性能分析上有着较大的差异。三、高速缓冲存贮器1 Cache的工作原理分和主存为大小相等的块，为了加速调块，一般让Cache块的大小取成主存在一个主存周期里能访问到的字节数。因此，主存贮器都采用模m多分体多

20、字交叉并行访问的组织形式。受主存实际效率的影响，模数m不可能很高，使得Cache块的大小一般只有十几到几十个字节，只是虚拟存贮器页面大小的几十分之一；三、高速缓冲存贮器2 地址的映象与变换 在Cache存贮器中，所谓地址的映象就是让主存块能装入到物理Cache中的哪些块位置的规则。映象规则好坏的评价标准：进行地址映象和变换所需增加的辅助硬件是否少；价格是否便宜；地址变换的速度是否高；实现是否方便；Cache的块冲突概率是否比较低；物理Cache的空间利用率是否比较高。三、高速缓冲存贮器全相联映象是在主存和Cache都机械等分成相同大小的块后，让主存中的任何一个块均可以映象装入到Cache中任何

21、一个块位置上。三、高速缓冲存贮器全相联映象优点：Cache块冲突概率最低Cache空间利用率最高全相联映象缺点：目录表容量太大，成本极高。结论：无法实用。Why?三、高速缓冲存贮器直接映象是在主存和Cache都机械等分成相同大小的块后，再将主存空间按物理Cache大小等分成区，让主存中每一个区中的各个块均只能按位置一一对应装入Cache中相应的块位置上。也就是说，当物理Cache共有n个块位置时，让主存第i块只能唯一映象装入到物理Cache的第i mod n块位置上。三、高速缓冲存贮器直接映象优点：目录表所需的硬件量很少，成本低，易于实现。采用直接映象时，查表找区号可以与访物理Cache同时进

22、行。所以Cache的实际访问速度很快。直接映象缺点：Cache块冲突的概率很高，Cache的空间利用率很低。结论：现在已很少使用。Why?三、高速缓冲存贮器组相联映象规则：分Cache和主存为大小相等的块；Cache分为几个大小相同的组，并顺序编号；主存各区以同样方式分组，使的主存每区组数等于Cache的组数，各区的分组单独顺序编号；主存和Cache各组内的块也单独顺序编号（以组为单位），一般从0开始；主存的组与Cache的组通过组号直接映象，组内块间全相联映象；三、高速缓冲存贮器三、高速缓冲存贮器地址映象和变换通过目录表来完成， Cache分几组，目录表有几个；组内有几块，目录表有几行，每行

23、有三个字段：区号（nd）、主存组内块号（S）、 Cache组内块号（S）；可否改进？三、高速缓冲存贮器一种改进方法：通常所有目录表存于一个单体多字存储器中，每存储单元字数m= Cache每组内块数， Cache有几组，存储器有几行（存储单元），存储器设有m个相等比较电路，按地址访问，按内容相联比较。三、高速缓冲存贮器例4 Cache一主存存贮层次中，主存有07共8块，Cache为4块，采用组相联映象。假设Cache已先后访问并预取进了主存的第5、1、3、7块，现访存块地址流又为1、2、4、1、3、7、0、1、2、5、4、6时， (1)画出用LRU替换算法，Cache内各块的实际替换过程图，并标

24、出命中时刻。其中Cache分为两组。 (2)求出在此期间的Cache命中率。三、高速缓冲存贮器例5 Cache分S116块，主存分S2256块，让主存第i块映象装入到Cache中的第j块，jI mod Sl。 (1)这是什么映象规则? (2)画出主存地址到Cache地址变换过程的示意图，图中应标识出主存与Cache地址各字段位数及对应关系；指出用于地址映象变换的辅助表存贮器的宽度和单元数；对变换过程作简单的文字说明。三、高速缓冲存贮器 3 提高Cache命中率的取算法 Cache的取算法会影响到Cache的块命中率。按需取进法是在Cache发生块失效时才去调块。预取法是在将要用到某块之前，就已经将该块预先取进Cache中了。 预取算法具体又有恒预取法和不命中时预取法两种。恒预取法是在访问到主存第i块的信息时，不管其是否在Cache中命中，恒将主存第 i +1块预取进Cache。不命中