页面置换算法.ppt

1、计算机操作系统 页面置换算法,页面置换算法,置换算法的前提:若需访问的页面不在内存而需将其调入，且内存中没有空闲页面，需从内存中调出一页程序或数据。 目的:选出一个被淘汰的页面。 把选择换出页面的算法称为页面置换算法。 置换算法的好坏直接影响系统的性能。一个好的置换算法应具有较低的页面更换频率。从理论上讲，应将那些以后不会再访问的页面换出，或者把那些在较长时间内不会再访问的页面换出。,1-随机淘汰算法,随机淘汰算法。在系统设计人员认为无法确定哪些页被访问的概率较低时，随机地选择某个用户的页面并将其换出将是一种明智的作法。,2-最佳页面置换(OPT)算法,最佳置换算法 其所选择的被淘汰页面，将是

2、以后永不再用的，或许是在最长(未来)时间内不再被访问的页面。 最佳置换算法是一种理想化的算法，具有最好的性能，但难于实现。先进先出置换算法最直观，但可能性能最差，故应用极少。 优点：保证获得最低的缺页率 缺点：无法预知一个进程在内存的若干个页面，哪个在未来最长时间内不再被访问。,3-先进先出算法(FIFO),先进先出算法(FIFO)。 FIFO算法认为先调入内存的页不再被访问的可能性要比其他页大，因而选择最先调入内存的页换出。 方法：把各个已分配页面按分配时间顺序链接起来，组成FIFO队列，并设置一置换指针指向FIFO队列的队首页面。这样，当要进行置换时，只需把置换指针所指的FIFO队列前头的

3、页顺次换出，而把换入的页链接在FIFO队尾即可。 缺点：a. 算法与进程的实际运行规律不相适应，因为进程中的某些页面经常被访问，但先进先出置换算法不能保证这些页面不被淘汰。b. 由实验和测试发现FIFO算法的内存利用率不高。,先进先出算法(FIFO)陷阱现象,FIFO有一种陷阱现象： 一般来说，对于任一进程，如果给它分配的内存页面数越接近于它所要求的页面数，则发生缺页的次数会越少。在极限情况下，这个推论是成立的。因为如果给一个进程分配了它所要求的全部页面，则不会发生缺页现象。 但是，使用FIFO算法时，在未给进程分配足它所要求的页面数时，有时会出现分配的页面数增多，缺页次数反而增加的奇怪现象。

4、这种现象称为Belady现象。,图 FIFO算法的Belady现象,3个页面 123412512345 111444555555 22211111333 3332222244 9次缺页 9/12=75%,4个页面 123412512345 111111555544 22222211115 3333332222 444444333 10 次缺页 10/12=83.3%,图 Belady现象示例,FIFO陷阱现象示例,4-最近最久未使用(LRU)置换算法,LRU (least recently used)： 基本思想: 当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。 该算法的主要出发点是，在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。反过来说，已经很久没有使用的页面很可能在未来较长的一段时间内不会被用到（局部性原理 ） 。,课堂练习：某程序在内存中分配三个页面，初始为空，页面走向为4，3，2，1，4，3，