3.2_3 页面置换算法
请求分页存储管理与基本分页存储管理的主要区别:
在程序执行过程中,当所访问的信息不在内存时,由操作系统负责将所需信息从外存调入内存,然后继续执行程序。
若内存空间不够,由操作系统负责将内存中暂时用不到的信息换出到外存。
页面置换算法的作用,就是选择:到底要把哪个页面换出到外存。
(一)最佳置换算法(OPT)
最佳置换算法(OPT,Optimal)
每次选择淘汰的页面将是以后永不使用,或者在最长时间内不再被访问的页面,这样可以保证最低的缺页率。
例子
假设系统为某进程分配了三个内存块,并考虑到有以下页面号引用串(即,会依次访问这些页面):7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
。
第一个要访问的页面是7号页面
。由于刚开始内存中的内存块都是空的,所以没什么问题,将其放入内存块1
即可。
第二个要访问的页面是0号页面
,同理。
第三个要访问的页面是1号页面
,同理。
第四个要访问的是2号页面
,但是,由于此时给这个进程分配的三个内存块都已经占满了,所以我们必须用页面置换算法选择淘汰其中的某一个页面、把那个页面先换出到外存。
根据最佳置换算法的规则,我们要换出的是,在今后最长时间内不会被使用到的页面。所以,我们可以看一下,从当前访问到的这个页号开始(即第四个,2号页面
)往后寻找,看一下此时在内存当中存放的7, 0, 1
这三个页面出现的顺序到底是怎样的。最后一个出现的页号就是最长时间未被访问的页面,也就是要淘汰的页面。
经过观察,我们可知,要淘汰的页面是7号页面
。将其换出到外存,并将此处需要访问的2号页面
放在它原来的位置上,即内存块1
。
第五个要访问的是0号页面
,由于它已经在内存当中了,所以此时不会发生缺页,可以正常地访问。
第六个要访问的是3号页面
,发生缺页中断,依然要看看应该淘汰哪个页面。和刚才一样,从现在这个位置往后寻找,看看此时内存当中存放的2, 0, 1
三个页面出现的先后顺序。
我们在向后寻找的过程中,分别遇到了0、2号页面,由此便可判断出,1号
页面是在今后最长时间内未被访问的。因此,选择将1号页面
换出到外存。再将此处要访问的3号页面换入内存,即内存块3
中。
之后的页面访问,就不再逐个分析了,可以按照上面的方法自行判断。
分析到最后,我们会发现,整个过程缺页中断发生了9次,页面置换发生了6次。
所以,一定要注意:缺页时未必发生页面置换。若还有可用的空闲内存块,就不用进行页面置换。
对于上例,在刚开始访问
7, 0, 1
这三个页面的时候,虽然它们都没有在内存当中,但是由于刚开始有空闲内存块,所以虽然会发生缺页中断、会发生调页,但是并不会发生页面置换。只有在内存块全部被占满之后,再次发生缺页中断的时候,才会发生页面置换。
缺页率 = 9 / 20
= 45%。
缺页率的计算也很简单,就是
发生缺页的次数 / 总共访问多少个页面
。
最佳置换算法可以保证最低的缺页率。但实际上,只有在进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面访问序列。因此,最佳置换算法是无法实现的。
(二)先进先出置换算法(FIFO)
先进先出置换算法(FIFO)
每次选择淘汰的页面是最早进入内存的页面。
实现方法
把调入内存的页面根据调入的先后顺序排成一个队列,需要换出页面时选择队头页面即可。队列的最大长度取决于系统为进程分配了多少个内存块。
例子
假设系统为某进程分配了三个内存块,并考虑到有以下页面号引用串:3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4
。
第一个,访问3号页面
,将其放入内存块1
。此外,由于采用的是先进先出置换算法,因此还需将访问的页面按先后顺序排成队列。因此,需要将3
号入队。
第二个,访问2号页面
,道理是一样的。
第三个,访问1号页面
,道理是一样的。
第四个,访问到0号页面
的时候。由于所有内存块都已经占满了,所以必须选择一个页面进行淘汰。根据系统维持的这个队列可知,3号页面
进入内存的时间是最早的。因此,选择淘汰3号页面,并将要访问的0号页面放入内存当中。相应地,3号页面
出队,0号页面
入队。
第五个,访问到3号页面
的时候,同理,将此时队头的页面换出外存,将该页面换入内存。此外,队头元素出队、当前页面入队。
剩下的过程同理,不再赘述。
整个过程下来,发现,如果给这个进程分配三个内存块的话,总的缺页次数是9次。
如果我们把这个题目的条件改一下,把内存块个数改为了四个。
具体的分析过程不再说明,总之,整个过程如上表所示。
可以发现,在页面访问序列不变的情况下,我们给内存块个数加了一个。但整个访问过程下来,缺页次数反而提升了。
分配四个内存块时,缺页次数:10次。
分配三个内存块时,缺页次数:9次。
但是从直觉来看,内存块越多,缺页次数应该发生的越少才对。
Belady异常——当为进程分配的物理块数增大时,缺页次数不减反增的异常现象。
在我们要学习的这些置换算法当中,只有FIFO算法会产生Belady异常。另外,FIFO算法虽然实现简单,但是该算法与进程实际运行时的规律不适应,因为先进入的页面也有可能最经常被访问。因此,算法性能差。
(三)最近最久未使用置换算法(LRU)
最近最久未使用置换算法(LRU,least recently used)
每次淘汰的页面是最近最久未使用的页面。
实现方法
赋予每个页面对应的页表项中,用访问字段记录该页面自上次被访问以来所经历的时间t。
当需要淘汰一个页面时,选择现有页面中t值最大的,即最近最久未使用的页面。
例子
假设系统为某进程分配了四个内存块,并考虑到有以下页面号引用串:1, 8, 1, 7, 8, 2, 7, 2, 1, 8, 3, 8, 2, 1, 3, 1, 7, 1, 3, 7
。
第一个,……,第十个,访问8号页面
,都是没什么可说的,要么是直接存入,要么是不发生缺页。
第十一个,访问3号页面
时,由于四个内存块都已经满了,所以必须选择淘汰其中的某一个页面。
在我们手动做题的时候,若需要淘汰页面,可以逆向检查此时在内存中的几个页面号。在逆向扫描过程中最后一个出现的页号就是要淘汰的页面。
注意不要分析混了。我们在访问第十一个页面,即
3号页面
时,要淘汰一个页面,我们淘汰的是上表中的1, 8, 7, 2
这四个在3号页面
还没有存入时的、已经呆在内存里的页面。所以我们要淘汰的页面是从这四个当中选一个的。具体这四个中选哪一个,我们是要看:从我们此时第十一个要访问的
3号页面
处,往前看,逆向地扫描,看谁是最后一个出现的。也即距离当前所要访问的页面而言,最近、且最久未被访问过的页面。从3号页面往前看,有8、1、2号页面。因此,可以判断出,7号页面是此时最近、最久未被访问过的页面。因此,我们会选择把7号页面淘汰,然后将3号页面存入。
后续同理,略。
该算法的实现需要专门的硬件支持,虽然算法性能好,但是实现困难,开销大。
(四)时钟置换算法(CLOCK / NRU)
最佳置换算法性能最好,但无法实现;
先进先出置换算法实现简单,但算法性能差(还会有Belady异常);
最近最久未使用置换算法性能好,是最接近OPT算法性能的,但是实现起来需要专门的硬件支持,算法开销大。
时钟置换算法
时钟置换算法是一种性能和开销较均衡的算法,又称CLOCK算法,或最近未使用算法(NRU,Not Recently Used)。
简单的CLOCK算法的实现方法
为每个页面设置一个访问位,再将内存中的页面都通过链接指针链接成一个循环队列(所以,有几个内存块,循环队列的长度就是几)。当某页被访问时,其访问位置为1。当需要淘汰一个页面时,只需检查页的访问位。如果是0,就选择该页换出;如果是1,就将它置0,暂不换出,继续检查下一个页面。若第一轮扫描中所有页面都是1,则将这些页面的访问位依次置0后,再进行第二轮扫描(第二轮扫描中就一定会有访问位为0的页面了,因此简单的CLOCK算法选择一个淘汰页面最多会经过两轮扫描)。
例子
假设系统为某进程分配了五个内存块,并考虑到有以下页面号引用串:1, 3, 4, 2, 5, 6, 3, 4, 7
。
前五个访问的页号,即
1, 3, 4, 2, 5
,都可以顺利地放入内存当中。只有考虑到第六个访问的页面时,才需要考虑淘汰哪个页面的问题。
内存当中的这五个页面,会通过链接指针的方式链接成一个循环队列。
接下来要访问6号页面
,且此时五个内存块已经满了。所以要使用CLOCK算法来选择一个页面进行淘汰。
于是,会从这个循环队列的队首开始扫描,尝试找到一个访问位为0
的页面。并且,被扫描过的页面需要把访问位由1改为0
。
所以,在经过第一轮扫描之后,并没有找到访问位为0
的页面,且所有的页面访问位都由1置为了0。
那么,在进行第二轮扫描的时候,就找到了1号页面
的访问位为0,从而选择淘汰此页面。
于是,6号页
会装入到1号页
以前占有的这个内存块当中。并且,6号页
的访问位会被置为1。并且,扫描的指针会指向下一个位置。
接下来,在访问过6号页之后,我们该访问3号页
了。由于3号页被访问,所以3号页的访问位要由0置为1。同样地,在访问过4号页
之后,它的访问位也要由0置为1。
需要注意的是,只是这个循环队列当中某页面的访问位由0改为1了,而与指针当前指向的位置没有关系。并不是说指针指向的是3号页,所以3号页的访问位才能得以修改;也并不是说,如果要修改4号页的访问位,则指针需要指向4号页……。
最后一个,该访问7号页
了,发生缺页。因此,要在循环队列里找到一个访问位为0
的页面,并且在扫描的过程中,被扫描的页面需要把访问位由1改为0。
因此,3号页、4号页的访问位会由1置为0。同时,发现了访问位为0的2号页,将其淘汰,并把要访问的7号页放进去。7号页的访问位置1,同时指针指向下一个位置。
通过上面的例子,可以看到,“扫描的指针”像一个时钟的指针转圈的过程,因此这个算法叫时钟置换算法。
此外,我们也可以理解,为什么它还叫“最近未用算法”。每个页面都设有一个访问位,访问位为1表示最近被用过,访问位为0表示最近没有被用过。我们要选择淘汰的页面就是第一个寻找到的、访问位为0的页面。因此,这种算法也叫最近未用算法。
(五)改进型的时钟置换算法
简单的时钟置换算法仅考虑到一个页面最近是否被访问过。
实际上,如果被淘汰的页面没有被修改过,就不需要执行I/O操作写回外存。只有被淘汰的页面被修改过时,才需要写回外存。
我们如果优先能选择没有被修改过的页面进行淘汰的话,就不需要一直将数据写回外存,从而提高性能。
因此,除了考虑一个页面最近有没有被访问过之外,操作系统还应考虑页面有没有被修改过。在其他条件都相同时,应优先淘汰没有修改过的页面,避免I/O操作。这就是改进型的时钟置换算法的思想。
所以,为了达到这个目的,我们还需要为各个页面增加一个修改位
。
修改位 = 0,表示页面没有被修改过;
修改位 = 1,表示页面被修改过。
为方便讨论,用(访问位, 修改位)
的形式表示各页面状态。如(1, 1)
表示一个页面近期被访问过,且被修改过。
算法规则
和“简单的时钟置换算法”一样,我们将所有可能被置换的页面排成一个循环队列。
1.第一轮:从当前位置开始扫描到第一个(0, 0)
的帧用于替换。本轮扫描不修改任何标志位。
即,第一轮扫描中,尝试找到一个“没有被访问过、且没有被修改过”的最完美页面。
2.第二轮:若第一轮扫描失败,则重新扫描,查找第一个(0, 1)
的帧用于替换。本轮将所有扫描过的帧访问位设为0。
即,第二轮扫描中,尝试找到一个”没有被访问过,但是被修改过“的页面。并且,被扫描过的页面的访问位都会被置为0。
3.第三轮:若第二轮扫描失败,则重新扫描,查找第一个(0, 0)
的帧用于替换。本轮扫描不修改任何标志位。
4.第四轮:若第三轮扫描失败,则重新扫描,查找第一个(0, 1)
的帧用于替换。
分析:由于第二轮已将所有帧的访问位设为0,因此经过第三轮、第四轮扫描,一定会有一个帧被选中,因此改进型CLOCK置换算法选择一个淘汰页面最多会进行四轮扫描。
例子
假设系统为该进程分配了五个内存块。且此时面临的情况是,需要选择一个页面将其淘汰。循环队列的指针现指向队头。
情况一:只需一轮扫描
第一轮扫描,往后寻找到第一个(0, 0)
的帧,且扫描的过程中不修改任何标志位。
第一轮扫描时,就找到了想要的页面,从而进行淘汰。
情况二:需要两轮扫描
第一轮想寻找一个(0, 0)
的帧,但一圈扫描下来,并没有发现。同时,第一轮扫描是不修改任何标志位的。
因此,会进行第二轮扫描。第二轮扫描会尝试找到一个原本就是(0, 1)
的页面。并且,对于第二轮的扫描,其扫描过的页面会把访问位
置为0。
在第二轮扫描时,对一个页面的访问位进行了修改。此外,最终找到了想要的(0, 1)
。
情况三:需要三轮扫描
第一轮扫描下来,发现都没有(0, 0)
。第一轮不修改任何标志位。
第二轮扫描下来,发现也没有(0, 1)
。第二轮扫描的同时会将被扫描到的访问位
置为0。
进行第三轮扫描。第三轮扫描需要找到一个(0, 0)
的帧。第三轮扫描不修改任何标志位。最终找到。
情况四:需要四轮扫描
第一轮扫描,未找到。
第二轮扫描,未找到,且访问位都被置为0。
第三轮扫描,未找到。
进行第四轮扫描,找到一个(0, 1)
的页面。能够找到。
再次回头思考一下这四轮背后的含义
第一轮:从当前位置开始扫描到第一个(0, 0)
的帧用于替换。本轮扫描不修改任何标志位。
第二轮:若第一轮扫描失败,则重新扫描,查找第一个(0, 1)
的帧用于替换。本轮将所有扫描过的帧访问位设为0。
第三轮:若第二轮扫描失败,则重新扫描,查找第一个(0, 0)
的帧用于替换。本轮扫描不修改任何标志位。
第四轮:若第三轮扫描失败,则重新扫描,查找第一个(0, 1)
的帧用于替换。
分析:
1.第一优先级:最近没访问,且没修改的页面。
2.第二优先级:最近没访问,但修改过的页面。
如果第二轮还没找到,那就说明,所有的这些页面,在此前,都一定是“被访问过”的页面,它们的访问位一定都是1。(因为我们无论是
(0, 0)
还是(0, 1)
都尝试找过了,但没找到)
3.第三优先级:最近访问过,但没修改的页面。
也就是“访问位是1,修改位是0”的页面。注意,已经来到第三轮了,说明所有的页面,它的访问位原本全部是1(只不过在第二轮的扫描过程中给全部置为0了)。
4.第四优先级:最近访问过,且修改过的页面。
同理。