当CPU用一个主存地址访问多级存储系统时，对于Cache来说必然存在“命中”或“不命中”两种可能性。对于“不命中”的情况，必须用一个适当的方法在Cache中选择一个即将被置换的旧块，然后用新块置换旧块，这称为替换策略或替换算法。对于直接映射方式来说，可以作为被置换的旧块只有唯一的一个，只有唯一的一种选择。全相联映射和组相联映射方式则存在多中选一的问题，常用的替换策略有以下3种。
1.先进先出（FIF0）策略
FIFO（First In First Out）策略总是把一组中最先调入Cache的字块替换出去，它不需要随时记录各个字块的使用情况，所以实现容易，开销小。缺点是此策略的效果不佳。
2.使用次数最少（LFU）策略
LFU（Least Frequently Used）策略算法是将迄今为止使用次数最少的字块作为被替换的旧块。LFU算法需要统计每一块被使用的次数，需要较多的硬件资源，效果比FIFO策略好。
3.近期最少使用（LRU）策略(www.xing528.com)
LRU（Least Recently Used）策略是把一组中近期最少使用的字块替换出去，这种替换策略需随时记录Cache中各个字块的使用情况，以便确定哪个字块是近期最少使用的字块。LRU替换策略的平均命中率比FIFO和LFU要高，并且当分组容量加大时，能提高该替换策略的命中率。
实现LRU的一种方法是，把组中各块的使用情况记录在一张表上，如图3-23所示，并把最近使用过的块放在表的最上面，设组内有8个信息块，其地址编号为0，1，…，7。当要求替换时，首先更新7号信息块的内容。如要访问7号信息块，则将7写到表的顶部，其他号向下顺移。接着访问5号信息块，如果此时命中，不需要替换，也要将5移到表的顶部，其他号向下顺移。6号数据块是以后要首先被替换的。
实现LRU策略的另一种方法是，对Cache存储器中的每一个字块都附设一个计数器，记录其被使用的情况。每当Cache中的一块信息被命中时，比命中块计数值少的信息块的计数器均加1，而命中块的计数器则清0。显然，采用这种计数方法，各信息块的计数值总是不相同的。一旦不命中的情况发生，新信息块就要从主存调入Cache，以替换计数值最大的那片存储区。这时，新信息块的计数值为0，而其余信息块的计数值均加1，从而保证了那些活跃的信息块（即经常被命中或最近被命中的信息块）的计数值要小，而近来越不活跃的信息块的计数值越大。这样，系统就可以根据信息块的计数值来决定先替换谁。
图3-23 LRU算法替换登记表
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
