【教学课件】第三章存贮系统.ppt

第三章 存贮系统,3.5 Cache存储器,3.5.1 cache基本原理1.cache的功能 cache是介于CPU和主存之间的小容量存储器，存取速度比主存快。它能高速地向CPU提供指令和数据，加快程序的执行速度。它是为了解决CPU和主存之间速度不匹配而采用的一项重要技术.组成原理-白中英网络版,3.5 Cache存储器,2.Cache的基本原理 CPU与cache之间的数据交换是以字为单位，而cache与主存之间的数据交换是以块为单位。一个块由若干定长字组成的。当CPU读取主存中一个字时，便发出此字的内存地址到cache和主存。此时cache控制逻辑依据地址判断此字当前是否在 cache中：若是，此字立即传送给CPU；若非，则用主存读周期把此字从主存读出送到CPU，与此同时，把含有这个字的整个数据块从主存读出送到cache中。由始终管理cache使用情况的硬件逻辑电路来实现LRU替换算法,3.5 Cache存储器,3.cache的命中率增加cache的目的，就是在性能上使主存的平均出时间尽可能接近cache的读出时间。因此,cache的命中率应接近于1。由于程序访问的局部性，这是可能的。在一个程序执行期间，设Nc表示cache完成存取的总次数，Nm表示主存完成存取的总次数，h定义为命中率，则有 若tc表示命中时的cache访问时间，tm表示未命中时的主存访问时间，1-h表示未命中率，则cache/主存系统的平均访问时间ta为：,3.5 Cache存储器,ta=htc+(1-h)tm（3.5）设r=tm/tc表示主存慢于cache的倍率,e表示访问效率，则有:为提高访问效率，命中率h越接近1越好，r值以510为宜，不宜太大。命中率h与程序的行为、cache的容量、组织方式、块的大小有关。,3.5 Cache存储器,【例5】CPU执行一段程序时，cache完成存取的次数为1900次，主存完成存取的次数为100次，已知cache存取周期为50ns，主存存取周期为250ns，求cache/主存系统的效率和平均访问时间。解:h=Nc/(Nc+Nm)=1900/(1900+100)=0.95r=tm/tc=250ns/50ns=5e=1/(r+(1-r)h)=1/(5+(1-5)0.95)=83.3%ta=tc/e=50ns/0.833=60ns,3.5 Cache存储器,3.5.2.主存与cache的地址映射 cache的容量很小，它保存的内容只是主存内容的一个子集，且cache与主存的数据交换是以块为单位。地址映射即是应用某种方法把主存地址定位到cache中。址映射方式有全相联方式、直接方式和组相联方式三种,3.5 Cache存储器,1.全相联映射方式主存中一个块的地址与块的内容一起存于cache的行中，其中块地址存于cache行的标记部分中。这种方法可使主存的一个块直接拷贝到cache中的任意一行上，非常灵活。它的主要缺点是比较器电路难于设计和实现,因此只适合于小容量cache采用。全相联映射的示意图演示(P108图3.37a).组成原理-白中英网络版,3.5 Cache存储器,2.直接映射方式这也是一种多对一的映射关系，但一个主存块只能拷贝到cache的一个特定行位置上去。cache的行号i和主存的块号j有如下函数关系：i=j mod m（m为cache中的总行数）直接映射方式的示意图演示(P109图3.38a).组成原理-白中英网络版直接映射方式的优点是硬件简单，成本低。缺点是每个主存块只有一个固定的行位置可存放,容易产生冲突。因此适合大容量cache采用。,3.5 Cache存储器,3.组相联映射方式这种方式是前两种方式的折衷方案。它将cache分成u组，每组v行，主存块存放到哪个组是固定的，至于存到该组哪 一行是灵活的，即有如下函数关系：muv 组号qj mod u 组相联映射的示意图演示.组成原理-白中英网络版组相联映射方式中的每组行数v一般取值较小，这种规模的v路比较器容易设计和实现。而块在组中的排放又有一定的灵活性,冲突减少。,例5,例：设主存的容量为1KB，Cache的容量为128B，每块的大小为8B。1.直接映射、全相联映射、组相联映射（2组并联）的主存地址格式可分成哪几个部分、各占多少位？2.如果一个主存的地址为0010010011，试说明在上述三种映射方式下，该地址页在Cache中应处的位置，并说明CPU访问该地址的过程。,例5,解：3 4 3 1.直接映射 主存组号 Cache行号 块内地址 7 32.全相联映射 主存块号 块内地址 4 3 33.组相联映射 主存组号 Cache组号 块内地址因为主存共分为1KB/8B=128个块，Cache共分为128B/8B=16个行主存共分为128/16=8个组,2.直接映射 主存 Cache 0#块 0#行 0#组 1#块 1#行 15#块 15#行 16#块 3位的标记位 1#组 31#块 001 0010 011 1#组 2#行 3#块内 112#块 地址 7#组 127#块,组相联映射 主存 Cache 0#块 0#行 0#组 0#组 1#块 1#行 2#行 1#组 7#块 3#行 8#块 1#组 7#组 15#块 15#行 4位的标记位 120#块 15#组 0010 010 011 127#块 2#主存组 2#cache组 3#块内,例5,全相联映射 此时该地址块可存放在Cache中的任何一行。,3.5 Cache存储器,3.5.3.替换策略 cache工作原理要求它尽量保存最新数据，必然要产生替换。对直接映射的cache来说，只要把此特定位置上的原主存块换出cache即可。对全相联和组相联cache来说，就要从允许存放新主存块的若干特定行中选取一行换出。,3.5 Cache存储器,3.5 Cache存储器,最不经常使用(LFU)算法 LFU算法将一段时间内被访问次数最少的那行数据换出。每行设置一个计数器。从0开始计数，每访问一次，被访行的计数器增1。当需要替换时，将计数值最小的行换出，同时将这些行的计数器都清零。这种算法将计数周期限定在对这些特定行两次替换之间的间隔时间内，不能严格反映近期访问情况。,3.5 Cache存储器,近期最少使用(LRU)算法 LRU算法将近期内长久未被访问过的行换出。每行也设置一个计数器，cache每命中一次，命中行计数器清零，其它各行计数器增1。当需要替换时，将计数值最大的行换出。这种算法保护了刚拷贝到cache中的新数据行，有较高的命中率。,3.5 Cache存储器,随机替换随机替换策略从特定的行位置中随机地选取一行换出。在硬件上容易实现，且速度也比前两种策略快。缺点是降低了命中率和cache工作效率。,3.5 Cache存储器,3.5.4 cache的写操作策略 CPU对cache的写入更改了cache的内容。可选用写操作策略使cache内容和主存内容保持一致。,3.5 Cache存储器,写回法当CPU写cache命中时，只修改cache的内容，而不立即写入主存；只有当此行被换出时才写回主存。实现这种方法时，每个cache行必须配置一个修改位，以反映此行是否被CPU修改过。,3.5 Cache存储器,写回法当CPU写cache不未命中时，为了包含欲写字的主存块在cache 分配一行，将此块整个拷贝到cache后对其进行修改。主存的写修改操作统一地留到换出时再进行。这种方法减少了访问主存的次数,因为对Cache的多次修改，只需要一次回写到主存。但是存在不一致性的隐患。,3.5 Cache存储器,全写法 当写cache命中时，cache与主存同时发生写修改，因而较好地维护了cache与主存的内容的一致性。当写cache未命中时，只能直接向主存进行写入。优点是cache中每行无需设置一个修改位以及相应的判断逻辑。缺点是cache对cpu向主存的写操作无高速缓冲功能，降低了cache的功效。,3.5 Cache存储器,写一次法 基于写回法并结合全写法的写策略,写命中与写未命中的处理方法与写回法基本相同，只是第一次写命中时要同时写入主存。这便于维护系统全部cache的一致性。该策略主要用于处理器的片内cache,3.5 Cache存储器,MESI协议 一致性要求:如cache中某个字被修改，那么在主存中，该字的副本立即或最后加以修改,并确保其它引用主存上该字的正确性.(1)目录协议:它由位于主存的目录来保存有关各个局部cache的全局性状态信息,并由一个集中式的主存/cache控制器来维护cache一致性.,3.5 Cache存储器,(2)监听协议:将维护一致性的责任分散到各个cache控制器。它必须识别出它的cache中哪些块是与其它cache共享的.当修改一个共享块时，必须在系统中广播有关信息。监听协议又分为写修改协议和写无效协议。MESI协议是采用写无效监听协议.,3.5 Cache存储器,每个cache行有两个状态位,用于描述该行当前处于M、E、S、I中的哪种状态,从而决定它的读/写操作行为。这四种状态的定义是:修改态(M):此cache行以被修改过，内容不同于主存并且为此cache专有；专有态(E):此cache行内容同于主存，但不出现在其它cache中；共享态(S):此cache行内容同于主存，但也出现在其它cache中；无效态(I):此cache行内容无效(空行)。,3.5 Cache存储器,3.5.5 奔腾PC机的cache 奔腾PC机采用两级cache结构。安装在主板上的2级cache(L2)采用2路组相联映射方式，集成在CPU内的 1级cache(L1)也采用2路组相联映射方式，L1又是L2的子集，从而使L1未命中处理时间大大缩短。CPU中的L1分设成各8KB的指令cache和数据cache,有利于CPU高速执行程序。数据cache采用2路组相联结构，采用LRU替换算法，一组两行共用一个LRU二进制位。数据cache的工作方式受CPU控制寄存器CR0中CD和NW位组合状态控制，如下表3.8所示。,3.5 Cache存储器,表3.10奔腾CPU片内数据cache工作方式 其中CD=1,NW=1时复位后状态，而CD=0,NW=0时最佳使用状态,3.5 Cache存储器,两级cache和主存之间的工作环境方框图演示.组成原理-白中英网络版CPU与外部数据交换时，存储器读写总线周期主要有两类:一类是256位猝发式传送，用于L1的行填入和行写出,一次完成整行的填入或写出。另一类是不经L1的64位传送，此时CHACE仅为高电平，称为非超高速缓存式传送。,3.5 Cache存储器,L2级cache采用的是写回法，L1级数据cache采用的是写一次法。为了维护cache的一致性，L1和L2均采用MESI协议,即要求每个cache行有两个状态位，用以描述该行当前是处于修改态、专有态、共享态或者无效态中的哪种状态，从而决定对它的读/写操作行为。总之，L2级cache的内容是主存的子集，而L1级cache又是L2级cache的子集。L2负责整个系统的cache/主存一致性，L1负责响应L2，与L2一起维护L1/L2两个cache的一致性，保证三级存储系统的一致性。,3.6虚拟 存储器,虚拟存储器的基本概念 虚拟存储器只是一个容量非常大的存储器的逻辑模型，不是任何实际的物理存储器。它借助于磁盘等辅助存储器来扩大主存容量，使之为更大或更多的程序所使用。它指的是主存-外存层次。以透明的方式给用户提供了一个比实际主存空间大得多的程序地址空间。,3.6虚拟 存储器,注意：物理地址由CPU地址引脚送出，用于访问主存的地址。虚拟地址由编译程序生成的，是程序的逻辑地址，其地址空间的大小受到辅助存储器容量的限制。主存-外存层次和cache-主存层次用的地址变换映射方法和替换策略是相同的，都基于程序局部性原理。它们遵循的原则是：,3.6虚拟存储器,把程序中最近常用的部分驻留在高速的存储器中。一旦这部分变得不常用了，把它们送回到低速的存储器中。这种换入换出是由硬件或操作系统完成的，对用户是透明的。力图使存储系统的性能接近高速存储器，价格接近低速存储器。两种存储系统的主要区别在于：在虚拟存储器中未命中的性能损失要远大于cache系统中未命中的损失。,3.6虚拟 存储器,2.主存-外存层次的基本信息传送单位 主存-外存层次的基本信息传送单位可采用几种不同的方案：段、页或段页。段是按照程序的逻辑结构划分成的多个相对独立部分，作为独立的逻辑单位。优点是段的逻辑独立性使它易于编译、管理、修改和保护,也便于多道程序共享；某些类型的段具有动态可变长度,允许自由调度以便有效利用主存空间。缺点是因为段的长度各不相同，起点和终点不定，给主存空间分配带来麻烦，而且容易在段间留下许多空余的零碎存储空间，造成浪费。,3.6虚拟 存储器,页是主存物理空间中划分出来的等长的固定区域。优点是页面的起点和终点地址是固定的,方便造页表,新页调入主存也很容易掌握，比段式空间浪费小。缺点是处理、保护和共享都不及段式来得方便。,3.6虚拟 存储器,段页式管理采用分段和分页结合的方法。程序按模块分段，段内再分页，进入主存以页为基本信息传送单位，用段表和页表进行两级定位管理。,3.6虚拟 存储器,页式虚拟存储器 页式虚拟存储系统中，虚拟空间分成页，称为逻辑页；主存空间也分成同样大小的页，称为物理页。虚存地址分为两个字段：高字段为逻辑页号，低字段为页内行地址。实存地址也分两个字段：高字段为物理页号，低字段为页内行地址。,3.6虚拟 存储器,页表中每一个虚存逻辑页号有一个表目，表目内容包含该逻辑页所在的主存页面地址(物理页号),用它作为实存地址的高字段，与虚存地址的页内行地址字段相拼接，产生完整的实主存地址，据此来访问主存。页式管理的地址变换演示.组成原理-白中英网络版,3.6虚拟存储器,为了避免页表已保存或已调入主存储器时对主存访问次数的增多,把页表的最活跃部分存放在高速存储器中组成快表。快表与慢表实现内部地址变换的方式演示 快表由硬件组成，比页表小得多，查表时，由逻辑页号同时去查快表和慢表，当在快表中有此逻辑页号时，就能很快地找到对应的物理页号送入实主存地址寄存器，从而做到虽采用虚拟存储器但访主存速度几乎没有下降。.组成原理-白中英网络版,3.6虚拟 存储器,段式虚拟存储器 在段式虚拟存储系统中，段是按照程序的逻辑结构划分的，各个段的长度因程序而异。虚拟地址由段号和段内地址组成,为了把虚拟地址变换成实主存地址，需要一个段表。段表也是一个段，可以存在外存中，但一般是驻留在主存中虚存地址向实存地址的变换过程演示.组成原理-白中英网络版,3.6虚拟存储器,3.6.4 段页式虚拟存储器 段页式虚拟存储器是段式虚拟存储器和页式虚拟存储器的结合。它把程序按逻辑单位分段以后，再把每段分成固定大小的页。程序对主存的调入调出是按页面进行的，但它又可以按段实现共享和保护，兼备页式和段式的优点。缺点是在映象过程中需要多次查表。,3.6虚拟存储器,在段页式虚拟存储系统中，每道程序是通过一个段表和一组页表来进行定位的。段表中的每个表目对应一个段，每个表目有一个指向该段的页表起始地址及该段的控制保护信息。由页表指明该段各页在主存中的位置以及是否已装入、已修改等状态信息。如果有多个用户在机器上运行，多道程序的每一道需要一个基号,由它指明该道程序的段表起始地址。虚拟地址格式如下：,基号,段号,页号,页内地址,3.6虚拟存储器,【例6】假设有三道程序(用户标志号为A，B，C)，其基址寄存器内容分别为SA，SB，SC，逻辑地址到物理地址的变换过程见演示。在主存中，每道程序都有一张段表，A程序有4段，C程序有3段。每段应有一张页表，段表的每行就表示相应页表的起始位置，而页表内的每行即为相应的物理页号。请说明虚实地址变换过程。.组成原理-白中英网络版,3.6虚拟 存储器,【解】地址变换过程如下：根据基号C执行SC加1（段号）操作，得到段表相应行地址，其内容为页表的起始地址。执行b+2（页号），得到物理页号的地址，其内容即为物理页10。物理页号与页内地址拼接即得物理地址。如计算机只有一个基址寄存器，基号可不要，多道程序切换时，操作系统修改基址寄存器内容。可以看出，段页式虚拟存储系统由虚拟地址向主存地址的变换至少需要查两次表。,3.6虚拟 存储器,3.6.5 替换算法 虚拟存储器中的页面替换策略和cache中的行替换策略有很多相似之处，但有三点显著不同：(1)缺页至少要涉及前一次磁盘存取，读取所缺的页，缺页使系统蒙受的损失要比cache未命中大得多。(2)页面替换是由操作系统软件实现的。(3)页面替换的选择余地很大，属于一个进程的页面都可替换。,3.6虚拟 存储器,虚拟存储器中的替换策略一般采用LRU算法、LFU算法 FIFO算法，或将两种算法结合起来使用。对于将被替换出去的页面，假如该页调入主存后没有被修改,就不必进行处理，否则就把该页重新写入外存，以保证外存中数据的正确性。为此,在页表的每一行应设置一修改位。,例7,【例7】假设主存只有a,b,c三个页框，组成a进c出的FIFO队列，进程访问页面的序列是0，1，2，4，2，3，0，2，1，3，2号。若采用FIFO算法，FIFO算法+LRU算法，用列表法分别求两种替换策略情况下的命中率。,例8,例8：下表表示用快表（页表）的虚实地址转换条件，快表放在相联存贮器中，其容量为8个存贮单元，问：当CPU按虚地址1、虚地址2、虚地址3去访问主存时主存的实地址码是多少？虚地址 页号 页内地址 1 15 0324 2 7 0128 3 48 0516,例8,该页在主存中的 页号 起始地址 32 42000 25 38000 7 96000 6 60000 4 40000 15 80000 5 50000 34 70000,例8,解：（1）80000+0324=80324（2）96000+0128=96128,(3）此时快表中没有48号的页号，因此应在页表中查找48号页，同时将48号页及该页在主存中的起始地址写入快表；如果页表中也没有48号页，则应该从外存中调入48号页到主存，然后将48号页及该页在主存中的起始地址写入快表。,3.6虚拟存储器,3.6.6 虚拟存储器实例奔腾PC的虚地址模式 奔腾PC的存储管理部件MMU包括分段部件SU和分页部件PU两部份，可允许SU，PU单独工作或同时工作。,3.6虚拟 存储器,分段不分页模式：虚拟地址由一个16位的段参照和一个32位的偏移组成。分段部件SU将二维的分段虚拟地址转换成一维的32位线性地址。优点是无需访问页目录和页表，地址转换速度快。对段提供的一些保护定义可以一直贯通到段的单个字节级。,3.6虚拟存储器,分段分页模式：在分段基础上增加分页存储管理的模式。即将SU部件转换后的32位线性地址看成由页目录、页表、页内偏移三个字段组成，再由PU部件完成两级页表的查找，将其转换成32位物理地址。兼顾了分段和分页两种方式的优点。,3.6虚拟存储器,不分段分页模式：这种模式下SU不工作，只是分页部件PU工作。程序也不提供段参照，寄存器提供的32位地址被看成是由页目录、页表、页内偏移三个字段组成。由PU完成虚拟地址到物理地址的转换。这种模式减少了虚拟空间，但能提供保护机制，比分段模式具有更大的灵活性。,3.6虚拟存储器,2.保护模式的分页地址转换奔腾机4MB分页方式地址转换演示 页面(页框)大小为4MB的分页方式 使用单级页表，只进行一次主存访问，地址转换过程加快了。在此方式下，32位线性地址分为高10位的页面和低22位的页内偏移两个字段。页表项的I位指示页面大小，P位为出现位,A位为访问过位,D位为修改过位.RW位用于读/写控制，US位用于用户/监督控制，PCD位用于页cache禁止的控制，PWT位用于页全写法的控制。.组成原理-白中英网络版,3.7 存储保护,3.7.1 存储区域保护 当多个用户共享主存时，应防止由于一个用户程序出错而破坏其他用户的程序和系统软件,以及一个用户程序不合法地访问不是分配给它的主存区域。在虚拟存储系统中，通常采用页表保护、段表保护和键式保护方法。,3.7 存储保护,1.页表保护和段表保护 每个程序的段表和页表本身都有自己的保护功能。每个程序的虚页号是固定的，经过虚地址向实地址变换后的实存页号也就固定了。那么不论虚地址如何出错，也只能影响到相对的几个主存页面。不会侵犯其他程序空间。段表和页表的保护功能相同，但段表中除包括段表起点外，还包括段长。段表保护方式演示.组成原理-白中英网络版,3.7 存储保护,2.键保护方式 这种方法是为主存的每一页配一个键，称为存储键，每个用户的实存页面的键都相同。为了打开这个锁,必须有钥匙，称为访问键。访问键赋予每道程序，并保存在该道程序的状态寄存器中。当数据要写入主存的某一页时，访问键要与存储键相比较。若两键相符，则允许访问该页，否则拒绝访问。键保护方式演示.组成原理-白中英网络版,3.7 存储保护,3.环保护方式 环保护方式可以做到对正在执行的程序本身的核心部分或关键部分进行保护。它是按系统程序和用户程序的重要性及对整个系统的正常运行的影响程度进行分层，每一层叫做一个环。在现行程序运行前由操作系统定好程序各页的环号，并置入页表中。然后把该道程序的开始环号送入CPU的现行环号寄存器。程序可以访问任何外层空间；访问内层空间则需由操作系统的环控例行程序判断这个向内访问是否合法。环保护方式演示.组成原理-白中英网络版,3.7 存储保护,3.7.2 访问方式保护 对主存信息的使用可以有三种方式:读(R)、写(W)和执行(E),相应的访问方式保护就有R，W，E三种方式形成的逻辑组合.这些访问方式保护通常作为程序状态寄存器的保护位，并且和区域保护结合起来实现。,3.7 存储保护,逻辑组合 含 义 R+W+E 不允许任何访问(R+E)W 只能写访问 R+W+E 可进行任何访问(R+E)W 不准写访问(R+W)E 只能读写，不可执行 R(W+E)只能读访问(R+W)E 只能执行，不可读写 R(W+E)不准读访问,本 章 小 结,1.对存储器的要求是容量大、速度快、成本低。为了解决了这三方面的矛盾，计算机采用多级存储体系结构，即cache、主存和外存。CPU能直接访问内存(cache、主存)，但不能直接访问外存。2.存储器的技术指标有存储容量、存取时间、存储周期、存储器带宽。3.广泛使用的SRAM和DRAM都是半导体随机读写存储器，前者速度比后者快，但集成度不如后者高。二者的优点是体积小，可靠性高，价格低廉，缺点是断电后不能保存信息。,本 章 小 结,4.只读存储器和闪速存储器正好弥补了SRAM和DRAM的缺点，即使断电也仍然保存原先写入的数据。5.双端口存储器和多模块交叉存储器属于并行存储器。前者采用空间并行技术，后者采用时间并行技术。6.相联存储器不是按地址而是按内容访问的存储器，在cache中用来存放行地址表，在虚拟存储器中用来存放段表、页表和快表。在这两种应用中，都需要快速查找。,本 章 小 结,7.cache是一种高速缓冲存储器，是为了解决CPU和主存之间速度不匹配而采用的一项重要的硬件技术,并且发展为多级cache体系，指令cache与数据cache分设体系。要求cache的命中率接近于18.主存与cache的地址映射有全相联、直接、组相联 三种方式。9.虚拟存储器指的是主存-外存层次，它给用户提供了一个比实际主存空间大得多的虚拟地址空间。因此,虚拟存储器只是一个容量非常大的存储器的逻辑模型，不是任何实际的物理存储器。,10.按照主存-外存层次的信息传送单位不同，虚拟存储器有页式、段式、段页式三类。11.当多个用户共享主存时，系统应提供存储保护。通常采用的方法是存储区域保护和访问方式保护，并用硬件来实现。有些机器中提供特权指令来实现某种保护。,谢谢！,