3)最近最少用页面替换算法(LRU, least Recently used) ●该算法淘汰的页面是在最近一段时 间里较久未被访问的那一页。它是 根据程序执行时所具有的局部性来 考虑的,即那些刚被使用过的页面, 可能马上还要被使用,而那些在较 长时间里未被使用的页面,一般说 可能不会马上使用到
3）最近最少用页面替换算法（LRU，least Recently used） 该算法淘汰的页面是在最近一段时 间里较久未被访问的那一页。它是 根据程序执行时所具有的局部性来 考虑的，即那些刚被使用过的页面， 可能马上还要被使用，而那些在较 长时间里未被使用的页面，一般说 可能不会马上使用到
维护一个特殊的队列 该队列中存放当前在主存中的页号,每 当访问一页时就调整一次,使队列尾总 指向最近访问的页,队列头就是最近最 少用的页。显然,发生缺页中断时总淘 汰队列头所指示的页;而执行一次页面 访问后,需要从队列中把该页调整到队 列尾
维护一个特殊的队列 该队列中存放当前在主存中的页号，每 当访问一页时就调整一次，使队列尾总 指向最近访问的页，队列头就是最近最 少用的页。显然，发生缺页中断时总淘 汰队列头所指示的页；而执行一次页面 访问后，需要从队列中把该页调整到队 列尾
例:给某作业分配厂三块主存,该作业依次访间 的页号为:4,3,0,4,1,1,2,3,2。于是 当访问这些页时,页面淘汰序列的变化情况如下: 4 4304 43 430 304 041 041 232 412 123 132
例：给某作业分配了三块主存，该作业依次访问 的页号为：4，3，0，4，1，1，2，3，2。于是 当访问这些页时，页面淘汰序列的变化情况如下： 4 4 3 4 3 0 4 3 0 4 3 0 4 1 0 4 1 3 1 0 4 1 2 4 1 2 0 3 1 2 3 4 2 1 3 2
LRU算法实现 ●第一种模拟方法可以通过设置标志位来实 现 给每一页设置一个引用标志位R,每次访 问某一页时,由硬件将该页的标志R置1 隔一定的时间将所有页的标志R均清0 在发生缺页中断时,从标志位R为0的那 些页中挑选一页淘汰。在挑选到要淘汰的 页后,也将所有页的标志R清0
LRU算法实现 第一种模拟方法可以通过设置标志位来实 现。 给每一页设置一个引用标志位R，每次访 问某一页时，由硬件将该页的标志R置1， 隔一定的时间t将所有页的标志R均清0。 在发生缺页中断时，从标志位R为0的那 些页中挑选一页淘汰。在挑选到要淘汰的 页后，也将所有页的标志R清0
第二种模拟方法是为每个页设 置一个多位寄存器r ●当页面被访问时,对应的寄 存器的最左边位置1;每隔时 间t,将r寄存器右移一位;在 发生缺页中断时,找最小数 值的r寄存器对应的页面淘汰
第二种模拟方法是为每个页设 置一个多位寄存器r 当页面被访问时，对应的寄 存器的最左边位置1；每隔时 间t，将r寄存器右移一位；在 发生缺页中断时，找最小数 值的r寄存器对应的页面淘汰