LRU 不会出现 belady 异常的证明

对于最近最久未使用算法(LRU, Least Recently Used),是不会出现belady异常(belady anomaly)的,证明如下:

设分配给当前进程的页面数量为n,令S_n为当前时刻t,某个进程驻留在内存中的所有页面的集合。要证明LRU不会出现belady异常,即证对于任意的k > 0,给进程分配的页面数量为n + k时,对于同一个页面访问序列,S_n 总是 S_{n+k} 的一个子集。不妨简单地令 k = 1k > 1 的情况同理。以下归纳地证明该结论。

  • t = 1时,S_nS_{n+1}都只包含同一个页面,结论成立。
  • 假设t < t_{k - 1}时,该结论成立。
  • t = t_k时,设此时访问的页面为c_k。以下分为三种情况讨论:
    • c_k \in S_n,则显然c_k \in S_{n+1},访问c_k不会引发缺页异常,因此访问c_k后假设显然成立。
    • c_k \in S_{n+1}但是c_k \notin S_n,此时对于序列S_n会引发一次缺页异常,导致其中一个页面被换出以及c_k被换入,此时仍然保持S_n \subset S_{n+1},假设成立。
    • c_k \notin S_n并且c_k \notin S_{n+1},此时两个集合都会产生缺页异常。假设此时S_n中被换出的页面为x_1,若S_{n+1}被换出的页面也是x_1,则假设仍然成立;否则,设S_{n+1}中被换出的页面为x_2, x_2 \neq x_1,由于是采用LRU算法,则x_2必然是比x_1更久未被使用的页面,倘若x_2 \in S_n,则S_n中被换出的页面也应该是x_2,而不是使用相对频繁的x_1,这与假设矛盾,故x_2 \notin S_n,缺页异常处理完毕后原假设仍然成立。

证毕。

实际上,对于最优置换算法(OPT),以及恢复计数的最不常用算法(LFU, Least Frequently Used),都可以类似地证明不会出现belady异常。然而,其他的页面置换算法,包括FIFO时钟置换算法(clock)以及改进的时钟置换算法,不恢复计数的最不常用算法,则都可以构造出出现belady异常的实例。

Leave a Reply

Your email address will not be published. Required fields are marked *