知识卡片
引用位给页面第二次机会
第二次机会沿循环表从current开始检查。遇到reference非0就清成0并前进,遇到0便选为候选;被访问的页获得一次暂缓机会,却不记录精确访问先后。
结构图: 类图:
classDiagram
class Page {
int number
int reference
}
class CListElmt {
void* data
CListElmt_* next
}
class API["候选选择函数(非类型)"] {
replace_page(CListElmt** current) int
}
CListElmt --> Page : data引用页面记录
CListElmt --> CListElmt : next形成循环
API ..> CListElmt : 改写当前节点位置
选择流程:
flowchart TD
A[检查current页面引用位] --> B{是否为0}
B -->|否| C[清0并沿next前进]
C --> A
B -->|是| D[返回该页面编号]
02754-02756的代码只返回Page.number,并通过二级指针留下候选位置;不实际换页、更新页表、载入新内容,也不在成功后自动把指针移到后继。假设有效有限环、数据均为Page且没有并发重置引用位,最坏可检查一圈并回到起点,得O(n);不把这个模型当并发系统的无条件时限。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
开始遍历链表直到找到一个引用值为0的元素。当遍历每一个页面时,操作系统将页面的引用值从1重设回0。一旦它遇到引用值为0的元素,它就找到了一个自从上次遍历链表以来都没有被系统访问过的页面,因此这个页面就是最近最少使用的页面。那么这个页面就在物理内存中和新的页面置换,新的页面被插入链表中原来页面的位置。
参考来源
- 位置:《算法精解:C语言描述》第5章《使用循环链表的例子:第二次机会页面置换法》(spine1228;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1195.html;u075-ch05-019)。
- 结论依据:75全文及02753时钟前后图、02754完整replace_page、02755-02756完整Page头文件,真实字段和唯一参数/返回直接核对;图与流程分开说明。
- 原始内容:开始遍历链表直到找到一个引用值为0的元素。当遍历每一个页面时,操作系统将页面的引用值从1重设回0。一旦它遇到引用值为0的元素,它就找到了一个自从上次遍历链表以来都没有被系统访问过的页面,因此这个页面就是最近最少使用的页面。那么这个页面就在物理内存中和新的页面置换,新的页面被插入链表中原来页面的位置。