存储管理的页面置换算法
存储管理的页面置换算法在考试中常常会考到，操作系统教材中主要介绍了3种常用的页面置换算法，分别是：先进先出法（FIFO）、最佳置换法（OPT）和最近最少使用置换法（LRU）。大家要理解3种置换算法的含义，然后能熟练地运用在具体的练习中就可以了。
-
为什么要进行页面置换
在请求分页存储管理系统中，由于使用了虚拟存储管理技术，使得所有的进程页面不是一次性地全部调入内存，而是部分页面装入。
这就有可能出现下面的情况：要访问的页面不在内存，这时系统产生缺页中断。操作系统在处理缺页中断时，要把所需页面从外存调入到内存中。如果这时内存中有空闲块，就可以直接调入该页面；如果这时内存中没有空闲块，就必须先淘汰一个已经在内存中的页面，腾出空间，再把所需的页面装入，即进行页面置换。
有助于理解的关键词有：请求分页、虚拟存储、缺页中断、页面置换。
-
常用的页面置换算法
教材中介绍的常用页面置换算法有：先进先出法（FIFO）、最佳置换法（OPT）和最近最少使用置换法（LRU）。
-
先进先出法（FIFO）
算法描述：由于认为最早调入内存的页不再被使用的可能性要大于刚调入内存的页，因此，先进先出法总是淘汰在内存中停留时间最长的一页，即先进入内存的页，先被换出。先进先出法把一个进程所有在内存中的页按进入内存的次序排队，淘汰页面总是在队首进行。如果一个页面刚被放入内存，就把它插在队尾。
【例1】教材第4章课后习题。
考虑下述页面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6。当内存块数量分别为3，5时，试问先进先出置换算法（FIFO）的缺页次数是多少？（注意，所有内存块最初都是空的，凡第一次用到的页面都产生一次缺页。）
解：当内存块数量分别为3时，FIFO算法的执行过程如下图所示。
|
页面 |
1 |
2 |
3 |
4 |
2 |
1 |
5 |
6 |
2 |
1 |
2 |
3 |
7 |
6 |
3 |
2 |
1 |
2 |
3 |
6 |
|
块1 |
1 |
1 |
1 |
4 |
|
4 |
4 |
6 |
6 |
6 |
|
3 |
3 |
3 |
|
2 |
2 |
|
2 |
6 |
|
块2 |
|
2 |
2 |
2 |
|
1 |
1 |
1 |
2 |
2 |
|
2 |
7 |
7 |
|
7 |
1 |
|
1 |
1 |
|
块3 |
|
|
3 |
3 |
|
3 |
5 |
5 |
5 |
1 |
|
1 |
1 |
6 |
|
6 |
6 |
|
3 |
3 |
|
缺页 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
打叉的表示发生了缺页，共缺页16次。
提示：当FIFO算法执行到蓝色的4号页面时，这时内存中有三个页面，分别是1，2，3。按照FIFO算法，在内存中停留时间最长的页面被淘汰。三个页面在内存中的停留时间用绿色区域标记出来了，可见，1号页面是停留时间最长的，因此要淘汰1号页面。
当内存块数量分别为5时，共缺页10次。FIFO算法的执行过程如下。
|
页面 |
1 |
2 |
3 |
4 |
2 |
1 |
5 |
6 |
2 |
1 |
2 |
3 |
7 |
6 |
3 |
2 |
1 |
2 |
3 |
6 |
|
块1 |
1 |
1 |
1 |
1 |
1 |
|
|
6 |
|
6 |
6 |
6 |
6 |
|
|
|
|
|
|
|
|
块2 |
|
2 |
2 |
2 |
2 |
|
|
2 |
|
1 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
块3 |
|
|
3 |
3 |
3 |
|
|
3 |
|
3 |
2 |
2 |
2 |
|
|
|
|
|
|
|
|
块4 |
|
|
|
4 |
4 |
|
|
4 |
|
4 |
4 |
3 |
3 |
|
|
|
|
|
|
|
|
块5 |
|
|
|
|
5 |
|
|
5 |
|
5 |
5 |
5 |
7 |
|
|
|
|
|
|
|
|
缺页 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
优缺点：先进先出法（FIFO）简单易于实现，但是性能不好，存在Belady现象。例如对于以下页面：1，2，3，4，1，2，5，1，2，3，4，5，当内存块为3时，出现9次缺页中断；当内存块为4时，出现10次缺页中断。缺页率随着内存块增加而增加的现象，称为Belady现象。有兴趣的同学可以试一试，看看是不是这样的。
-
最佳置换法（OPT）
算法描述：最佳置换算法（OPT）在为调入新页面而必须预先淘汰某个老页面时，所选择的老页面应在将来不被使用，或者是在最远的将来才被访问。采用这种算法，能保证有最小缺页率。
【例2】教材第4章课后习题。
考虑下述页面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6。当内存块数量分别为3，5时，试问最佳置换法（OPT）的缺页次数是多少？（注意，所有内存块最初都是空的，凡第一次用到的页面都产生一次缺页。）
解：当内存块数量分别为3时，OPT算法的执行过程如下图所示。
|
页面 |
1 |
2 |
3 |
4 |
2 |
1 |
5 |
6 |
2 |
1 |
2 |
3 |
7 |
6 |
3 |
2 |
1 |
2 |
3 |
6 |
|
块1 |
1 |
1 |
1 |
1 |
|
|
1 |
1 |
|
|
|
3 |
3 |
|
|
3 |
3 |
|
|
6 |
|
块2 |
|
2 |
2 |
2 |
|
|
2 |
2 |
|
|
|
2 |
7 |
|
|
2 |
2 |
|
|
2 |
|
块3 |
|
|
3 |
4 |
|
|
5 |
6 |
|
|
|
6 |
6 |
|
|
6 |
1 |
|
|
1 |
|
缺页 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
打叉的表示发生了缺页，共缺页11次。
提示：当OPT算法执行到蓝色的4号页面时，这时内存中有三个页面，分别是1，2，3。按照OPT算法，在最远的将来才被访问的页面先淘汰。这三个页面在未来页面走向序列的位置用绿色区域标记出来了，可见，3号页面是最晚被访问到的，因此要淘汰3号页面。到了最后一个6号页面时，由于没有后续的页面序列了，可以随机选择一个页面淘汰。
当内存块数量分别为5时，共缺页7次。OPT算法的执行过程如下。
|
页面 |
1 |
2 |
3 |
4 |
2 |
1 |
5 |
6 |
2 |
1 |
2 |
3 |
7 |
6 |
3 |
2 |
1 |
2 |
3 |
6 |
|
块1 |
1 |
1 |
1 |
1 |
1 |
|
|
1 |
|
|
|
|
1 |
|
|
|
|
|
|
|
|
块2 |
|
2 |
2 |
2 |
2 |
|
|
2 |
|
|
|
|
2 |
|
|
|
|
|
|
|
|
块3 |
|
|
3 |
3 |
3 |
|
|
3 |
|
|
|
|
3 |
|
|
|
|
|
|
|
|
块4 |
|
|
|
4 |
4 |
|
|
6 |
|
|
|
|
6 |
|
|
|
|
|
|
|
|
块5 |
|
|
|
|
5 |
|
|
5 |
|
|
|
|
7 |
|
|
|
|
|
|
|
|
缺页 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
优缺点：OPT算法因为要需要预先知道一个进程在整个运行过程中页面走向的全部情况，因此只是一种理想状态，实际是行不通的。一般用算法来衡量（如通过模拟实验分析或理论分析）其他算法的优劣。
-
最近最少使用置换法（LRU）
算法描述：最近最少使用置换法（LRU）是选择在最近一段时间里最久没有使用过的页面予以淘汰。借鉴FIFO算法和OPT算法，以“最近的过去”作为“不久将来”的近似。
【例3】教材第4章课后习题。
考虑下述页面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6。当内存块数量分别为3，5时，试问最近最少使用置换法（LRU）的缺页次数是多少？（注意，所有内存块最初都是空的，凡第一次用到的页面都产生一次缺页。）
解：当内存块数量分别为3时，LRU算法的执行过程如下图所示。
|
页面 |
1 |
2 |
3 |
4 |
2 |
1 |
5 |
6 |
2 |
1 |
2 |
3 |
7 |
6 |
3 |
2 |
1 |
2 |
3 |
6 |
|
块1 |
1 |
1 |
1 |
4 |
|
4 |
5 |
5 |
5 |
1 |
|
1 |
7 |
7 |
|
2 |
2 |
|
|
2 |
|
块2 |
|
2 |
2 |
2 |
|
2 |
2 |
6 |
6 |
6 |
|
3 |
3 |
3 |
|
3 |
3 |
|
|
3 |
|
块3 |
|
|
3 |
3 |
|
1 |
1 |
1 |
2 |
2 |
|
2 |
2 |
6 |
|
6 |
1 |
|
|
1 |
|
缺页 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
打叉的表示发生了缺页，共缺页15次。
提示：当LRU算法执行到蓝色的4号页面时，这时内存中有三个页面，分别是1，2，3。按照LRU算法，在最近一段时间里最久没有使用过的页面予以淘汰。这三个页面在4号页面之前的页面走向序列中的位置用绿色区域标记出来了，可见，1号页面是最久没有被使用过的，因此要淘汰1号页面。
当内存块数量分别为5时，共缺页8次。LRU算法的执行过程如下。
|
页面 |
1 |
2 |
3 |
4 |
2 |
1 |
5 |
6 |
2 |
1 |
2 |
3 |
7 |
6 |
3 |
2 |
1 |
2 |
3 |
6 |
|
块1 |
1 |
1 |
1 |
1 |
1 |
|
|
1 |
|
|
|
1 |
1 |
|
|
|
|
|
|
|
|
块2 |
|
2 |
2 |
2 |
2 |
|
|
2 |
|
|
|
2 |
2 |
|
|
|
|
|
|
|
|
块3 |
|
|
3 |
3 |
3 |
|
|
6 |
|
|
|
6 |
6 |
|
|
|
|
|
|
|
|
块4 |
|
|
|
4 |
4 |
|
|
4 |
|
|
|
3 |
3 |
|
|
|
|
|
|
|
|
块5 |
|
|
|
|
5 |
|
|
5 |
|
|
|
5 |
7 |
|
|
|
|
|
|
|
|
缺页 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
优缺点：LRU算法是经常采用的页面置换算法。缺点是实现上需要大量的硬件支持。
3. 需要注意的问题
-
不要把存储管理的页面置换算法与处理机调度算法混淆。有的同学可能会将FIFO和FCFS弄混，FIFO是先进先出页面置换算法，FCFS是先来先服务的作业调动算法，虽然道理相似，却用在不同的地方。
-
缺页率。教材中提到了缺页率，没有给出它的概念。缺页率=缺页次数/页面总数。以上面3个例题为例，缺页率如下：
|
算法 |
FIFO |
OPT |
LRU |
|
内存块为3 |
16/20=80% |
11/20=55% |
15/20=75% |
|
内存块为5 |
10/20=50% |
7/20=35% |
8/20=40% |
影响缺页率的因素有分配给进程的内存块数和页面尺寸等。一般来说，内存块数多，页面增大，使得发生缺页的可能性下降。但是这不是绝对的，还存在着Belady现象。
（3）衡量页面置换算法好坏的标准是：好的算法能适当减少缺页率，避免系统“抖动”。