存储系统必修课市公开课获奖课件_第1页
存储系统必修课市公开课获奖课件_第2页
存储系统必修课市公开课获奖课件_第3页
存储系统必修课市公开课获奖课件_第4页
存储系统必修课市公开课获奖课件_第5页
已阅读5页,还剩91页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、第4章 存储系统教学目的与要求:理解:单体多字并行存储器和交叉编址并行存储器工作原理; 理解:程序局部性和存储器系统层次结构及其性能指标掌握:存储体系构成及其设计原则访存局部性原理。Cache基本结构和工作原理,研究地址映象与变换、替换策略和更新策略工作原理和设计办法,分析影响Cache性能指标原因及优化办法。先进Cache结构和一致性处理办法。虚拟存储器结构与实现技术。 第1页第1页第4章 存储系统教学目的与要求:重点:地址映象与变换、替换策略和更新策略工作原理和设计办法;页式存储器工作原理及替换算法;Cache存储器3种地址映象规则以及相应地址变换办法难点:虚拟存储器和Cache存储器地址

2、映象规则以及相应地址变换办法第2页第2页4.1存储系统层次结构与性能指标 长久存在问题:在合理总价格限制下,单纯性主存设备速度跟不上CPU发展,容量不能满足软件尺寸扩大。 本章学习两种提升主存系统性能/价格比结构化方法:并行存放器与存放层次技术。后者为主。 存放系统设计目标:以较小成本使存放系统工作速度与处理机速度相匹配;同时要求存放系统有尽也许大容量;价格尽也许低。 存放系统定义 两个或两个以上速度、容量和价格各不相同存放器用硬件、软件、或软件与硬件相组合方法连接起来成为一个存放系统。 特点:这个存放系统对应用程序员是透明,而且,从应用程序员角度看,它是一个存放器,这个存放器速度靠近速度最快

3、那个存放器,存放容量与容量最大那个相等,单位容量价格靠近最廉价那个存放器。第3页第3页4.1存储系统层次结构与性能指标一、存储系统层次结构基本概念与定义: 时间局部性:程序最近未来要用到信息很也许是现在正在使用信息 空间局部性:程序最近未来要用到信息很也许出现在正在使用信息在存储空间位置上是相邻。 存储容量S:以字节数表示,单位为B、KB、MB、GB、TB等。 存储器速度T:存储器访问周期,与命中率相关。 存储器价格C:表示单位容量平均价值单位为C/bit或C/KB。计算机存储系统三个基本参数:第4页第4页4.1存储系统层次结构与性能指标1. 从用户角度来看,存储器三个主要指标是: 容量,速度

4、,价格(每位价格)2. 人们对这三个指标盼望:这个存储器速度靠近速度最快那个存储器,存储容量与容量最大那个相等,单位容量价格靠近最廉价那个存储器。3. 这三个指标互相矛盾4. 处理办法: 采用各种存储器技术,构成存储层次。 演示 演示 (局部性原理)第5页第5页4.1存储系统层次结构与性能指标一、存储系统层次结构第6页第6页第一层第二层第三层第四层第五层存储系统层次结构速 度 提 高容 量 增 加 通用存储器M1高速缓冲存储器M2 主存储器M3 脱机大容量存储器M5 辅助存储器M4 每级存储器性能参数能够表示为Ti,Si,Ci。存储系统性能可表示为:TiTi+1;SiCi+1。第7页第7页4.

5、1存储系统层次结构与性能指标第8页第8页4.1存储系统层次结构与性能指标一、存储系统层次结构 三级存储系统:当前多数计算机有Cache、主存储器和辅存构成。它一个实现方式是组织成2个独立二级存储器。1. 从主存角度来看 “Cache主存”层次:填补主存速度不足 “主存辅存”层次: 填补主存容量不足2. “Cache主存”层次 主存与CPU速度差距第9页第9页4.1存储系统层次结构与性能指标第10页第10页 “Cache - 主存”层次第11页第11页3. “主存辅存”层次第12页第12页4.1存储系统层次结构与性能指标存储层次CPU对第二级访问方式比较项目目存储管理实现 访问速度比值(第一级和

6、第二级)典型块(页)大小失效时CPU是否切换“Cache 主存”层次“主存辅存”层次为了填补主存速度不足为了填补主存容量不足主要由专用硬件实现主要由软件实现几比一几百比一几十个字节几百到几千个字节可直接访问均通过第一级不切换切换到其它进程“Cache主存”与“主存辅存”层次区别第13页第13页4.1存储系统层次结构与性能指标二、存储系统性能指标 1.存放系统容量S要求:提供尽也许大地址空间,(靠近M2)能进行随机访问2.存放器带宽:存放器提供数据传输速率3.每位价格C 设:S 容量 TA 访问时间 C 每位价格下面仅考虑由M1和M2组成两级存放层次: M1参数:S1,TA1,C1 M2参数:S

7、2,TA2,C2则每位价格C: C C1S1C2S2S1S2第14页第14页4.1存储系统层次结构与性能指标二、存储系统性能指标 4. 命中率 H 和失效率 F 命中率H定义为CPU产生逻辑地址在存储器M1中访问到指定信息概率。HN1/(N1N2) N1 访问M1次数 N2 访问M2次数 失效率 F1H第15页第15页4.1存储系统层次结构与性能指标第16页第16页4.1存储系统层次结构与性能指标二、存储系统性能指标 5. 等效访问周期T(平均访问时间)二级存储器等效访问周期T为 THT1(1H )T2T1 M1存储器访问周期 T2 M2存储器访问周期第17页第17页4.1存储系统层次结构与性

8、能指标第18页第18页4.1存储系统层次结构与性能指标二、存储系统性能指标 6. 访问效率二级存储器访问效率为T1 M1存储器访问周期 T2 M2存储器访问周期e T1HT1(1-H)T2T1T第19页第19页4.2 并行存储器一、单体多字并行存储器 频带宽度:单位时间内所能访问数据量。并行存储器:在一个存储器访问周期内能并行访问到多个存储字存储器,能有效提升带宽。第20页第20页4.2 并行存储器一、单体多字并行存储器 定义:把存储器存储字长增长n倍,以存储n个指令字或数据字 长处:简朴、容易。缺点:访问冲突大。主要冲突:取指令冲突(条件转移时)读操作数冲突(需要多个操作数不一定都存储在同一

9、个存储字中)写数据冲突(必须凑齐n个数才一起写入存储器)读写冲突(要读出一个字和要写入一个字处于同一个存储字内时,无法在一个存储周期内完毕)。第21页第21页4.2 并行存储器e T1HT1(1-H)T2T1T第22页第22页4.2 并行存储器二、多体并行存储器 定义:指由多个存储体构成一个更大容量主存。办法:采用交叉编址方式分类:1.地址码高位交叉编址 2.地址码地位交叉编址第23页第23页4.2 并行存储器e T1HT1(1-H)T2T1T第24页第24页一、高位交叉访问 低位部分:体内地址 b=log2n高位部分:存储体体号 a=log2mm: 体数n:每个体容量数据总线地址总线 WMD

10、R0 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第25页第25页二、低位交叉访问 低位交叉存储器结构 低位部分:存储体体号 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 nm-1 MARm-1译码 a b数据总线地址总线分时访问第26页第26页比如,n=8 m=4多体

11、并行低位交叉编址 012345678910111213141516171819202122232425262728293031 b a09182712510304个体并行2个体并行第27页第27页存储层次四个问题当把一个块调入高一层(靠近CPU)存储器时,能够放在哪些位置上? (地址映象,映象规则)实际运营中,地址如何找到? (地址变换,查找算法)3. 当发生失效时,应替换哪一块? (替换算法)4. 当进行写访问时,应进行哪些操作? (写策略)1. 2.并行存储器与存储层次技术存储层次技术:虚拟存储器、Cache存储器第28页第28页4.3 虚拟存储器基本概念 虚空间:程序所能利用空间。又称虚

12、存空间或虚拟存储器空间,它是应用程序员用来编写程序地址空间,这个地址空间非常大。虚地址:虚存空间上地址,又称为虚存地址。编程序时程序员所用地址,在编译程序中由处理机生成。一个用户程序要访问虚拟存储器时,必须给出多用户虚地址主存储器地址空间:也称主存地址空间、主存物理空间或实存地址空间实地址:主存物理空间编址;又称为主存实地址、主存物理地址、主存储器地址辅存地址空间:也就是磁盘存储器地址空间磁盘存储器地址:又称为磁盘地址、辅存地址 第29页第29页4.3 虚拟存储器基本概念: 地址映象:虚地址与实地址之间相应关系规则 地址变换:在程序被装入主存储器之后,在实际运营时,把多用户虚地址变换成主存实地

13、址(内部地址变换)或磁盘存储器地址(外部地址变换)。 访问失效:按虚地址访问数据不在主存中(未命中) 外部地址变换:访问失效时,需要访问磁盘存储器,这时把虚地址变换为磁盘存储器物理地址(普通为软件实现) 内部地址变换:把虚地址变换为主存物理地址 主存冲突:有新数据调入,主存却没有相应空闲位置 替换算法:当发生主存冲突时,应替换主存哪一块 地址变换和替换算法是虚拟存储器两个主要技术第30页第30页 1961年英国曼彻斯特大学Kilbrn等人提出。到了70年代被广泛地应用于大中型计算机系统中。当前,许多小型计算机,甚至微型机也开始使用虚拟存储器。 4.3.1虚拟存储器地址映象与地址变换4.3.2页

14、面替换算法及其命中率4.3 虚拟存储器第31页第31页4.3 虚拟存储器虚拟存储器由主存储器和联机工作外部存储器共同构成。把主存储器、磁盘存储器和虚拟存储器都划分成固定大小页 主存储器页称为实页,虚拟存储器中页称为虚页。一个主存地址A由两部分构成,实页号p和页内偏移d一个虚地址Av由三部分构成,用户号U、虚页号P和页内偏移D第32页第32页一个用户程序要访问虚拟存储器时,必须给出多用户虚拟地址Av。内部地址变换: (1)多用户虚拟地址Av变换成实地址A (2)多用户虚拟地址中页内偏移D直接作为主存实地址中页内偏移d (3)主存实页号与它页内偏移d直接拼接起来就得到主存实地址A第33页第33页外

15、部地址变换:首先查外页表得到磁盘存储器实地址把磁盘存储器实地址和主存储器实页号送入输入输出处理机把要访问数据所在一整页都从磁盘存储器调入到主存储器第34页第34页4.3 虚拟存储器第35页第35页4.3 虚拟存储器 CPU存储管理主存 辅 存I或DI或DVAPA外存地址虚拟存储器中CPU、MS、辅存间关系 第36页第36页4.3.1 地址映象与变换虚拟存储器中有三种地址空间,虚拟地址空间,主存储器地址空间,辅存地址空间 虚拟地址空间:又称虚存空间或虚拟存储器空间,它是应用程序员用来编写程序地址空间,这个地址空间非常大。主存储器地址空间:也称主存地址空间、主存物理空间或实存地址空间辅存地址空间:

16、也就是磁盘存储器地址空间虚拟地址:虚存空间上地址,又称为虚存地址或者虚地址主存地址:又称为主存实地址、主存物理地址、主存储器地址磁盘存储器地址:又称为磁盘地址、辅存地址第37页第37页地址映像:把虚拟地址空间映象到主存地址空间,详细地说,就是把用户用虚拟地址编写程序按照某种规则装入到主存储器中,并建立多用户虚地址与主存实地址之间相应关系。地址变换:在程序被装入主存储器之后,在实际运营时,把多用户虚地址变换成主存实地址(内部地址变换)或磁盘存储器地址(外部地址变换)。第38页第38页4.3 虚拟存储器一、虚拟存储器地址变换 虚拟存储器能够分为三类:段式,页式、段页式1.段式虚拟存储器地址映象和地

17、址变换地址映象办法:每个程序段都从0地址开始编址,长度可长可短,能够在程序执行过程中动态改变程序段长度 第39页第39页4.3 虚拟存储器一、虚拟存储器地址变换1.段式虚拟存储器地址变换 每个程序都用一个段表(通常在主存中)来存储该程序各段装入主存相关信息地址变换办法:由用户号找到基址存储器(CPU内)从基址存储器中读出段表起始地址把起始地址与多用户虚拟地址中段号相加得到段表地址把段表中给出起始地址与段内偏移D相加就能得到主存实地址 第40页第40页4.3 虚拟存储器一、虚拟存储器地址变换1.段式虚拟存储器地址变换地址变换办法图示第41页第41页4.3 虚拟存储器 段式管理主要长处: 程序模块

18、化性能好,各段在功效上是互相独立; 便于程序与数据共享; 程序动态链接比较容易; 便于实现存储保护。地址变换所需时间比较长。 主存空间利用不充足。对辅存(磁盘)管理比较困难。段式管理主要缺点:第42页第42页4.3 虚拟存储器一、虚拟存储器地址变换2.页式虚拟存储器地址映象和地址变换地址映象办法:把虚拟地址空间划分成一个个固定大小块,每块称为一页(Page),把主存储器地址空间也按虚拟地址空间同样大小划分为页。页是一个逻辑上划分,它能够由系统管理软件任意指定。 第43页第43页4.3 虚拟存储器一、虚拟存储器地址变换2.页式虚拟存储器地址映象和地址变换每个程序都用一个页表(通常在主存中)来存储

19、该程序各个虚页装入主存实页位置等相关信息地址变换办法:由用户号找到基址存储器(CPU内)从基址存储器中读出页表基地址Pa把页表基地址Pa与多用户虚拟地址中页号P相加得到页表地址把页表中给出主存实页号p与虚地址中页内偏移D拼接起来就得到主存实地址A 第44页第44页4.3 虚拟存储器第45页第45页4.3 虚拟存储器一、虚拟存储器地址变换2.页式虚拟存储器地址映象和地址变换 页式管理主要长处1、 主存储器利用率比较高 2、 页表相对比较简朴 3、 地址映象和变换速度比较快 4、 对辅存(磁盘存储器)管理比较容易 页式管理主要缺点 1、 程序模块化性能不好 2、 页表很长,需要占用很大存储空间第4

20、6页第46页4.3 虚拟存储器一、虚拟存储器地址变换3.段页式虚拟存储器地址映象和地址变换 其基本思想是对用户本来编写程序虚拟存储空间采用分段办法管理 ,每个程序段分成几种固定大小页。地址变换办法:1.先查段表,得到该程序段页表起始地址和页表长度2.再查页表找到要访问主存实页号3.最后把实页号p与页内偏移d拼接得到主存实地址第47页第47页4.3 虚拟存储器3.段页式虚拟存储器地址映象和地址变换 页式管理主要长处1、 主存储器利用率比较高 第48页第48页第49页第49页 外部地址变换目的是要找到辅存(磁盘存储器)实地址,并且把需要访问那一页或那一个程序段调入到主存储器中。在操作系统中,通常把

21、页面失效当作一个异常故障来处理。 每个用户程序都有一张外页表,虚拟地址空间中每一页或每个程序段,在外页表中都有相应一个存储字。每一个存储字除了磁盘存储器地址之外,至少还包括一个装入位 第50页第50页4.3 虚拟存储器一、虚拟存储器地址变换4.加快地址变换办法 1.目录表基本思想是:压缩页表存储容量,用一个容量比较小高速存储器来存储页表,从而加快页表查表速度。第51页第51页4.3 虚拟存储器一、虚拟存储器地址变换4.加快地址变换办法 2.快慢表 用多用户虚页号同时去查快表和慢表。由于快表查表速度要比慢表快得多,假如在快表中查到与多用户虚地址相等存储字,就马上终止慢表查表过程,并读出该存储字中

22、实页号p送入到主存储器地址存储器中。假如在快表中没有查到,就到存储在主存储器中慢表中去找。假如在慢表中查到了,则把查到实页号p送入主存储器地址存储器,同时,也把这个实页号连同多用户虚地址等信息送入快表中。这时,若快表已满,则要采用某种替换算法,替换掉其中一个不惯用存储字。 第52页第52页4.3 虚拟存储器一、虚拟存储器地址变换4.加快地址变换办法快慢表:快表:TLB(translation Lookaside buffer)高速硬件实现,采用相联访问方式慢表:当快表中查不届时,从主存慢表查找,软件实现快表与慢表也构成一个两极存储系统 第53页第53页4.3 虚拟存储器二、页面替换算法及其命中

23、率1.页面替换发生时间:(问题提出) 当发生页面失效时,要从磁盘中调入一页到主存。假如主存所有页面已经被占用,必须从主存中淘汰掉一个不常使用页面,以便腾出主存空间来存储新调入页面2.评价页面替换算法好坏原则: 一是命中率 二是算法要容易实现 第54页第54页4.3 虚拟存储器二、页面替换算法及其命中率1.几种页面替换算法 1、 随机算法,即RAND算法(Random algorithm)。利用软件或硬件随机数发生器来拟定主存储器中被替换页面。这种算法最简朴,并且容易实现。但是,这种算法完全没有利用主存储器中页面调度情况历史信息,也没有反应程序局部性,因此命中率比较低。2、 先进先出算法,即FI

24、FO算法(First-In First-Out algorithm)。这种算法选择最先调入主存储器页面作为被替换页面。它长处是比较容易实现,能够利用主存储器中页面调度情况历史信息,但是,没有反应程序局部性。由于最先调入主存页面,很也许也是经常要使用页面。 第55页第55页4.3 虚拟存储器二、页面替换算法及其命中率1.几种页面替换算法 3、 近期至少使用算法,即LRU算法这种算法选择近期至少访问页面作为被替换页面。显然,这是一个非常合理算法,由于到当前为止至少使用页面,很也许也是未来至少访问页面。该算法既充足利用了主存中页面调度情况历史信息,又正确反应了程序局部性。但是,这种算法实现起来非常困

25、难。它要为每个页面设置一个很长计数器,并且要选择一个固定期钟为每个计数器定期计数。在选择被替换页面时,要从所有计数器中找出一个计数值最大计数器。因此,通常采用另外一个变通办法,就是下面LRU算法。 第56页第56页4.3 虚拟存储器二、页面替换算法及其命中率1.几种页面替换算法 4、 最久没有使用算法,也称为LRU算法(Least Recently Used algorithm)。这种算法把近期最久没有被访问过页面作为被替换页面。它把LRU算法中要统计数量上“多”与“少”简化成判断“有”与“无”,因此,实现起来比较容易。 5、 最优替换算法,即OPT算法(OPTimal replacemant

26、 algorithm)。最好算法应当是选择未来最久不被访问页面作为被替换页面。这种替换算法命中率一定是最高。这就是最优替换算法,简称OPT算法。 要实现OPT算法,唯一办法是让程序先执行一遍,统计下实际页地址流情况。 第57页第57页4.4 高速缓冲存储器举例阐明: 设有一道程序,有1至5共五页,执行时页地址流(即执行时依次用到程序页页号)为: 2,3,2,1,5,2,4,5,3,2,5,2若分派给该道程序主存有3页,分别采用FIFO和LRU替换算法表示这3页使用和替换过程。阐明: (1)随机算法:用随机数拟定要替换块; (2)FIFO算法:替换最早装入主存页; (3)LRU算法:依据各块使用

27、情况,选择最近至少使用块替换。第58页第58页时间t 1 2 3 4 5 6 7 8 9 10 11 12页地址流 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次2第59页第59页4.3 虚拟存储器第60页第60页4.3 虚拟存储器第61页第61页4.

28、3 虚拟存储器第62页第62页4.3 虚拟存储器LRU和OPT算法是堆栈型算法,FIFO不是堆栈型算法 普通情况,操作系统在失效率较高时会增长分派给某个程序页面,以减少其失效率(即提升命中率)第63页第63页4.4 高速缓冲存储器表:Cache与虚拟存储器主要区别存储系统Cache虚拟存储器要达到目的提升(主存)速度扩大(主存)容量实现办法所有硬件软件为主两级存储器速度比310倍10000倍页(块)大小116字1KB16KB等效存储容量主存储器虚拟存储器透明性系统和应用程序员仅相应用程序员不命中时处理方式等待主存储器任务切换可直接访问均通过第一级CPU对第二级访问可直接访问均通过第一级第64页

29、第64页4.4 高速缓冲存储器一、Cache地址映象与地址变换基本工作原理:当CPU要访问Cache时,送来主存地址放入主存地址存储器。通过主存Cache地址变换部件把主存地址中块号B变换成Cache块号b放入Cache地址存储器中,并且把主存地址中块内地址W直接作为Cache块内地址w装入到Cache地址存储器中。假如变换成功(称为Cache命中),就用所得到Cache地址去访问Cache,从Cache中取出数据送往CPU。假如变换不成功,则产生Cache失效信息,并且用主存地址访问主存储器。从主存储器中读出一个字送往CPU。同时,把包括被访问字在内一整块都从主存储器中读出来,装入到Cach

30、e中去。这时,假如Cache已经满,则要采用某种Cache替换算法把不惯用一块先调入主存储器中本来存储它地方。以便腾出空间来存储新调入块。 第65页第65页4.4 高速缓冲存储器一、Cache地址映象与地址变换第66页第66页4.4 高速缓冲存储器一、Cache地址映象与地址变换地址映象:把存储在主存中程序按照某种规则装入到Cache中,并建立主存地址与Cache地址之间相应关系 地址变换:是指当程序已经装入到Cache之后,在实际运营过程中,把主存地址如何变换成Cache地址。选取地址映象办法考虑主要原因: 地址变换硬件要容易实现, 速度要快 主存空间利用率是否高, 发生块冲突概率要小 第6

31、7页第67页4.4 高速缓冲存储器一、Cache地址映象与地址变换 全相联方式 直接相联 组相联三种地址映象:1. 全相联映象 全相联:主存中任一块能够被放置到Cache中任意一个位置。(主存与缓存分成相同大小数据块) 举例 对比: 阅览室位置 随便坐 特点: 空间利用率最高,冲突概率最低, 实现最复杂。第68页第68页4.4 高速缓冲存储器一、Cache地址映象与地址变换全相联映象方式 :映象规则:主存中任意一块能够映象到Cache中任意一块。假如Cache块数为Cb,主存块数为MB,映象关系共有CbMB种。B(b):块号C:Cache容量M:主存容量 块0 块1 : 块i:块MB-1 块0

32、 块1 :块Cb-1Cache主存储器第69页第69页4.4 高速缓冲存储器一、Cache地址映象与地址变换全相联地址变换 块号 块内地址主存地址 块号 块内地址Cache地址 Bi bi 1 主存块号B Cache块号b 有效位目录表第70页第70页4.4 高速缓冲存储器一、Cache地址映象与地址变换2. 直接映象 直接映象:主存中每一块只能被放置到 Cache中唯一一个位置。 举例 (循环分派) 对比:阅览室位置 只有一个位置可 以坐 特点:空间利用率最低,冲突概率最高, 实现最简朴。第71页第71页4.4 高速缓冲存储器一、Cache地址映象与地址变换映象规则:主存中一块只能映象到Ca

33、che一个特定块中。 计算公式:bB mod Cb 其中:b为Cache块号,B是主存块号,Cb是Cache块数。 整个Cache地址与主存地址低位部分完全相同。第72页第72页4.4 高速缓冲存储器直接相联地址映象主存储器 块0 块1 : 块C/B-1 块C/B 块C/B+1 :块2C/B-1 : 块M/B-C/B 块M/B-C/B+1 : 块M/B-1区0区1区M/C-1 块0 块1 : 块C/B-1cache第73页第73页4.4 高速缓冲存储器一、Cache地址映象与地址变换地址变换过程:用主存地址中块号B去访问区号存储器把读出来区号与主存地址中区号E进行比较 比较结果相等,且有效位为

34、1,则Cache命中。 比较结果相等,有效位为0,表示Cache中这一块已经作废。 比较结果不相等,有效位为0,表示Cache中这一块是空。 比较结果不相等,有效位为1,表示Cache中这一块是有用 第74页第74页4.4 高速缓冲存储器 直接相联地址变换 目录表存储器块失效相等比较区号Ei 块号i 块内地址块号i 块内地址 主存地址Cache地址相等 Ei 1 区号(按地址访问) 有效位访问Cache第75页第75页例3-3 设有一个cache容量为2K字,每个块为16字,求(1) 该cache可容纳多少个块?(2) 假如主存容量是256K字,则有多少个块?(3) 主存字地址有多少位?Cac

35、he 字地址有多少位?(4) 在直接映象方式下,主存中第i块映象到cache中哪一个块中?(5) 进行地址映象时,存储器地址分成哪几段?各段分别有多少位?解:(1) cache中有2048/16=128个块。(2) 主存有256K/16=16384个块。(3)主存:字地址为18位,256K=218字。 cache:字地址为11位,2K=211字。(4) 主存中第i块映象到cache中第 i mod 128个块中。(5) 存储器字地址分成三段:区号、块号、块内字地址。区号长度为18-11=7位,块号为7位。块内字地址为4位。第76页第76页4.4 高速缓冲存储器一、Cache地址映象与地址变换

36、组相联:主存中每一块能够被放置到Cache 中唯一一个组中任何一个位置。 举例 组相联是直接映象和全相联一个折衷3. 组相联映象第77页第77页4.4 高速缓冲存储器一、Cache地址映象与地址变换组相联映象规则 1. 主存与缓存分成相同大小块;2. 主存与缓存分成相同大小组;3. 主存容量是缓存容量整数倍,将主存空间按缓存大小分成区,主存中每一区组数与缓存组数相同。4. 组间直接相联;组内全相联。 思考题: 当组相联映象组内块数大到等于Cache时,就变成什么映象?而当块数小到只有一块时就变成了什么映象?第78页第78页组相联地址映象 区0区Me1组1组0组C/B1 块0 块B1 块B 块2

37、B1 Cache块0块B1 块B 块2B1组1组C/B1组0组C/B(Me1)组C/BMeC/B+1组C/BMe1第79页第79页4.4 高速缓冲存储器一、Cache地址映象与地址变换地址变换过程:用主存地址中组号G按地址访问块表存储器。把读出来一组区号和块号与主存地址中区号和块号进行相联比较。假如有相等,表示Cache命中。假如没有相等,表示Cache没有命中。3. 组相联映象第80页第80页4.4 高速缓冲存储器组相联映象地址转换 相等不等Cache地址区号 组号 组内块号 块内地址主存地址 组号 组内块号 块内地址相联比较区号E 组内块号 组内块号 EiBi bi块表第81页第81页4.

38、4 高速缓冲存储器一、Cache地址映象与地址变换 组相联映象方式长处:块冲突概率比较低,块利用率大幅度提升,块失效率明显减少。 组相联映象方式缺点:实现难度和造价要比直接映象方式高。3. 组相联映象第82页第82页4.4 高速缓冲存储器二、Cache替换算法及其实现随机法:(Random,RAND法) 先进先出法(First-In First-Out,FIFO法) 近期至少使使用办法(Least Recently Used,LRU法) 所要处理问题:当新调入一块,而Cache又已被占满时,替换哪一块?第83页第83页4.4 高速缓冲存储器举例阐明: 设有一道程序,有1至5共五页,执行时页地址

39、流(即执行时依次用到程序页页号)为: 2,3,2,1,5,2,4,5,3,2,5,2若分派给该道程序主存有3页,分别采用FIFO和LRU替换算法表示这3页使用和替换过程。阐明: (1)随机算法:用随机数拟定要替换块; (2)FIFO算法:替换最早装入主存页; (3)LRU算法:依据各块使用情况,选择最近至少使用块替换。第84页第84页时间t 1 2 3 4 5 6 7 8 9 10 11 12页地址流 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*

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论