1. 为什么要页面置换？
先说下局部性原理(principle of locality)：指程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域。
- 时间局部性：一条指令的一次执行和下次执行，一个数据的一次访问和下次访问都集中在一个较短时期内；
- 空间局部性：当前指令和邻近的几条指令，当前访问的数据和邻近的数据都集中在一个较小区域内。
部分装入：在程序装入时，不必将其全部读入到内存，而只需将当前执行需要的部分页或段读入到内存，就可让程序开始执行。
在局部性原理下，虚拟存储器的概念应运而生，之前将程序全部放到内存里，现在只将执行的一部分放入到内存中，在程序执行过程中，如果需执行的指令或访问的数据尚未在内存，则程序利用操作系统提供的请求调页功能，将相应的页调入到内存，然后继续执行程序，同时需要将内存中暂时不使用的页调出内存，保存在外存上，将程序需要调入的页或段放到内存中。如果不进行页面置换，内存肯定不够用。
2. 页面置换发生在什么时候？
程序运行过程中，有时要访问的页面不在内存中，这时需要将其调入内存，但是内存已经无空闲空间存储页面，为保证程序正常运行，系统必须从内存中调出一页程序或数据送到磁盘对换区，并把所要访问的页面放入到内存中。
简单来说，就是发生在page fault时。
3. 页面置换算法介绍
3.1. 最优页面置换算法 -- Optimal Page Replacement algorithm, OPT
算法基本思想：发生缺页时，有些页面在内存中，其中有一页将很快被访问（也包含紧接着的下一条指令的那页），而其他页面则可能要到10、100或者1000条指令后才会被访问，每个页面都可以用在该页面首次被访问前所要执行的指令数进行标记。最佳页面置换算法只是简单地规定：标记最大的页应该被置换。
当缺页发生时，操作系统无法知道各个页面下一次是在什么时候被访问，因此这是一种理想情况下的页面置换算法，实际上不可能实现。
虽然这个算法不可能实现，但是最佳页面置换算法可以用于其他置换算法的性能衡量。
3.2. 最近最久未使用置换算法 -- Least recent used, LRU
算法基本思想：当需要置换一页时，选择在之前一段时间里最久没有使用过的页面予以置换。
实现方式：栈或计数器
3.3. 先进先出置换算法 -- FIFO
实现方式：维护了一个队列。
算法基本思想：第一个分配的页会被第一个置换掉，也就是说在每次page fault时处于队首的页面会被置换掉。
3.4 Clock置换算法/最近未使用算法- Not Recently Used, NUR
算法基本思想：简单的CLOCK算法为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成
一个循环队列。当某页被访问时，其访问位置为1。当需要淘汰一个页面时，只需检查页的访问位。如果是0，就将该页换出；如果是1，则将它置为0，暂不换出，继续检查下一个页面，若第一轮扫描中所有页面都是1，则将这些页面的访问位依次置为0后，再进行第二轮扫描（第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK算法选择一个淘汰页面最多会经过两轮扫描）。
实现方式：可通过循环链表、循环队列、数组等结构来组织页面。
3.5 改进版的Clock时钟置换算法
- 算法基本思想
简单的时钟置换算法仅考虑到一个页面最近是否被访问过。事实上，如果被淘汰的页面没有被修改过，就不需要执行I/O操作写回外存。只有被淘汰的页面被修改过时，才需要写回外存。因此，除了考虑一个页面最近有没有被访问过之外，操作系统还应考虑页面有没有被修改过。在其他条件都相同时，应优先淘汰没有修改过的页面，避免I/O操作。这就是改进型的时钟置换算法的思想。
修改位=0：表示页面没有被修改过；修改位=1：表示页面被修改过。
为方便讨论，用（访问位，修改位）的形式表示各页面状态。如（1, 1）表示一个页面近期被访问过，且被修改过。 - 算法具体实现逻辑
将所有可能被置换的页面排成一个循环队列，按照优先级循环扫描
优先级：[最近没访问且没修改] --> [最近没访问但是修改过] --> [最近访问过，但没修改过] --> [访问且修改过]
① 从当前位置开始扫描到第一个（0, 0）的帧用于替换。本轮扫描不修改任何标志位；
② 若第一轮扫描失败，则重新扫描，查找第一个（0, 1）的帧用于替换。本轮将所有扫描过的帧的访问位设为0；
③ 若第二轮扫描失败，则重新扫描，查找第一个（0, 0）的帧用于替换。本轮扫描不修改任何标志位；
④ 若第三轮扫描失败，则重新扫描，查找第一个（0, 1）的帧用于替换。
由于第二轮已将所有帧的访问位设为0，因此经过第三轮、第四轮扫描一定会有一个帧被选中，因此改进型CLOCK置换算法选择一个淘汰页面最多会进行四轮扫描。
| 置换算法 | 算法规则 | 优缺点 |
|---|---|---|
| OPT | 优先淘汰最长时间内不会被访问的页面 | 缺页率最小，性能最好;但无法实现 |
| FIFO | 优先淘汰最先进入内存的页面 | 实现简单；但性能很差,可能出现Belady异常 |
| LRU | 优先淘汰最近最久没访问的页面 | 实现简单，算法开销小;但未考虑页面是否被修改过。 |
| CLOCK/NRU | 循环扫描各页面 第一轮淘汰访问位=0的，并将扫描过的页面访问位改为1。若第一轮没选中，则进行第二轮扫描。 | 性能很好；但需要硬件支持，算法开销大 |
| 改进型CLOCK | 若用(访问位,修改位)的形式表述，则 第一轮：淘汰(0, 0) 第二轮：淘汰(0, 1)，并将扫描过的页面访问位都置为0 第三轮：淘汰(0, 0) 第四轮：淘汰(0, 1) | 算法开销较小，性能也不错 |
4. 页面置换可能导致的后果---Belady's Anomaly
所谓Belady现象就是指采用FIFO算法时，如果对一个进程未分配他所要求的全部页面，有时就会出现分配的页面数增多但缺页率反而提高的异常现象。
举个栗子：页面访问顺序为 ： 0,1,5,3,0,1,4,0,1,5,3,4
- 在页框数 = 3 的情况
| Request | 0 | 1 | 5 | 3 | 0 | 1 | 4 | 0 | 1 | 5 | 3 | 4 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Frame 3 | 5 | 5 | 5 | 1 | 1 | 1 | 1 | 1 | 3 | 3 | ||
| Frame 2 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 5 | 5 | 5 | |
| Frame 1 | 0 | 0 | 0 | 3 | 3 | 3 | 4 | 4 | 4 | 4 | 4 | 4 |
| Miss/Hit | Miss | Miss | Miss | Miss | Miss | Miss | Miss | Hit | Hit | Miss | Miss | Hit |
不命中次数 = 9
- 在页框数 = 4的情况
| Request | 0 | 1 | 5 | 3 | 0 | 1 | 4 | 0 | 1 | 5 | 3 | 4 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Frame 4 | 3 | 3 | 3 | 3 | 3 | 3 | 5 | 5 | 5 | |||
| Frame 3 | 5 | 5 | 5 | 5 | 5 | 5 | 1 | 1 | 1 | 1 | ||
| Frame 2 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 4 | |
| Frame 1 | 0 | 0 | 0 | 0 | 0 | 0 | 4 | 4 | 4 | 4 | 3 | 3 |
| Miss/Hit | Miss | Miss | Miss | Miss | Hit | Hit | Miss | Miss | Miss | Miss | Miss | Miss |
不命中次数 = 10
还有，在哪些算法里会出现这种问题呢？
- 第二次几乎算法
- 随机置换算法
- FIFO
参考
https://www.cnblogs.com/fkissx/p/4712959.html
https://baike.baidu.com/item/%E9%A1%B5%E9%9D%A2%E7%BD%AE%E6%8D%A2%E7%AE%97%E6%B3%95/7626091?fr=aladdin#1_1
MOOC王道教程
网友评论