Cache, 一个在计算机中几乎随时接触的概念。
CPU中Cache能极大提高存取数据和指令的时间
让整个存储器既有Cache的高速度,又能有内存的大容量
操作系统中的内存page中使用的Cache能使得频繁读取的内存磁盘文件较少的被置换出内存,从而提高访问速度;
数据库中数据查询也用到Cache提高效率;即便是Powerbuilder的DataWindow数据处理也用到了Cache的类似设计。
Cache的算法设计常见的有FIFO和LRU,
FIFO对CPU的指令序列非常有效,但更多的,对于Memory或者磁盘文件的这种Cache
LRU就更有效多了
FIFO的算法设计很简单明了,就不做讨论,在此只是对LRU展开。
Cache中的存储空间被分成若干块,每一块对应内存或者磁盘文件的一段数据,形成这种映射关系
当Cache中的存储块被用完,而需要把新的数据Load进Cache的时候
我们就需要设计一种良好的算法来完成数据块的替换。
LRU的思想是基于“最近用到的数据被重用的概率比较早用到的大的多”这个设计规则来实现的。
Cache中的所有块位置都用双向链表链接起来,当一个位置被命中后,就将通过调整链表的指向将该位置调整到链表的头位置,新加入的内容直接放在链表的头上。
这样,在进行过多次查找操作后,最近被命中过的内容就向链表的头移动,而没有被命中的内容就向链表的后面移动。当需要替换时,链表最后的位置就是最近最少被命中的位置,我们只需要将新的内容放在链表前面,淘汰链表最后的位置就是想了。
对于双向链表的使用,基于两个考虑。首先是Cache中块的命中可能是随机的,和Load进来的顺序无关,所以我们需要用链表这种结构来保存位置队列,使得其可以灵活的调整相互间的次序。其次,双向链表使得在知道一个位置的情况下可以很迅速的移到其他的地方,时间复杂度为O(1)。