知识卡片
缓存淘汰策略分时间与频率
- FIFO淘汰最早进入的块,LIFO淘汰最后进入的块;
- LRU淘汰最久未使用的块,LFU淘汰累计访问最少的块,同频时选最早进入者。
前两者按入缓存时间,后两者按使用记录决策。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第27章 在线算法 · 查看原书依据
First-in, first-out (FIFO): evict the block that has been in the cache the longest time. Last-in, first-out (LIFO): evict the block that has been in the cache the shortest time. Least Recently Used (LRU): evict the block whose last use is furthest in the past. Least Frequently Used (LFU): evict the block that has been accessed the fewest times, breaking ties by choosing the block that has been in the cache the longest. To analyze these algorithms, we assume that
参考来源
- 位置:《算法导论(第4版)》第27章《在线算法》(OEBPS/chapter027.xhtml,文本字符[25000,30000))。
- 结论依据:原文分别定义逆序、势能比较或缓存策略及其成本模型;正文补充其用途与边界。
- 原始内容:First-in, first-out (FIFO): evict the block that has been in the cache the longest time. Last-in, first-out (LIFO): evict the block that has been in the cache the shortest time. Least Recently Used (LRU): evict the block whose last use is furthest in the past. Least Frequently Used (LFU): evict the block that has been accessed the fewest times, breaking ties by choosing the block that has been in the cache the longest. To analyze these algorithms, we assume that