Cache的作用及替换策略

在计算机技术发展过程中,主存储器存取速度一直比中央处理器操作速度慢得多，使中央处理器的高速处理能力不能充分发挥，整个计算机系统的工作效率受到影响。有很多方法可用来缓和中央处理器和主存储器之间速度不匹配的矛盾，如采用多个通用寄存器、多存储体交叉存取等，在存储层次上采用高速缓冲存储器也是常用的方法之一。

很多大、中型计算机以及新近的一些小型机、微型机也都采用高速缓冲存储器。高速缓冲存储器的容量一般只有主存储器的几百分之一，但它的存取速度能与中央处理器相匹配。根据程序局部性原理，正在使用的主存储器某一单元邻近的那些单元将被用到的可能性很大。因而，当中央处理器存取主存储器某一单元时，计算机硬件就自动地将包括该单元在内的那一组单元内容调入高速缓冲存储器，中央处理器即将存取的主存储器单元很可能就在刚刚调入到高速缓冲存储器的那一组单元内。于是，中央处理器就可以直接对高速缓冲存储器进行存取。在整个处理过程中，如果中央处理器绝大多数存取主存储器的操作能为存取高速缓冲存储器所代替，计算机系统处理速度就能显著提高。

1. 根据程序局部性规律可知：程序在运行中，总是频繁地使用那些最近被使用过的指令和数据。这就提供了替换策略的理论依据。综合命中率、实现的难易及速度的快慢各种因素，替换策略可有随机法、先进先出法、最近最少使用法等。

(1).随机法(RAND法)随机法是随机地确定替换的存储块。设置一个随机数产生器，依据所产生的随机数，确定替换块。这种方法简单、易于实现，但命中率比较低。(2).先进先出法(FIFO法)先进先出法是选择那个最先调入的那个块进行替换。当最先调入并被多次命中的块，很可能被优先替换，因而不符合局部性规律。这种方法的命中率比随机法好些，但还不满足要求。先进先出方法易于实现，(3).最近最少使用法(LRU法)LRU法是依据各块使用的情况， 总是选择那个最近最少使用的块被替换。这种方法比较好地反映了程序局部性规律。 实现LRU策略的方法有多种。

2 在多体并行存储系统中，由于 I/O 设备向主存请求的级别高于 CPU 访存，这就出现了 CPU 等待 I/O 设备访存的现象，致使 CPU 空等一段时间，甚至可能等待几个主存周期，从而降低了 CPU 的工作效率。为了避免 CPU 与 I/O 设备争抢访存，可在 CPU 与主存之间加一级缓存，这样，主存可将 CPU 要取的信息提前送至缓存，一旦主存在与 I/O 设备交换时， CPU 可直接从缓存中读取所需信息，不必空等而影响效率。3 目前提出的算法可以分为以下三类(第一类是重点要掌握的)：(1)传统替换算法及其直接演化，其代表算法有 ：①LRU( Least Recently Used)算法：将最近最少使用的内容替换出Cache ;②LFU( Lease Frequently Used)算法：将访问次数最少的内容替换出Cache;③如果Cache中所有内容都是同一天被缓存的，则将最大的文档替换出Cache，否则按LRU算法进行替换 。④FIFO( First In First Out)：遵循先入先出原则，若当前Cache被填满，则替换最早进入Cache的那个。(2)基于缓存内容关键特征的替换算法，其代表算法有：①Size替换算法：将最大的内容替换出Cache②LRU— MIN替换算法：该算法力图使被替换的文档个数最少。设待缓存文档的大小为S，对Cache中缓存的大小至少是S的文档，根据LRU算法进行替换;如果没有大小至少为S的对象，则从大小至少为S/2的文档中按照LRU算法进行替换;③LRU—Threshold替换算法：和LRU算法一致，只是大小超过一定阈值的文档不能被缓存;④Lowest Lacency First替换算法：将访问延迟最小的文档替换出Cache。(3)基于代价的替换算法，该类算法使用一个代价函数对Cache中的对象进行评估，最后根据代价值的大小决定替换对象。其代表算法有：①Hybrid算法：算法对Cache中的每一个对象赋予一个效用函数，将效用最小的对象替换出Cache;②Lowest Relative Value算法：将效用值最低的对象替换出Cache;③Least Normalized Cost Replacement(LCNR)算法：该算法使用一个关于文档访问频次、传输时间和大小的推理函数来确定替换文档;④Bolot等人 提出了一种基于文档传输时间代价、大小、和上次访问时间的权重推理函数来确定文档替换;⑤Size—Adjust LRU(SLRU)算法：对缓存的对象按代价与大小的比率进行排序，并选取比率最小的对象进行替换。