392 字
2 分钟
缓存淘汰策略
- opt算法 理论的最优解，用来和其他方法比较
- random算法
- fifo算法 belady问题
- lru算法 （lfu）
- 简单clock 思路类似lru是lru的简化版，仅考虑最近访问过没有
- 像钟表指针一样转过一轮自己的驻留集，转到访问位为1的页则把访问位置为0，否则停止转动把访问位为0的页换出内存作为新页
- 转过一周后即返回最初的位置，此时驻留集内所有页的访问位均为0，所以把转动最初位置的页换出内存
- 改进clock 同时考虑脏和最近访问过没有 实现方法：设置一个修改位，用于表示页面被修改过。0表示未被修改，1表示已修改。为方便讨论，用（访问位，修改位）的形式表示各页面状态。简单clock需要转1轮即可，改进clock需要转4圈
- 第一轮：从当前位置开始扫描到第一个（0，0）的帧用于替换。本轮扫描不修改任何标志位
- 第二轮：若第一轮扫描失败，则重新扫描，查找第一个（0，1）的帧用于替换。本轮将所有扫描过的帧访问位设为0
- 第三轮：若第二轮扫描失败，则重新扫描，查找第一个（0，0）的帧用于替换。本轮扫描不修改任何标志位
- 第四轮：若第三轮扫描失败，则重新扫描，查找第一个（0，1）的帧用于替换。