熟悉完操作系统的第五篇章，开始学习第六篇章，关于操作系统的页面置换算法。

0猜你喜欢

操作系统系列文章

操作系统学习笔记 1概述

操作系统学习笔记 2操作系统介绍

操作系统学习笔记 3内存管理

操作系统学习笔记 4非连续内存分配

操作系统学习笔记 5虚拟内存

操作系统学习笔记 6页面置换算法

操作系统学习笔记 7进程管理

操作系统学习笔记 8CPU调度

操作系统学习笔记 9同步&互斥

操作系统学习笔记 10信号量&管程

操作系统学习笔记 11死锁

操作系统学习笔记 12进程间通信

操作系统学习笔记 13文件系统

6页面置换算法

  • 功能与目标

  • 实验设置与评价方法

  • 局部页面置换算法

    最优页面置换算法（OPT，optimal）

    先进先出算法（FIFO）

    最近最久未使用算法（LRU，Least Recently Used）

    时钟页面置换算法（Clock）

    最不常用算法（LFU，Least Frequently Used）

    Belady现象

    LRU、FIFO和Clock的比较

  • 全局页面置换算法

    工作集模型

    工作集页置换算法

    缺页率置换算法

6.1功能目标

  • 功能

    当缺页中断发生，需要调入新的页面而内存已满时，选择内存当中哪个物理页面被置换。

  • 目标

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

  • 页面锁定

    用于描述必须常驻内存的操作系统的关键部分或时间关键的应用程序。实现的方法是：在页表中添加锁定标志位（lock bit）。

6.2模拟操作系统环境

记录一个进程对页访问的一个轨迹

一个正在运行的程序会有一系列的访问，把访问的内存记录下来，读和写的内存地址记录下来，形成一个序列。如下图6-1所示，以页号和页内偏移量作为一个标记，（3, 0）表示第三个页面的第0个页内偏移量，这一系列的序列就形成了一个访问序列。

这里面可以忽略页内偏移量，只关注页号。因为只有当一个页不存在的时候，才会产生缺页中断，才会考虑是否把页置换出去。如果在同一个页内多次访问，只有在第一次才可能缺页，一旦把页调到内存中来就不会产生缺页中断。否则之后在进程访问中又被置换出去了才会再次缺页中断。

只有页号形成页访问序列的list，list可以用来设计页面置换算法，来看看在一定的页帧或者物理页大小的情况下，我们用某种算法会造成多少次的缺页次数。缺页次数越少，性能越好。

图6-1 一个进程对页访问的轨迹图 图6-1 一个进程对页访问的轨迹图

6.3最优页面置换算法

基本思路

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

缺点

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

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

举例说明

这里有四个页帧，访问的页有五个，显然会出现物理页不够的情况，就会产生缺页中断。这里的最优置换算法的实现，0时刻在1时刻之前，物理页帧已经存了abcd四个虚拟页了，访问前四个时刻，由于对应的物理页都存到了abcd虚拟页，这四次访问不会产生缺页中断。第五个时刻，访问e的时候，虚拟的页没有在物理页当中，我们需要把其他一个页给换出去。

根据最优置换算法，应该换里上下时刻访问最远的那个页。其中，a最近一次是7时刻，b最近一次是6时刻，c最近一次是9时刻，d最近一次是10时刻。可以看出来，最远是d，所以替换d换成e。

6.4先进先出算法

基本思路

选择在内存中驻留时间最长的页面并淘汰之。具体来说，系统维护着一个链表，记录了所有位于内存当中的逻辑页面。从链表的排列顺序来看，链首页面的驻留时间最长，链尾页面的驻留时间最短。当发生一个缺页中断时，把链首页面淘汰出局，并把新的页面添加到链表的末尾。

性能

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

Belady现象

当给一个运行的程序更多的物理页的时候，按理来说缺页次数会变得更少了，但采用FIFO算法，物理页帧越多反而产生的缺页次数越大。

举例说明

如下图6-2所示，已经放置了abcd四个物理页。前四个时刻范文cadb在物理页中都存在，不会产生缺页中断。第五个时刻访问e的时候，不在当前的物理页帧存着，需要把某一个页替换出去。这里有一个假设，a->b->c->d的顺序。

可以看出驻留时间最长的物理页是a，需要替换出去，换成e。以此类推，可以看到在7,8,9,10的时候会产生缺页中断，置换新的虚拟页放在物理页中。实现简单，但反而会产生更多的中断。

图6-2 先进先出算法示例图 图6-2 先进先出算法示例图

6.5最近最久使用算法

最近最久使用算法LRU（Least Recently Used）

基本思路

当一个缺页中断发生时，选择最久未使用的那个页面，并淘汰之。

原理

它是对最优页面置换算法的一个近似，其依据是程序的局部性原理，即在最近一小段时间（最近几条指令）内，如果某些页面被频繁的访问，那未来的一小段时间内，他们还可能会再一次被频繁地访问。反过来说，如果在过去某些页面长时间未被访问，那么在将来它们还可能会长时间地得不到访问。

这是对最优置换算法的近似，它是对过去的推测应该把那个页置换出去。

举例说明

跟前面类似，前四次的时刻都不会产生缺页中断，第五次会发生缺页中断。根据最久未被访问算法，得出上一次a=2时刻，上一次b=4时刻，上一次c=1时刻，上一次d=3时刻，由此得知应该置换c，c相对来说最久未被访问。

以此类推，第九时刻，由于上一次a=7时刻，上一次b=8时刻，上一次e=5时刻，上一次d=3时刻，此时置换应该是d；同理，第10时刻，应该把e置换换成d。

6.5.1两种可能的实现方法

LRU算法需要记录各个页面使用的先后顺序，开销比较大。

  • 系统维护一个页面链表

    最近刚刚使用过的页面作为首结点，最久未使用的页面作为尾结点。每一次访问内存时，找到相应的页面，把它从链表中摘下来，在移动到链表之首。每次缺页中断发生时，淘汰链尾末尾的页面。

  • 设置一个活动页面栈

    当访问某页时，将此页号压入栈顶，然后考察站内是否有与此页面相同的页号，若有则抽出。当需要淘汰一个页面时，总是选择栈底的页面，它就是最久未使用的。

6.5.2性能

根据设置一个活动页面栈的算法，可以得到下图6-5所示。

每次访问都需要去查找栈，如果内存中物理页帧比较多的情况下，查找会比较费时。

6.6时钟页面置换算法

Clock页面置换算法，LRU的近似，对FIFO的一种改进。（到不到LRU的效果，但是会接近LRU的效果）

基本思路

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

原理

如下图6-3所示，被分配了五个物理页帧，系统访问的虚拟页有8个。建立一个环形的list，左边的图显示，虚拟页有74031的五个虚拟页。

最左边的那一位代表存在位，1的话代表这个页在物理页帧中是存在的。

第二位代表的是可访问位，1的话代表这个页已经被访问一次，由硬件把它置为1。

第三位是页帧号，这边有五个页帧号，分别为1,2,3,4,5。

具体流程

  • 当前指针指向虚拟页为0对应的页表项，页表项里面的可访问位是1，表示当前这个页已经被访问过了，把可访问位是0，然后指针指向下一位。
  • 然后指针指到虚拟页为3对应的页表项，页表项里面的可访问位是1，表示当前这个页已经被访问过了，把可访问位是0，然后指针指向下一位。
  • 然后指针指到虚拟页为1对应的页表项，页表项里面的可访问位是0，表示可以直接置换当前的页面。把对应的虚拟页的内容放置到物理页帧5的位置中去，同时把可访问位置为1。
图6-3 时钟页面置换算法流程图 图6-3 时钟页面置换算法流程图

举例说明

如下图6-4所示，同上述例子相似，前四个时刻不会产生缺页中断。并且这里维护了一个环形指针，且abcd的可访问位都置为1，这个时候的指针指向了a。

如果是1，继续变成0，指针往下挪。如果是0，这个页就会做被替换页，直接替换当前虚拟页对应的页帧内容。所以第五个时刻，a页面会被替换成e页面，同时指针指向下一个位置，指向b。

第六个时刻，没有产生中断，但是硬件会将b对应的页表项可访问位置为1。

第七个时刻，产生缺页中断，由于当前的指针是b，把当前的表项里面的可访问位置为0，然后指针指向下一项c。因为当前指向的c的可访问位是0，把对应的虚拟页的内容放置到原本c对应的物理位置中去，同时把可访问位置为1。

以此类推，接下来的两次中断都会同样的方式替换。

图6-4 时钟页面置换算法示例图 图6-4 时钟页面置换算法示例图

6.7二次机会法

上面的可访问页面没有区分读和写，页表项中除了可访问位之外，还存在脏位（写位）。如果存在页面写的操作，脏位会被硬件置成1。如果仅是读操作，脏位是0。

所谓置换，就是页面的换入换出。如果某个页从硬盘读到内存中来，程序对页进行访问，意味着内存中页的内容和硬盘的内容一致，如果我们把这一页替换出去，就不需要再把这个页重新写回到硬盘里面去，直接释放即可。如果程序访问某个页的时候对其写操作，内存中的数据和硬盘中的数据不一致，如果我们把这一页替换出去，需要把这个页重新写回到硬盘里面去，确保未来访问数据的时候硬盘中存的数据是最新的数据。

二次机会法，减少对硬盘的回写操作次数。

如下图6-5所示，也是一样的环形list。不是刚才的一个可访问位，这里还多了一个脏位，根据这两个位来确定哪一页被置换出去。

左边图是一个展示的例子，第二位是可访问位，第三位是脏位。根据右下角的表的映射关系，来确定选择哪个页作为置换位。

  • 如果可访问位为0，脏位为0，这个是需要替换的页。
  • 如果可访问位为0，脏位为1，这个时候会把脏位置为0，指针继续往下走（1次循环）
  • 如果可访问位为1，脏位为0，这个时候会把可访问位置为0，指针继续往下走（1次循环）
  • 如果可访问位为1，脏位为1，这个时候会把可访问位置为0，把脏位置为1，指针继续往下走（2次循环）
图6-5 二次机会法流程图 图6-5 二次机会法流程图

举例说明

如下图6-6所示，其中对某个虚拟页的访问，有一个上标w，代表对页面访问是一个写操作。

初始情况，abcd标记位都是10，代表这些页都是读操作。接下来的四次访问对cd是读操作，对ab是写操作，标记位会发生变化，a(11),b(11),c(10),d(10)，硬件会对ab的脏位置为1。

到第五时刻的时候，当前指针指向的是a，对应的标志位改成01，指针指向下一个b。当前指针指向的是b，对应的标志位改成01，指针指向下一个c。当前指针指向的是c，对应的标志位改成00，指针指向下一个d。当前指针指向的是d，对应的标志位改成00，指针指向下一个a。经过一次循环之后，发现直到指针指向第二轮的c，对应的标志位为0，把对应的虚拟页的内容放置到原本c对应的物理位置中去，并把标志为置为10。

以此类推，接下来的两次中断都会同样的方式替换。

图6-6 二次机会法示例图 图6-6 二次机会法示例图

6.8最不常用法

最不常用法（LFU，Least Frequently Used），使用的策略是最不常使用的页面策略。

基本思路

当一个缺页中断发生时，选择访问次数最少的那个页面，并淘汰之。

实现方法

对每个页面设置一个访问计算器，每当一个页面被访问时，该页面的访问计数器加1。在发生缺页中断时，淘汰计数值最小的那个页面。

LRU和LFU区别

LRU考虑的是多久未访问，时间越短越好；而LFU考虑的是访问的次数，访问次数越多越好。

问题

一个页面在进程开始时使用的很多，但以后就不使用了，同时实现也费时费力。

解决方法

定期把次数寄存器右移一位

举例说明

如下图6-7所示，其中假设最初的访问次数是a(8)，b(5)，c(6)，d(2)。每一个访问页的时候上标为访问次数。

前四个时刻不存在缺页，所以不会被置换页面。第一个时刻的时候，c页面会访问7次，所以访问次数是a(8)，b(5)，c(13)，d(2)。第二个时刻的时候，a页面会访问1次，所以访问次数是a(9)，b(5)，c(13)，d(2)。第三个时刻的时候，d页面会访问14次，所以访问次数是a(9)，b(5)，c(13)，d(16)。第四个时刻的时候，b页面会访问5次，所以访问次数是a(9)，b(10)，c(13)，d(16)。

到第五时刻的时候，发生缺页中断，由于四时刻结束之后a虚拟页面的访问次数最少被替换，把对应的虚拟页的内容放置到原本a对应的物理位置中去，并将访问e的次数加上e(18)，b(10)，c(13)，d(16)。同理第六时刻e(18)，b(11)，c(13)，d(16)，第七时刻发生中断，访问次数e(18)，a(19)，c(13)，d(16)，第八时刻发生中断，访问次数e(18)，a(19)，b(20)，d(16)，第九时刻发生中断，访问次数e(18)，a(19)，b(20)，c(20)，第十时刻发生中断，访问次数d(17)，a(19)，b(20)，c(20)。

图6-7 最不常用法示例图 图6-7 最不常用法示例图

6.9Belady现象、LRU、FIFO、Clock比较

前面的局部页面置换算法，针对一个正在运行的程序，程序访问内存页的情况，来决定应该采用什么策略，并且指定相应的算法把页给替换出去。

6.9.1Belady

6.9.1.1Belady现象

在采用FIFO算法时，有时会出现分配的物理页面数增加，缺页率反而提高的异常现象

6.9.1.2Belady现象的原因

FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，与置换算法的目标是不一致的（即替换较少使用的页面），因此，被它置换出去的页面并不一定是进程不会访问的

举例说明

如下图6-8所示，物理页帧为3。序列一共12次。因为这里的物理页帧为3个，所以前三个序列会产生缺页中断，到第4个时刻，访问4页面，替换当前内存中最久的那一页，直接从list中摘掉1就ok了，把4在放到尾巴上。同理接下来到第5个时刻，访问1页面，替换当前内存中最久的那一页，直接从list中摘掉2就ok了，把1在放到尾巴上。

以此类推，最终这里的缺页中断次数为9次。

图6-8 物理页帧为3的FIFO算法图 图6-8 物理页帧为3的FIFO算法图

但是当物理页帧为4，理论来说缺页中断会变少，但FIFO这个算法可能会使得缺页中断增加。

如下图6-9所示，同样的序列一共12次。因为这里的物理页帧为4个，所以前四个序列会产生缺页中断，到第5个时刻，访问1页面，不会产生缺页中断。到第6个时刻，访问2页面，不会产生缺页中断。第7的时刻，页面5不在这几个虚拟页对应的物理位置中，就去掉头1，替换对应的1所在物理位置中。

以此类推，之后的每一次访问，都需要缺页中断，把对应的虚拟页的内容放置到原本FIFO头部页面对应的物理位置中去。这里的缺页中断次数为10次，高于物理页帧只有3的场景。

图6-9 物理页帧为4的FIFO算法图 图6-9 物理页帧为4的FIFO算法图

但如果是LRU算法，情况跟上述会不一样，当物理页帧从3至4，缺页中断会变少，从10次缺页中断到8次缺页中断。

6.9.2LRU、FIFO、Clock比较

LRU算法、FIFO算法和Clock算法本质上都是先进先出的思路。

算法 特点 不足
LRU算法 LRU符合一种栈算法的特点，意味着能满足一种属性，给的物理页帧越多，缺页中断次数越少。只不过LRU是针对页面的最近访问时间来进行排序，所以需要在每一次页面访问的时候动态地调整各个页面之间的先后顺序（有一个页面的最近访问时间变了） LRU算法性能较好，但系统开销较大。
FIFO算法 FIFO是针对页面进入内存的时间来进行排序，这个时间是固定不变的，所以各页面之间的先后顺序是固定的。 FIFO算法没有考虑页面访问的历史信息，可能会发生Belady现象。
Clock算法 Clock算法是LRU的近似，用到了两个bit，可访问位和脏位，用于表示访问时间。两个bit位不可能精确的表示出一段时间内，不同页面访问的先后顺序，是一种近似。通过使用硬件的bit位，来模拟页面访问时间和先后顺序。它可以有效的逼近LRU算法，且开销相对比较小。 如果没有局部性的特征，LRU算法和FIFO算法的结果可能会一样。

FIFO算法没有考虑页面访问的历史信息，但是LRU算法会考虑到这一点。如果程序具有局部性的特点，LRU就能更好的体现出适应局部性特点，产生更少的缺页次数。缺页次数不仅是算法本身的问题，也会和程序本身相关，如果没有局部性的特征，LRU算法和FIFO算法的结果可能会一样。如果一个页面在进入内存后没有被访问，那么它的最近访问时间就是它进入内存的时间。换句话说，如果内存当中的所有页面都未曾访问过，那么LRU算法就退化为FIFO算法。

LRU算法性能较好，但系统开销较大。FIFO算法系统的开销较小，因此，折衷的办法就是Clock算法，在每一次页面访问时，它不必去动态地调整该页面在链表中的顺序，而仅仅是做一个标记，然后等到发生缺页中断的时候，再把它移动到链表末尾。对于内存当中那些未被访问的页面，Clock算法的表现和LRU算法一样好；而对于那些曾经被访问过的页面，它不像LRU算法那样，记住它们的准确位置。

LRU算法就退化为FIFO算法

例如：给进程分配3个物理页面，逻辑页面的访问顺序为1、2、3、4、5、6、1、2、3。

6.10局部页替换算法问题、工作集模型

6.10.1局部页替换算法问题

上述的页面置换算法都是针对一个进程来说，实际上操作系统可以支持多个正在执行的程序。如果每个执行程序都采用一个固定的局部置换算法，会带来一系列的问题，因此还需要研究全局页面置换算法。

如下图6-10所示，使用FIFO算法，三个物理页帧会发生9次缺页中断，四个物理页帧只会发生一次页面中断。

图6-10 FIFO页面置换算法图 图6-10 FIFO页面置换算法图

显然，物理页帧的大小会对整个页面置换算法最后的效果产生很大的影响。

如果对一个正在运行的程序分配固定的物理页帧，从某种程度上限制了程序它产生缺页的特点。程序在运行中有一个阶段性，开始访问的时候可能需要很多内存，中间这段时间可能需要的内存很少，在结束的时候又需要很多的内存，这是动态变化的过程，对物理页帧的需求是可变的。

前面的算法，有一个假定，它的物理页帧都是固定的。系统里面只跑一个程序，把所有的物理页帧都分配给它是没有问题的。但是操作系统里面有很多程序，如果分配固定的物理页帧，就会限制灵活性。根据程序运行的不同阶段，能分配不同大小的物理页帧，这样才能保证灵活性。

6.10.2工作集模型

前面介绍的各种页面置换算法，都是基于一个前提，即程序的局部性原理。

  • 如果局部性原理不成立

    那么各种页面置换算法就没有什么分别，也没有什么意义。例如：假设进程对逻辑页面的访问顺序是1,2,3,4,5,6,7,8…即单调递增，那么在物理页数有限的前提下，不管采用何种置换算法，每次的页面访问都必然导致缺页中断。

  • 如果局部性原理成立

    那么如何来证明它的存在，如果来对它进行定量地分析？这就是工作集模型

6.10.2.1工作集模型

举例说明

如下图6-11所示，页面的访问序列很长。起始时间为t1，△表示当前往过去的长度。这里约定△长度为10，那么左侧工作集的访问的页面集合是1,2,5,6,7,这几个页面。w(t1, △)大小为5。同理，起始时间为t2，窗口还是10，它访问的页面时3和4，w(t2, △)大小为2。

可以看到t2时间里，具有更高的局部性，重复的访问3和4页面。

图6-11 工作集模型示例图 图6-11 工作集模型示例图

6.10.2.2工作集大小

工作集大小的变化

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

6.10.3常驻集

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

  • 工作集是进程在运行过程中固有的性质（内存加外存），而常驻集取决于系统分配给进程的物理页面数目，以及所采用的页面置换算法。
  • 如果一个进程的整个工作集都在内存当中，即常驻集大于等于工作集，那么进程将很顺利地运行，而不会造成太多的缺页中断（直到工作集发生剧烈变动，从而过渡到另一个状态）
  • 当进程常驻集的大小达到某个数目之后，再给它分配更多的物理页面，缺页率也不会明显下降

如果给不同的运行中的程序不同的常驻集，使得整体的缺页中断次数比较少，那么整体的性能就会提高。采用局部页面置换算法，可能就不能有效的解决这个问题。

6.11两个全局置换算法

6.11.1工作集全局置换算法

熟悉了前面工作集的概念，在当前时刻t之间的△时间窗口当中的所有页面所组成的集合。（随着t的变化，该集合也在不断地变化）

  • 在这个工作集窗口里面的页，表示当前时间段内被访问的页。
  • 如果说这个页要替换，要替换页是不在工作集页面中的页
  • 随着程序的执行，在滑动过程中，其中一个页不再这个时间窗口之内，这个页会被丢掉，并不是发生缺页中断的时候才开始去丢掉页。

举例说明

我们把工作集的滑动窗口大小设置为4，这里有分配了5个物理页帧，在1时刻之前已经访问了三个物理页帧，分别是ade。

在第一个时刻访问c，发生缺页中断，工作集就是acde。第2个时刻，访问c的时候，这个时候工作集会调整为acd，没有产生缺页也需要把e换出去。在第四个时刻，访问b的时候，会被换出去a，工作集调整为bcd。

同理，因为滑动窗口是固定的4，可以推断处之后,不同时刻的工作集。

原理就是上述的滑动思想

6.11.2 缺页率页面置换算法

  • 可变分配策略

    常驻集大小可变。例如：每个进程在刚开始运行的时候，先根据程序大小给它分配一定数目的物理页面，然后在程序运行过程中，在动态地调整常驻集的大小。

    可采用全局页面置换算法的方式，发生一个缺页中断时，被置换的页面可以是在其他进程当中，各个并发进程竞争地使用物理页面。

  • 优缺点

    性能较好，但增加了系统开销

  • 具体实现

    可以使用缺页率算法（PFF，page fault frequency）来动态调整常驻集的大小

6.11.2.1缺页率

缺页率表示“缺页次数/内存访问次数”（比率）或者“缺页的平均时间间隔的倒数”。

6.11.2.2影响缺页率的因素

  • 页面置换算法
  • 分配给进程的物理页面数目
  • 页面本身的大小
  • 程序的编写方法

若程序缺页率过高，则通过增加工作集来分配更多的物理页面；若运行的程序的缺页率过低，则通过减少工作集来减少它的物理页面数。力图使得运行的每个程序的缺页率保持在一个合理的范围内。

一个交替的工作集计算明确的试图最小化页缺失

  • 当缺页率高的时候，增加工作集
  • 当缺页率低的时候，减少工作集

6.11.2.3算法–保持追踪缺失发生概率

  • 当缺失发生时，从上次页缺失起计算这个时间记录这个时间，tlast是上次的页缺失的时间

  • 如果发生页缺失之间的时间是“大”的，之后减少工作集

    如果tcurrent - tlast > T时，之后从内存中移除所有在[tlast, tcurrent]时间内没有被引用的页

  • 如果这个发生页缺失的时间是“小”的，之后增加工作集

    如果tcurrent - tlast <= T时，之后增加缺失页到工作集中

举例说明

假设window size大小为2，指的是两次中断发生的间隔

如果tcurrent - tlast > 2，从工作集中移除没有在[tlast, tcurrent]被引用的页面

如果tcurrent - tlast <= 2，仅增加缺失页到工作集中

跟刚才类似，在第一时刻访问c，发生一次缺页中断，没有上一次，所以这里不考虑算法。直到第四个时刻的时候访问b，这个时候发生缺页中断，tcurrent - tlast大小为3，需要动态调整工作集，在时刻1到时刻4之间访问的页可以放到工作集中，所以调整完之后，还剩下bcd。

第五个时候没有变化，第六个时刻又发生一次缺页中断，tcurrent - tlast大小为2，因为这需要把缺页的这个页加入到工作集中，调整完之后是bcde。同理可知9和10时刻的中断，原理类似。

6.11.2.4与工作集置换算法区别

对页的调整时机不一样。每一次访问页的时候都需要判断一下，是否需要把这个页清除出去或者是加进来，缺页率页面置换算法只有在发生缺页中断的时候才需要判断

但都是和之前的局部页面置换算法有区别，这里是根据工作集的大小和缺页率大小动态的调整内存中需要把哪些放进来，这样做能够使得经常访问的页能够驻留到内存中。对操作系统而言，多个正在运行的程序，采用全局页面置换算法效果会好于局部页面置换算法。

6.12抖动问题

6.12.1抖动

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

6.12.2原因

随着主流内存的进程数目增加，分配给每个进程的物理页面数不断减少，缺页率不断上升。所以OS要选择一个适当的进程数目和进程需要的帧数，以便在并发水平和缺页率之间达到一个平衡。

6.12.3抖动问题量化方式

如下图6-12所示，横坐标是程序运行的数量，纵坐标是CPU的利用率，一般情况下CPU的利用率会很高，但是频繁的对页面换入换出使得CPU的利用率会比较低。

我们从CPU角度可以找到一个最优值，即Nmax，这个点对应的CPU的使用率是最好的，是一个极值点。

操作系统希望达到的目标，第一跑的程序尽量多，第二系统的利用率很高。为此，找到这个平衡点，两个缺页产生的平均时间和完成一次中断服务时间尽量相等。蓝色的线代表两个缺页产生的平均时间和完成一次中断服务时间的比值。比值越大，意味着缺页频率很低，大部分时间花在程序跑上面，CPU的利用率会很高。随着程序的增加，缺页频率很高，完成一次中断服务时间不变，CPU的利用率会变低。在比值为1的交汇点，对应的点为NI/O-BALANCE，这个时候的CPU利用率也是很高的。

图6-12 程序运行数量和CPU利用率图 图6-12 程序运行数量和CPU利用率图

但是这里面存在一个程序，消耗了很大的内存，依然会产生内存抖动现象。

内存抖动现象是一个综合的因素，需要的内存大量都在外存，导致不停的发生缺页中断，从而使得整个操作系统的CPU利用率变得很低的状态。