文档介绍：(1)Cache从主存读取数据块时有三种方式:需要时读取、预读取和选择读取。这三种方式各有优缺点,请注意比较。课本中提到"共享的数据放在主存中比放在Cache中合适,特别是在多处理机系统中",因为共享的数据经常由别的处理过程改写,若放到cache中,则经常涉及到数据的一致性问题,因此放在主存中可保证其单一性,不致发生数据一致性错误的问题。在层次式的存储体系中,访问某层存储器的内容时将从该层取数据块层层复制到上层存储器中,而上层的存储器容量总比下层的少,则在复制到上层时,就会发生替换掉原有数据块的问题。若被替换的块中有新写入的数据(如计算结果)则这些数据还得先写到下层存储器的相应块中,这就涉及更新策略。(2)在直接映象方式下,不存在块替换的算法,因为每一块的位置映象是固定的,需要哪一块数据就可直接确定地将该块数据调入上层确定位置。而其他两种映象就存在替换策略的问题,就是要选择替换到哪一个Cache块。即替换算法。思想优点缺点随机算法RAND用软的或硬的随机数产生器产生上层中要被替换的页号简单、易于实现没有利用上层存储器使用的"历史信息",没有反映等程序局部性,命中率低。先进先出FIFO选择最早装入上层的页作为被替换的页实现方便,利用了主存历史的信息不能正确反映程序局部性原理,命中率不高,可能出现一种异常现象。近期最少使用法LRU选择近期最少访问的页作为被替换的页比较正确反映程序局部性,利用访存的历史信息,命中率较高实现较复杂优化替换算法OPT将未来近期不用的页换出去命中率最高,可作为衡量其他替换算法的标准不现实,只是一种理想算法FIFO替换方式的块分配操作示意图 一个容量为4个块的全相联Cache,假定访问的地址块号序列为:2,11,2,9,7,6,4,3,在先进先出替换方式下,队列中的变化情况如下:22222666—1**********———99993————777712345678211297643访问顺序:地址块号:操作状态:调进调进命中调进调进替换替换替换LRU替换方式的块分配操作 一个容量为4个块的全相联Cache,假定访问的地址块号序列为:2,11,2,9,7,6,4,3,在最久未使用替换方式下,队列中的变化情况如下:22222244—**********———99993————777712345678211297643访问顺序:地址块号:操作状态:调进调进命中调进调进替换替换替换FIFO块替换中出现的颠簸现象 同样对于上述的4个块的全相联Cache,假定访问的地迁块号字列为:2,11,9,7,6,2,11,9,在先进先出替换方式下,队列中的变化情况如下:22226666—**********——99991111———77779123456782119762119访问顺序:地址块号:操作状态:调进调进调进调进替换替换替换替换LUR算法的实现过程(1)计数器法:每个块一个计数器,定时时间间隔计数一次,块数据被访问时计数器清零。计数值表示上一次访问后经过的时间,替换选择计数值最大的块替换出去。由于计数器存在最大长度,计数满后溢出,造成时间最小。因此,改进方法就是采用相对计数值。例如,当Cache命中时,其他非命中的块的计数值如果小于命中块的计数值就加1,计数值较大的不变。命中块的计数值清零。LUR算法的实现过程(2)寄存器栈法:一套寄存器,存放每个块的记录。最近使用过的块始终保持在栈的顶部,最久未使用过的块放在栈的底部。块访问时,从栈顶向栈底顺序查找该块的寄存器内的标识,如果找到,将该寄存器抽出来放在栈顶,如果没有找到,栈顶压入该标识的寄存器,栈底的标识出栈。寄存器栈法示意图 11,6访问时:2**********找到21197662119没找到