OS操作系统系列文章目录

目录

• OS操作系统系列文章目录
• 第六章：页面置换算法
• • 页面置换的功能和目标
  • 局部页面置换算法
  • • 最优页面置换算法（OPT）
    • 先进先出算法（FIFO）
    • 最近最久未使用算法（LRU）
    • 时钟页面置换算法
    • 二次机会法
    • 最不常用算法（LFU）
    • 算法比较
  • 全局页面置换算法
  • • 工作集模型
    • 工作集
    • 常驻集
    • 两个全局页面置换算法
    • 抖动问题

第六章：页面置换算法

页面置换的功能和目标

• 功能：
  当缺页中断发生，需要调入新的页面而内存已满时，选择内存中合适的物理页面被置换；

• 目标：
  尽可能地减少页面的换进换出次数（即缺页中断的次数）；
  具体而言，把未来不再使用的，或短期内较少使用的页面换出，通常只能在局部性原理指导下，依据过去的统计数据来进行预测；
   

• 页面锁定：
  用于描述必须常驻内存的操作系统的关键部分，或时间关键的应用进程，实现的方式是在页表中添加锁定标记位（lock bit）；

• 实例：

局部页面置换算法

最优页面置换算法（OPT）

• 基本思路：
  当一个缺页中断发生时，对于保存在内存中的每一个逻辑页面，计算在它的下一次访问之前，还需要等待多长时间，从中选择等待时间最长的那个，作为被置换的页面；

• 缺点：
  这只是一种理想情况，在实际中无法实现，因为操作系统无法直到每一个页面要等待多长时间以后才会被再次访问；

• 作用：
  可用作其它算法的性能评价的依据，在一个模拟器上运行某个程序，并记录每一次的页面访问情况，在第二遍运行时即可使用最优算法；

• 实例：

先进先出算法（FIFO）

• 基本思路：
  选择在内存中驻留时间最长的页面并淘汰；
  具体而言，系统维护着一个链表，记录了所有位于内存中的逻辑页面；从链表的排列顺序来看，链首页面的驻留时间最长，链尾页面的驻留时间最短；当发生一个缺页中断时，将链首页面移出，并将新的页面添加到链表的末尾；

• 缺点：
  性能较差，调出的页面可能是经常要访问的页面，并且有Belady现象；
  FIFO算法很少单独使用；

• 实例：

最近最久未使用算法（LRU）

• 基本思路：
  当一个缺页中断发生时，选择最久未使用的那个页面，用来置换；
  它是对最优页面置换算法的一个近似；其依据是程序的局部性原理，即在最近一小段时间（最近几条指令）内；
  如果某些页面被频繁访问，那么将来一小段时间内，它们可能还会再一次被频繁访问；反过来说，如果在过去某些页面长时间未被访问，那么在将来它们可能会长时间得不到访问；

• LRU算法需要记录各个页面使用时间的先后顺序，开销比较大；有两种可能实现的方法：
  • 系统维护一个页面链表：
    最近刚刚使用过的页面作为首节点，最久未使用的页面作为尾节点；每一次访问内存时，找到相应的页面，把它从原来的位置移动到链表之首；每一次缺页中断发生时，淘汰链表末尾的页面；
  • 设置一个活动页面栈：
    当访问某页时，将此页号压入栈顶；然后，考察栈内是否与此页面相同的页号，若有则抽出；当需要淘汰一个页面时，总是选择栈顶的页面，它就是最久未使用的页面；

时钟页面置换算法

• 基本思路：
  • 需要用到页表项当中的访问位，当一个页面被装入内存时，把该位初始化为0，然后如果这个页面被访问（读/写），则把该位置为1；
  • 把各个页面组织成环形链表，把指针指向指向最老的页面（最先进来）；
  • 当发生一个缺页中断时，考察指针所指向的最老页面，若它的访问位为0，则淘汰；若访问为1，则将该位设为0，然后指针往下移动一格；如此下去，直到找到被淘汰的页面，然后把指针移动到它的下一格；

• 维持一个环形页面链表保存在内存中
  • 用一个时钟（或使用/引用）位来标记一个页面是否经常被访问；
  • 但一个页面被引用的时候，这个位置设为1；
• 时钟头扫遍页面寻找一个带有used bit = 0的页面；
  • 替换在一个周转内没有被访问过的页面；

二次机会法

• 这是时钟页面置换算法的优化，，每次替换脏页的代价很大，现在运行脏页总是在一次时钟头扫描中保留下来，同时使用脏位和使用位来指导置换；

• 脏位（dirty bit）
  • 如果是一次写操作，脏位会设为1，说明内存访问该部分数据时，是有写入操作的，和硬盘上的原数据不一样，所以要写入硬盘；
  • 如果是一次读操作，脏位保持不变，此时对这部分内存没有写操作；
  • 目的：
    减少对硬盘的写入操作；

• 置换机制
  • 如果use bit和dirty bit都为0，那么直接将访问页帧覆盖原页帧；
  • 如果use bit = 0, dirty bit = 1，则进行硬盘数据从写入更新，并将脏位置零；
  • 如果use bit = 1, dirty bit = 0，则将使用位置零；
  • 如果use bit = 1, dirty bit = 1，则将使用为置零；

• 实例：

最不常用算法（LFU）

• 基本思路：
  当一个缺页中断发生时，选择访问次数最少的那个页面，并淘汰；
   

• 实现方法：
  对每个页面设置一个访问计数器，每层一个页面被访问时，该页面的访问计数器加1；
  在发生缺页中断时，淘汰计数值最小的那个页面；

• LRU和LFU的区别：
  LRU考察的是多久未访问，时间越短越好；而LFU考察的是访问次数或频度，访问次数越多越好；

• 缺点：
  初始化时访问次数多，而正常时访问次数少的帧明显有问题；
   

算法比较

• Belady现象：
  在采用FIFO算法时，有时会出现分配的物理页面数增加，缺页率反而提高的异常现象；
• Belady现象出现的原因：
  FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，与置换算法的目标是不一致的（即替换较少使用的页面），因此被它置换出去的页面并不一定是进程不会访问的；

• 实例：

  • FIFO算法：

  

  
   

  • LRU算法：

  

• LRU、FIFO和Clock的比较
  • LRU和FIFO本质上都是先进先出的思路，只不过LRU是针对页面的最近访问时间进行排序，所以需要在每一次访问后进行动态调整各个页面之间的先后顺序（有一个页面的最近访问时间变了）；而FIFO是针对页面进入内存的时间进行排序，这个时间是固定不变的，故各个页面之间的先后顺序是固定的；
  • 如果一个页面在进入内存后没有被访问，那么它的最近访问时间设为进入内存的时间，换句话说，如果内存中的所有页面都未曾访问，那么LRU将会退化未FIFO；
  • LRU算法性能较好，但系统开销较大；
    FIFO算法系统开销较小，但是可能会发生Belady现象；
    因此，折衷的方法是选择Clock算法，在每一次页面访问时，不必动态调整该页面在链表当中的顺序，而仅仅是做个标记，然后等发生缺页中断的时候，再将其移动到链表末尾；
    对于内存中那些未被访问的页面，Clock算法的表现和LRU算法一样；而对于那些曾经被访问过的页面，Clock不能像LRU那样记住准确的位置；
     

全局页面置换算法

工作集模型

• 局部页面置换算法，都基于一个前提，即程序的局部性原理；
  • 假设局部性原理不成立，那么各种页面置换算法都没有区别，也没有意义；
    例如：假设进程对逻辑页面的访问顺序是1、2、3、4、5、6、6、…，即单调递增，那么再物理页面数有限的前提下，不管采用何种置换算法，每次的页面访问都必然导致缺页中断；
  • 工作集模型可以证明局部性原理的存在，可以对其进行定量地分析；
     

工作集

• 工作集：
  一个进程当前正在使用的逻辑页面集合，可以用一个二元函数 W ( t , Δ ) W(t, \Delta) W(t,Δ)来表示：
  • t是当前的执行时刻；
  • Δ \Delta Δ称为工作集窗口，即一个定长的页面访问的时间窗口；
  • $W(t, \Delta) $ 等于在当前时刻t之前的 Δ \Delta Δ时间窗口当中的所有页面所组成的集合（随着t的变化，该集合也在不断地变化）；
  • ∣ W ( t , Δ ) ∣ |W(t, \Delta)| ∣W(t,Δ)∣ 指工作集的大小，即页面数目；

• 实例：

• 工作集大小的变化：
  进程开始执行后，随着访问新页面逐步建立稳定的工作集；当内存访问的局部性区域的位置大致稳定时，工作集大小也大致稳定；
  局部性区域的位置改变时，工作集快速扩张和收缩过渡到下一个稳定值；

常驻集

• 常驻集：
  指在当前时刻，进程实际驻留在内存当中的页面集合；

• 工作集是进程在运行过程中固有的性质，而常驻集取决于系统分配给进程的物理页面数目，以及所采用的页面置换算法；

• 如果一个进程的整个工作集都在内存当中，即 常 驻 集 ⊇ 工 作 集 常驻集\supseteq 工作集 常驻集⊇工作集，那么进程将很顺利地运行，而不会造成太多的缺页中断（直到工作集发生剧烈变动，从而过渡到另一个状态）；
   

• 当进程常驻集的大小达到某个数目之后，再给它分配更多的物理页面，缺页率也不会明显下降；

两个全局页面置换算法

• 工作集页置换算法
  随着内存访问的进行，工作集窗口会进行滑动，如果有在物理内存中出现的页，却不在工作集中的话，则该也会被淘汰，而不会等待缺页中断时才中断；

• 缺页率置换算法
  • 可变分配策略：
    常驻集大小可变；例如每个进程在刚开始运行的时候，先根据程序大小给它分配一定数目的物理页面，然后在进程运行过程中，再动态地调整常驻集的大小；
    • 可采用全局页面置换的方式：当发生一个缺页中断时，被置换的页面可以是在其它进程当中，各个并发进程竞争地使用物理页面；
    • 优缺点：性能较好，但增加了系统开销；
    • 具体实现：可以使用缺页率算法（PFF）来动态调整常驻集的大小；
  • 缺页率：
    缺页率表示“缺页次数 / 内存访问次数”（比率）或“缺页的平均时间间隔的倒数”；影响的缺页率的因素：
    • 页面置换算法；
    • 分配给进程的物理页面数目；
    • 页面本身大小；
    • 程序的编写方法；

• 缺页率算法（PFF）
  • 一个交替的工作集计算明确的试图最小化页缺失：
    • 若运行的程序的缺页率过高，则通过增加工作集来分配更多的物理页面；
    • 若运行的程序的缺页率过低，则通过减少工作集来减少它的物理页面数；
  • 保持追踪缺失发生概率
    • 但缺失发生时，从上次也缺失起记录整个时间， t l a s t t_{last} tlast​是上次页缺失的时间；
    • 如果发生页缺失之间的时间是“大”的，之后减少工作集；如果 t c u r r e n t − t l a s t > T t_{current} - t_{last} > T tcurrent​−tlast​>T，从内存中移除所有在 [ t l a s t , t c u r r e n t ] [t_{last}, t_{current}] [tlast​,tcurrent​]时间内没有被引用的页；
    • 如果发生页缺失之间时间是“小”的，之后增加工作集；如果 t c u r r e n t − t l a s t ⩽ T t_{current} - t_{last} \leqslant T tcurrent​−tlast​⩽T，之后增加缺失页到工作集中；

• 实例：

• 两个全局页面置换算法的区别：
  • 对页的调整时机不一样；PFF只在缺页中断时判断是否更改，而工作集置换算法时在每次换入换出时都做判断；
  • 都与局部页置换算法不一样；这两种涉及到工作集大小的调整；而局部只是在工作集满了之后才考虑换入换出；
  • 全局页置换算法效果比局部页置换算法更好；

抖动问题

• 抖动的定义：
  如果分配给一个进程的物理页面太少了，不能包含整个的工作集，即常驻集 ⊂ \subset ⊂ 工作集，那么进程将会造成很多的缺页中断，需要频繁地在内存与外存之间替换页面，从而使进程的运行速度变得很慢；

• 产生抖动的原因：
  随着驻留内存的进程数目增加，分配给每个进程的物理页面数不断减少，缺页率不断上升；所以OS要选择一个适当的进程数目和进行需要的帧数，以便在并发水平和缺页率之间达到一个平衡；