3.5.2 先进先出算法（FIFO）(重点)

• 选择在内存中驻留时间最长的页并置换它
• 实现：页面链表法

3.5.3 第二次机会算法（SCR）

在先进先出算法的基础上进行该机而来的，此算法按照先进先出算法选择某一页面，检查其访问位R，如果为0，则置换该页；如果为1，则给第二次机会，并将访问位置零，并将其从链头取下放到链尾。

3.5.4 时钟算法（CLOCK）

在第二次机会算法中当给某个页面第二次机会的时候，将其访问位置零，然后将其挂到链尾，这都是需要开销的，于是我们改进为时钟算法。

**说明：**其实就是将之前的链表改为了环形链表，当给某个页面第二次机会的时候不需要将其取下然后挂到链尾，只需要移动一下指针即可，这样可以降低开销。

3.5.5 最近未使用算法（NRU）

• 选择在最近一段时间内未使用过的一页并置换
• 实现：置换页表表象的两位，访问位R，修改位M。硬件会设置这些位，如果硬件没有这些位，则可用软件模拟。
• 进程启动时，R、M位置零，R位被定期清零。
• 发生缺页中断时，操作系统检查R、M：

*   第一类：无访问，无修改（`00`）

• 第二类：无访问，有修改（01）
• 第三类：有访问，无修改（10）
• 第四类：有访问，有修改（11）
• 算法思想
  随机从编号最小的非空类中选择一页置换出去。
• 时钟算法的实现

对此算法有一个时钟算法的实现

1、从指针的当前位置开始，扫描页框缓冲区，选择遇到的第一个页框（r=0，m=0）用于置换（本扫描过程中，对使用位不做任何修改）

2、如果第一步失败，则重新扫描，选择第一个（r=0；m=1）的页框（本次扫描工程中，对每个跳过的页框，将其使用位置为零）

3、如果第二部失败，指针将回到它的最初位置，并且集合中的所有页框的使用位均为零。重复第一步，并且，如果有必要，重复第二步，这样将可以找到置换的页框。

3.5.6 最近最少使用（LRU）(重点)

选择最后一次访问时间距离当前时间最长的一页并置换，即置换未使用时间最长的一页。

性能接近最佳页面置换算法

实现：时间戳或维护一个访问页的栈，导致开销较大。

硬件实现

• 页面访问顺序0,1,2,3,2,1,0,3,2,3，该图案例只有四页。

访问第0页时先将页的第0行置为1，然后将第0列置为0，

以此类推，在访问完之后将行编号最小的那一页置换出去。我们看到j中最小的是第1行，于是将第1页置换出去。

3.5.7 最不经常使用算法（NFU）

即Not frequently Used，选择访问次数最少的页面置换

• 一开始提出此算法是LRU（最近最少使用算法）的一种软件解决方案，但是实际上差距有点大。
  
• 实现
  

*   软件计数器，一页一个，初值为零

• 每次时钟中断时，计数器加R

• • 发生缺页中断时，选择计数器值最小的一页置换。

3.5.8 老化算法（AGING）

• 改进（模拟LRU）：计数器在加R前先右移一位，R位加到计数器的最左端。

这样如果R值为零，则计数器没有影响，如果值为1，则会变得很大，于是如果一个页面长久不被访问，则计数器值就会越来越小。最后选择值最小的置换出去。

3.5.9 页面置换算法的应用

例子：

• 系统给某进程分配了三个页框（采用固定分配策略），初始为空
• 进程执行时，页面访问顺序为：2 3 2 1 5 2 4 5 3 2 5 2

要求：计算应用FIFO、LRU、OPT算法时的缺页次数

应用FIFO、LRU页面置换算法

可以看到FIFO发生六次缺页异常，而LRU发生四次缺页异常。

应用OPT页面置换算法

发生三次缺页异常。

3.5.10 BELADY现象

例子：系统给某进程分配m个页框，初始为空页面访问顺序为

1 2 3 4 1 2 5 1 2 3 4 5，采用FIFO算法，计算当m=3和m=4时的缺页中断次数。

结论：m=3时，缺页中断九次；m=4时，缺页中断十次。注意：FIFO页面置换算法会产生异常现象（Belady现象），即：当分配给进程的物理页面数增加时，缺页次数反而增加。

3.5.11 页面缓冲算法(PBA)(重点)

该算法采用了可变分配和局部置换方式，置换算法则采用FIFO。

该算法规定将一个被淘汰的页放入两个链表中的一个，

若页面未被修改，直接放入空闲链表末尾，否则放入已修改页面链表末尾。

这种方式使得已修改和未修改的页面都仍然留在内存中，当进程以后再次访问这些页面时，只需花较小的开销，使这些页面又返回到该进程的驻留集中。

当被修改页面达到一定数量时，才一次性地将他们写回到外存，这样就显著地减少了外存的I/O次数

假设采取FIFO固定分配局部置换，每次缺页都要淘汰该进程最早装入内存的页面，而这里采用可变分配局部置换，即分配进程一个空白块，将原本应该淘汰的最早装入的页面挂在两个队列之一，直到没有空白块或修改页面达到上限才启动磁盘写回外存

3.6 页面置换算法2：工作集算法

3.6.1 影响缺页次数的因素

• 页面置换算法的不同
• 页面本身的大小
• 程序的编制方法
• 分配给进程的页框数量

缺页越多，系统的性能越差，这称为颠簸（抖动）：虚存中，页面在内存与磁盘之间频繁调度，使得调度页面所需的时间比进程实际运行的时间还多，这样导致系统效率急剧下降，这种现象称为颠簸或抖动。

3.6.2 页面尺寸问题

• 确定页面大小对分页的硬件设计非常重要，而对操作系统是个可选的参数
  
• 要考虑的因素
  内部碎片
  页表长度
  辅存的物理特性
  
• Intel 80x86/Pentium: 4096或4M
  
• 多种页面尺寸：为了有效使用TLB带来灵活性，但给操作系统带来复杂性。
  

3.6.3 程序编制方法对缺页次数的影响

例子：

分配了一个页框，页面大小为128个整数，矩阵A(128 x 128)按行存放。

可以看到左边是按列赋值，右边是按行赋值。按列编制就是首先读入第一页（一行，因为矩阵是按行存放的），然后给第0个位置赋值，每次读入一行，直到将第0列赋值完，读完之后再给第1列赋值，这样会产生128*128次缺页异常；而按行赋值，第一次读入一页，给第0行的所有元素赋值，这样会产生128次缺页异常。于是可以看到程序的编制方法对缺页次数是有很大影响的。

3.6.4 分配给进程的页框数与缺页率的关系

**说明：**可以看到页框数越多那么缺页率越低，但是我们不可能给出所有的页框，于是需要找到一个平衡点W，超过这个点之后页框数的增加对缺页率的降低有限，这也是工作集算法的出发点。

3.7 工作集模型

• 基本思想
  根据程序的局部性原理，一般情况下，进程在一段时间内总是集中访问一些页面，这些页面称为活跃页面，如果分配给一个进程的物理页面数太少了，使得该进程所需的活跃页面不能全部装入内存，则进程在运行过程中将频繁发生中断。
  

如果能为进程提供与活跃页面数相等的物理页面数，则可减少缺页中断次数，这是由Denning提出的。

• 工作集：一个进程当前正在使用的页框集合
  

• 例子

3.8 工作集算法

• 基本思路
  找出一个不在工作集的页面并置换它
  

*   每个页表项中有一个字段：记录该页面最后一次被访问的时间

• 设置一个时间值T

• • 判断

根据一个页面的访问时间是否落在“当前时间 - T”之前或之中决定其在工作集 之外还是之内。

实现：扫描所有页表项，执行操作

1、如果一个页面的R位是1，则将该页面的最后一次访问时间设为当前时间，将R位清零

2、如果一个页面的R位为0，则检查该页面的访问时间是否在“当前时间 - T”之前，如果是，则该页面是需要被置换的页面；否则，记录当前所有被扫描过页面的最后访问时间里面最小值。扫描下一个页面并重复上述操作。

四、其他与存储管理相关技术

4.1 内存映射文件

• 基本思想
  进程通过一个系统调用（mmap）将一个文件（或部分）映射到其虚拟地址空间的一部分，访问这个文件就像访问内存中的一个大数组，而不是对文件进行读写
  
• 在多数实现中，在映射共享的页面时不会实际读入页面的内容，而是在访问页面时，页面才会被每次一页的读入，磁盘文件则被当作后备存储。
  
• 当进程退出或显式地解除文件映射时，所有被修改页面会写回文件
  

4.2 支持写时复制技术

如图，两个进程共享同一块物理内存，每个页面都被标志成了写时复制。注意：共享的物理内存中每个页面都是只读的。如果每个进程想改变某个页面时，就会与只读标记冲突，而系统在检测出页面是写时复制的，则会在内存中复制一个页面，然后进行写操作。新复制的页面对执行写操作的进程是私有的，对其他共享写时复制页面的进程是不可见的。