页面调度算法

最优调度算法为什么最优

我们发现换页时换入的页总是固定的, 我们要挑选的是换出的页面。优先换出不再被访问的页面是显然的。首先注意换出的页面在下次访问时是一定会被换入的。只要考虑没被换出的页面有没有离开即可。如果不用最优调度算法换出A, 而换出一个下次访问更早的页面B, 那么:

  • 如果A在下次访问A前未被调出, 那么换出A仍能使得下次访问B前B未被调出
  • 如果A在下次访问A前被调出了, 那么换出A有可能可以使得B不用被调出, 因为B的下次访问更早

于是换出A一定不比换出B差, 无论换出B后采用什么策略。

堆栈式算法

堆栈式算法是指: 访问第$t$个页面时, 考虑驻留集大小为$n$时的驻留集$S$和驻留集大小为$n+1$时的驻留集$S'$, 如果可以证明在某种调度算法下无论对什么输入下的哪个$t$, 都有$S\subset S'$成立, 那么这个调度算法就是堆栈式算法。

堆栈式算法的好处

这种算法没有Belady现象, 也就是: 页框增加时缺页中断次数不会增加。

证明: 页框增加时, 由于任何时刻$S\subset S'$, 那么$P\notin S'\Rightarrow P\notin S$, 即某页在页框多时缺页$\Rightarrow$该页在页框少时也缺页, 缺页中断次数不会更少。

最优调度算法/LRU为什么是堆栈式算法

用数学归纳法。初始时$S=S'=\emptyset$

假设对某个访问序列满足$S\subset S'$, 现在再访问一页$P$

$P\notin S'$, 那么$P\notin S$, 同时产生缺页中断。设在$S$中换出页$P_1$, $S'$中换出$P_2$。对OPT/LRU中的每一种, 要么$P_2\in S'-S$, 要么$P_1=P_2$, 无论哪种情形, 换出页后仍满足$S\subset S'$

综上, 对任意输入, 这两种算法都是堆栈式算法。

这个证明的核心在于: 要么$P_2\in S'-S$, 要么$P_1=P_2$。看到网上的一个理解, 说是: 给驻留集里的页面一个与$n$无关的优先级, 选择优先级最高的那个, 于是不会选择$S-\{P_1\}$中的元素。对FIFO算法, 这个优先级是进入时间, 然后我们会发现这个东西不完全取决于驻留集这个集合本身, 还取决于它进入驻留集的时刻。有可能: 驻留集小时的缺页导致一个页面换出后再次换入, 但驻留集大时则总是驻留, 从而它在驻留集小时优先级低而驻留集大时优先级高。这时有可能$P_2$是那个$S'$中总是驻留的页面, 而$P_1$是其他的页面, 于是这个$P_2$现在仍在$S$中而不在$S'$中。