homework -8 Version 0 |
|
👤 Author: by zhangleilaogeqqcom 2019-11-14 10:27:30 |
1.最佳置换算法(OPT)(理想置换算法):从主存中移出永远不再需要的页面;如无这样的页面存在,则选择最长时间不需要访问的页面。于所选择的被淘汰页面将是以后永不使用的,或者是在最长时间内不再被访问的页面,这样可以保证获得最低的缺页率。 即被淘汰页面是以后永不使用或最长时间内不再访问的页面。(往后看)
最佳置换算法可以用来评价其他算法。假定系统为某进程分配了三个物理块,并考虑有以下页面号引用串:
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
进程运行时,先将7, 0, 1三个页面依次装入内存。进程要访问页面2时,产生缺页中断,根据最佳置换算法,选择第18次访问才需调入的页面7予以淘汰。然后,访问页面0时,因为已在内存中所以不必产生缺页中断。访问页面3时又会根据最佳置换算法将页面1淘汰……依此类推,如图所示。从图中可以看出釆用最佳置换算法时的情况。
可以看到,发生缺页中断的次数为9,页面置换的次数为6。
访问页面 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
物理块1 7 7 7 2 2 2 2 2 7
物理块2 0 0 0 0 4 0 0 0
物理块3 1 1 3 3 3 1 1
缺页否 √ √ √ √ √ √ √ √
2.先进先出置换算法(FIFO):是最简单的页面置换算法。这种算法的基本思想是:当需要淘汰一个页面时,总是选择驻留主存时间最长的页面进行淘汰,即先进入主存的页面先淘汰。其理由是:最早调入主存的页面不再被使用的可能性最大。 即优先淘汰最早进入内存的页面。(往前看)
访问页面 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
物理块1 7 7 7 2 2 2 4 4 4 0 0 0 7 7 7
物理块2 0 0 0 3 3 3 2 2 2 1 1 1 0 0
物理块3 1 1 1 0 0 0 3 3 3 2 2 2 1
缺页否 √ √ √ √ √ √ √ √ √ √ √ √ √ √ √
这里仍用上面的实例,釆用FIFO算法进行页面置换。进程访问页面2时,把最早进入内存的页面7换出。然后访问页面3时,再把2, 0, 1中最先进入内存的页换出。由图可以看出,利用FIFO算法时进行了 12次页面置换,比最佳置换算法正好多一倍。
FIFO算法还会产生当所分配的物理块数增大而页故障数不减反增的异常现象,这是由 Belady于1969年发现,故称为Belady异常,如图3-28所示。只有FIFO算法可能出现Belady 异常,而LRU和OPT算法永远不会出现Belady异常。
访问页面 1 2 3 4 1 2 5 1 2 3 4 5
物理块1 1 1 1 4 4 4 5 ,5' 5
物理块2 2 2 2 1 1 1 3 3
物理块3 3 3 3 2 2 2 4
缺页否 √ √ √ √ √ √ √ √ √
1 1 1 5 5 5 5 4 4
物理块2* 2 2 2 2 1 1 1 1 5
物理块3* 3 3 3 3 2 2 2 2
物理块4* 4 4 4 4 3 3 3
缺页否 √ √ √ √ √ √ √ √ √
注意:内存的页面中“最老“的页面,会被新的网页直接覆盖,而不是“最老“的页面先出队,然后新的网页从队尾入队。
3.最近最久未使用(LRU)算法:这种算法的基本思想是:利用局部性原理,根据一个作业在执行过程中过去的页面访问历史来推测未来的行为。它认为过去一段时间里不曾被访问过的页面,在最近的将来可能也不会再被访问。所以,这种算法的实质是:当需要淘汰一个页面时,总是选择在最近一段时间内最久不用的页面予以淘汰。 即淘汰最近最长时间未访问过的页面。(往前看)
再对上面的实例釆用LRU算法进行页面置换,如图所示。进程第一次对页面2访问时,将最近最久未被访问的页面7置换出去。然后访问页面3时,将最近最久未使用的页面1换出。
访问页面 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
物理块1 7 7 7 2 2 4 4 4 0 1 1 1
物理块2 0 0 0 0 0 0 3 3 3 0 0
物理块3 1 1 3 3 2 2 2 2 2 7
缺页否 √ √ √ √ √ √ √ √ √ √ √ √
实际上,LRU算法根据各页以前的情况,是“向前看”的,而最佳置换算法则根据各页以后的使用情况,是“向后看”的。
***LRU性能较好,但需要寄存器和栈的硬件支持。LRU是堆栈类的算法。理论上可以证明,堆栈类算法不可能出现Belady异常。FIFO算法基于队列实现,不是堆栈类算法。