LRU的改进算法LIRS |
| 发布： 2011-11-18 10:51 |
|
LRU（Least Recent Used）是我们在cache替换算法中最普遍使用的算法，在缓存块已满，而需要缓存新的数据块的时候，这时需要从缓存中找到一个“没有价值”的块用新的数据块去替换它。 LRU的特点是简洁高效，但是缺点是LRU的缺点是不能对weak locality的数据进行缓存。 a. 如果stack size有1000个块，而一个文件是1001个块的大小，而且每次访问都是从头到尾的访问。则LRU的性能非常差，几乎没有任何缓存。 b. 假设我们要邀请学习好的同学到一个容纳10人的会议室开会。如果是LRU算法的话，会邀请90分以上或者80分以上的人，，但是如果没有80分以上的同学则一个都不邀请，而会议室也就白白浪费了，对于LIRS，邀请成绩前在10名的同学到会议室。这里会议室为我们的stack ，这样我们的会议室也就是stack至少不会浪费。 所以我们这里边的问题就是如何把一些weak locality的数据也能够缓存起来，使我们的cache得到充分的使用？ 2. 两个概念 Reuse: 一个块被使用之后，再次被使用 Recency：一个块被访问后，和上一次访问之间的距离。 LIRS的基本思想是对访问的数据块进行分类，一部分为hot数据块，一部分为cold数据块。对于hot数据块我们可以分配90％以上的cache给它们。而对于cold数据块给它们分配10%。 从LIRS算法的描述来看，可以理解为两个LRU队列的组合，利用cold缓冲区来保护Hot缓冲区，提高了进入hot缓冲区的门槛，阻止hot缓冲区频繁地变化。 LIRS算法实现： 首先说明LRU算法的实现。 采用带表头的单链表来存储数据节点，head指针指向表头，tail指针指向链表最后一个节点。数据节点则记录了每个缓存块的ID，加载状态，数据指针，next指针。另有unUsedSize变量存放未分配的缓存块数量。 当用户访问命中时，将对应的数据节点移到队列尾部。当用户访问未命中时，若能分配新数据节点，则分配，否则从表头摘下一个数据节点，并卸载数据。更新得到的数据节点的信息，并加到队列尾部。 最后，为了避免在查找数据节点时遍历整个链表，增加了Dictionary 再说明LIRS算法的实现。 为了简化实现，将算法实现为多个逻辑LRU队列（可实现多级缓冲区），在物理实现上，仍采用带表头的单链表来存储数据节点。对于N级缓冲区的实现（原始的LIRS算法为2级），使用unUsedSize[N]数组存放每个缓冲区的未分配数量，使用head[N+1]存放缓冲区的头尾指针。这样head[0]、head[1]指示了第0块缓冲区的头尾，依次类推，head[N-1]、head[N]指示了第N-1块缓冲区的头尾。0号缓冲区是cold的缓冲区，N-1号则是最hot的。由于使用了多级缓冲区，数据节点也需要增加一个选择器selector，用于指示该节点属于哪个缓冲区。 当用户访问未命中，分配新节点时，先检查N-1号缓冲区是否能分配新节点，若不能则依次向前检查。若分配了新节点，则直接加入相应缓冲区的尾部，否则就从0级缓冲区头部摘下一个节点来，更新节点信息后加入0级缓冲区尾部。 当用户访问命中时，则将x级的节点提升到x+1级，并加到缓冲区尾部，x+1级的头部节点，则被移到x级缓冲区的尾部 同样的，增加了Dictionary |
|
原文： http://qtchina.tk/?q=node/609 |
|
Powered by zexport
|
