3.7 高速缓冲存储器

3.7.4 Cache中主存块的替换算法

　　当采用全相联映像和组相联映像方式从主存向Cache传送一个新块，而Cache中的可用位置已经占满时，就产生了替换算法的问题。目前，常用的替换算法主要有以下几种。
　　1．随机替换算法
　　随机替换算法的思想最简单，即随机地选择一个Cache块进行替换，它不考虑Cache块过去、现在及将来的使用情况。
　　2．先进先出算法
　　先进先出（First Input First Output，FIFO）算法的思想是：按调入Cache的先后决定淘汰的顺序，即在需要更新时，将最先进入Cache的块作为被替换的块。这种方法不需要随时记录各个块的使用情况，容易实现，而且系统开销小。其缺点是可能会把一些需要经常使用的程序块（如循环程序）也作为最早进入Cache的块替换掉。
　　3．近期最少使用算法
　　最近最少使用（Least Recently Used，LRU）算法是把CPU近期最少使用的块作为被替换的块。这种替换方法需要随时记录Cache中各块的使用情况，以便确定哪个块是近期最少使用的块。LRU算法相对合理，但实现起来比较复杂，系统开销较大。通常需要对每一块设置一个称为计数器的硬件或软件模块，用以记录其被使用的情况。
　　无论FIFO算法还是LRU算法，都不能确定调出去的块近期将绝不会再被使用。研究表明，采用这两种算法后可使Cache的命中率达到90%左右，其中LRU算法略优于FIFO算法，这在实际使用中已经是很不错的了。