1. 局部页替换算法的问题

局部页面置换算法 OPT，FIFO，LRU，Clock 等等，这些算法都是针对一个正在运行的程序来讲的，但操作系统其实可以支持多个正在执行的程序，如果每个执行程序都采取一个固定的局部页面置换算法会带来一些问题。这是为什么接下来要研究全局页面置换算法的很重要原因，可以看看到底有哪些问题？

接下看个例子：


这个例子采取 FIFO 页面算法。如果分配 3 个物理页帧会产生 9 次缺页错误，但是如果分配4个物理页帧，则会产生一次缺页错误，这很显著的区别，可以看到物理页帧的大小确实会对页面置换算法的效果产生很大的影响。

2. 全局置换算法的工作原理

那如果要对一个正在运行的程序分配一个固定的物理页帧，那其实就在某种程度上限制了这个程序产生缺页的特点，因为程序在运行过程中有阶段性，可能一开始是一种访问特征，可能需要很多内存，中间段可能需要很少，结束时又需要很多，是动态变化的过程，那么对物理页帧的需求是可变的。但是前面介绍算法都有一个假定，假定分配给进程的物理页帧是固定的.

如果系统里只跑这一个程序，那可以把所有的物理页帧都分配给它，这是没问题，但是操作系统里面可以跑多个程序，这时候在给每个程序分配固定的物理页帧，其实就限制了灵活性。

能不能根据程序不同运行阶段动态调整物理页帧的大小，这就是全局页面置换算法要考虑的问题。

3. 工作集模式

考虑这个问题之前，介绍一个能够有效实现全局页面置换算法的一些基本原理，一个很重要的原理就是工作集模型。

前面介绍的各种页面置换算法，包括局部性算法和接下来要介绍的全局页面置换算法都有一个前提，如果这个算法要有效，一般来说需要这个程序具有局部性，又一次提到局部性原理，程序具有局部性原理，那么像 LRU 和 Clock 算法就可以产生更少的缺页异常。但如果访问序列没有任何局部性，那么无论采取哪种页面置换算法都会导致缺页中断，但如果局部性原理是成立的，也就说程序具有局部性原理，具有时间访问局部性也具有空间访问局部性，那么采取不同的页面置换算法就应该有不同的效果，那么怎么来表现出这个所谓的局部性呢？可以通过一种所谓的工作集模型来表现它，从而可以有效地分析它的局部性。

3.1 工作集

工作集是说一个进程当前正在使用的逻辑页面的集合称之为工作集。这里面两个需要注意的地方，第一个当前正在使用，当前正在使用就是一个时间段，就是起始时间以及持续的时间长度，第二个是逻辑页面集合，这是一个集合，集合里面存了在这个时间段内这个运行程序访问的页面集合。

• 那怎么来表示它？

  t 代表当前执行时刻，然后长度形成所谓的工作集窗口，长度用 Δ 表示，Δ 称之为工作集窗口，具体含义是一个定长的页面访问的时间窗口，需要注意 t + Δ 形成时间段，W（ t，Δ ）代表从这个时刻开始持续一段时间，在这个时间段里面所有访问到的页面形成的集合，很显然如果 t 在变，因为执行过程中这个 t 一直在变，但 Δ 不变，在这种情况下，工作集窗口一直在滑动，滑动中工作集窗口访问的页集合也会不断变化，用两个竖线框起来，中间写W（ t，Δ ），代表工作级大小，代表在这个时间段内，访问页集合的大小。

  例子来表示:
  

  上面列出页面访问序列，起始时间是 t1，需要注意是从当前往过去一段长度，这么一个长度是 Δ。如果 Δ 是10，那么左侧工作集是1 2 5 6 7 这几个页面，集合大小是5，一共有5个页面。

  另一个起始件是 t2，窗口还是10，访问的页面只有两个3 4，那可以看出来这两个特点不一样，其实访问特点表示出了这个程序在不同的运行阶段，它对内存访问特点的展现，比如在这里会看出来 t2 起始时间的工作集，它具有很好的局部性，因为它重复的访问3和4，局部性比较好，而 t1 可以看出来重复性没有那么强，但是在某个小时间段里面它重复访问了 4 次 7这个页面，它有一定的局部性，那它的整体局部性不如 t2。

3.2 工作集的变化

工作集在整个执行过程中会随着程序执行的特点变化而变化，在一开始时，可能它访问新的页不具有一定局部性，会有大的波动，当访问到局部性比较好的区域时，它的工作集大小也会比较稳定，但是由于程序本身的特点，有可能在某些地方会出现工作集快速扩展或者快速收缩的情况，也可能在某阶段保持一定的稳定性。

如上图所示，随着程序执行过程，会体现一定特征，有波峰、波谷、平的情况，希望能够根据它这个特征来有效地设计一个基于多个程序的页面置换算法。

4 常驻集

除了工作集概念之外，还需要另外一个概念，常驻集。常驻很显然是常驻内存的意思，常驻集是指在当前时刻正在运行的程序实际驻入在内存中的页面集合。工作集其实体现了运行程序在运行过程中对页面访问的属性，是这个程序本身的固有属性。

而常驻集是操作系统和计算机系统给运行程序分配的物理空间大小，以及它采用的页面置换算法来决定到底应该把哪些页面放在这个内存中，所以常驻集和工作集体现的特点是不一样。常驻集就是当前运行程序需要访问的页哪些在内存中，而工作集指的是当程序在运行过程中它所需要访问的页是哪些。

当然程序访问页有可能在内容中，也可能不在内存中，这是工作集和常驻集的不同之处，当然希望工作集所涉及那些页都在内存中，也就都在常驻集中，那这种情况最好，一旦工作集中某些页不在常驻集里面，那就意味着不在内存中，这时候就会产生缺页中断，希望这两个集合尽量是重叠的，这样可以使得缺页次数比较小。

当程序在跑的时候，操作系统可以给运行程序分配很大的常驻集，也可以分配很小的长驻集，那么大和小其实相对的，就说有可能分配小了之后，会产生很多缺页中断，但是分配的多也有一个上限，不是说给它越多越好，可能给到一定数量之后再给它更多的物理页意义不大。这时候需要通过动态调整，把多余的物理页给其他程序，这样整体上来说不同的程序合在一起，它总的缺页次数比较小。

其实可以看出来，常驻集就是体现出来一种，如果说根据不同的程序的运行特点不同的常驻级，使得整体缺页次数少，那么整体系统性能就会都到提高。那采取局部页面置换算法可能就不能有效地解决问题，因此需要考虑设计全局页面置换算法来解决这个问题。