3第三讲_存储.ppt

* * * * * * * * * * * * * 直接映射的仿真 假设内存M=16 字节, 块B=2 字节/块, S=4 组, E=1 路/组 内存访问的地址流 (reads): 0 [00002], 1 [00012], 13 [11012], 8 [10002], 0 [00002] x t=1 s=2 b=1 xx x 1 0 m[1] m[0] v tag data 0 [00002] (miss) (1) 1 0 m[1] m[0] v tag data 1 1 m[13] m[12] 13 [11012] (miss) (3) 1 1 m[9] m[8] v tag data 8 [10002] (miss) (4) 1 0 m[1] m[0] v tag data 1 1 m[13] m[12] 0 [00002] (miss) (5) 0 M[0-1] 1 1 M[12-13] 1 1 M[8-9] 1 1 M[12-13] 1 0 M[0-1] 1 1 M[12-13] 1 0 M[0-1] 1 * 5.6.3 替换算法和更新策略 CPU用主存地址访问多级存储系统，对于缓存“不命中”的情况，必须在缓存中选择一个即将被置换的旧块，然后用新块置换旧块。 对于直接映像方式来说，只有惟一的一种选择。全相联映像和组相联映像方式则存在多中选一的问题。 常用的替换算法有以下4种： 随机替换算法 先进先出（First In First Out, FIFO）算法 使用次数最少（Least Frequently Used, LFU）算法：将迄今为止使用次数最少的块作为被替换的旧块。LFU算法需要统计每一块被使用的次数，需要较多的硬件资源，效果强于前者。 近期最少使用（Least Recently Used, LRU）算法：将迄今为止最常时间没有被访问过的块作为被替换的候选块。LRU算法是目前效果最好的算法，其硬件实现也不复杂。 5.6 高速缓冲存储器 * 5.6.3 替换算法和更新策略 LRU算法的硬件实现示意图。 5.6 高速缓冲存储器 设一个寄存器堆，每个寄存器中存放一个块号，寄存器的地址表示该块的优先级别。地址0中的块号级别最高，表示近期刚刚被访问过的块；地址n中的块号级别最低，表示最长时间没有被访问过的块，是即将被换出的候选块。当缓存中某块被访问时，根据其块号查出其在寄存器堆中的地址k，然后令寄存器堆从地址0到地址k执行一次循环移位，改变各块的优先级。当前被访问块的优先级被提升到最高，其余各块的优先级递降一级。 * 5.6.3 替换算法和更新策略 主存和缓存内容的一致性：缓存中的块是主存中某块的副本，应当时时保持一致。当CPU执行写操作时，是否应当同时写入主存和缓存呢？ 更新策略： 写直达（Write Through）法：CPU执行写操作时，必须把数据同时写入主存和缓存。保证了主存与缓存数据的一致性，但增加了访问主存的次数，降低了存取速度。 拖后写（Write Back）法：CPU执行写操作时，当时只把数据写入缓存而不写入主存，写入主存的时机拖到以后再说。目的是为了减少访问主存的次数，但同时还得保持主存与缓存数据的一致性，为此需要增添一些硬件设施和合理的更新策略。 5.6 高速缓冲存储器 * 5.6.3 替换算法和更新策略 为了实现拖后写，需要在块标记中再增加1个“已修改”标志位。在执行写操作时，需要将该块的“已修改”标志位置1，表示此块的内容已经和主存不一致。 当有另外的CPU或外设执行读操作时，需要根据访问主存的地址检查该块是否在缓存中。如果在缓存中，还要检查该块的“已修改”标志是否为1，若为1则需要暂停此读操作，将此块写回主存后再启动被暂停的读操作。 当缓存中某块被选做替换块时，先检查其“已修改”标志是否为1，若为1则需要先将此旧块整块写回主存，然后再换入新块。 5.6 高速缓冲存储器 * 5.7.1 虚拟存储器的基本概念 虚拟存储器：面向应用程序员提供一个虚拟存储空间，该空间远大于实际的主存空间。用户编程的地址称为虚地址或逻辑地址，而实际的主存地址则称为实地址，虚地址远大于实地址。 虚拟存储器的物理基础：主存和辅存。 虚拟存储器的工作原理：与缓存相似，将主存和辅存划分成若干块，主存中每一块都是辅存中对应块的副本。程序和数据初始状态在辅存中，在CPU用到它们时才调入主存，如果主存已被装满，则采用适当的替换算法在主存和辅存之间交换。 根据块的划分方法，虚拟存储器分为： 段式虚拟存储器； 页式虚拟存储器； 段页式虚拟存储器。 5.7 虚拟存储器 * 5.7.1 虚拟存储器的基本概念 缓存和虚存的比较 5.7 虚拟存储器 * 5.7.2 段式虚拟存储器 以段为单位在主存和辅存之间进行信息交换。 段的大小