LIRS 要点

| 分类 Algorithm  | 标签 algorithm  lirs  cache 

简单记录一下 LIRS 相关要点。

Recency & Inter-reference Recency

LIRS*: Low Inter-reference Recency Set,中文??

Recency

页面上次访问至今,共访问了多少其他页面。

IRR: Inter-Reference Recency

页最近两次访问之间访问了多少次其他页面。 IRR 越大 (high),表示该页被使用的间隔越长,频率越低,越 “冷”。反之, IRR 越小 (low), 该页使用间隔越小,频率越高,即越 “热”。

冷页与热页

面根据 IRR 分为了两类: LIR (low IRR) 与 HIR (high IRR) ,也即:热页与冷页。中,热页驻留内存,而冷页则不一定驻留。

页的数量略小于 Cache 中能缓存的页面总数大小,再热页限制到达之前,所有页面都是热页。而当热限制到达之后, LIRS 根据算法 来进行后续处理。

Stack & Queue

LIRS* 算法中借用了两个数据结构来实现: Stack & Queue

Stack

tack (栈) 是 LIRS 算法中的主要数据结构,其中存储了所有的热页以及最近使用的冷页。 tack 本身依据 Recency 排序:越老的越靠近栈底,越新的越靠近栈顶。栈里面比 least recent hot page 还的页会从栈中移除 (stack pruning),因此栈底的页始终是热页。

tack 中的冷页其实是住在一个 “试用期”,如果期间冷页被再次引用,则转为热页,否则将最终被栈底移除。

Queue

Queue (队) 中保存了所有驻留内存的冷页。当热页从 Stack 中移除时,该页被加入到 Queue 末尾。而当需要进行页面替代时, LIRS 会从 Queue 的首部取出一个页面以供使用。

页替换规则

LIRS List 中插入页时,会根据待插入的页类型来进行处理:

热页

果待插入页为热页,将该页置于栈顶,而如果该页之前处于栈底,则需对栈进行清理

驻留冷页

先将该页置于栈顶,并做如下处理:

如果该页之前已经在栈里

  1. 则将其转换为热页,并从队中移除。
  2. 将栈底标记为冷页,并移到队尾。
  3. 对栈进行清理

如果该页之前仅在队里(之前为冷页)

不改变冷热状态,但挪动队尾。

非驻留冷页

队首移除一条记录,并将其从 Cache 中驱逐。如果被驱逐的记录之前已经在栈里,则其仍处于未绑定,依然处于试用期。将这个记录与 cache 页绑定,并移植栈顶:果该页之前已经在栈里:

  1. 则将其转换为热页,并从队中移除。
  2. 将栈底标记为冷页,并移到队尾。
  3. 对栈进行清理

如果该页之前仅在队里(之前为冷页)

不改变冷热状态,但挪动队尾。

页的状态

栈里面的页可以是绑定的,页可以是非绑定的,但队里面的页必须是绑定状态的。


上一篇     下一篇