原博客地址：?http://blog.chinaunix.net/uid-26762723-id-3259013.html

一、LRU链：

? ? ?任何缓存的大小都是有限制的，并且总不如被缓存的数据多。就像Buffer?cache用来缓存数据文件，数据文件的大小远远超过Buffer?cache。因此，缓存总有被占满的时候。当缓存中已经没有空闲内存块时，如果新的数据要求进入缓存，就只有从缓存中原来的数据中选出一个牺牲者，用新进入缓存的数据覆盖这个牺牲者。这一点我们在共享池中曾提及过，这个牺牲者的选择，是很重要的。缓存是为了数据可以重用，因此，通常应该挑选缓存中最没有可能被重用的块当作牺牲者。牺牲者的选择，从CPU的L1、L2缓存，到共享池、Buffer?cache池，绝大多数的缓存池都是采用著名的LRU算法，不过在Oracle中，Oracle采用了经过改进的LRU算法。具体的算法它没有公布，不过LRU算法总的宗旨就是――“最近最少”，其意义是将最后被访问的时间距现在最远的内存块作为牺牲者。比如说，现在有三个内存块，分别是A、B、C，A被访问过10次，最后一次访问是在10:20，B被访问过15次，最后一次访问是10:18，C也被访问10次，最后一次被访问是在10:22。当需要选择牺牲者时，B访问次数最多，牺牲者肯定不是它。A、C访问次数一样，但A在10:20被访问，而C在10:22被访问，A最后被访问的更早些，牺牲者就是A。注意，这就是LRU的宗旨，“将最后访问时间距现在最远的块作为牺牲者”。

? ? ?为了实现LRU的功能，Oracle在Buffer?cache中创建了一个LRU链表，Oracle将Buffer?cache中所有内存块，按照访问次数、访问时间排序串在链表中。链表的两头我们分别叫做热端与冷端，?如下图

?

? ? ?当你第一次访问某个块时，如果这个块不在Buffer?cache中，Oracle要选将它读进Buffer?cache。在Buffer?cache中选择牺牲者时，Oracle将从冷端头开始选择，在上图的例子中，内存块U将是牺牲者。

?

?

?如上图，新块将会被读入U，覆盖U原来的内容。这里，我们假设新块是V。但是块V不会被放在冷端头，因为冷端头的块，会很快被当作牺牲者权覆盖的。这不符合“将最后访问时间距现在最远的块作为牺牲者”的宗旨。块V是最后时间距当前时刻最近的，它不应该作为下一个牺牲者。Oracle是如何实验LRU的，我们继续看。