考点频率★★★★☆选择题常考是LRU的工程实现方案难度⭐⭐⭐建议重点掌握CLOCK算法的指针扫描过程理解改进型CLOCK中访问位和修改位的组合策略1️⃣ 为什么需要CLOCK算法上一篇文章讲了LRU最近最久未使用它性能很好但存在一个实际问题LRU需要记录每个页面的精确访问顺序如维护一个访问链表或时间戳硬件开销大实现成本高。能不能用更简单的硬件机制实现近似LRU的效果CLOCK算法就是这样一个经典方案。它用一个指针和一个“使用位”访问位来近似判断哪些页面最近被访问过被广泛应用于实际操作系统如Linux、Windows的页置换。2️⃣ 基本CLOCK算法又称NRUNot Recently Used2.1 数据结构内存中的页面排成一个循环队列每个页面有一个使用位Reference BitR位页面被访问时R位被硬件置为1页面未被访问时R位保持为0系统维护一个指针Hand指向当前要检查的位置2.2 算法步骤发生缺页时检查指针当前指向的页面如果R 0选择该页面换出淘汰指针指向下一个位置如果R 1将R位清零清为0指针指向下一个位置继续检查重复步骤1直到找到一个 R 0 的页面进行置换核心逻辑给每一个页面一个“第二次机会”。被访问过的页面R1指针经过时不清除相当于“保留一次”。如果一轮循环后所有页面都刚被访问过指针转了一圈自然会把第一个遇到的R0页面即最早被清0的淘汰。2.3 算法执行示例假设内存中有3个页面页框指针初始指向页框0访问序列中发生缺页时操作如下页框初始R位指针指向缺页处理过程结果页框01指针→页框0R1 → 清0指针移向页框1继续扫描页框11指针→页框1R1 → 清0指针移向页框2继续扫描页框20指针→页框2R0 →淘汰页框2装入新页R1指针移向页框0完成置换注意到R0的页面被淘汰后指针指到了下一个位置页框0而不是原地。这保证了公平性。2.4 优点与缺点优点缺点硬件开销小只需要一个访问位只是LRU的近似不能精确区分页面的访问时间先后顺序实现简单性能稳定如果所有页面的R位都为1需要扫描一整圈才能淘汰一个页面最坏情况3️⃣ 改进型CLOCK算法增强型NRU基本CLOCK算法只考虑了页面是否被访问过但没有考虑页面是否被修改过。如果换出一个被修改过的页面脏页需要写回磁盘代价比换出干净页要大得多。改进型CLOCK在R位的基础上增加了修改位Modified BitM位也称脏位根据R和M的组合决定淘汰优先级。3.1 四种页面类别类别R位M位含义淘汰优先级第1类00最近未访问且未被修改最高最优淘汰第2类01最近未访问但已被修改中等换出前需写回磁盘第3类10最近被访问但未被修改较低给第二次机会第4类11最近被访问且已被修改最低最不希望淘汰3.2 算法扫描过程改进型CLOCK执行多轮扫描每次扫描寻找不同类别的页面第一轮扫描寻找(R0, M0)的页面找到即淘汰。扫描过程中将遇到的R1的页面置为0给它们第二次机会但M位不变。第二轮扫描如果第一轮没找到寻找(R0, M1)的页面找到即淘汰。第三轮扫描如果还没找到重新扫描一遍此时所有R位都已被清零。再次寻找(R0, M0)并淘汰因为第一轮时R1的页面已被清0。第四轮扫描如果仍然没有再次寻找(R0, M1)并淘汰必能找到。3.3 为什么第四轮一定能找到经过前三轮所有的R位都已经是0且页面的M位非0即1。因此第四轮扫描时(0,0)和(0,1)两类页面必然存在至少能找到一类。这是算法终止的保障。4️⃣ 基本CLOCK vs 改进型CLOCK对比项基本CLOCK改进型CLOCK使用位仅R位访问位R位访问位 M位修改位淘汰依据仅看是否最近被访问同时考虑是否被访问和是否被修改是否考虑磁盘I/O代价否是优先淘汰干净页扫描轮数通常1轮最多4轮实现复杂度低中等5️⃣ 经典例题例题1某系统采用基本CLOCK置换算法内存中有4个页面R位依次为[1, 0, 0, 1]指针当前指向第0个页面。发生缺页中断时被淘汰的页面是哪个解析检查页0R1 → 清0指针→页1检查页1R0 → 淘汰页1答案页1例题2某系统采用改进型CLOCK算法某时刻内存中4个页面的R位和M位分别为页0: (1,0)页1: (0,1)页2: (0,0)页3: (1,1)指针指向页0。发生缺页时淘汰哪个页面解析第一轮扫描查找(0,0)页0: (1,0) → R清0变成(0,0)指针→页1页1: (0,1) → 不是目标指针→页2页2: (0,0) →找到淘汰页2答案页2例题3概念改进型CLOCK算法相比基本CLOCK算法主要改进之处在于 。A. 增加了R位B. 增加了M位优先淘汰未被修改的页面C. 用链表代替循环队列D. 淘汰页面时不需要扫描解析改进型CLOCK增加了修改位M位优先淘汰(0,0)类页面未被访问且未被修改以减少磁盘I/O开销。选B。6️⃣ 记忆口诀时钟算法循环查R位为零就换它。R位为一清零走二次机会给一下。改进加上M位判优先替换干净页。零零最优零一次一一最差放一边。7️⃣ 小测验评论区对答案某系统采用基本CLOCK置换算法内存中有3个页面R位依次为[0, 1, 1]指针当前指向页0。发生缺页中断时被淘汰的页面是 。经过这次淘汰后指针指向 。A. 页0页1B. 页0页2C. 页1页2D. 页2页0本专栏日更2篇点击头像 → 专栏《软考中级高频考点》订阅第一时间接收新内容#软考中级 #软件设计师 #CLOCK算法 #页面置换 #NRU #操作系统