OPT

理想页面置换算法(Optimal replacement，OPT)
OPT算法淘汰以后不再需要的或者在最长时间以后才会用到的页面

页面走向可以从左往右看

例题

某程序在内存中分配三个页面，初始为空，所需页面的走向为4,3,2,1,4,3,5,4,3,2,1,5。采用OPT算法，计算缺页次数。

列表

解题过程：

   开始时，内存中三个页面都是空的，故产生第一个缺页异常，需要把页面4调入。同样也产生第二个缺页异常，需要把页面3调入；产生第三个缺页异常，需要把页面2调入
   此时，三个页面都已满了，根据OPT的原则，发现页面2比页面3，4需要更长时间才会出现，把页面2替换成页面1，继续走向页面4，发现有页面4存在，无需替换，则没有缺页情况；
   继续，直到走到页面5，发现没有页面5存在，查找当前存在的页面，发现页面1需要很长时间才会用到，替换页面1；走到页面4，发现有页面4存在，无缺页情况；继续，直到走到页面2，发现内存中没有页面2存在，然后查找，发现除了页面5后面要用到，其它都不需要，那么选一个替换(两个都可以，这里选中时间长的)，后面也是上面步骤
   缺页异常为7次

FIFO

先进先出页面置换算法(First-In First-Out，FIFO)
总是选择最先装入内存的页面调出，或者说，把驻留在内存中时间最长的那一页调出。

页面走向可以从右往左看

例题1

某程序在内存中分配三个页面，初始为空，所需页面的走向为4,3,2,1,4,3,5,4,3,2,1,5。采用FIFO算法，计算缺页次数。

列表

解题过程

基本思路和OPT一样，只不过淘汰的是存在时间最长的(OPT是淘汰很长时间不用的)
缺页异常9次

例题2

某程序在内存中分配m个页面，初始为空，所需页面的走向为1,2,3,4,1,2,5,1,2,3,4,5。m=3,m=4时，使用FIFO算法，计算缺页次数。说明所出现的现象

解题过程
m = 3时

缺页异常9次

m = 4时

缺页异常10次

Belady现象:

当分配给进程的页面数增加时，缺页次数反而增加

LRU

最近最少使用算法(Least Recently Used，LRU)
总是选择距离现在最长时间内没有被访问过的页面先调出。

页面走向可以从右往左看

例题

某程序在内存中分配三个页面，初始为空，所需页面的走向为4,3,2,1,4,3,5,4,3,2,1,5。采用FIFO算法，计算缺页次数。

列表
时间短中长页面为：没有被访问过的时间长短

解题过程

   基本过程和FIFO一样，只是每次要按没被访问过的时间排列。
   向上面的无缺页那项，按照没被访问过的时间重新排列，长时间没被访问过的放在最下面(也就是具体该页面最远的)，其次是最近时间访问过的
   产生10次缺页异常

缺页率

f = F / A
F为缺页次数，A为页面总访问次数

参考

• 英俊帅比林-页面置换算法（OPT，FIFO，LRU）
• fkissx-操作系统之页面置换算法