操作系统算法多语言实现.zip

## 页面置换算法 页面的换入换出, 需要启动磁盘的IO 会有较大的开销 , 因此好的页面置换算法应该 ==追求更少的缺页率== <img src="https://xingqiu-tuchuang-1256524210.cos.ap-shanghai.myqcloud.com/1082/image-20221222172809672.png" style="zoom:80%;" /> ### 1.最佳置换算法 =>无法实现 最佳置换算法（OPT，Optimal): **每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面**，这样可以保证最低的缺页率。 <u>最佳置换算法可以保证最低的缺页率</u>，但实际上，只有在进程执行的过程中才能知道接下来会访问到的是哪个页面。 <u>操作系统无法提前预判页面访问序列</u>。因此，**最佳置换算法是无法实现的**。 > 只有当 内存块全部占满并且出现了缺页中断 才会发生 页面置换  ### 2.先进先出置换算法-FIFO 先进先出置换算法（FIFO): **每次选择淘汰的页面是最早进入内存的页面** 实现方法:把调入内存的页面根据调入的先后顺序排成一个队列，需要换出页面时选择队头页面即可。队列的最大长度取决于系统为进程分配了多少个内存块。  那么当我们增加了内存块的个数 :  可以发现虽然我们增加了内存块的个数, 缺页中断的 发生次数反而增加了 , 这就是 Belady 异常 **Belady**异常：**当为进程分配的物理块数增大时，缺页次数不减反增的异常现象。** **只有FIFO算法会产生Belady异常**。另外，FIFO算法虽然实现简单，但是该算法与进程实际运行时的规律不适应，因为先进入的页面也有可能最经常被访问。因此，**算法性能差。** ### 3.最近最久未使用算法-LRU 最近最久未使用置换算法（LRU，least recently used): **每次淘汰的页面是最近最久未使用的页面。** 实现方法:赋予每个页面对应的页表项中，<u>用访问字段记录该页面自上次被访问以来所经历的时间t</u>。 当需要淘汰一个页面时，选择现有页面中t值最大的，即最近最久未使用的页面。  ### 4.时钟置换算法-NRU 最佳置换算法性能最好，但**无法实现**;先进先出置换算法实现简单，**但算法性能差**;最近最久未使用置换算法性能好，是最接近OPT算法性能的，但是实现起来需要专门的硬件支持，**算法开销大**。 **<u>时钟置换算法**是一种性能和开销较均衡的算法，又称CLOCK算法，或最近未用算法(NRU，NotRecently Used)</u> 简单的CLOCK 算法实现方法: 为每个页面设置一个**访问位**，再将内存中的页面都通过链接指针链接成一个**循环队列**。 当某页被访问时，其访问位置为1。当需要淘汰一个页面时，只需检查页的访问位。 - 如果是0，就选择该页换出; - 如果是1，则将它置为0，暂不换出，继续检查下一个页面， 若第一轮扫描中所有页面都是1，则将这些页面的访问位依次置为0后，再进行第二轮扫描（<u>第二轮扫描中一定会有访问位为0的页面</u>，**因此简单的CLOCK算法选择一个淘汰页面最多会经过两轮扫描)**  ### 5.改进型的时钟置换算法 <u>简单的时钟置换算法仅考虑到一个页面最近是否被访问过。</u> 事实上，==如果被淘汰的页面没有被修改过，就不需要执行I/o操作写回外存。只有被淘汰的页面被修改过时，才需要写回外存。== 因此，<u>除了考虑一个页面最近有没有被访问过之外，操作系统还应**考虑页面有没有被修改过**。</u> 在其他条件都相同时，应优先淘汰没有修改过的页面，避免I/o操作。这就是改进型的时钟置换算法的思想。修改位=0，表示页面没有被修改过;修改位=1，表示页面被修改过。 为方便讨论，用==（访问位，修改位）==的形式表示各页面状态。 - 如（1，1)表示一个页面近期被访问过，且被修改过。 **算法规则**: 将所有可能被置换的页面排成一个**循环队列** 第一轮:从当前位置开始扫描到第一个（0，0）的帧用于替换。<u>本轮扫描不修改任何标志位</u> 第二轮:若第一轮扫描失败，则重新扫描，查找第一个（0，1）的帧用于替换。本轮将所有扫描过的帧访问位设为0 第三轮:若第二轮扫描失败，则重新扫描，查找第一个(0，0）的帧用于替换。本轮扫描不修改任何标志位 第四轮:若第三轮扫描失败，则重新扫描，查找第一个（0，1）的帧用于替换。 由于第二轮已将所有帧的访问位设为0，因此经过第三轮、第四轮扫描一定会有一个帧被选中，因此**改进型CLOCK置换算法选择一个淘汰页面最多会进行四轮扫描**  > 第一优先级：最近没访问，且没修改的页面 > 第二优先级：最近没访问，但修改过的页面 > 第三优先级：最近访问过，但没修改的页面 > 第四优先级：最近访问过，且修改过的页面