第三章 内存管理 十三、页面置换算法（最佳置换算法、先进先出置换算法、最近最久未使用置换算法、时钟置换算法、改进型的时钟置换算法）_页面置换算法的最佳置换算法、先进先出置换算法、最近最久未使用置换算法。

目录

一、定义

二、分类

1、最佳置换算法 / 最远置换算法（OPT，Optimal):

1.1、定义：

1.2、例子：

2、先进先出置换算法(FIFO）:

2.1、定义：

2.2、实现方法：

2.3、例子：

3、最近最久未使用置换算法（LRU，least recently used):

3.1、定义：

3.2、实现方法：

3.3、例子：

4、时钟置换算法是一种性能和开销较均衡的算法，又称CLOCK算法，或最近未用算法（NRU，NotRecently Used)

4.1、简单的CLOCK算法实现方法:

4.2、例子：

5、改进型的时钟置换算法

5.1、实现方式

三、总结

---

一、定义

页面置换算法是指在操作系统中，当需要调入一个页面时，若所有的物理页面已被占用，则需要选择一个页面进行置换。页面置换算法是解决内存不足的问题，从而实现更多程序同时运行的重要手段之一。

二、分类

1、最佳置换算法 / 最远置换算法（OPT，Optimal):

1.1、定义：

每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率。

1.2、例子：

（1）在上例中，首先依次访问页面，并将页面放入内存块中，直到内存块装满。

（2）装满后，接下来要访问的是2号页面；

（3）根据OPT算法规则，我们依次往后查看要访问的页面，发现在0，1，7三个页面中，页面7是最远会被访问的。

（4）所以，我们就会将内存块中的7页面淘汰，替换为页面2装入。

（5）依此类推，整个过程缺页中断发生了9次，页面置换发生了6次.（前3次没有发生页面置换）

缺页率：缺页次数 / 总的访问次数

注意：缺页时未必发生页面置换。若还有可用的空闲内存块，就不用进行页面置换。

2、先进先出置换算法(FIFO）:

2.1、定义：

每次选择淘汰的页面是最早进入内存的页面

2.2、实现方法：

把调入内存的页面根据调入的先后顺序排成一个队列，需要换出页面时选择队头页面即可。

队列的最大长度取决于系统为进程分配了多少个内存块。

2.3、例子：

（1）在上例中，首先依次访问页面，并将页面放入内存块中，直到内存块装满。

（2）下一个访问的是页面0，此时就要把最早进来的页面3淘汰。

（3）替换为页面0.

3、最近最久未使用置换算法（LRU，least recently used):

3.1、定义：

每次淘汰的页面是最近最久未使用的页面

3.2、实现方法：

赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间t。

当需要淘汰一个页面时，选择现有页面中t值最大的，即最近最久未使用的页面。

3.3、例子：

（1）在上例中，首先依次访问页面，并将页面放入内存块中，直到内存块装满。

（2）一直访问，直到访问到页面3时。

（3）在此之前，我们依次访问过了7，2，1，8，所以7是最久没有被访问的。

（4）所以将7替换为3.

4、时钟置换算法是一种性能和开销较均衡的算法，又称CLOCK算法，或最近未用算法（NRU，NotRecently Used)

4.1、简单的CLOCK算法实现方法:

1. 为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。
2. 当某页被访问时，其访问位置为1。当需要淘汰一个页面时，只需检查页的访问位。
3. 如果是0，就选择该页换出;如果是1，则将它置为0，暂不换出，继续检查下一个页面，若第一轮扫描中所有页面都是1，则将这些页面的访问位依次置为O后，再进行第二轮扫描（第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK算法选择一个淘汰页面最多会经过两轮扫描)

4.2、例子：

（1）若我们有如上例子，且有5个内存块，在依次访问了1，3，4，2，5后，我们会得到如下视图

        

（2）此时这几个内存块都被访问过，所以它们的访问位都为1.

（3）我们从1号页面依次扫描，而且要将经过的访问位为1的页面的访问位改为0，并且找到访问位为0的页面。

（4）在上图中，我们找了一圈也没有找到访问位为0的页面，而且我们将它全部重置为0了。

（5）然后我们进行第二次扫描，发现1号页为0，所以淘汰它，并且替换为6号页

（6）接下来访问3，4，7；

因为有3号页了，所以指针不动，只是将3号页的访问位改为1；

4号页同样如此。

（7）然后访问7，此时转动指针，将3，4的访问位改为0；而且找到了2号页的访问位为0；所以将7号页存到下方。

5、改进型的时钟置换算法

5.1、实现方式

（1）和简单时钟置换算法相似，其实就是将找0，改为了找（0，0）；

（2）只不过第一轮并不会相简单的那样将1改为0；

（3）而是，如果第一轮没有找到（0，0），就会将（0，1）看作（0，0）进行淘汰。

（4）在第二轮的查找中，会将访问位重置为0

（5）找到为（0，0）的页淘汰

（6）若是如下例子

（7）第一轮扫描（0，0），发现都不是。

（8）第二轮扫描（0，1），且被扫描过的页面的访问位都会被置为0

（9）第三轮扫描（0，0），没找到，不改变什么

（10）第四轮扫描，将（0，1）当作（0，0）淘汰

三、总结