时钟置换算法

⑴ 计算机操作系统中页面置换的三种方式

常见的置换算法有：
1．最佳置换算法（OPT）（理想置换算法）
2．先进先出置换算法（FIFO）：
3．最近最久未使用（LRU）算法
4．Clock置换算法改御（LRU算法的近似实现坦陪）核信岩
5．最少使用（LFU）置换算法
6．工作集算法
7 . 工作集时钟算法
8. 老化算法（非常类似LRU的有效算法）
9. NRU(最近未使用）算法
10. 第二次机会算法

⑵ 页面置换算法有哪些

页面置换算法有先进先出（FIFO）算法、最近最久未使用（LRU）算法、最不常用（LFU）算法、时钟（Clock）算法、最佳（OPT）算法。

1、先进先出（FIFO）算法

这是最简单的页面置换算法。它通过维护一个页面队列，将最早进入内存的页面置换出去。当一个新的页面需要进入内存时，会将最早进入内存的页面置换出去。FIFO算法的优点是实现简单，但它没有考虑页面的访问频率和重要性，可能会导致性能低下。

⑶ 页面置换算法

  上文说到，请求分页管理方式中，当需要调入页面到内存中，但此时内存已满，就需要从内存中按照一定的置换算法决定将哪个页面取出将内存给调入的页面。本文将介绍几种页面置换算方法。
   本文内容

  算法思想：每次选择 淘汰的页面 将是 以后永不使用 ，或者 在最长时间内不再被访问的页面 ，这样可以保证最低的缺页率。
  举例说明，假设系统为进程分配了三个内存块，并考虑到有以下页面号引用串（会依次访问这些页面）：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1

  ....按照此算法依次执行，最后的结果如下

  结果图

  注：缺页时未必发生页面置换，若还有可用的空闲内存空间就不用进行页面置换。
  最佳置换算法可以保证最低的缺页率，但是实际上，只有进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面的访问序列。因此， 最佳置换算法是无法实现的 。

  算法思想：每次选择 淘汰的页面是最早进入内存的页面。
  该算法很简单，每次淘汰最在内存中待时间最久的各个，下面分别给出系统为进程分为配三个内存块和四个内存块的执行情况图。访问序列为3,2,1,0,3,2,4,3,2,1,0,4
  分配三个内存块的情况：

  分配四个内存块的情况：

  当为进程分配的物理块数增大时，缺页次数不减反增的异常现象称为 贝莱迪（Belay）异常 。
   只有FIFO算法会产生Belay异常。 另外，FIFO算法虽然实现简单，但是该算法与进程实际运行时的规律不适应。因为先进入的页面也有可能最经常被访问。因此， 算法性能差。

  算法思想： 每次淘汰的页面是最近最久未使用的页面。
  实现方法：赋予每个页面对应的页表项中，用 访问字段记录该页面纯亏自上次被访问以来所经历的时间t。 当需要淘汰一个页面时，选择现有页面中t最大的页面，即最近最久未使用。

  举例说明，加入某系统为某进程分配了四个内存块，并考虑到有以下页面号引用串：1,8,1,7,8,2,7,2,1,8,3,8,2,1,3,1,7,1,3,7
  这里先直接给出答案

  结果图

  最佳置换算法那性能最好，但无法实现。先进先出置换算法实现简单，但是算法性能差。最近最久未使用置换算法性能好，是最接近OPT算法性能的，但是实现起来需要专门的硬件支持，算法开销大。 时钟置换算法 是一种 性能和开销均春裤配平衡 的算法。又称 CLOCK算法 ，或 最近未用算法 （ NRU ，Not Recently Used）
   简单CLOCK算法 算法思想：为每个页面设置一个 访问位 ，再将内存中的页面都通过 链接指针链接成一个循环队列 。当某个页被访问时，其访问位置1.当需要淘汰一个页面时，只需检查页的访问位。如果是0，就选择该页换出；如果是1，暂不换出，将访问位改为0，继续检查下一个页面，若第一轮扫描中所有的页面都是1，则将这些页面的访问位一次置为0后，再进行第二轮扫描（第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK算法选择一个扒指淘汰页面最多会经过 两轮扫描 ）。

  这个算法指针在扫描的过程就像时钟一样转圈，才被称为时钟置换算法。

  简单的时钟置换算法仅考虑到了一个页面最近是否被访问过。事实上，如果淘汰的页面没有被修改过，就不需要执行I/O操作写回外存。 只有淘汰的页面被修改过时，才需要写回外存。
  因此，除了考虑一个页面最近有没有被访问过之外，操作系统还需要考虑页面有没有被修改过。
  改进型时钟置换算法的 算法思想 ： 在其他在条件相同时，应该优先淘汰没有被修改过的页面， 从而来避免I/O操作。
  为了方便讨论，用（访问位，修改位）的形式表示各页面的状态。如（1,1）表示一个页面近期被访问过，且被修改过。
   算法规则 ：将所有可能被置换的页面排成一个循环队列

  由于第二轮已将所有的页的访问位都设为0，因此第三轮、第四轮扫描一定会选中一个页，因此 改进型CLOCK置换算法最多会进行四轮扫描。

  假设系统为进程分配了5个内存块，某时刻，各个页的状态如下图

  如果此时有新的页要进入内存，开始第一轮扫描就找到了要替换的页，即最下面的状态为（0,0）的页。

  某一时刻页面状态如下

  如果此时有新的页要进入内存，开始第一轮扫描就发现没有状态为（0，0）的页，第一轮扫描后不修改任何标志位。所以各个页状态和上图一样。
  然后开始第二轮扫描，尝试找到状态为（0,1）的页，并将扫描过后的页的访问位设为0，第二轮扫描找到了要替换的页。

  某一时刻页面状态如下

  第一轮扫描没有找到状态为（0,0）的页，且第一轮扫描不修改任何标志位，所以第一轮扫描后状态和上图一致。
  然后开始第二轮扫描，尝试找状态为（0,1）的页，也没有找到，第二轮扫描需要将访问位设为1，第二轮扫描后，状态为下图

  某一时刻页面状态如下

  具体的扫描过程和上面相同，这里只给出最后的结果，如下图

  所以，改进型的CLOCK置换算法最多需要四轮扫描确定要置换的页。从上面的分析可以看出，改进型的CLOCK置换算法
  (1) 第一优先级淘汰的是 最近没有访问且没有修改 的页面。
  (2) 第二优先级淘汰的是 最近没有访问但修改 的页面。
  (3) 第三优先级淘汰的是 最近访问但没有修改 的页面。
  (4) 第四优先级淘汰的是 最近访问且修改 的页面。

⑷ 页面置换算法有哪些

页面置换算法包括先进先出（FIFO）、最近最久未使用（LRU）、最不常用（LFU）、时钟（Clock）以及理想（OPT）算法。
1. 先进先出（FIFO）算法
该算法的基本原则是先进入内存的页面先被置换。当内存空间不足时，系统会选择最早进入内存的页面进行置换。FIFO算法的优势在于实现简单，但其缺点在于未能考虑页面的实际使用频率和重要性，可能导致不必要的性能损耗。
2. 最近最久未使用（LRU）算法
LRU算法依据页面的历史访问记录来进行页面置换。它倾向于将最长时间未被访问的页面置换出内存。为了有效地追踪页面访问顺序，LRU算法通常需要使用特殊的数据结构，如链表或栈。尽管LRU算法在理论上较为合理，但其实现复杂度较高，且需要额外的存储空间来维护访问顺序。
3. 最不常用（LFU）算法
LFU算法是基于页面访问频率的置换策略。它认为访问频率低的页面在未来也较少会被访问，因此将这些页面置换出内存。LFU算法需要跟踪每个页面的访问频率，并进行相应的排序。然而，LFU算法可能会导致一些频繁访问的页面被过早置换，影响系统性能。
4. 时钟（Clock）算法
Clock算法是基于FIFO的一种改进。它使用一个时钟指针来遍历页面队列，并根据特定的标记位（如访问位或修改位）来决定置换页面。当新页面需要加载时，时钟指针继续移动，直到找到一个标记位为0的页面进行置换。Clock算法的优势在于其实现相对简单且效率较高。
5. 理想（OPT）算法
理想算法是一个理论上的最优页面置换算法，它能够准确预测未来的页面访问模式，并据此选择最长时间内不会被访问的页面进行置换。然而，由于实际中无法准确预测访问模式，OPT算法在现实中无法完美实现。

⑸ 一文看懂页面置换算法

页面置换算法分为两类：局部页面置换算法与全局页面置换算法。其主要功能是在内存已满时，选择应置换出内存的物理页面，目标是减少页面换进换出次数，通常基于过去数据预测未来行为。页面锁定用于关键部分或时间关键应用，不参与置换。页面置换算法通常仅考虑页号，通过模拟行为记录缺页次数。下面介绍几种常用的页面置换算法。

最优页面置换算法考虑每个逻辑页面在下一次访问前的等待时间，选择等待时间最长的页面置换。然而，该算法无法实时运行，只能通过上帝视角模拟。

先进先出算法(FIFO)选择内存中最久未使用的页面置换，实现简单，但产生缺页次数较多，且可能频繁置换出经常访问的页面。

最近最久未使用算法(LRU)选择最久未被访问的页面置换，基于局部性原理预测未来访问行为，效果较好但实现复杂。

时钟页面置换算法结合了LRU与FIFO的优点，通过访问位和环形链表实现更优化的页面置换策略。

二次机会法通过区分读写操作，优先保留经常读取的页面，减少频繁置换，降低回写概率。

最不常用算法(LFU)选择访问次数最少的页面置换，虽然实现简单，但增加计数器消耗资源，且容易产生不合理置换。

Belady现象指增加物理页面导致缺页率提高的反直觉现象，源于FIFO算法与动态特征不匹配。相比之下，LRU算法与栈属性相匹配，较少出现Belady现象。

局部页面置换算法适用于单程序情况，而全局页面置换算法更适合多程序环境，需考虑动态分配物理页帧以适应进程需求变化。工作集模型描述了进程当前使用的逻辑页面集合，常驻集则表示实际驻留在内存的页面。工作集页置换算法根据工作集大小动态调整物理页帧，缺页率页面置换算法则基于缺页率调整常驻集大小。

抖动问题发生在物理页面分配不足时，频繁置换导致进程运行效率降低。解决抖动的关键在于平衡并发进程数与物理页面数量，确保系统稳定运行。通过优化算法与资源分配，可有效减少抖动，提高系统整体性能。