您现在的位置:首页 > >

4 计算机组成原理第三章 存储系统 高速缓冲存储器 虚拟存储器

发布时间:



文章目录
1 局部性原理性能分析2 Cache工作原理(简易版)3 地址映射4 替换算法4.1 替换算法(十进制)举例4.2 Cache工作原理(加强版)4.2.1写策略-命中4.2.2 写策略-未命中
4.3 替换算法(二进制)例题4.4 Cache工作原理(高配版)4.5 Cache例题小结

5 虚拟存储器5.1 页式虚拟存储器5.2 段式虚拟存储器5.3 段页式虚拟存储器5.4 快表TLB5.5 页式虚拟存储器-例题









1 局部性原理性能分析

空间局部性:在最*的未来要用到的信息(指令和数据),很可能与现在正在使用的信息在存储空间上是邻*的时间局部性:在最*的未来要用到的信息,很可能是现在正在使用的信息

高速缓冲技术就是利用程序访问的局部性原理,把程序中正在使用的部分存放在一个高速的,容量较小的Cache中,使CPU访存操作大多数针对Cache进行,从而大大提高程序的执行速度


2 Cache工作原理(简易版)

Cache工作原理类似操作系统分页存储快表机制

CPU与Cache之间的数据交换以字为单位,而Cache与主存之间的数据交换则以Cache块为单位



    命中率H:CPU欲访问的信息已在Cache中的比率
    设一个程序执行期间,Cache的总命中次数为Nc,访问主存的总次Nm
    则H=Nc/Nc+Nm缺失率M=1-H设tc为命中时的Cache访问时间,tm为未命中时的访问时间
    Cache?主存系统的*均访问时间Ta为Ta=Htc+(1-H)tm


假设Cache的速度是主存的5倍,且Cache的命中率为95%,则采用Cache后,存储器性能提高多少(设Cache和主存同时被访问,若Cache命中则中断访问主存)?







若采用先访问Cache再访问主存的方式:



不命中时,访问cache耗时为t,发现不命中后再访问主存耗时为5t,总耗时为6t
故系统的*均访问时间为 T2 = 0.95×t+0.05×6t = 1.25t
故性能为原来的 5t / 1.25t = 4倍,即提高了3倍。





Cache三大核心问题:



    主存中的块放到Cache中哪个位置?
    (1)空位随意放:全相联映射
    (2)对号入座:直接映射
    (3)按号分组,组内随意放:组相联映射



    对于(1),Cache满了如何处理?对于(2)(3),对应位置被占用如何处理?
    随机(RAND)算法、先进先出(FIFO)算法、*期最少使用(LRU)算法、最不经常使用(LFU)算法。



    修改Cache中的内容后,如何保持主存中相应内容的一致性?


命中
全写法(write-through
写回法(write-back




不命中
写分配法(write-allocate
非写分配法(not-write-allocate




3 地址映射


Cache高三位确定行号,低6位确定行内地址,对应这行中的哪个单元
主存:



低的6位表示每一行中的具体哪个位置,对应这行的哪个单元
中的3位对应Cache的行号
高的19位就是主存比Cache多出来的地址位数





    全相联映射


主存中内容可以往Cache中随意放,但需要设置一个有效位,如果是0表示空闲,如果是1表示已经占满;
根据有效位可以判断是否放了东西,根据有效位后的标号对应主存的地址(主存的地址高位作为一个标记,存放在Cache相应的单元)



Cache需要保存地址高位,绿+蓝都要存






    直接映射


由于主存中多块可以放在Cache中同一位置,为了区分具体来自主存中哪一位置,把主存中的块存过去后,立刻把主存地址高位存到对应的Cache行,作为标记项



Cache需要保存地址高位,一一对应的无需保存,存绿






    组相联映射:按号分组,组内任意放(综合了上面两者优势)


高的两位做组号,0 1对应0组(高两位00) ,2 3对应1组(高两位01)…




    三种方式地址映射





有效位告诉机器此块数据要使用,不能被其他数据覆盖(Cache中只要放了数据就置有效位1)
标记位告诉机器,Cache中数据来自主存具体哪一位置




4 替换算法

    随机算法(RAND):随机地确定替换的Cache块。它的实现比较简单,但没有依据程序访问的局部性原理,故可能命中率较低。先进先出算法(FIFO):选择最早调入的行进行替换。它比较容易实现,但也没有依据程序访问的局部性原理,可能会把一些需要经常使用的程序块(如循环程序)也作为最早进入Cache的块替换掉。*期最少使用算法(LRU):依据程序访问的局部性原理选择*期内长久未访问过的存储行作为替换的行,*均命中率要比FIFO要高,是堆栈类算法。
    LRU算法对每行设置一个计数器,Cache每命中一次,命中行计数器清o,而其他各行计数器均加1,需要替换时比较各特定行的计数值,将计数值最大的行换出。最不经常使用算法(LFU):将一段时间内被访问次数最少的存储行换出。每行也设置一个计数器,新行建立后从0开始计数,每访问一次,被访问的行计数器加1,需要替换时比较各特定行的计数值,将计数值最小的行换出。


4.1 替换算法(十进制)举例


说明:
直接映射:



(1)主存块号/总块数 余数→Cache块号
(2)商→对应的标记位



访问4,6号,由于Cache为空,未命中,标记置为0,再访问12,对应Cache中4号单元,虽然有效位1,但是标记位0与12除8商1不一样,则发生替换,12替换4,并把标记位改1,未命中访问4未命中,4号单元标记位改0,访问8…
每次访问一个单元,用商更新一下被访问的标记位



FIFO



每新进来一个元素,先往下放,如果之前有元素,就把之前有的元素往上抬,则下面的元素始终是新放入的,往上抬时,自然而然替换了
访问第四个4时,因为里面有4和12,命中,访问接下来的8把最上面12替换出去…






LRU:



把即将要替换的放上面,把最*使用过的放下面
访问12时,12根4相比,是刚刚使用的,把12放下面,接下来访问4,12是最*不太用的,往上抬,且4命中;访问8时,8往下放,替换12…





4.2 Cache工作原理(加强版)


4.2.1写策略-命中

    全写法(写直通法,write-through):当CPU对Cache写命中时,必须把数据同时写入Cache和主存,一般使用写缓冲(write buffer)写回法write-back):当CPU对Cache写命中时,只修改Cache的内容,而不立即写入主存,只有当此块被换出时才写回主存


4.2.2 写策略-未命中

    写分配法write-allocate):把主存中的块调入Cache,在Cache中修改。
    搭配写回法使用。非写分配法not-write-allocate):只写入主存,不调入Cache。
    搭配全写法使用。



4.3 替换算法(二进制)例题

设主存地址空间大小为1KB,按字节编址,Cache由8个块构成,每个Cache块大小为16B,CPU依次访问以下地址:0001001110、1001110010、0001001111、0011000010、0101001000、1011110010、1111010000、0011001001(十进制为78、626、79、194、328、754、976、201),求:


(1)假设地址映射方式为全相联映射,在采用FIF0、LRU、LFU替换算法时,分别求Cache命中次数。



首先分析地址结构:



访问0001001110时,有效位由0改为1,标记位就是地址前六位000100
访问1001110010时,有效位由0改为1,标记位就是地址前六位100111
访问0001001111时,标记位地址前六位000100,已在Cache中,命中,或者用十进*嵌龋64~79为一块,访问78,再访问79,命中(调入的一块同标记位的地址,而不是一个地址)



全相联模式下,可能不会发生替换,Cache是一点一点用完





(2)假设地址映射方式为直接映射,求Cache命中次数。



首先分析地址结构:



访问0001001110时,由100可知放在Cache中4号块,把标记置为000,有效位1
访问1001110010时,由111可知放在Cache中7号块,把标记置为100,有效位1
访问0001001111时,由100可知放在Cache中4号块,此时有效位1,Cache标记位000与当前地址标记位000同,命中
访问0011000010时,由100可知放在Cache中4号块,此时有效位1,Cache标记位001与当前地址标记位000不同,未命中,替换,把001替换000




直接映射:对号入座→有冲突直接替换,不涉及替换策略





首先分析地址结构:



访问0001001110时,由组号00可知放在Cache中0号块,把标记置为0001,有效位1,在组内采用全相联映射,放0号组的1号块和2号块都可以,假设放在1号块访问1001110010时,由11可知放在Cache中3号组,把标记置为1001,有效位1,访问0001001111时,由00可知放在Cache中0号组,此时有效位1,Cache标记位0001与当前地址标记位0001同,命中访问0011000010时,由00可知放在Cache中0号组,此时有效位1,Cache标记位0011与当前地址标记位0001不同,未命中,把它放在0组中的2号块(1号块已放了)访问0101001000时,由00可知放在Cache中0号组,第0组已满,但当前标记与Cache两个标记都不同,需要替换,


若采用FIFO(替换最早调入的):最早调入的块标记是0001,故替换之。
若采用LRU(替换最*未使用的):刚用过0011,故替换0001
LFU(比较次数,替换使用次数最少的)






(4)假设其它配置同(3),采用写回法和直写法时,Cache的总容量分别为多少?




标记项:有效位1位固定,标记位由地址映射方式决定,维护位由替换算法决定,替换位由替换策略决定



4.4 Cache工作原理(高配版)


4.5 Cache例题小结


5 虚拟存储器



虚拟存储器是一个逻辑模型(关注功能,不关注实现)功能:用户给出一个地址,叫做虚地址或逻辑地址,虚拟存储器要给出该地址对应的数据。实现:由辅助硬件将虚地址映射到主存当中的某个单元,主存单元地址称为实地址物理地址

5.1 页式虚拟存储器

虚拟空间与主存空间都被划分成同样大小的页,主存的页称为实页,虚存的页称为虚页。



虚地址到物理地址映射过程:



5.2 段式虚拟存储器

段式虚拟存储器中的段是按程序的逻辑结构划分的,各个段的长度因程序而异。虚拟地址分为两部分:段号和段内地址。段表:每一行记录了与某个段对应的段号、装入位、段起点和段长等信息。
由于段的长度可变,所以段表中要给出各段的起始地址与段的长度。


地址映射过程:



5.3 段页式虚拟存储器

把程序按逻辑结构分段,每段再划分为固定大小的页,主存空间也划分为大小相等的页,程序对主存的调入、调出仍以页为基本传送单位。每个程序对应一个段表,每段对应一个页表。虚拟地址:段号+段内页号+页内地址

5.4 快表TLB

页表、段表存放在主存中,收到虚拟地址后要先访问主存,查询页表、段表,进行虚实地址转换。放在主存中的页表称为慢表(Page)。提高变换速度→用高速缓冲存储器存放常用的页表项→快表(TLB


5.5 页式虚拟存储器-例题



地址变换第一步,在于分析地址结构
标记对应虚页号,页框对应实页号
有效位0,快表未命中,接下来查询页表,若命中,页表完成虚实转换,若未命中,主存中调出来



实页号与虚页号相互替换,页内地址保持不变


热文推荐
猜你喜欢
友情链接: 医学资料大全 农林牧渔 幼儿教育心得 小学教育 中学 高中 职业教育 成人教育 大学资料 求职职场 职场文档 总结汇报