概述所谓LRU（Leastrecentlyused）算法的基本概念就是当内存中剩余的可用空间不够用时，缓冲区尽可能先保留用户最常使用的数据，换句话说，优先清除“不常用的数据”，释放其空间。之所以把“不太常用的数据”打上引号，是因为这里所谓的不太常用的数据判断使用的标准是人为的，并不严格。所谓MRU（Mostrecentlyused）算法的含义与LRU算法正好相反。Oracle在高速缓冲区的工作机制中使用了该算法。来看看吧~LRU链：任何缓存的大小都是有限的，并没有缓存数据那么多。就像Buffercache是??用来缓存数据文件一样，数据文件的大小要比Buffercache大很多。因此，缓存总是满的。当缓存中没有空闲内存块时，如果需要新的数据进入缓存，则只从缓存中的原始数据中选择一个victim，用缓存中新进入的数据覆盖victim。这个受害者的选择非常重要。缓存是为了让数据可以重用，因此，通常应该选择缓存中最不可能被重用的块作为牺牲品。受害者的选择，从CPU的L1、L2缓存，到sharedpool、Buffercachepool，大部分的缓存池都使用了著名的LRU算法，但是在Oracle中，Oracle使用了改进的LRU算法。具体的算法没有公布，但是LRU算法的大意是“leastrecent”，意思是最后访问的内存块距离现在最远的就是victim。比如现在有3个内存块，分别是A、B、C，A被访问了10次，最后一次访问是在10点20分。B被访问了15次，最后一次访问时间是10:18。C也被访问。访问了10次，最后一次访问是在10:22。需要选择victim的时候，B的访问量最多，victim肯定不是它。A和C的访问次数相同，但是A在10点20分被访问，C在10点22分被访问，A最后访问得更早，受害者就是A。为了实现LRU的功能，Oracle在Buffercache中创建一个LRU链表，Oracle将Buffercache中的所有内存块按照访问次数和访问时间串入链表中。链表的两端分别称为热端和冷端。如下图所示，当你第一次访问一个block时，如果这个block不在Buffercache中，Oracle会选择将其读入Buffercache中。当在Buffercache中选择一个victim时，Oracle会从冷端开始选择。在上面的例子中，内存块U将成为受害者。如上图，新的block会被读入U，覆盖掉U原来的内容。这里，我们假设新的block是V。但是V的block不会放在冷端，因为冷端的block作为受害者的权利将很快被覆盖。这不符合“将最后一次访问时间距现在最远的块作为受害者”的目的。BlockV是离当前时刻最近的最后一次，应该不会是下一个受害者。让我们继续看看Oracle是如何用LRU进行实验的。Oracle把LRU链从中间分成两半，一半记录热端块，另一半记录冷端块。如上图所示，刚刚访问过的块V如下图所示：如果有新的块进入Buffercache，比如块X被读入Buffercache，它会覆盖T并将移到blockV的前面，如下图：如果继续这样下去，最右边冷端的block一定是最后一次访问时间距离现在最远的block。那么访问量大的区块就不会被选为受害者。甲骨文是如何意识到这一点的？这很简单。Oracle一般以2倍为准。如果一个块被访问超过2次，它就有机会进入热端。Oracle增加了一个标志位来记录内存中每个块的访问次数。假设图中每个block的访问次数如下：如果有新的block要读入Buffercache，Oracle就开始从冷端开始寻找。受害者，冷端的第一个块S，它的访问次数为2，那么不能被覆盖，只要访问次数大于等于2个块，Oracle就会认为它可能被频繁访问，Oracle将把它移动到热端，它会选择R作为这次的牺牲品：块S将从冷端移动到热端，它的访问计数将被重置。此时，块R是受害者，因为它的访问次数少于两次。新的区块Y覆盖区块R，移动到冷端区块的开头，其访问计数为1。如果再次访问区块Y，其访问计数变为2：Y虽然被访问过两次，但不会被访问立即移动到热端，它保持在原来的位置，并且随着越来越多的新块的加入，插在它的前面，它被不断地向后推。如上图，新增了很多块，将Y推到冷端。当新的块进入Buffercache时，Y不会成为牺牲品，它会被移到热端S的前面，而Y后面的Z，其访问次数还没有达到2，就会成为牺牲品。以上就是Oracle中Buffercache管理LRU的原理。这样，Oracle就可以将频繁使用的块尽可能长时间地保留在Buffer缓存中。而且，每有一个新块进入Buffercache，Oracle就会从冷端从右到左搜索victimblock。因为离冷端越近，块的访问次数可能越少，最后一次访问的时间离现在最远。脏块和脏LRU链：Oracle中修改块的规则是只修改Buffercache中的块，不能直接修改磁盘中的块。如果要修改的块不在Buffercache中，Oracle会先将其读入Buffercache，然后在Buffercache中进行修改。当Buffercache中的块被修改时，Oracle会将其标记为“脏”块。脏块包含脏数据，脏数据是用户修改过的数据。Oracle定期将脏块写入磁盘。有一个专门的后台进程负责将脏块写入磁盘，它就是DBWn。我们也把DBWn将脏块写入磁盘的过程称为刷新脏块。刷新后，脏块不再脏，重新变成干净块。其实有一个块A，如果Buffercache中这个块的数据和磁盘上的块中的数据不一致，那么这个块就是脏块。否则，它是一个干净的块。修改完成后，因为Oracle只修改了Buffercache，所以block和磁盘中的数据肯定是不一致的，block是dirtyblock。块刷新后，将块写入磁盘，此时磁盘中的块数据与Buffercache中的数据一致，此时块又变成了干净的块。在脏块回写到磁盘之前，也就是它还是脏块的时候，是不能被覆盖的，因为脏块中包含了用户修改过的数据，而这些数据还没有被写入磁盘。如果此时覆盖掉脏块，则用户的修改结果将丢失。假设当前LRU链如上图所示，其中V、L、O、P、Q为脏块。当一个新块要进入Buffercache时，Oracle从冷端选择牺牲块。Q、P、O不能作为牺牲块，因为它们是脏块。这次N是受害者，新进入的区块会覆盖N，然后在Y之前插入新区块。然后，下次有block进入Buffercache时，Oracle就从冷端开始查找。它还检查Q、P和O，发现它们不能被覆盖，然后将M设置为受害者。等等，每次都要检查O、P、Q，太费时间了。甲骨文不会那么傻。Oracle准备了一条脏LRU链来保存脏块。当一个块变脏时，该块不会立即移动到脏LRU。只有当Oracle从冷端开始寻找受害者时，才会将找到的脏块移动到脏LRU链中。这样做的目的是下次寻找受害者时，就不用去检查这些脏块了。总结一下LRU链和脏LRU链的原理，我们可以发现Oracle节省了大量的LRU冷端寻找受害者的工作。当区块的访问次数增加超过2时，区块在LUR链中的位置不变；当块变脏时，块在LRU链中的位置不会改变。只有从LRU冷端搜索victim时，才会将找到的脏块移动到脏LRU链上，访问次数超过2的才会插入热端。这是Oracle改进的LRU算法。当访问次数大于2的块过多，或者脏块过多时，这些块无论如何也无法被覆盖，Oracle不得不将它们移动到该去的地方。当遇到这样的块超过LRU总块数的40%时，也就是说搜索了LRU链的一小半，没有找到可以覆盖的牺牲品，Oracle就不会去找了，并且它会唤醒DBWn来刷新脏块。DBWn刷新期间的等待将记录在空闲缓冲区等待事件中。在寻找受害者的过程中发现脏块，Oracle将其移至脏LRU链，但脏LRU链中的脏块数量达到限制，DBWn唤醒并开始刷新脏块，Oracle必须等待对于脏块在继续搜索前需要刷新的牺牲品，这期间的等待事件，也会记录在freebufferinspected中。简而言之，freebufferwaits事件的主要原因是在LRU中寻找受害者的时间过长。如果这个等待事件频繁发生，说明Buffercache中脏块太多，一般是DBWn的写刷新率慢导致的。
