存储管理——页面置换算法

内存的空间相对来说是比较小的，这个时候程序在执行过程中遵循一个局部性原理，当前正在运行的部分需要装载内存中，不在运行的部分会从内存中退出，所以会有一个不断装载和退出的过程，这就是置换过程。

置换过程有一种叫先进先出，先进先出指的是那一页先进的内存，淘汰的时候就先淘汰那一页。

还有一种叫最佳置换法，就是查看这一页在内存中访问的状况，如果这一页经常被访问到，那么这一页就不用进行置换，置换的是不经常被访问的那一页。

最后是最近最少使用置换法，就是看最近那一页最少被使用然后对其进行一个置换。

例题

“×”为缺页，“○”为不缺页

先进先出法（FIFO）：

考虑下述页面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6。当内存块数量为3时，试问先进先出置换算法（FIFO）的缺页次数是多少？（注意：所有内存块最初都是空，凡是第一次用到页面都产生一次缺页）

第一次访问的页面为1，但是内存是空的，所以缺页，这时候把1装载到块1里面。

第二次访问页面2，这时候块1装载的是页面1，块2和块3是空的，所以缺页，然后把页面2转装到块2中。

第三次访问页面3，这时候块1装载的是页面1，块2装载的是页面2，快3为空，所以访问页面3的时候缺页，然后把页面3装载到块3中。

第四次访问的是页面4，这时候块1装载的是页面1，块2装载的是页面2，块3装载的是页面3，所以也是缺页，但是这时候内存占满，已经没有空间装载页面4，所以开始淘汰，这里使用的是先进先出淘汰法（FIFO），也就是最先装载的最先淘汰，页面1是最先装载进来的，所以先把页面1淘汰掉腾出空间装载页面4。

第五次访问的是页面2，这时候块1里面装载的是页面4，块2里面装载的是页面2，块3里面装载的是页面3，需要访问的是页面2，就存在块2中，所以不缺页，不缺页就不需要装载，所以内存块里面的页面保持不变。

第六次访问的是页面1，这时候块1里面是页面4，块2里面是页面2，块3里面是页面3，也是缺页的并且内存被占满，这时候就需要淘汰掉一个然后把页面1装载进来，最先装载的是块1里面的页面1，然后是块2里面的页面2，再到块3里面的页面3，第四次访问的时候页面1刚被置换掉，第六次访问的时候保持不变，所以现在最先进入的是块2，需要把块2里面的页面2置换成当前所需的页面1。

第七次访问的是页面5，这时候块1里面是页面4，块2里面是页面1，块3里面是页面3，也是缺页并且内存占满，这时候最先进入的是页面3，因为块1和块2里面的页面页面4和页面1是刚置换装载的，把页面3置换为现在需要的页面5

第八次访问的是页面6，这时块1里面是页面4，块2里面是页面1，块三里面是页面5，也是缺页并且内存被占满，这时候块1，块2，块3都已经被置换过一次了，最先置换进来的是块1的页面4，所以现在要把页面4置换为当前所需的页面。

第九次访问的是页面2，这时块1里面是页面6，块2里面是页面1，块3里面是页面5，也是缺页并且内存占满，块1已经被置换过两次了，块2和块3都只被置换1次，块2比块3先被置换的，也就是目前块2里面的页面1是最先进入的，所以把块2里面的页面1置换为当前所需要的页面。

第十次访问的是页面1，这时块1里面时页面6，块2里面是页面2，块3里面是页面5，也是缺页并且内存占满，块1和块2已经置换两次，就剩块3只置换了一次，置换次数越少的说明进入时间是最早的，所以需要把快三里面的页面5置换为当前所需要的页。

第十一次访问的是页面2，这时候块1里面是页面6，块2里面是页面2，已经存在页面2，就说明不缺页了，内存里面的页面页不需要置换。

第十二次访问的是页面3，块1到块3里面没有页面3，缺页，块1到块3都经历了两次置换，现在最先进入的是块1的页面6，把最先进入的置换为当前所需的。

第十三次访问的是页面7，这时候块1到块3里面都没有页面7，所以缺页，块1已经经历3次置换，块2和块3才经历了2次置换，目前为止块2的页面2是最先进入的，所以需要把块2的页面2置换为当前所需的。

以此类推，最后得出的结果如下表，总共缺页16次。

最佳置换法（OPT）：

考虑下述页面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6。当内存块数量为3时，试问最佳置换算法（FIFO）的缺页次数是多少？（注意：所有内存块最初都是空，凡是第一次用到页面都产生一次缺页）

最开始访问页面1的时候，这时候内存为空，所以为缺页，把页面页装载到块1中

第二次访问的是页面2，这时候块1厘面为页面2，块2和块3为空，所以缺页，把页面2装载到块2中

第三次访问的是页面3，这时候块1里面为页面1，块2里面为页面2，块3为空，所以缺页，把页面3装载到块3中

第四次访问的是页面4，这时候块2、块2、块3里面分别是页面1，页面2和页面3，没有页面4并且内存占满，所以为缺页，这时候需要把一个块里面的页面置换为页面4，这里使用的是最佳置换法（OPT），最佳置换法需要看后面访问到的页面，页面4之后访问的是页面2，在后面是页面1，页面2和页面1是马上就需要访问的，所以不能置换掉，只能把块3里面的页面3置换为页面4。

第五次访问的是页面2，页面2就在块2中，不缺页，所以不需要置换，内存里面的内容保持不变。

第六次访问的页面1，页面1在块1中，不缺页，所以不需要置换，内存里面的内容保持不变。

第七次访问的是页面5，块1到块3中都不存在页面5，缺页，现在需要置换掉一个块里面的页为当前需要访问的页面5，使用最佳置换法，页面5之后需要访问到的是页面6，当前块1到块3中也没有页面6，所以忽略掉，页面6之后需要访问的是页面2，块2中存在页面2，不能置换，页面2之后需要访问的是页面1，当前块1中存在页面1，所以也不能置换，那么只能把块3中的页面4置换为当前所需要访问的页面5

第八次访问的是页面6，块1到块3中不存在页面6，缺页，需要把一个块里面的页面置换为页面6，页面6之后需要访问到的是页面2，不能置换掉，页面2之后需要访问的是页面1，不能置换，那么只能把块3里面的页面5置换为现在需要访问的页面6了。

第九次访问的是页面2，块2中的就是页面2，不缺页，所以不需要置换，内存里面的内容保持不变。

第十次访问的是页面1，块1中即为页面1，不缺页，所以不需要置换，内存里面的内容保持不变。

第十一次访问的是页面2，块2中就是页面2，不缺页，所以不需要置换，内存中的内容保持不变。

第十二次访问的是页面3，块1到块3中没有页面3，需要置换掉一个块里面的页面为页面3，页面3之后需要访问的是页面7，当前块1到块3中没有页面7，忽略掉往下看，页面7之后是页面6，块3中为页面6，不能置换，页面6之后是页面3，块1到块3中没有页面3，忽略掉往下看，页面3之后是页面2，块2中为页面2，所以置换的是块1中的页面1。

以此类推得出下表，可以看出使用最佳置换法有11个缺页。

注意：因为在实际中，下一个需要访问的页是不可预测的，所以最佳置换法不可行

最近最少使用置换法（LRU）

考虑下述页面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6。当内存块数量为3时，试问最近最少使用置换算法（LRU）的缺页次数是多少？（注意：所有内存块最初都是空，凡是第一次用到页面都产生一次缺页）

第一次访问的是页面1，当前内存为空，所以缺页，把页面1加载到块1中。

第二次访问的是页面2，当前内存中块1里面加载的为页面1，块2和块3为空，所以缺页，把页面2加载到块2中。

第三次访问的是页面3，当前内存中块1为页面1，块2为页面2，块3为空，所以缺页，把页面3加载到块3中。

第四次访问的是页面4，现在块1到块3中的内容分别是页面1、页面2、页面3，没有页面4，缺页，需要把一个块里面的页面置换为当前需要访问的页面，这里使用最近最少使用置换法，最近使用的页面是1、2、3，而且都是使用了1次，所以从头开始置换，把块1中的页面1置换为现在需要访问的页面4。

第五次访问的是页面2，块2中就是页面2，不缺页，内存里的内容保持不变。

第六次访问的页面是1，块1到块3中没有页面1，缺页，最近使用的是页面2和页面4，所以块1和块2中的页面4和页面2不能置换掉，只能把块3中的页面3置换为页面1。

第七次访问的是页面5，块1到块3中没有页面5，缺页，最近访问到的页面为页面1和页面2，所以置换掉块1中的页面4。

第八次访问的是页面6，块1到块3中没有页面6，最近访问的页面为页面5和页面1，所以块1和块3不能置换掉，只能把块2的页面2置换为页面6。

以此类推，最后得出的结果为下表，得出缺页数为15。