【正确答案】数据可以存放在CPU或者内存中。CPU处理快，但是容量少；内存容量大，但是转交给CPU处理的速度慢。为此，需要Cache(缓存)来做一个折中。将最有可能调用的数据先从内存调入Cache，CPU再从Cache读取数据，这样会快许多。然而，Cache中所存放的数据不是全部有用的。CPU从Cache中读取到有用数据称为“命中”。
   由于主存中的块比Cache中的块多，所以当要从主存中调一个块到Cache中时，会出现该块所映射到的一组(或一个)Cache块已全部被占用的情况。此时，需要被迫腾出其中的某一块，以接纳新调入的块，这就是替换。
   Cache替换算法有RAND算法、FIFO算法、LRU算法、OPT算法和LFU算法。
   (1)随机(RAND)算法随机算法就是用随机数发生器产生一个要替换的块号，将该块替换出去，此算法简单、易于实现，而且它不考虑Cache块过去、现在及将来的使用情况。但是由于没有利用上层存储器使用的“历史信息”、没有根据访存的局部性原理，故不能提高Cache的命中率，命中率较低。
   (2)先进先出(FIFO)算法先进先出(First In First Out，FIFO)算法是将最先进入Cache的信息块替换出去。FIFO算法按调入Cache的先后决定淘汰的顺序，选择最早调入Cache的字块进行替换，它不需要记录各字块的使用情况，比较容易实现，系统开销小，其缺点是可能会把一些需要经常使用的程序块(如循环程序)也作为最早进入Cache的块替换掉，而且没有根据访存的局部性原理，故不能提高Cache的命中率。因为最早调入的信息可能以后还要用到，或者经常要用到，如循环程序。此法简单、方便，利用了主存的“历史信息”，但并不能说最先进入的就不经常使用，其缺点是不能正确反映程序局部性原理，命中率不高，可能出现一种异常现象。例如，Solar—16/65机Cache采用组相连方式，每组4块，每块都设定一个两位的计数器，当某块被装入或被替换时该块的计数器清为0，而同组的其他各块的计数器均加1，当需要替换时就选择计数值最大的块被替换掉。
   (3)近期最少使用(LRU)算法近期最少使用(Least Recently Used，LRU)算法是将近期最少使用的Cache中的信息块替换出去。
   LRU算法是依据各块使用的情况，总是选择那个最近最少使用的块被替换。这种方法虽然比较好地反映了程序局部性规律，但是这种替换方法需要随时记录Cache中各块的使用情况，以便确定哪个块是近期最少使用的块。LRU算法相对合理，但实现起来比较复杂，系统开销较大。通常需要对每一块设置一个称为计数器的硬件或软件模块，用以记录其被使用的情况。
   实现LRU策略的方法有多种，例如计数器法、寄存器栈法及硬件逻辑比较法等，下面简单介绍计数器法的设计思路。
   计数器方法：缓存的每一块都设置一个计数器。计数器的操作规则如下：
   1)被调入或者被替换的块，其计数器清“0”，而其他的计数器则加“1”。
   2)当访问命中时，所有块的计数值与命中块的计数值要进行比较，如果计数值小于命中块的计数值，则该块的计数值加“1”；如果块的计数值大于命中块的计数值，则数值不变。最后将命中块的计数器清“0”。
   3)需要替换时，则选择计数值最大的块被替换。
   (4)最优替换(OPT)算法使用最优替换(OPTimal replacement，OPT)算法时必须先执行一次程序，统计Cache的替换情况。有了这样的先验信息，在第二次执行该程序时便可以用最有效的方式来替换，以达到最优的目的。
   前面介绍的几种页面替换算法主要是以主存储器中页面调度情况的历史信息为依据的，它假设将来主存储器中的页面调度情况与过去一段时间内主存储器中的页面调度情况是相同的，显然，这种假设不总是正确的。最好的算法应该是选择将来最久不被访问的页面作为被替换的页面，这种替换算法的命中率一定是最高的，它就是最优替换算法。
   要实现OPT算法，唯一的办法是让程序先执行一遍，记录下实际的页地址的使用情况。根据这个页地址的使用情况才能找出当前要被替换的页面。显然，这样做是不现实的。因此，OPT算法只是一种理想化的算法，然而它也是一种很有用的算法。实际上，经常把这种算法用来作为评价其他页面替换算法好坏的标准。在其他条件相同的情况下，哪一种页面替换算法的命中率与OPT算法最接近，那么它就是一种比较好的页面替换算法。
   (5)近期最少使用(LFU)算法近期最少使用(Least Frequently Used，LFU)算法选择近期最少访问的页面作为被替换的页面。显然，这是一种非常合理的算法，因为到目前为止最少使用的页面，很可能也是将来最少访问的页面。该算法既充分利用了主存中页面调度情况的历史信息，又正确反映了程序的局部特性。但是，这种算法实现起来非常困难，它要为每个页面设置一个很长的计数器，并且要选择一个固定的时钟为每个计数器定时计数。在选择被替换页面时，要从所有计数器中找出一个计数值最大的计数器。