Question

FIFO可能会发生Belady异常，堆栈算法不会发生Belady异常，如LRU。证明为何不会异常。

这是清华计算机912考研题，要求证明OPT,LRU,LFU等为什么不会发生Belady异常。没要你证明FIFO会发生异常，这个是个科班生都知道。
水平不够的求你们不要乱答行不行。

Answer 1

LRU置换算法不会出现Belady异常：
在先进先出算法(FIFO)——选择装入最早的页面置换的过程中，可以通过链表来表示各页的装入时间先后。FIFO的性能较差，因为较早调入的页往往是经常被访问的页，这些页在FIFO算法下被反复调入和调出，并且有Belady现象。所谓Belady现象是指：采用FIFO算法时，如果对—个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多但缺页率反而提高的异常现象。

追问

题目要你证明。你复制一段没用的给我，你是傻还是是无聊还是机器人？快改答案

Answer 2

FIFO，当内存没有空闲页时，会将最早使用的页调出（无论之后是否使用）
Belaye现象：给予更多的页框，却会出现更多的缺页
1. 如果页框数增加，页框中的元素集合包含页框中页框小时元素集合，那么一定不会出现Belaye

（想一下就知道了）
2. FIFO出现了Belaye现象，所以存在页框中的元素集合A 并 页框小时页框中元素集合B 不等于A
3. 所以只需要说明这个问题，最好的方式就是反证，假设成立，但是你在成立的条件下还是找到了一个不对的例子，就完全可以说明这个问题了
证明：
对于这样的序列，ABCDABF

页框为3时，最后集合为{A，B, F} 缺页7次
页框为4时，最后集合为{B, C, D, F} 缺5页次
已经出现集合的包含关系不成立了，但是缺页数还是不同
接下来凑成缺页数相同的
ABCDABFAB
此时：
页框为3时，最后集合为{A，B, F} 缺页7次
页框为4时，最后集合为{D, F, A, B} 缺7页次
但是包含关系又成立了，但是会发现顺序不对，那么容易想到再出现所有集合中都没有出现的序列，使集合中序列不停推进。最终一定会满足却依然次数相同且包含关系不成立的情况
eg: ABCDABFABCD
页框为3时，最后集合为{F, C, D} 缺页9次
页框为4时，最后集合为{A, B, C, D} 缺9页次
所以入下一个是元素为F，那么页框为4的缺页数还更大。

Answer 3

使用LRU，内存有n页的情况下，内存里放的是最近访问的n页内存。在任何时间t，如果你能在最近访问的n页里找到你想要的那一页内存，那你也能在最近的n+1页里找到那页内存。所以缺页率不会上升。

追答

顺便堆栈算法是什么。。那个需要预知未来的算法吗

哦我知道了。。无视我

追问

除了lru呢。。其他也需要证明。

意思大概行，但纵观整个回答，我觉得应该和标准答案(如果有)差了挺多。OPT这种没法实现的算法也能证明？要是又考到这题。。。怎么组织语言。逐个证明简直无语。

追答

OPT也是和内存页数无关的优先级啊。。我来组织一下
对于任意堆栈算法F，和一个给定的内存访问顺序P={a0, a1, .....}，用F(n, t)表示当内存总页数为n，时间为t时，内存中存放的内存页的集合。要证明缺页率不会上升，只要证明F(n, t)≦F(n+1, t)。（符号打不出来将就一下）
由堆栈算法的性质得知，在任意时间点t，我们都可以给每个内存页k一个与n无关的优先级p(k, t)，并且对于k1≠k2, p(k1, t)≠p(k2, t)。所以可以根据优先级给所有内存页一个排序p1, p2, ... pM，F(n, t)是这个排序的前n个，F(n+1, t)是前n+1个，所以F(n, t)≦F(n+1, t)。