替换算法、写策略、数据读取

Cache的规模远比主存储器要小，所以Cache的命中率不可能达到100%，在Cache访问不命中的时候，主存储器中相应的存储块就必须被装入Cache行，这时就需要将某一Cache行中原来的数据被替换掉。当Cache使用组相联策略或者全相联策略时，主存中的一个数据块可能对应于多个Cache行，这就需要一个替换算法来决定使用哪个Cache行来缓存这个数据块，常用的替换算法包括：

●最近最少使用算法LRU：替换在Cache中驻留时间最长且未被引用的块。

●先进先出算法FIFO：替换在Cache中驻留时间最长的块。

●最不经常使用算法LFU：替换在Cache中被引用次数最少的块。

●随机替换算法：随机替换Cache中的一个块，不考虑以前的使用情况。

这几种算法中，LRU算法是理论上替换效果最好的一种算法，但是在全相联时实现比较复杂，所以在全相联Cache中经常使用FIFO或LFU算法来替代。对于组相联策略Cache，尤其在组的规模比较小，比如二路或四路组相联时，用硬件实现LRU算法比较容易，使用LRU算法是一种非常普遍的做法。

从功能上来讲，Cache主要用来提高存储系统提供数据的能力，减小处理器从主存储器中读取数据带来的时延。同时，Cache对于存储系统接受数据的能力也能够有所改善，也就是说，适当的写策略能够降低处理器向存储系统写数据时的写时延。常见的写策略有如下三种。

●写直达（或写通过，Write Through）：每次对主存储器的读写都直接“穿过”Cache

的缓冲而写入到主存储器中，同时对Cache中的内容也做相应更新。写直达的写策略能够保证主存储器中的数据块总是有效的，避免无效的主存储器数据块造成的数据不一致。但是写直达的写策略在每次写入数据时都要操作主存储器，等待时间长，总线占用多，效率比较低。

●写回（Write back）：与写直达策略相反，写回策略充分利用Cache的缓冲能力，将对存储系统的写操作限制在对Cache的写操作，借以减少对主存储器操作的次数，减少对总线的占用，提高存储系统的效率。写回策略的基本思想是每次对存储系统的写都只对Cache行进行，并在写入完成之后对Cache行设置修改标志。当设置了修改标志的Cache行被替换出Cache时，再真正将数据写入到主存储器中。实验表明，写回策略能够将处理器与主存储器的通信量减少到十几分之一的水平上，大大提高了存储系统的效率。但是写回策略会造成一段时间内主存储器中的数据块是无效的，这时就需要更加复杂的一致性协议来保证数据访问的正确性，实现的电路也更加复杂。(www.xing528.com)

●写一次（Write Once）：写一次策略是写直达和写回策略的一种综合，其基本思想是对于一个Cache行的第一次写操作采用写直达策略，而其后的写操作采用写回策略。写一次策略能够结合写直达和写回策略的优点，提高存储系统的效率，并在一定程度上减小写回策略带来的一致性协议开销。

在实际的分层存储器系统中，通常会综合使用这三种不同的写策略，使它们能够在不同层次、不同用户和不同规模的缓存条件下互相补充，提高存储系统的访问性能。

从读取方式上来区分，Cache可以被分为贯穿读出（Look through，又称通视）和旁路读出（Look aside，又称旁视）两种读取方式（见图5-5）。

图5-5 贯穿读出和旁路读出

a）贯穿续出 b）旁路缓出

在贯穿读出的Cache中，处理器从存储系统中读取数据时总是先访问Cache，如果Cache命中，则不启动主存储器的访问周期，直接从Cache中读取数据。只有当Cache不命中时，主存储器访问周期才被启动，从主存储器中读入数据给处理器并填充Cache。与之相反，在旁路读出的Cache中，如果处理器要从存储系统中读取数据，则Cache控制器会同时启动对Cache和主存储器的访问。当Cache不命中时，数据被从主存储器中读出并填充Cache。当Cache命中时，Cache中的数据被读出，同时主存储器的访问将被Cache控制器中止。

贯穿读出和旁路读出两种读出方式各有优缺点。对于贯穿读出来讲，当Cache命中时，Cache控制器就不再需要启动主存储器的访问周期，从而节省了主存储器的访问带宽。但是当Cache不命中时，Cache控制器需要等到确认了Cache不命中之后才启动主存储器的访问，浪费了一段时间。而旁路读出刚好相反，当Cache不命中时，主存储器读周期的提前启动使得主存储器中存储的数据能够更早地送到处理器并填充Cache。但是当Cache命中时对主存储器无用的访问则无谓地占用了总线，浪费了宝贵的存储器带宽。在Pentium及其后的X86系列微处理器中大多采用贯穿读出（Look through）方式。