抖动 *3.2.5 抖动和工作集 操作系统中的页面置换算法普遍遵循一个原则：尽可能保留近期访问过的页面，优先淘汰未 访问过的页面。简单 CLOCK 算法仅依据访问位判断页面是否“被访问过”;而改进型 CLOCK 算法则在此基础上进一步细化：对“未访问过”的页面，优先换出其中未修改者；即使所有页面 均“被访问过”,仍优先选择未修改者换出，以最小化磁盘写回成本。 改进型CLOCK 算法优于简单CLOCK算法之处在于：优先淘汰未修改的页面，从而降低磁 盘I/O 开销。但为定位合适的淘汰页，可能需多轮扫描，算法本身的运行开销相应增加。 零，随后重复第①步；若仍无1类页面，则执行第②步。此时必能找到可淘汰页面。 ③若前两步均失败(所有页面A=1), 则将指针复位至起始位置，并将所有帧的访问位清 ②若第①步失败，则进行第二轮扫描，寻找A=0 且 M=1 的2类页面，将第一个找到的2 类页面作为淘汰页。此轮扫描中，将所有经过的页面的访问位A 置为0。 ①从当前指针位置开始，进行第一轮扫描，寻找A=0 且 M=0 的1类页面，将第一个找到 的1类页面作为淘汰页。此轮扫描不修改任何访问位A。 内存中的每一页必属于这四类页面之一。进行页面置换时，算法采用与简单CLOCK 类似的 循环扫描机制，区别在于该算法需同时检查访问位与修改位，具体步骤如下。 ●4类 (A=1,M =1): 最近已被访问，且已被修改，可能再次被访问。 ●3类 (A=1,M=0): 最近已被访问，但未被修改，可能再次被访问。 ●2类 (A=0,M=1): 最近未被访问，但已被修改，是次佳的淘汰页。 ●1类 (A=0,M=0): 最近未被访问，且未被修改，是最佳的淘汰页。 将一个页面换出时，若该页已被修改，则需将其写回磁盘；若未被修改，则无须写回。可见， 修改过的页面置换代价更高。为降低I/O 开 销 ，改进型 CLOCK 算法在访问位( A) 的基础上，引 入修改位( M) , 综合考虑页面的使用情况与置换代价。在选择淘汰页时，优先考虑既未被访问 过又未被修改的页面。根据(A,M) 的组合，页面可分为以下四类： 改 进CLOCK 算法的应用分析(2016、2021) 考点追踪 改进 CLOCK 算法的思想(2018) (2)改进型CLOCK 算法 (b) 第6次缺页中断缺页中断时替换指针扫描示意图(a) 第5次缺页中断 图3.26 (b) 第6次缺页中断 缺页中断时替换指针扫描示意图 帧3 页2(0)页2(1)页0(0)页1(1)页4(1)页1(0)页1(0)页2(0) 页0(0) 页1( 页2(0) 页2(1) 页0(0) 页1(1) 页4(1) 页1(0) 页1(0) 帧2帧 4 帧2 页3(1)页3(1)页3(1)页7(0) 页3(1) 页3(1) 页3(1) 帧1 存在，每次访问均将对应帧的访问位置为1。当访问1时发生第7次缺页，此时替换指针指向帧4, 且所有帧的访问位均为1,算法再次完成一轮扫描并将访问位清零，故淘汰帧4中的页面2。后续 访问3,已存在，访问位置为1。最后访问2时发生第8次缺页，替换指针指向帧1,帧1的访问位 为1,将其置0后继续扫描，帧2的访问位为0,故淘汰帧2中的页面0,装入页面2。 初始阶段，页面7,0,1,2依次调入，访问位均置为1。随后访问0,已存在，访问位保持为1。 访问3时发生第5次缺页，此时替换指针位于帧1,而所有页框的访问位均为1。算法遂完整扫 描一圈，将各帧访问位清零，指针回到最初的位置(帧1),故淘汰帧1中的页面7,装入页面3, 访问位置为1,如图3.26(a) 所示。接着访问0,已存在，访问位置为1。访问4时发生第6次缺页， 替换指针指向帧2(上次替换位置的下一帧),帧2的访问位为1,将其置0后继续扫描；帧3的 访问位为0,故淘汰帧3中的页面2,装入页面4,如图3.26(b)所示。此后访问2,3,0,3,2,均已 图3.25 CLOCK 算法时的置换图 帧1 1 1 7 1 7 1 7 1 7 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 0 3 1 3 0 帧2 0 1 0 1 0 l 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 2 1 帧3 1 1 1 1 1 1 1 0 1 0 4 1 4 1 4 1 4 1 4 1 4 1 4 0 4 0 4 0 帧4 2 1 2 1 2 0 2 0 2 0 2 1 2 1 2 l 2 l 2 1 1 1 1 1 1 1 缺页否 √ √ √ √ √ √ 访问顺序 7 0 1 2 0 3 0 4 2 3 0 3 2 1 3 2 假设页面访问需列为7,0,1,2,0,3,0,4,2,3,0,3,2,1,3,2,采用简单CLOCK 算 法 ，分配4 个页框，每个页框记录(页面号，访问位),具体过程如图3.25所示。 考点追踪 CLOCK 算法的应用分析(2010) 简单的CLOCK 算法为每个页面设置一个访问位，当某页首次被装入内存或被访问时，其访 问位被置为1。系统将所有页框组织成一个循环队列，并维护一个替换指针，指向当前检查位置。 发生缺页且需置换时，算法按以下规则操作：若指针所指页面的访问位为0,则直接淘汰该页； 若为1,则将其置为0,指针顺移至下一页面，给予该页一次“宽恕”机会——即暂不淘汰，待 后续轮询时再行判断。由于指针在队列中循环移动，形如时钟指针，故称CLOCK 算法。又因其 仅依据“最近是否被使用”这一粗略信息进行决策，也被称为最近未用( NRU) 算法。 (1)简单的CLOCK 算法 LRU 算法的性能接近OPT 算法，但其实现开销较大。因此，操作系统的设计者尝试了许多 算法，试图以较小的开销接近LRU 算法的性能，这类算法统称为CLOCK 算法的变体。

[tag_link]

正确答案：D