页面三大置换算法_如果页面大小为100,给出页面访问序列

---

在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断。当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。

最佳置换算法（OPT）

这是一种理想情况下的页面置换算法，但实际上是不可能实现的。该算法的基本思想是：发生缺页时，有些页面在内存中，其中有一页将很快被访问（也包含紧接着的下一条指令的那页），而其他页面则可能要到10、100或者1000条指令后才会被访问，每个页面都可以用在该页面首次被访问前所要执行的指令数进行标记。

最佳页面置换算法只是简单地规定：标记最大的页应该被置换。这个算法唯一的一个问题就是它无法实现。当缺页发生时，操作系统无法知道各个页面下一次是在什么时候被访问。虽然这个算法不可能实现，但是最佳页面置换算法可以用于对可实现算法的性能进行衡量比较。

• 原理：每次选择未来长时间不被访问的或者以后永不使用的页面进行淘汰。
• 举例：假定系统为某进程分配了三块物理块，并有以下页面：

7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1

算法执行如下操作步骤：

1. 程序运行时，先将7,0,1三个页面装入内存。(最开始的时候内存不为空)
2. 之后，当进程要访问页面2的时候，将会产生缺页中断。此时根据最佳置换算法，因为页面7要在第18次才能访问，页面0在第5次访问，页面1在第14次访问，页面7最久不被使用，所以将页面7淘汰；
3. 当进程0要访问时，因为它已存在在内存所以不必产生缺页中断； 当页面3要访问时，又引起缺页中断淘汰1；
4. 依次类推直到最后一个页面访问完。下图为采用最佳置换算法的置换图。由图可得，采用最佳置换算法发生了6次缺页中断。

• 当数字不在框中，从当前向后找最后一个将要访问的数字进行替换
• 当数字在框中，则不做改变，继续向后

先进先出置换算法（FIFO）

最简单的页面置换算法是先入先出（FIFO）法。这种算法的实质是：总是选择在主存中停留时间最长（即最老）的一页置换，即先进入内存的页，先退出内存。理由是：最早调入内存的页，其不再被使用的可能性比刚调入内存的可能性大。建立一个FIFO队列，收容所有在内存中的页。被置换页面总是在队列头上进行。当一个页面被放入内存时，就把它插在队尾上。

这种算法只是在按线性顺序访问地址空间时才是理想的，否则效率不高。因为那些常被访问的页，往往在主存中也停留得最久，结果它们因变“老”而不得不被置换出去。

FIFO的另一个缺点是，它有一种异常现象，即在增加存储块的情况下，反而使缺页中断率增加了。当然，导致这种异常现象的页面走向实际上是很少见的。(先进先出的性能最差，因为与通常页面的使用规则不符合，所以实际应用少)

• 原理： 把内存中驻留时间最久的页面置换算法予以淘汰
• 举例： 在分页中，采用FIFO页面置换算法，序列 4，3，2，1，4，5，4，3，2，1，5，当物理块为3时，计算缺页次数和缺页率？

算法执行如下操作步骤：

1. 程序运行时，先将4,3，2三个页面装入内存。
2. 之后，当进程要访问页面1的时候，将会产生缺页中断此时根据先进先出置换算法，因为页面4是最先进入内存的，所以将页面4换出；同理4 3 2分别替换3，2，1。
3. 当进程4要访问时，因为它已存在在内存所以不必产生缺页中断； 当页面2要访问时，又引起缺页中断淘汰4；
4. 依次类推直到最后一个页面访问完。图为采用先进先出置换算法的置换图。由图可得，采用先进先出置换算法发生了9次缺页中断。先进先出的页面置换比最佳置换算法的页面置换正好多了一倍；

• 当数字不在框中，横着找最长的连续数字（划掉），将新的数字填入
• 当数字在框中，则不做改变，即空白列

缺页次数=总列数-空白列数=7
缺页率=缺页数/总列数=87.5%

最近最久未使用算法（LRU）

FIFO算法和OPT算法之间的主要差别是，FIFO算法利用页面进入内存后的时间长短作为置换依据，而OPT算法的依据是将来使用页面的时间。如果以最近的过去作为不久将来的近似，那么就可以把过去最长一段时间里不曾被使用的页面置换掉。它的实质是：当需要置换一页时，选择在之前一段时间里最久没有使用过的页面予以置换。这种算法就称为最久未使用算法（Least Recently Used，LRU）。

LRU算法是与每个页面最后使用的时间有关的。当必须置换一个页面时，LRU算法选择过去一段时间里最久未被使用的页面。(LRU算法是经常采用的页面置换算法)

• 原理：选择最近且最久未被使用的页面进行淘汰
• 举例：在分页中，采用LRU页面置换算法，序列 7，0，1，2，0，3，0，4当物理块为3时，计算缺页次数？

算法执行如下操作步骤：

1. 程序运行时，先将7,0,1三个页面装入内存。
2. 之后，当进程要访问页面2的时候，将会产生缺页中断。此时根据最近最久未使用置换算法，因为页面7是最近最久未被使用的的，所以将页面7淘汰；
3. 当进程0要访问时，因为它已存在在内存所以不必产生缺页中断；
4. 在进程要访问页面3的时候，因为页面1是最近最久未被使用的，所以将页面1淘汰；

依次类推直到最后一个页面访问完。下图为采用最近最久未使用的置换算法的置换图。由图可得，采用最近最久未使用置换算法发生了3次缺页中断。

知识点习题

1. 在虚拟存储系统中，若进程在内存中占三块(开始时为空)，采用先进先出页面淘汰算法，当执行访问页号序列为1、2、3、4、1、2、5、1、2、3、4、5、6时，将产生（）次缺页中断。

A. 7
B. 8
C. 9
D. 10

正确答案： D

答案解析：

最开始内存块是空的，即会产生三次中断。

访问页号序列号：1、2、3、4、1、2、5、1、2、3、4、5、6
第一次（1）：1
第二次（2）：1 2
第三次（3）：1 2 3
第四次（4）：2 3 4
第五次（1）：3 4 1
第六次（2）：4 1 2
第七次（5）：1 2 5
未改变（1）
未改变（2）
第八次（3）：2 5 3
第九次（4）：5 3 4
未改变（5）
第十次（6）：3 4 6
总共10次