第4章 存储系统

第4章存储体系（P101）,本章学习重点：两种提高主存系统性能/价格比的结构化方法：并行存储器与存储层次技术。后者为主。,对存储系统的基本要求:高速度、大容量、低价格,并行存储系统（P74）,并行存储器技术的基本思想是用多个独立的存储部件组成主存系统，让它们并行工作，在一个存储周期内可以访问到多个数据，从而实现较高的存取流量。并行存储器包括多种类型,重点了解低位交叉访问,由n个存储体组成（一般n为2的整次幂），每个体均有独立的地址译码器和数据缓冲器，多体并行存储交叉访问,各体存储单元交叉连续(单体多字多体单字多体多字)增加数据宽度,低位交叉访问并行存储器的结构：,以主存地址低位字段作为体选译码信号，而剩下的高位字段则是体内地址。如图所示（设n=4）。,低位交叉访问并行存储器的加速机理：,衡量存储器速度的指标是存储周期Tm，它是同一存储单元连续两次启动的最小时间间隔，数值越小表明存储器件速度越快由多个存储体构成的并行存储器中，各个存储体都有独立的地址译码器和数据缓冲器，它们可以并行工作，使得一个Tm周期内可完成多次访问，相当于加速了多倍。最好情况下一个Tm周期内可完成n次访问。,访存冲突当前Tm周期中只要发现有一个新的访问地址与前面地址属于同一个存储体，该地址及其后面的地址就会被阻塞（称为访存冲突）,留到下一个Tm周期访问。,存储体系的概念,依据：程序访问的局部化原理（时间局部化，空间局部化）模型：如右图所示，存储层次由三层组成，,存储体系,即层次化存储系统,CPU寄存器,CACHE,主,存,储,器,辅,助,存,储,器,主存-辅存存储层次P101图4-1,Cache-主存存储层次P102图4-2,一.存储层次的两种形式:,存储层次,CPU对第二级的访问方式,比较项目,目的,存储管理实现,访问速度的比值(第一级和第二级),典型的块(页)大小,失效时CPU是否切换,“Cache主存”层次,“主存辅存”层次,为了弥补主存速度的不足,为了弥补主存容量的不足,主要由专用硬件实现,主要由软件实现,几比一,几百比一,几十个字节,几百到几千个字节,可直接访问,均通过第一级,不切换,切换到其他进程,“Cache主存”与“主存辅存”层次的区别,两种存储层次存储器的比较,二.存储层次的四个问题,当把一个块调入高一层(靠近CPU)存储器时，可以放在哪些位置上?(映象规则),当所要访问的块在高一层存储器中时，如何找到该块?(查找算法),3.当发生失效时，应替换哪一块？(替换算法),4.当进行写访问时，应进行哪些操作?(写策略),1.,2.,三.存储层次的管理方式(P104),根据程序的局部化性质，存储层次机构对用户文件的管理应该划分成较小的基本调度单位来进行。依划分标准不同，存在3种存储层次管理方式。-段式管理页式管理段页式管理,(1)段式管理(P104)段是程序中的一个逻辑单位，可以是一个程序模块，或者是一个数据结构。段的长度不一，但段内所有数据的信息属性一般是相同的，便于统一进行信息保护。每段使用独立的逻辑地址空间，即都从0开始计算地址。段式管理方法的主要缺点是各段长短不一，调进调出之后容易形成大量不规则的零碎空间。段式管理方法的虚实变换算法是查段表(书P105)。,(2)页式管理(P106)页是系统规定的固定长度单位。按页划分用户文件可以避免上述零碎空间浪费。我们把用户文件划分得到的一个长度单位称为“虚页”，因为它的页号是在虚地址空间中编排的；实地址空间按页的大小划分得到的一个长度单位称为“实页”。页式管理方法的主要缺点是按固定长度分出来的同一页内常有不同属性的信息，不便于信息保护的实现。页式管理方法的虚实变换算法是查页表(P107)。,(3)段页式管理(P107)它把上述两种管理方式结合起来，首先将整个文件分段，然后在各段内分页，所以有一个段表和若干个页表。其虚实变换算法是先查段表，查出该段的页表起始地址再查相应的页表(P108)。段页式管理的主要缺点是多查一次表，虚实变换费时较多，占用空间也较大。由于段页式管理方法的最小调度单位仍是页，或者说它是分段之后的分页管理。,四.地址映象与变换(P109),基本术语：逻辑地址（又称为相对地址、虚地址）是程序员在编写和编译一个程序模块时分配指令和数据的空间单位序号，总是从0开始（可以按字节编址、按CPU字编址等）。逻辑地址的取值范围称为逻辑地址空间、虚空间或虚存。物理地址（又称为绝对地址、实地址）是任一级存储器为全部存储单元分配的序号。物理地址的取值范围称为物理地址空间、实空间或实存。从M1到Mn各层都有自己的物理地址空间，而对当前执行的程序模块来说，逻辑地址空间只有一个。,存储器实际物理的址形成,0000,1918,.,1514.210,偏移地址,地址加法器,1918.210,物理地址,段地址,1514,.,210,6543210,.,物理地址=段地址*16+偏移地址,地址映象方式指的是虚页集合与实页集合的对应规则，或者说是约束关系。地址变换（又叫虚实变换）指逻辑地址到物理地址的变换过程或者算法。页失效指当前被访问存储级中没有所需的信息，也就是不命中现象。实页争用又叫实页冲突，指虚页调入时，根据地址映象方式划定的实空间范围内已没有空闲实页的状况。,五.4种常见的地址映象方式,全相联直接相联组相联段相联,1)全相联(P126),全相联：主存中的任一块可以被放置到Cache中的任意一个位置。举例对比：阅览室位置随便坐特点：空间利用率最高，冲突概率低，实现最复杂。,全相联映像,2.全相联映像（续）,N=区内块数，阴影区表示查找范围,2.全相联映像（续）,2)直接相联(127),直接映象：主存中的每一块只能被放置到Cache中唯一的一个位置。举例(循环分配)对比：阅览室位置只有一个位置可以坐特点：空间利用率最低，冲突概率最高，实现最简单。,直接映象,直接映象（续）,块地址的概念存储容量、块数、块容量与地址格式中区号、块号、块内地址位数的关系。,直接映象（续）,直接相联映象方式优缺点:直接相联映象方式不需要借助页表来进行虚实变换，大大节省了相应的空间与时间（当然页表中的装入位和修改位还得保留）但是由于每个虚页的选择范围太小，实页争用的发生频率较高，常出现明明实存有空闲空间却不得不调出一个现有虚页以腾出所在实页的情况，这使系统的命中率和运行效率大大下降。这种映象方式主要用于一些对实存价格非常敏感的Cache-主存层次。,组相联映象方式是全相联与直接相联的一个折中方案，性能也是二者的折中。,3.)组相联(129),组相联：主存中的每一块可以被放置到Cache中唯一的一个组中的任何一个位置。举例,组相联映像,n路组相联：组内有n块,组相联映像（续）,N=区内块数，阴影区表示查找范围，根据组号在块表中寻找组，组内相联查找。,3.组相联映像（续）,例：设有8个块，分成2个组,六.替换算法(P112),地址映象方式是在虚页调入时的“选址”规则，而地址变换方法则是命中时获得实地址的手段。,问题的提出：CPU要用到的指令或数据不在主存中，即产生了页面失效故障，产生了不命中情况,不命中时需要进行的操作就是“替换”。调出一页，以腾出一个实页之后再调入新的页称为“替换”。替换算法要解决的是选择调出对象的问题,也就是决定选择哪个页替换出去替换算法的目的是在发生实页争用时，选择将来不太可能使用或者使用最晚的虚页作为调出对象。,2.几种常用的替换算法(P112-116),(1)随机算法RAND在比较范围内任取一页作为淘汰页；(2)先进先出算法FIFO在比较范围内选取调入最早的一页作为淘汰页；(3)最不经常使用算法LFU在比较范围内选取最近单位时间内使用次数最少的一页作为淘汰页；(4)最不接近使用算法LRU在比较范围内选取最后一次使用离现在最久的一页作为淘汰页；(5)最优替换算法OPT在比较范围内选取下一次使用时间离现在最久的一页作为淘汰页。,堆栈型替换算法不是指某一种具体算法，而是使用堆栈处理技术去处理、模拟前面所述的几种替换算法（LRU、OPT、）以便仅仅进行一次模拟,就可同时求得对某地址流在不同的主存页数时的命中率.它的基本思想是：随着分配给程序的主存页面数增多，主存命中率提高，至少不下降。,3.堆栈型替换算法(P116),堆栈型的替换算法性质:在任何时刻t，在n个实页中的虚页集合总是被包含中n+1个实页中的虚页集合之内。(书P116)t新的页地址实页为4n实页为4+1,实例：堆栈模拟图,研究堆栈型替换算法的性质，一方面可以设计优化的操作系统算法另一方面也可推导出一些分析工具，例如“堆栈模拟法”。堆栈模拟图可以通过一次作图，描述同一地址流在各种实存分区容量下的命中情况。例,时间,1,2,3,4,5,6,7,8,9,10,11,12,页地址流,2,3,2,1,5,2,4,5,3,2,5,2,n=4,*,*,*,*,*,*,6,n=5,*,*,*,*,*,*,*,7,最高命中率：H=7/12,时间,1,2,3,4,5,6,7,8,9,10,11,12,页地址流,2,3,2,1,5,2,4,5,3,2,5,2,n=4,*,*,*,*,*,*,6,n=5,*,*,*,*,*,*,*,7,书P144、题6分析：LRU属堆栈型替换算法，要找出达到最高命中率时所分配的最少实页数，只要求出分配给该道程序不同实面数时的页命中率即可。解答：,最高命中率：H=7/12,最高命中率：H=7/12,第三节Cache一、基本原理,基本概念命中、命中率、失效、失效率、块、命中访问时间、失效访问时间(misspenalty)设计问题地址映象替换策略更新策略容量,二、地址映象与变换1.直接映象,1.直接映象（续）,块地址的概念存储容量、块数、块容量与地址格式中区号、块号、块内地址位数的关系。,1.直接映象（续）,2.全相联映像,2.全相联映像（续）,N=区内块数，阴影区表示查找范围,2.全相联映像（续）,3.组相联映像,n路组相联：组内有n块,3.组相联映像（续）,N=区内块数，阴影区表示查找范围，根据组号在块表中寻找组，组内相联查找。,3.组相联映像（续）,例：设有8个块，分成2个组,三、替换策略及更新策略,替换策略：随机法先进先出法近期最少使用法（近期最久未使用法）,三、替换策略及更新策略（续）先进先出替换策略,三、替换策略及更新策略（续）近期最久未使用替换策略,三、替换策略及更新策略（续）