文档介绍：最佳页面置换算法(Optimal):(先进先出法)(1)实质:总是选择在主存中停留时间最长的一页置换,即先进入内存页,先退出内存。(2)理由:最早调入内存的页,起不再被使用的可能性比刚调入内存的可能性大。(3)方法:建立一个FIFO队列,收容所有在内存中的页。被置换页面总是在队列头上进行,当一个页面被放入内存时,就把它插在队尾上。(4)缺点:只是在按线性顺序访问地址空间时才是理想的,否则效率不高。因为那些常被访问的页,往往在贮存中也停留得最久,结果它们因变“老”而不得不被置换出去。当然,导致这种异常现象的页面走向实际上是很少见的。:(最优置换算法)(1)实质:当调入新的一页而必须预先置换某个老页时,所选择的老页应是将来不再被使用,或者是在最远的将来才被访问。(2)理论算法,不可实现。:(最久未使用算法)(1)实质:当需要置换一页时,选择在最近一段时间里最久没有使用过的页面予以置换。(2)LRU的近似算法NUR(最近未使用算法):它在存储分块表的每一表项中增加一个引用位,操作系统定期地将它们置为0。当某一页被访问时,由硬件将改为置为1。过一段时间后,通过检查这些位可以确定哪些页使用过,哪些页自上次置0后还未使用过。就可以把该位是0的页淘汰出去,因为在最近一段时间里它未被访问过。(第二次机会算法)(1)思想:当选择置换页面时,检查它的访问位。如果是0,就淘汰这页;如果访问位是1,就给它第二次机会,并选择下一个FIFO页面。当一个页面得到第二次机会时,它的访问位就清为0,它的到达时间就置为当前时间。如果该页在此期间被访问过,则访问位置1。这样给了第二次机会的页面将不会被淘汰,直至所有其他页面被被淘汰过(或者也给了第二次机会)。因此,如果一个页面经常使用,它的访问位总保持为1,它就从来不会被淘汰出去。(2)方法:可视为一个环形队列。用一个指针指示哪一页是下面要淘汰的。当需要一个存储块时,指针就前进,直至找到访问位是0的页。随着指针的前进,把访问位就清0。(3)缺点:在最坏的情况下,所有的访问位都是1,指针要通过整个队列一周,每个页都给第二次机会。这时就退化成了FIFO算法了。