缓存生效原理

访问局部性原理
访问局部性原理可以总结为以下三点

1. 空间局部性

空间局部性为最近访问的数据在不远的将来会再次被访问。

1. 时间局部性

访问趋向于在地址空间中聚集（比如：访问数据或者循环操作）。

1. 顺序局部性

指令趋向于按顺序访问。

访问局部性原则是的计算机系统可以使用少量的快速存储器加速对们速存储的高效访问。

典型术语

1. 命中

要访问的信息存在与给定层次的存储器中。

1. 失效

要访问的信息在给定的存储器中没有找到。

1. 命中率

在给定层次存储器中找到所需信息的比率。

1. 失效率

在给定层级存储器中没有找到所需信息的比率。

1. 命中时间

在给定层次的存储器中访问信息需要的时间。

1. 失效惩罚

处理一次失效所需的时间，包括在较高层次存储器中替换一个块的时间和将所需数据传给处理所需要的额外开销。

缓存算法

1. 最优缓存（仅作为度量标准）
2. 最近未使用算法
3. 先进先出
4. 第二次机会
5. 时钟算法
6. 最近最少使用算法 LRU
7. 最不常用算法 LFU

缓存设计问题

1. 颠簸（Denning）

部分缓存算法实现

github地址

1. LRU https://github.com/fofcn/operation-system/tree/main/%E5%AE%9E%E8%B7%B5/os/src/main/java/cache/lru
2. LFU

https://github.com/fofcn/operation-system/tree/main/%E5%AE%9E%E8%B7%B5/os/src/main/java/cache/lfu