323_页面置换算法
# 3.2_3_页面置换算法
在这个小节中我们会学习请求分页存储管理当中很重要的一个知识点考点，页面置换算法。那么通过之前的学习，我们知道在请求分页存储管理当中，如果说内存空间不够的话，那么操作系统会负责把内存当中暂时用不到的那些信息先换出外存。页面置换算法其实就是用于选择到底要把哪个页面换出外存。
通过之前的学习我们知道页面的换入换出其实是需要启动磁盘的 IO 的，因此它是会造成比较大的时间开销，所以一个好的页面置换算法应该尽可能的追求更少的缺页率，也就是让换入换出的次数尽可能的少。这个小节中我们会介绍考试中要求我们掌握的 5 种页面置换算法，分别是最佳置换，先进先出，最近最久未使用，还有时钟置换，改进型的时钟置换这样 5 种。除了注意他们的中文名字之外，大家也需要能够区分他们的英文缩写到底分别是什么，我们按从上至下的顺序依次介绍。
# 最佳置换算法
首先来看什么是最佳置换算法，其实最佳置换算法的思想很简单，由于置换算法需要追求尽可能少的缺页率，为了追求最低的确页率，最佳置换算法在每次淘汰页面的时候，选择的都是那些以后永远不会被使用到的页面，或者在之后最长的时间内不可能再被访问的页面。
我们直接来看一个例子来加深理解，假设系统为一个进程分配了三个内存块，然后进程执行的过程当中会依次需要访问到这些页面，那刚开始进程需要访问的是 7 号页面，由于刚开始为进程分配的这三个内存块都是空的，所以我们可以选择把 7 号页面放入内存块一当中。
第二个要访问到的页面是 0 号页，由于此时依然还有空闲的内存块，所以我们可以把 0 号页放入内存块二当中。
第三个要访问的是一号页面，同样的此时还剩一个空闲的内存块，所以一号页面可以放到内存块三当中。
第四个我们需要访问到的是二号页面，但是由于此时给进程分配的三个内存块都已经占满了，所以我们必须用页面置换算法选择淘汰其中的某一个页面，把那个页面先换出外存。根据最佳置换算法的规则，我们要选择的是在今后最长时间内不会被使用到的页面，所以其实我们在手动做题的时候，可以看一下它的序列，我们从当前访问的页号开始往后寻找，看一下此时在内存当中的 0，1，7 这三个页面出现的顺序到底是什么？最后一个出现的序号肯定就是在之后最长时间内不会再被访问的页面。所以从这往后看，0 号页面是最先出现的，三号页面不属于 017 当中的任何一个，所以跳过 0 号页面之后会再次出现，然后 4 号也不属于 017，之后又会出现 2 号页面、3 号页面，0 号页面，然后一直到这个位置，我们发现一号页面也开始出现了，所以 0，1，7 这三个页面当中，0 号和 1 号会在之后依次被使用，但是 7 号页面是在之后最长的时间内不会再被访问到的页面，因此我们会选择淘汰 7 号页面，然后让 2 号页面放入到 7 号页面，原先占有的内存块也就是内存块一当中，因此二号页面是放在这个位置的，
接下来要访问的 0 号页面已经在内存当中了，所以此时不会发生缺页，可以正常的访问。
再之后访问三号页面，也会发现此时三号页面并没有在内存当中，所以我们依然需要用置换算法选择淘汰一个页面。那么那和刚才一样，我们从这个位置开始往后寻找，看一下此时内存当中存放的2，0，1 这三个页面出现的先后顺序，我们会发现 2，0，1 当中0 号页面是最先出现的，之后 2 号页面紧接着出现，那么一号页面就是最后一个出现的，因此一号页面是在今后最长时间内不会再被访问的页面，所以我们会选择把 201 这三个页面当中的一号页面给淘汰，先换出外存，然后三号页面再换入一号页面以前占有的内存块，也就是内存块三当中，所以三号页面是放在这个地方的。
对于之后的这些页面序号的访问，我们就不再细细的分析了，大家可以自己尝试着去完善一下这个表。最终我们会发现整个访问这些页面的过程当中，缺页中断发生了 9 次，也就打钩的这些位置发生了缺页中断，但是页面置换只发生了 6 次，所以大家一定需要注意，缺页中断之后未必发生页面置换，只有内存块已经都满了的时候才需要页面置换。因此在刚开始访问 701 这三个页面的时候，虽然他们都没有在内存当中，但是由于刚开始有空闲的内存块，所以虽然发生了缺页中断，发生调页，但是并不会发生页面置换这件事情，只有所有的内存块都已经占满了之后，再发生缺页的话，才需要进行页面置换这件事情。因此区域中段总共发生了 9 次，但是页面置换只发生了 6 次，前面的 3 次只是发生了缺页，但是并没有页面置换。
缺页率的计算也很简单，我们只需要把缺页中断发生的次数，再除以我们总共访问了多少次的页面，就可以得到确认率是 45%，这是最佳置换算法。其实最佳置换算法执行的前提条件是我们必须要知道之后会依次访问的页面序列到底是哪些，不过在实际应用当中，只有在进程执行的过程当中，才能一步一步的知道接下来会访问到的到底是哪一个页面，所以操作系统其实根本不可能提前预判各个页面的访问序列，所以最佳置换算法它只是一种理想化的算法，在实际应用当中是无法实现的。
# 先进先出
接下来我们再来看第二种先进先出置换算法，这种算法的思想很简单，每次选择淘汰的页面是最早进入内存的页面，所以在具体实现的时候，可以把调入内存的这些页面，根据调入的先后顺序来排成一个队列，当系统发现需要换出一个页面的时候，只需要把对头的页面淘汰就可以了。需要注意的是这个队列有一个最大长度的限制，最大长度取决于系统为进程分配了多少个内存块。
我们还是来看一个例子，假设一个系统为进程分配了三个内存块，然后会按照这样的顺序依次访问各个页面，
首先访问的是三号页面，此时内存块一是空闲的，所以可以把三号页面放到内存块一当中，并且把三号页面放到我们之前提到的队列的队头。第二个页面是二号页面，此时也有内存块空闲，所以二号页面放到内存块二当中，然后再把二号页面放到队列的队尾，也就是把它接在三号页面之后的位置。同样的一号页面此时也有内存块，所以它放在内存块三当中，并且把一号页面放到队列的队尾。
接下来访问到第四个页面的时候，此时要访问的是 0 号页面，但是由于此时所有的内存块都已经占满了，所以必须选择淘汰其中的某一个页面。那么根据系统维持的队列，可以知道三号页面进入内存的时间是最早的，所以会选择淘汰三号页面，然后把三号页面占有的内存块一分配给 0 号页面，相应的 0 号页面放入内存之后，也需要把它插到队列的队尾。
接下来如果还要再访问三号页面的话，同样的是需要把队头的页面给淘汰掉，所以二号页面会换出外存，然后三号页面放到二号页面以前占有的内存块二当中，并且会把三号页面放到队列的队尾
以此类推，剩下的过程就不再细细分析了，大家可以自己再去尝动手尝试一下。整个过程下来会发现，如果给进程分配了三个内存块的话，那么缺页次数总共是 9 次，
我们再把这个题目的条件改一下，如果说给进程分配的是 4 个内存块的话，按照我们之前分析的这种方法，最终会得到这样一系列的结果，大家也可以自己动手尝试分析整个过程。不过这个地方我们想强调的是，当为进程分配了 4 个内存块的时候，虽然说页面的访问序列依然是这样 1 个序列，但是整个过程下来缺页次数总共发生了 10 次，大家可以数一下，但是之前本来改给进程分配的内存块只有 3 个，但是 3 个内存块的时候，缺页次数反而更少，只发生了 9 次。
其实乍一想来为一个进程分配的内存块越多，进程的缺页次数应该越少才对。所以像这个地方我们发现的这种现象就是为进程分配物理块增大的时候，缺页次数不增防减的这种现象，就称作为 Belady 异常，在我们要学习的所有的这些算法当中，只有先进先出算法会产生这种 Belady 异常。所以虽然先进先出算法实现起来很简单，但是先进先出的这种规则其实并没有考虑到进程实际运行时候的一些规律，因为先进入内存的页面，其实在之后也有可能会被经常访问到，所以只是简单粗暴的让先进入的页面淘汰的话，显然这是不太科学的，所以先进先出置换算法的算法性能是很差的。
# 最近最久未使用置换算法
接下来我们再来看第三个，最近最久未使用置换算法，英文缩写是 LRU，大家也需要记住它的英文缩写，很多题目出题的时候就直接用这样 LRU 来表示置换算法。这个算法的规则就像它的名字一样，就是要选择淘汰最近最久没有使用的页面，所以为了实现这件事，我们可以在每个页面的页表项当中的访问字段这儿，记录这个页面自从上一次被访问开始，到现在为止所经历的时间 T。我们需要淘汰一个页面的时候，只需要选择 T 值最大的，也就是最久没有被访问到的页面进行淘汰就可以了。
我们依然还是结合一个例子，如果 1 个系统为进程分配了 4 个内存块，然后有这样的一系列的页面访问序列，
首先要访问的是一号页，此时有内存块空闲，所以一号页放到内存块一当中。
然后第二个访问 8 号页面也可以直接放到空闲的内存块二当中，以此类推访问一号页面，由于此时 1 号页已经在内存中了，所以不会发生缺页，之后访问的 7 号 8 号 2 号，所有的这些都不会发生页面置换，因为此时一直都会有空闲的内存块
一直到后面访问到三号页面的时候，由于此时给进程分配的 4 个内存块都已经用完了，所以必须选择淘汰其中的某个页面。如果我们在手动做题的时候，可以从一号开始逆向的往前检查，此时在内存当中拥有的 1872 这几个页号，从逆向扫描来看，出现的先后顺序是什么样的？最后一个出现的页号肯定最近最久没有使用的页面了，所以从这往前看，8 号页面首先出现之后出现了 1 号页面，再之后出现了 2 号页面，所以 7 号页面其实是这 4 个页面当中最近最久没有被使用到的页面，因此会选择把 7 号页面淘汰，然后 3 号页就会放入到以前 7 号页占用的内存块三当中
同样的在之后的这一系列访问当中都不会发生缺页，一直到访问到 7 号页的时候，又发生了一次缺页，并且需要选择淘汰一个页面。和之前一样，我们从这个地方开始逆向的往前检查，看一下这几个一号出现的顺序分别是什么样的。首先一号页是最先出现的，再往前三号也出现了，再往前是二号也出现了，所以8 号页是这几个页面当中最近最久没有被使用到的页面，因此会选择淘汰 8 号页，然后把 7 号页放入8 号也以前占用的内存块二当中。
最近最久未使用置换算法，在实际的应用当中实际上是需要专门的硬件的支持的，所以这个算法虽然性能很好，但是实现起来会很困难，并且开销很大。在我们学习的这几个算法当中，最近最久未使用这个算法的性能，是最接近最佳置换算法的。
# 时钟置换算法
接下来我们再来看第四种时钟置换算法，之前我们学到的这几种算法当中，最佳置换算法性能是最好的，但是无法实现。先进先出算法，虽然实现简单，但是算法的性能很差，并且也会出现 Belady 异常。最近最久未使用置换算法，虽然性能也很好，但是实现起来开销会比较大，所以之前提到的那些算法都不能做到算法效果，还有实际开销的一个平衡
因此人们就提出了时钟置换算法，它是一种性能和开销比较均衡的算法，又称为 clock 算法，或者叫最近未用算法，而英文缩写是 NRU。在考试中我们需要掌握两种时钟置换算法，分别是的时钟置换算法，还有改进型的时钟置换算法，
我们先来看简单的这种算法。首先我们要为每个页面设置一个访问位，访问位为一的时候就表示这个页面最近被访问过，访问位为 0 的时候表示这个页面最近没有被访问过，因此如果说访问了某个页面的话，需要把这个页面的访问位变为一
内存中的这些页面，需要通过链接指针的方式把它们链接成一个循环队列，当需要淘汰某一个页面的时候，需要扫描循环队列，找到一个最近没有被访问过的页面，也就是访问位为 0 的页面，但是在扫描的过程中，需要把访问位为一的这些页面的访问位再重新置为 0
所以这个算法有可能会经过两轮的扫描，如果说所有的页面访问位都是一的话，第一轮扫描循环队列就并不会找到任何一个访问位为 0 的页面，只不过在第一轮扫描当中会把所有的页面的访问位都置为 0，所以在第二轮扫描的时候就肯定可以找到一个访问位为 0 的页面。所以这个算法在淘汰一个页面的时候，最多会经历两轮的扫描，
光看文字的描述其实还是很抽象的，我们直接来看 1 个例子，假设 1 个系统为进程分配了 5 个内存块，然后对各个页面号的引用是按照这样的顺序进行的，刚开始由于有 5 个空闲的内存块，所以前 5 个访问的页号 1，3，4，2，5都可以顺利的放入内存当中，只有在访问到 6 号页的时候，才需要考虑淘汰某个页面。
那么在内存当中的 1，3，4，2，5 这几个页面，会通过链接指针的方式链接成一个这样的循环队列。由于接下来要访问 6 号页面，但是 5 个内存块都已经满了，所以需要用 clock 算法来选择淘汰其中的某一个页面，于是会从这个循环队列的对手开始扫描，尝试找到一个访问位为 0 的页面，并且被扫描过的页面需要把访问位 1 改为 0。
所以在经过第一轮的扫描之后，所有的这些页面的访问位都由一致为了 0。那在进行第二轮扫描的时候，一号页面的访问位为 0，所以会选择淘汰一号页面，于是 6 号页会装入到 1 号页以前占用的内存块当中，并且 6 号页的访问位会被制为一，然后扫描的指针指向下一个页面，
接下来的访问当中会依次访问到 3 号和 4 号页面，在访问了三号页面之后，三号页的访问位需要由 0 变为 1，同样的在访问了 4 号页面的时候，需要把 4 号页的访问位由 0 变为 1，
在之后需要访问 7 号页，由于此时 7 号页没有在内存中，所以需要选择淘汰其中的某一个页面，然后把 7 号页放到内存中，同样的需要从此时扫描到的位置依次的扫描，找到第一个访问位为 0 的页面，并且扫描过的那些页面的访问位需要由 1 变为 0，所以 3 号和 4 号在扫描过后访问位会变为 0。在扫描到二号页面的时候发现二号页面的访问位本来就是 0 了，因此会选择淘汰二号页面，然后让 7 号页面放到这个位置，访问位置为 1，然后扫描的指针再指向下一个页面的位置
可能通过动画会更容易理解时钟置换算法的一个运行的过程。并且通过刚才的这个例子，大家会发现扫描的过程有点像一个时钟的时针在不断的转圈的过程，所以为什么这个算法要叫做时钟置换算法，它其实是一个很形象的比喻。
其实经过刚才的分析，我们也很容易理解为什么它还称作最近未用算法，因为我们会为各个页面设置一个访问位，访问位为一的时候表示最近用过，访问位为 0 的时候表示最近没有用过，但是我们在选择淘汰一个页面的时候，是选择那种最近没有被访问过也就访问位 0 的页面，因此这种算法也可以称作为最近未用算法。
# 改进型的时钟置换算法
接下来我们再来学习改进型的时钟置换算法，其实在之前学习的简单的时钟置换算法当中，只是很简单的考虑到了一个页面最近是否被访问过，但是通过之前的讲解，我们知道如果一个被淘汰的页面没有被修改过的话，那么是不需要执行 IO 操作，把它写回外存的。
所以如果说我们能够优先淘汰没有被修改过的页面的话，那么实际上就可以减少这些 IO 操作的次数，从而让置换算法的性能得到进一步的提升，这就是改进型的时钟置换算法的一个思想，
所以为了实现这件事，我们还需要为各个页面增加一个修改位为 0 的时候，表示这个页面在内存当中没有被修改过，修改位为一的时候表示页面被修改过，我们在接下来讨论当中会用访问位，修改位这样的二元组的形式来标识各个页面的状态。比如说访问一，修改位也为一的话，那就表示这个页面近期被访问过，并且也曾经被修改过，
和简单的时钟置换算法一样，我们也需要把所有的可能被置换的页面排成一个循环队列
在第一轮扫描的时候会从当前位置开始往后依次扫描，尝试找到第一个最近没有被访问过，并且也没有修改过的页面对他进行淘汰。第一轮扫描是不修改任何的标志位的，如果第一轮扫描没有找到 00 这样的页面的话，就需要进行第二轮的扫描。
第二轮扫描会尝试找到第一个最近没有被访问过，但是被修改过的页面进行替换，并且被扫描过的那些页面的访问位都会被设置为 0。
如果第二轮扫描失败，需要进行第三轮扫描，会尝试找到第一个访问位和修改位都为 0 的页面进行淘汰，并且第三轮扫描并不会修改任何的标志位。
如果第三轮扫描失败的话，还需要进行第四轮扫描，找到第一个 01 的页帧用于替换。由于第二轮的扫描已经把所有的访问位都设为了 0 了，所以经过第三轮第四轮扫描之后，肯定是可以找到一个要被淘汰的页面的，所以改进型的这种时钟置换算法选择一个淘汰页面，最多会进行 4 轮扫描。
其实这个过程光看文字描述也是很抽象的，不太容易理解，假设系统为 1 个进程分配了 5 个内存块，当个内存块被占满之后，各个页面会用这种链接的方式连成一个循环的队列，此时如果要淘汰一个页面的话，需要从队列的队头开始依次到扫描。
根据这个算法规则，在第一轮的扫描当中并不修改任何的标志位，需要尝试找到访问位和修改位都为 0 的这样一个页面，所以往后寻找了之后，发现这个页面是满足条件的，所以在第一轮扫描的时候就找到了一个页面用于替换，因此会淘汰这个页面，这是只需要一轮扫描的情况。
再来看下一种情况。假设此时各个页面的状态是这样的
如果需要淘汰一个页面的话，需要从第一个页面开始往后依次的扫描，然后尝试找到第一个 00 这样的页帧，并且第一轮的扫描是不改变任何的标志位的，所以第一轮扫描下来发现所有的这些都不满足 00 这样的状态，因此会进行第二轮扫描
第二轮扫描会尝试找到一个原本就是 01 的页面，并且扫描过的页面会把访问位置为 0。所以在第二轮扫描当中，第一个页面被扫描过之后，会把它的访问位置为 0，在扫描到第二个页面的时候发现它原先本来就是 01 这样的状态，因此会选择淘汰这个页面，所以这是需要进行两轮扫描的一个例子。
接着看下种情况，假设此时各个页面的状态是这样的，和之前一样需要淘汰一个页面的时候需要进行扫描，第一轮的扫描需要找到 00 这样的页面，但是第一轮扫描下来发现所有的页面都没有满足 00 这样的条件的，
所以会进行第二轮扫描，第二轮扫描会开始寻找 01 这样的页面，并且被扫描过的页面都会把访问位置为零。因此在经过第二轮的扫描之后，所有的这些页面的访问位都被置为了 0，但是第二轮扫描依然没有发现原本 01 这样的页面，所以就会进行第三轮的扫描。
第三轮扫描需要找到第一个 00 这样的页面，扫描到这个页面的时候，就会发现它已经满足第三轮扫描所要找的这种页面的条件，于是会淘汰页面，这是需要经过三轮扫描的一个例子。
再来看 4 轮扫描的例子，假设此时所有的页面的状态都是 11 这样的状态，第一轮扫描的时候需要找到 00 这样的页面，显然所有的都不满足。
第二轮扫描的时候需要找到 01 这样的页面，并且被扫描过的页面，访问位都会被置为 0，所以经过第二轮扫描之后，所有的这些页面的访问位都被置为了 0，但是依然没有找到原本就是 01 的页面，于是会进行第三轮的扫描
第三轮扫描会尝试找 00 这样的页面，但是也不修改任何的标志位，所以第三轮扫描下来也没发现满足这个条件的
于是会进行第四轮扫描，第四轮扫描会找到 01 这样的页面，显然第一个页面此时已经满足条件了，所以此时应该淘汰这个页面，这就是需要经过 4 轮扫描的一个例子。
因此通过刚才的这个例子，我们也可以很直观的感受到，改进型的时钟置换算法在选择一个淘汰页面的时候，最多会进行 4 轮扫描，而简单的时钟置换算法在淘汰一个页面的时候，最多只会进行两轮扫描。
我们再从另外一个角度来看，其实第一轮优先选择淘汰 00 这样的页面，就意味着其实低优先级被淘汰的页面，应该是最近没有被访问过，并且也没有被修改过的页面，
同样的第二轮要找的是 01 这样的页面，所以第二优先级的应该是最近没有被访问，但是修改过的页面
如果第二轮都没有找到一个合适的页面的话，那就说明所有的这些页面在以前，访问位其实都是 1 因此其实在第三轮淘汰的这些页面其实是最近访问过，但是没有修改过的页面，也就是访问位以前是 1，然后修改位以前是 0 这样的页面。
同理第四优先级的被淘汰的页面应该是最近访问过，并且也被修改过的这样的页面。所以我们也可以用这样的角度来理解各轮选择淘汰的页面到底是哪种类型的页面。
# 小结
那么这个小节我们介绍了 5 种页面置换算法，分别是最佳置换先进先出，还有最近最久未使用，还有时钟置换也叫最近未用算法。另外还介绍了改进型的时钟置换或者叫改进型的最近未用算法，这个小节的内容重点需要理解个算法的规则，如果题目中给出一个页面的访问序列，那需要自己能够用手动的方式来模拟各个算法运行的一个过程。
除了算法规则之外，各个算法的优缺点有可能在选择题当中进行考察，需要重点注意的是最佳置换算法在现实当中是无法实现的，然后先进先出算法，它的性能差，并且是唯一一个有可能出现 Belady 异常的算法。好的，那么以上就是小节的全部内容。
