页面置换算法

最优页面置换算法（OPT）

当出现缺页异常，需调入新页面而内存已满时，置换算法选择被置换的物理页面。页面置换算法的设计目标是尽可能减少页面的调入调出次数，把未来不再访问或短期内不访问的页面调出。

当一个缺页异常发生时，把将来最长时间不需要的页面置换。这是一种理想的情况，在实际的系统中无法准确实现，因为操作系统无法知道每一个页面要等待多长时间以后才会再次被访问。该算法用作参考，评价其它算法。

互动实验

OPT：查看未来访问

重置实验访问权限PRO

PRO EXCLUSIVE探索不止于此

解锁完整互动实验、进阶解析与精选参考答案。

尊享 Pro 权益

动手练习

OPT：追踪一组新访问串

中等·15 分钟查看参考答案

框0～3预装2、4、6、8，初始装入与使用次序由左到右从旧到新；预装不计缺页。OPT并列时选择最小框号。

6 → 2 → 8 → 4 → 9 → 2 → 7 → 4 → 6 → 9 → 8 → 2

1. 按OPT计算每次访问后的四个页框，标出命中或缺页。
2. 每次缺页比较各驻留页下一次使用的位置。
3. 计算缺页数、命中数和缺页率。

#	访问页	框0～3	命中／缺页	牺牲页／次序
1	6	___ | ___ | ___ | ___	___	___
2	2	___ | ___ | ___ | ___	___	___
3	8	___ | ___ | ___ | ___	___	___
4	4	___ | ___ | ___ | ___	___	___
5	9	___ | ___ | ___ | ___	___	___
6	2	___ | ___ | ___ | ___	___	___
7	7	___ | ___ | ___ | ___	___	___
8	4	___ | ___ | ___ | ___	___	___
9	6	___ | ___ | ___ | ___	___	___
10	9	___ | ___ | ___ | ___	___	___
11	8	___ | ___ | ___ | ___	___	___
12	2	___ | ___ | ___ | ___	___	___

查看提示

先进先出FIFO

FIFO算法选择在内存驻留时间最长的页面进行置换。算法实现需要维护一个队列，出现缺页时，选择队头页面进行置换，新页面加到队尾。FIFO算法实现简单，但是性能可能较差，调出的页面可能是经常访问的。

互动实验

FIFO：按装入次序排队

重置实验访问权限PRO

PRO EXCLUSIVE探索不止于此

解锁完整互动实验、进阶解析与精选参考答案。

尊享 Pro 权益

动手练习

FIFO：追踪一组新访问串

中等·15 分钟查看参考答案

框0～3预装2、4、6、8，初始装入与使用次序由左到右从旧到新；预装不计缺页。OPT并列时选择最小框号。

6 → 2 → 8 → 4 → 9 → 2 → 7 → 4 → 6 → 9 → 8 → 2

1. 按FIFO计算每次访问后的四个页框，标出命中或缺页。
2. 维护装入队列，并记录被移出的队头页面。
3. 计算缺页数、命中数和缺页率。

#	访问页	框0～3	命中／缺页	牺牲页／次序
1	6	___ | ___ | ___ | ___	___	___
2	2	___ | ___ | ___ | ___	___	___
3	8	___ | ___ | ___ | ___	___	___
4	4	___ | ___ | ___ | ___	___	___
5	9	___ | ___ | ___ | ___	___	___
6	2	___ | ___ | ___ | ___	___	___
7	7	___ | ___ | ___ | ___	___	___
8	4	___ | ___ | ___ | ___	___	___
9	6	___ | ___ | ___ | ___	___	___
10	9	___ | ___ | ___ | ___	___	___
11	8	___ | ___ | ___ | ___	___	___
12	2	___ | ___ | ___ | ___	___	___

查看提示

最近最久未使用算法（LRU, Least Recently Used）

LRU算法是对最优置换算法的近似，以过去推未来。根据程序的局部性原理，在最近一小段时间，如果某些页面被频繁访问，那么在将来的一小段时间内，它们还可能再一次被频繁访问。反之，如果在过去某些页面长时间未被访问，那么将来它们还可能会长时间地得不到访问。因此，LRU算法选择最长时间没有被引用的页面进行置换。

LRU算法的实现需要记录每个驻留页面的上一次访问时间，选择上一次使用到当前时间最长的页面。该算法在某些访问序列上可能达到最优效果，但是精确维护访问次序的开销比较大。

互动实验

LRU：跟踪最近使用

重置实验访问权限PRO

PRO EXCLUSIVE探索不止于此

解锁完整互动实验、进阶解析与精选参考答案。

尊享 Pro 权益

动手练习

LRU：追踪一组新访问串

中等·15 分钟查看参考答案

框0～3预装2、4、6、8，初始装入与使用次序由左到右从旧到新；预装不计缺页。OPT并列时选择最小框号。

6 → 2 → 8 → 4 → 9 → 2 → 7 → 4 → 6 → 9 → 8 → 2

1. 按LRU计算每次访问后的四个页框，标出命中或缺页。
2. 维护最久未用到最近使用的次序，注意命中也要更新。
3. 计算缺页数、命中数和缺页率。

#	访问页	框0～3	命中／缺页	牺牲页／次序
1	6	___ | ___ | ___ | ___	___	___
2	2	___ | ___ | ___ | ___	___	___
3	8	___ | ___ | ___ | ___	___	___
4	4	___ | ___ | ___ | ___	___	___
5	9	___ | ___ | ___ | ___	___	___
6	2	___ | ___ | ___ | ___	___	___
7	7	___ | ___ | ___ | ___	___	___
8	4	___ | ___ | ___ | ___	___	___
9	6	___ | ___ | ___ | ___	___	___
10	9	___ | ___ | ___ | ___	___	___
11	8	___ | ___ | ___ | ___	___	___
12	2	___ | ___ | ___ | ___	___	___

查看提示

时钟页面置换算法（Clock）

Clock是LRU的近似和对FIFO的改进。算法使用访问位（access bit），页装入时可初始化为0，实际访问后置为1。页面组织为环形链表，指针指向下一个候选页面，而不一定是全局最老的页面。

发生缺页异常时，如果指针所指页面的访问位为0，则淘汰；若为1，清零并向前移动，直到找到可淘汰页。装入的新页因本次访问置为1，指针移到下一格。

例如按1、2、3、4的顺序访问页面，四个页框会被填满。

此后按1、2、3、4、5访问，前四次直接命中。访问5时需要置换：扫描清零四个访问位后，淘汰指针最初所指的页面1，装入5，再前移。

互动实验

Clock：转动时钟指针

重置实验访问权限PRO

PRO EXCLUSIVE探索不止于此

解锁完整互动实验、进阶解析与精选参考答案。

尊享 Pro 权益

动手练习

Clock：追踪一组新访问串

中等·15 分钟查看参考答案

使用四个初始为空的页框，指针从框0开始。每次实际访问将R置1，命中不移动指针；首次装入也计缺页。

2 → 4 → 6 → 8 → 2 → 6 → 9 → 4 → 7 → 2 → 8 → 9

1. 按Clock计算每次访问后的四个页框，标出命中或缺页。
2. 每次缺页记录扫描框、访问位清零、牺牲页和最终指针；命中时更新访问位。
3. 计算缺页数、命中数和缺页率。

#	访问页	框0～3	命中／缺页	牺牲页／次序
1	2	___ | ___ | ___ | ___	___	___
2	4	___ | ___ | ___ | ___	___	___
3	6	___ | ___ | ___ | ___	___	___
4	8	___ | ___ | ___ | ___	___	___
5	2	___ | ___ | ___ | ___	___	___
6	6	___ | ___ | ___ | ___	___	___
7	9	___ | ___ | ___ | ___	___	___
8	4	___ | ___ | ___ | ___	___	___
9	7	___ | ___ | ___ | ___	___	___
10	2	___ | ___ | ___ | ___	___	___
11	8	___ | ___ | ___ | ___	___	___
12	9	___ | ___ | ___ | ___	___	___

查看提示

知识测验

重做

题目

驻留页反复命中，FIFO与LRU如何处理？

AFIFO保留装入年龄，LRU更新最近使用次序B两者都必须把它移到最新装入位置CFIFO预测其下次未来使用DLRU忽略命中