Skip to content

Latest commit

 

History

History
75 lines (55 loc) · 3.99 KB

Cache replacement algorithm.md

File metadata and controls

75 lines (55 loc) · 3.99 KB

Cache替换算法

随机算法(RAND)

随机算法(RAND, Random) -- 若Cache已满, 则随机选择一块替换

设总共有4个Cache块, 初始整个Cache为空. 采用全相联映射, 依次访问主存块{1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5}

访问主存块 1 2 3 4 1 2 5 1 2 3 4 5
Cache #0 1 1 1 1 1 1 1 1 1 1 4 4
Cache #1 2 2 2 2 2 2 2 2 2 2 2
Cache #2 3 3 3 3 5 5 5 5 5 5
Cache #3 4 4 4 4 4 4 3 3 3
Cache命中? 否 否 否 否 是 是 否 是 是 否 否 是
Cache替换? 否 否 否 否 否 否 是 否 否 是 是 否

随机算法 -- 实现简单, 但完全没考虑局部性原理, 命中率低, 实际效果很不稳定

先进先出算法(FIFO)

先进先出算法(FIFO, First In First Out) -- 若Cache已满, 则替换最先被调入Cache的块

设总共有4个Cache块, 初始整个Cache为空. 采用全相联映射, 依次访问主存块{1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5}

访问主存块 1 2 3 4 1 2 5 1 2 3 4 5
Cache #0 1 1 1 1 1 1 5 5 5 5 4 4
Cache #1 2 2 2 2 2 2 1 1 1 1 5
Cache #2 3 3 3 3 3 3 2 2 2 2
Cache #3 4 4 4 4 4 4 3 3 3
Cache命中? 否 否 否 否 是 是 否 否 否 否 否 否
Cache替换? 否 否 否 否 否 否 是 是 是 是 是 是

先进先出算法 -- 实现简单, 最开始按照#0#1#2#3放入Cache, 之后轮流替换#0#1#2#3, FIFO依然没有考虑局部性原理, 最先被调入Cache的块也有可能是被频繁访问的

抖动现象: 频繁的换入换出现象(刚被替换的块很快又被调入)

近期最少使用算法(LRU)

近期最少使用算法(LRU, Least Recently Used) -- 为每一个Cache块设置一个"计数器", 用于记录每个Cache块已经有多久没有被访问了. 当Cache满后替换"计数器"最大的

设总共有4个Cache块, 初始整个Cache为空. 采用全相联映射, 依次访问主存块{1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5}

访问主存块 1 2 3 4 1 2 5 1 2 3 4 5
Cache #0 1 1 1 1 1 1 1 1 1 1 1 5
Cache #1 2 2 2 2 2 2 2 2 2 2 2
Cache #2 3 3 3 3 5 5 5 5 4 4
Cache #3 4 4 4 4 4 4 3 3 3
Cache命中? 否 否 否 否 是 是 否 是 是 否 否 否
Cache替换? 否 否 否 否 否 否 是 否 否 是 是 是
  1. 命中时, 所命中的行的计数器清零, 比其低的计数器+1, 其余不变;
  2. 未命中且还有空闲行时, 新装入的行的计数器置0, 其余非空闲行全加1;
  3. 未命中且无空闲行时, 计数值最大的行的信息块被淘汰, 新装行的块的计数器置0, 其余全加1

Cache块的总数=2^n, 则计数器只需要n位. 且Cache装满后所有计数器的值一定不重复

LRU算法 -- 基于"局部性原理", 近期被访问过的主存块, 在不久的将来也很有可能被再次访问, 因此淘汰最久没访问过的块是合理的. LRU算法的实际效果优秀, Cache命中率高. 若被频繁访问的主存块数量>Cache行的数量, 则有可能发生抖动, 如:{1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2...}

最不经常使用算法(LFU)

最不经常使用算法(LFU, Least Frequently Used) -- 为每一个Cache块设置一个"计数器", 用于记录每个Cache块被访问过几次. 当Cache满后替换"计数器"最小的

设总共有4个Cache块, 初始整个Cache为空. 采用全相联映射, 依次访问主存块{1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5}

访问主存块 1 2 3 4 1 2 5 1 2 3 4 5
Cache #0 1 1 1 1 1 1 1 1 1 1 1 1
Cache #1 2 2 2 2 2 2 2 2 2 2 2
Cache #2 3 3 3 3 5 5 5 3 3 5
Cache #3 4 4 4 4 4 4 4 4 4
Cache命中? 否 否 否 否 是 是 否 是 是 否 是 否
Cache替换? 否 否 否 否 否 否 是 否 否 是 否 是

新调入的块计数器=0, 之后每被访问一次计数器+1. 需要替换的时候, 选择计数器最小的一行

LFU算法 -- 曾经被经常访问的主存块在未来不一定会使用到(如: 微信视频聊天相关的块)并没有很好地遵循局部性原理, 因此实际运行效果不如LRU