操作系统中的缺页和置换

定义

在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断。当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法

页面置换算法的目的

虚拟存储性能的一个评价指标是有效存储访问时间(EAT, Effective memory Access Time)，好的页面置换算法可以有效地降低缺页率，从而提升虚拟存储整体性能

页面置换算法的设计目标

• 应该尽可能减少页面的调入调出次数
• 把未来不再访问或短期不再访问的页面调出
• 页面锁定(frame locking)

用于描述必须常驻内存的逻辑页面
操作系统的关键部分
要求响应速度的代码和数据
实现方法是，在页表中添加锁定标志位(lock bit)。
1
2
3
4

页面置换算法分类

• 局部页面置换算法

  1. 置换页面的选择范围仅限于当前进程占用的物理页面
  2. 最优算法、先进先出算法、最近最久未使用算法 、时钟算法（简单 + 改进) 、最不常用算法

• 全局页面置换算法

  1. 置换页面的选择范围是所有可换出的物理页面
  2. 工作集算法，缺页率算法

  局部页面置换算法

  • 最优页面置换算法(OPT-Optimal Page Replacement Algorithm)
    - 基本思想：选择以后再也不用的页面；没有的话，选择以后最长时间不用的页面；看未来
    - 实现：无法实现，因为页面的访问顺序无法预知；
    - 特点：无法实现，仅具有理论意义；
    - 栈式的页面置换算法。对于栈式的页面置换算法，是不会出现belady现象的

  • 先进先出算法(FIFO-First-In-First-Out algorithm)
    - 基本思想：基于程序的顺序执行特点选择到达内存最早的页面，予以淘汰；驻留在内存中时间最长的页面被置换 ；看自古以来历史
    - 实现：页面在内存中按时间排序；需要维护一个队列，来记录所有页面进入内存的先后次序。队列头驻留内存的时间最长，队列尾最短。出现缺页时，选择队列头页面进行置换，将被换入的页置于队列尾
    - 特点：效果不佳（程序不是严格顺序执行）；
    - belady现象 : 每次刚被换出的页面，恰好是下一次访存会访问的页面。即被置换出去的页面 FIFO可能会存在Belady现象。

    页面走向:1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6
    

  • 最近最久未使用算法(LRU-Least Recently Used algorithm)
    - 基本思想：基于程序运行的局部性原理，选择最近以来最久未使用的页面，予以淘汰；看最近历史
    - 实现：移位寄存器，栈
    - LRU的可能实现方法可以使用一个页面链表，LRU算法运行的开销很大，一次未发生缺页的访问也需要遍历链表
    - 特点：调度性能教好；
    
    它会将最近访问的节点放在前面，将最近没有访问的节点放在后面。如果缓存空间满了，就会将最后一个节点删掉，并将新的节点添加到首部。

  ————————————
  通过分析。FIFO的性能之所以很差，是因为它只记录了各个页面进入内存的时间，却没有利用上过去一段时间内对这些页面的访问信息。而LRU虽然性能很好，但是算法本身运行的开销却太大，这是因为它完全保存了过去一段时间的页面访问情况
  ————————————

  • 时钟置换算法(clock)
    - 原理
    1. 时钟算法使用一个循环链表来组织页面，每个页面都有一个标志位（通常是一个"访问位"），用于指示页面是否被访问过。
    2. 当需要置换页面时，算法从当前位置开始遍历循环链表，检查每个页面的访问位。
    3. 如果页面的访问位为0，表示该页面没有被访问过，可以选择置换该页面。
    4. 如果页面的访问位为1，表示该页面被访问过，算法将访问位设为0，继续遍历下一个页面。
    5. 算法继续遍历整个循环链表，直到找到一个访问位为0的页面，将其置换出去，或者遍历一圈回到起始位置。
    6. 如果遍历一圈后没有找到访问位为0的页面，算法会再次遍历循环链表，将第一个访问位为0的页面置换出去。

      注意 
      - 所有被访问过的页面的访问位都会被设置为0
      - 循环链表中的页面是按照它们在内存中的顺序组织起来的。每个页面都有一个指针，指向下一个页面。最后一个页面的指针指向第一个页面，形成一个闭环。这样，当需要遍历循环链表时，可以从任意一个页面开始，通过页面的指针依次访问下一个页面，直到回到起始页面。
      - 关于时间，循环链表的页面组织是在操作系统初始化时或者在页面调度算法中进行的。当操作系统初始化时，会根据内存中的页面数量创建循环链表，并按照页面在内存中的顺序进行链接。在页面调度算法中，当需要置换页面时，算法会根据当前位置开始遍历循环链表，因此循环链表的组织顺序会根据页面的访问情况动态变化。
    1
    2
    3
    4

  • 改进的时钟置换算法(improved-clock)
    前置知识
    外存中的页面在被加载到内存中时会有一个副本,当内存和外存操作完毕后，需要进行同步工作
    在选择被换出的页面时，可以优先选择没有被修改的页面，从而节省开销

    • 基本思想 ： 总是优先选择未被访问(访问位为零)，且未被修改的页面被置换

    整体过程
    1. 第一次循环查找访问位为零且修改位也为零的页面，同时将经过的页面的访问位清零；
    2. 如果第一次循环没有找到一个这样的页面，则进行第二次循环，继续查找访问位和修改位同时为零的页面，但是这次不做其他任何操作；
    3. 如果第二次循环仍然失败，则直接将当前指针所指的页面换出，因为此时内存的所有页面都有访问位为零，而修改位为一，只能换出第一个被修改的页面。

  • 最不常用算法(LFU - Least Frequently Used)

    • 基本思想 : 在每次缺页时，将访问次数最少的页面换出到外存当中
    • 具体实现 : 对每个页面被访问的次数进行计数，在缺页时选出计数值最小的页面进行换出
    • 存在的问题 ： 考虑某一页面，在进程运行的前一半时间内经常被该进程访问；后来该页面的功能已经完成了，在该进程运行的后半时间里面，对这个页面将不再访问
      
      在链表的开始插入元素，每插入一次计数一次
      按照次数重新排序链表，
      如果次数相同的话，按照插入时间排序，然后从链表尾部选择淘汰的数据

  全局页面置换算法

  • 为什么还需要全局页面置换算法
    - 进程在运行的整个生命周期内，对内存的需求是变化的，例如一个进程在刚开始运行的时候需要比较多的内存空间，在运行的后期进行收尾工作了，需要的内存空间也因此变少了
    - 无法把一个进程多余的页面分配给其他更需要的进程使用
    - 不同的进程对内存的需求也不一样，一些进程需要更多的空间，另一些进程则较小的空间就可以满足，对于这种情况，局部页面置换算法也难以适应

  • 全局页面置换算法包括工作集置换算法和缺页率置换算法。

    工作集置换算法
    - 工作集是指一个进程当前正在使用的逻辑页面的集合
    - 工作集的大小，就可以表示当前时刻，一个进程对内存的需求量
    - 工作集置换算法的思路就是换出不在工作集中的页面。可见，工作集置换算法也是基于局部性原理的，它认为过去访问过的页面（工作集中的页面），在以后有很大可能再次被访问。

    这里需要引入一个常驻集的概念，常驻集是指在当前时刻，进程实际驻留在内存中的页面的集合。工作集和常驻集具有以下的关系，即

    • 当常驻集大于工作集时，缺页较少。
    • 常驻集增大到一定的规模以后，缺页率也不会明显下降。
    • 在工作集发生剧烈变动（过渡阶段）时，缺页较多。

    工作集链表的具体工作流程

    1 创建一个工作集链表，用于记录进程当前的工作集。
    2 当一个页面被访问时，将其添加到工作集链表的末尾。
    3 如果工作集链表的长度超过了预设的阈值（例如，内存中只能容纳10个页面），则需要进行页面置换。
    4 选择工作集链表开头的页面进行置换，即将最久未被访问的页面换出到磁盘上。
    5 更新工作集链表，将刚刚被访问的页面移动到链表末尾。
    6 重复步骤2至5，直到进程执行结束或者不再需要进行页面置换。
    1
    2
    3
    4
    5
    6

    为了实现工作集置换算法，只需要维护一个工作集链表。在访存时，将不在工作集中的页面换出内存；在发生缺页时，直接为换入的页面分配新的内存空间，并且更新工作集链表。这样，在每一次访问后，都可以保证工作集和常驻集的大小相等。

    缺页率置换算法
    缺页率 = 缺页次数 / 内存访问次数

    缺页率置换算法的思路是，如果一个进程的缺页率显著地高于某一个阈值，则认为分配给该进程的物理页面数过少，从而增加分配给该进程的物理页面；而如果一个进程的缺页率明显太低，则认为该进程所占用的物理内存空间太多，从而回收该进程的部分空间。这样，通过调整常驻集的大小，使每个进程的缺页率保持在一个合理的范围内
    1

    
    
    两个全局页面置换算法的比较
    实际上，工作集置换算法和缺页率置换算法，在本质上，都是希望尽可能地跟踪进程运行周期内，对内存需求量的动态变化。工作集置换算法无疑具有更好的性能，因为每次访存后，工作集置换算法都会保证常驻集的大小等于工作集，但是也因为此，它执行起来需要更大的开销。缺页率置换算法则是开销与性能的一种折中。

抖动与负载控制
当运行缺页率置换算法的时候，几乎所有进程的缺页率都大于预先设定的阈值。按照缺页率置换算法，此时应该给这些进程分配更多的内存空间，但是此时已经没有剩余的内存空间可以分配了，并且由于所有进程的缺页率都高于阈值，也并不可以将某一个进程的页面换入到内存中来获得空闲的内存空间。这种现象就是抖动(thrashing)

对于传统的缺页置换算法，是无法解决抖动的。此时需要负载控制来解决抖动问题。

负载控制 : 调整并发进程数，以获得较高的CPU利用率
负载控制需要主要考虑两个指标，即平均缺页间隔时间(MTBF, Mean time Between page Faults)以及缺页异常处理时间(PFST, Page Fault Service Time)。考虑一种极端情况，即
PFST/MTBF=1 此时，每次访存都会产生缺页，CPU的全部时间都用于处理缺页异常的换入换出了，对应于CPU的利用降到了零