6．4．3　高速缓存的替换算法

6．4．3　高速缓存的替换算法

当要从主存调入一个块到Cache中时，经常会出现该块所映射到的Cache块位置（一个或一组）已经被占用的情况。这时，需要选择其中的某一块，用新调入的块取而代之。那么应如何选择这个被替换的块呢？ 这就是替换算法要解决的问题。

替换算法和映射方式有关，直接映射方式不需要替换算法；在全相联映射方式下，由于存储器任何一块数据都可以调入Cache中任意一块位置，因此替换算法比较复杂；在组相联映射方式下，由于组内采用全相联映射方式，因此组内需要使用替换算法。

常用的替换算法有FIFO 算法、随机替换算法、LRU 算法。

1．FIFO 算法

FIFO（First In First Out）算法是一种先进先出替换算法，其算法思想是将同一组中最先调入Cache中的块替换出去。这种方法实现容易，开销较小。缺点是一些频繁使用的块也会被替换出去，而频繁调入/调出又增加了开销。

2．随机替换算法

随机替换算法就是随机选取被替换的块。其优点是简单，易于用硬件实现，但这种方法没有考虑Cache块过去被使用的情况，反映不了程序的局部性，所以命中率比较低。

3．LRU 算法

LRU（Least Recently Used）算法即最近最少使用算法，这是一种最常用的替换算法。这种算法的思想是把一组中近期最少使用的块替换出去。这种方法所依据的是程序的局部性原理的一个推论：近期刚用过的块很可能马上要再用到，因此最久没用过的块就是最佳的被替换者。LRU 能较好地反映程序的局部性原理，因而命中率较高，但必须记录组中各块的使用情况，这样才能确定出近期最少使用的块，硬件成本比较高。

方法：每行设置一个计数器，每命中一次清“0”，其他计数器加“1”。需替换时，比较各计数器值，将最大值的行换出。