扫一扫二维码
进群一起备考
查看更多
当前 - 选择题 - 存储器系统困难
单选题
2016年5月第13题
困难
单选题
2016年5月第13题
#第二版教材
#了解即可
Cache 的替换算法中，（LFU）算法计数器位数多，实现困难。
问题（1）
浓缩知识点
Cache替换算法用于缓存空间不足时筛选待淘汰的缓存块，常见类型包括FIFO、LRU、LFU及随机置换（RAND）。其中FIFO按缓存块进入顺序淘汰，实现简单无需额外计数器，但存在可能导致缓存命中率下降的Belady异常；LRU依据最近访问情况淘汰最近最少使用的块，可通过堆栈或链表结构实现，无需长期统计访问次数，实现复杂度适中；RAND随机选择淘汰块，几乎无额外性能开销，是实现最简单的一类；LFU则统计每个缓存块在整个使用周期内的访问次数，以此为依据淘汰访问频率最低的块，随着系统运行时间增加，其记录访问次数的计数器所需位数会持续增长，因此是这几种算法中实现难度最高的，该算法更适配访问模式稳定、高频数据持续被访问的场景。
正确答案
B
本题考察的是高速缓存存储器（Cache）的替换算法特点。
常见的替换算法包括 FIFO（先进先出）、LFU（最少使用）、LRU（最近最少使用）、RAND（随机置换）。
A选项 FIFO：先进先出算法只需要维护一个队列，记录进入 Cache 的先后次序，实现简单，不需要额外的计数器。错误。
B选项 LFU：最少使用算法需要对每个块设置一个计数器，记录块在整个使用周期中的访问次数。随着时间推移，计数器可能需要很多位来统计，且更新代价较高，实现最复杂，正确。
C选项 LRU：最近最少使用算法只关注最近访问时间，可以通过堆栈或链表来实现，不需要无限增长的计数器，复杂度虽高但仍低于 LFU。错误。
D选项 RAND：随机算法在需要替换时随机选择一块，不考虑访问历史，几乎不需要额外开销，实现最简单。错误。
因此答案是 B. LFU。