Cache 的替换算法中，（ ）算法计数器位数多，实现困难。

Question

A.FIFO
B.LFU
C.LRU
D.RAND

Answer 1

【答案】：C
最常用的Cache 的替换算法有三种：（1）随机算法。这是最简单的替换算法。随机法完全不管cache块过去、现在及将来的使用情况，简单地根据一个随机数，选择一块替换掉。（2）先进先出（First In and First Out，FIFO）算法。按调入cache的先后决定淘汰的顺序，即在需要更新时，将最先进入cache的块作为被替换的块。这种方法要求为每块做一记录，记下它们进入cache的先后次序。这种方法容易实现，而且系统开销小。其缺点是可能会把一些需要经常使用的程序块（如循环程序）替换掉。（3）近期最少使用（Least Recently Used，LRU）算法。LRU算法是把CPU近期最少使用的块作为被替换的块。这种替换方法需要随时记录cache中各块的使用情况，以便确定哪个块是近期最少使用的块。LRU算法相对合理，但实现起来比较复杂，系统开销较大。通常需要对每一块设置一个称为"年龄计数器"的硬件或软件计数器，用以记录其被使用的情况。