最优调度算法为什么最优
我们发现换页时换入的页总是固定的，我们要挑选的是换出的页面。优先换出不再被访问的页面是显然的。首先注意换出的页面在下次访问时是一定会被换入的。只要考虑没被换出的页面有没有离开即可。如果不用最优调度算法换出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\not\in S'\Rightarrow P\not\in S$，即某页在页框多时缺页$\Rightarrow$该页在页框少时也缺页，缺页中断次数不会更少。
最优调度算法/LRU为什么是堆栈式算法
用数学归纳法。初始时$S=S'=\emptyset$。
假设对某个访问序列满足$S\subset S'$，现在再访问一页$P$。
若$P\not\in S'$，那么$P\not\in 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'$中。