(七) 高速缓冲存储器(Cache实际上,这是来自法文的一个单词,意思是隐蔽之所或藏东西的地方) 概述
1. 问题的提出
避免 CPU “空等” 现象 CPU 和主存(DRAM)的速度差异
1. 程序访问的局部性
从大量的统计中得到的一个规律是,程序中对于存储空间90%的访问局限于存储空间的10%的区域中,而另外10%的访问则分布在存储空间的其余90%的区域中.这就是通常说的局部性原理.访存的局部性规律包括两个方面:
时间局部性:如果一个存储项被访问,则可能该项会很快被再次访问.
空间局部性:如果一个存储项被访问,则该项及其邻近的项也可能很快被访问. 2. Cache的基本工作原理
Cache通常由两部分组成,块表和快速存储器.其工作原理是:处理机按主存地址访问存储器,存储器地址的高段通过主存-Cache地址映象机构借助查表判定该地址的存储单元是否在Cache中,如果在,则Cache命中,按Cache地址访问Cache.否则,Cache不命中,则需要访问主存,并从主存中调入相应数据块到Cache中,若Cache中已写满,则要按某种算法将Cache中的某一块替换出去,并修改有关的地址映象关系.
从这个工作原理我们可以看出,它已经涉及到了两个问题.首先是定位,然后是替换的问题.
Cache的存在对程序员是透明的.其地址变换和数据块的替换算法均由硬件实现.通常Cache被集成到CPU内以提高访问速度.
3. Cache和主存之间的映射方式
因为处理机访问都是按主存地址访问的,而Cache的空间远小于主存,如何知道这一次的访问内容是不是在Cache中,在Cache中的哪一个位置呢? 这就需要地址映象,即把主存中的地址映射成Cache中的地址.让Cache中一个存储块(空间)与主存中若干块相对应,如此,访问一个主存地址时,就可以对应地知道在cache中哪一个地址了.地址映象的方法有三种:直接映象,全相联映象和组相联映象.
直接映象就是将主存地址映象到Cache中的一个指定地址.任何时候,主存中存储单元的数据只能调入到Cache
中的一个位置,这是固定的,若这个位置已有数据,则产生冲突,原来的块将无条件地被替换出去.
全相联映象就是任何主存地址可映象到任何Cache地址的方式.在这种方式下,主存中存储单元的数据可调入到Cache中的任意位置.只有在Cache中的块全部装满后才会出现块冲突.
组相联映象指的是将存储空间的页面分成若干组,各组之间的直接映象,而组内各块之间则是全相联映象. 4. Cache中主存块的替换算法
在直接映象方式下,不存在块替换的算法,因为每一块的位置映象是固定的,需要哪一块数据就可直接确定地将该块数据调入上层确定位置.而其他两种映象就存在替换策略的问题,就是要选择替换到哪一个Cache块.即替换算法.
思想 优点 缺点 随机算法用软的或硬的随机数产生器产没有利用上层存储器使用的\历史信息简单,易于实现 RAND 生上层中要被替换的页号 \没有反映等程序局部性,命中率低. 先进先出选择最早装入上层的页作为被实现方便,利用了主存历不能正确反映程序局部性原理,命中率FIFO 替换的页 史的信息 不高,可能出现一种异常现象. 比较正确反映程序局部近期最少选择近期最少访问的页作为被性,利用访存的历史信实现较复杂 使用法LRU 替换的页 息,命中率较高 优化替换命中率最高,可作为衡量将未来近期不用的页换出去 不现实,只是一种理想算法 算法OPT 其他替换算法的标准 5. Cache写策略 对Cache的写操作,情况比读操作要复杂一些.由于写入Cache时,并没有写入主存,因此就出现Cache和主存数据不一致的情况.如何处理Cache和主存不一致的方法就称为更新策略. 更新策略 思想 优点 缺点 是指在CPU执行写操作时,信息只写入有利于省去许多将Cache中,仅当需要替换时,才将改写过的需设修改位增加Cache的写回法 中间结果写入主存Cache块先送回主存(写回),然后再调块复杂性 的无谓开销. (设置dirty位) 在写操作时,将数据同时写入Cache和主为了写中间结果浪费了全写法(写直达法) 实现开销小,简单 存 不少时间 另外,当写不命中时(也就是写Cache块时,这块早被人替换出去而在Cache中找不到时)是不是要把这块再取回Cache中,有两个解决方法:
? 不按写分配法,就是直接写到主存里,不再把该地址对应的块调回Cache中. ? 按写分配法,就是写到主存,而且把这一块从主存中调入到Cache. 一般写回法用按写分配法,全写法则采用不按写分配. (八) 虚拟存储器
1. 虚拟存储器的基本概念
虚拟存储器是主存的扩展,虚拟存储器的空间大小取决于计算机的访存能力而不是实际外存的大小,实际存储空间可以小于虚拟地址空间.从程序员的角度看,外存被看作逻辑存储空间,访问的地址是一个逻辑地址(虚地址),虚拟存储器使存储系统既具有相当于外存的容量又有接近于主存的访问速度.
虚拟存储器的访问也涉及到虚地址与实地址的映象,替换算法等,这与Cache中的类似,前面我们讲的地址映象以块为单位,而在虚拟存储器中,地址映象以页为单位.设计虚拟存储系统需考虑的指标是主存空间利用率和主存的命中率.
虚拟存储器与Cache存储器的管理方法有许多相同之处,它们都需要地址映象表和地址变换机构.但是二者也是不同的.
虚拟存储器的三种不同管理方式:按存储映象算法,分为段式,页式和段页式等,这些管理方式的基本原理是类似的.
2. 页式虚拟存储器
页式管理:是把虚拟存储空间和实际空间等分成固定大小的页,各虚拟页可装入主存中的不同实际页面位置.页式存储中,处理机逻辑地址由虚页号和页内地址两部分组成,实际地址也分为页号和页内地址两部分,由地址映象机构将虚页号转换成主存的实际页号.
页式管理用一个页表,包括页号,每页在主存中起始位置,装入位等.页表是虚拟页号与物理页号的映射表.页式管理由操作系统进行,对应用程序员的透明的. 3. 段式虚拟存储器
段式管理: 把主存按段分配的存储管理方式.它是一种模块化的存储管理方式,每个用户程序模块可分到一个段,该程序模块只能访问分配给该模块的段所对应的主存空间.段长可以任意设定,并可放大和缩小.
系统中通过一个段表指明各段在主存中的位置.段表中包括段名(段号),段起点,装入位和段长等.段表本身也是一个段.段一般是按程序模块分的. 4. 段页式虚拟存储器
段页式管理:是上述两种方法的结合,它将存储空间按逻辑模块分成段,每段又分成若干个页,访存通过一个段表和若干个页表进行.段的长度必须是页长的整数倍,段的起点必须是某一页的起点. 5. TLB(快表)
在虚拟存储器中进行地址变换时,需要虚页号变换成主存中实页号的内部地址变换,这一般通过查内页表实现.当表中该页对应的装入位为真时,表示该页在主存中,可按主存地址问主存;如果装入位为假时,表示该页不在存储器中,就产生页失效中断,需从外存调入页.
中断处理时先通过外部地址变换,一般通过查外页表,将虚地址变换为外存中的实际地址,到外存中去选页,然后通过I/0通道调入内存.当外存页面调入主存中时还存在一个页面替换略的问题.
提高页表的访问速度是提高地址变换速度的关键.因为,每次访存都要读页表,如果页存放在主存中,就意味着访存时间至少是两次访问主存的时间,这样查表的代价大大.只有内部地址变换速度提高到使访问主存的速度接近于不采用虚拟存储器时的访主存速度时,虚拟存储器才能实用.
根据访存的局部性,表内各项的使用的概率不是均匀分布的.在一段时间内,可能只用表中的很少几项,因此应重点提高使用概率高的这部分页表的访问速度,可用快速硬件构成全表小得多的部分表格,而将整个表格放在主存中,这就引出了快表和慢表的概念和技术.这样,虚地址到实地址的变换方法如后图所示.
查表时,根据虚页表同时查找快表和慢表,当在快表中查到该虚页号时,就能很快找到对应的实页号,将其送入主存实地址寄存器,同时使慢表的查找作废,这时主存的访问速度没降低多少.
如果在快表中查不到,则经过一个访主存的时间延迟后,将从慢表中查到的实页送入实地址寄存器,同时将此虚页号和对应的实页号送入快表,这里也涉及到用一个替换算法从快表中替换出一行.
快表的存在对所有的程序员都是透明的.