知识卡片

结构图卡 · 5654.d.1.b.4.r · 生成模型:未记录

引用位给页面第二次机会

理解等级:中级

第二次机会沿循环表从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的元素,它就找到了一个自从上次遍历链表以来都没有被系统访问过的页面,因此这个页面就是最近最少使用的页面。那么这个页面就在物理内存中和新的页面置换,新的页面被插入链表中原来页面的位置。