页面置换算法

## 1 背景

> 在介绍页面置换算法之前，我们先介绍一下页面置换发生的背景。

1. 通过前面对**虚拟页**的介绍我们可以知道，**如果虚拟页尚未被分配使用**，那么**在页表中自然没有相应的物理映射**，反过来说，**虚拟页被分配使用之后**，**在页表中依然可能没有映射到物理页**。
2. 虚拟内存中的**换页机制**的基本思想是**当物理内存容量不够的时候**，**操作系统应该把若干物理页的内容写到类似于磁盘这种容量更大且更加便宜的存储设备中**，**然后就可以回收这些物理页并继续使用了**。
3. 换页需要完成的步骤如下：
   1. 当操作系统希望**从应用程序$A$那里回收物理页**$P$（对应于应用程序$A$中的虚拟页$V$）时，操作系统需要**将物理页$P$的内容写到磁盘上的一个位置**，并且**在应用程序$A$的页表中去除虚拟页$V$的映射**，同时**记录该物理页被换到磁盘上的对应位置**，该过程称为把物理页$P$**换出**（Swap Out）。
   2. 此时**物理页$P$就可以被操作系统回收**，并且**分配给别的应用程序使用**，此时，虚拟页$V$就处于**已分配但未映射至物理内存的状态**。
4. **缺页异常**是与换页机制密不可分的，也是换页机制能够工作的前提，当**应用程序访问已分配但未映射至物理内存的虚拟页**时，就会**触发缺页异常**，此时**CPU会运行操作系统预先设置的缺页异常处理函数**，该函数会**找到**（也可能是通过换页的方式）**一个空闲的物理页**，**将之前写到磁盘上的数据内容重新加载到该物理页中**，并且**在页表中填写虚拟地址到这一物理页的映射**，该过程被称为**换入**（Swap In），之后，**CPU可以回到发生缺页异常的地方继续运行**。
   ![](https://notebook.ricear.com/media/202207/2022-07-03_204034_617644.png)
5. 利用换页机制，操作系统可以**把物理内存放不下的数据临时存放到磁盘上**，**等到需要的时候再放回到物理内存中**，从而能够**为应用程序提供超过物理内存容量的内存空间**。
6. 由于**换页过程涉及耗时的磁盘操作**，因此操作系统往往会引入**预取机制**进行优化，其基本思想是**当发生换入操作时**，**预测还有哪些页即将被访问**，**提前将他们一并换入物理内存**，从而**减少发生缺页异常的次数**。
7. 同时，当应用程序申请分配内存时，操作系统可选择将新分配的虚拟页标记成**已分配但未映射至物理内存状态**，而**不必为这个虚拟页分配对应的物理页**，当**应用程序访问这个虚拟页**的时候，会**触发缺页异常**，此时操作系统才真正**为这个虚拟页分配对应的物理页**，并且**在页表中填入对应的映射**，这种**按需分配**的机制使得**操作系统能够在应用程序真正需要使用物理内存的时候再分配物理页**，因而**能够有效地节约物理内存**，**提高资源利用率**。
8. 在按需分配机制中也存在着一个权衡，虽然节约了内存资源，但对每个内存页来说，**初次访存时产生的缺页异常会导致访问延迟增加**，不过，操作系统依然可以利用**应用程序访存的时空局部性特点**来改善该问题，例如，在缺页异常处理函数中采用预取机制，即在发生缺页异常时，将临近的虚拟页也进行映射，从而减少发生缺页异常的次数，提升应用程序的性能。

> 下面介绍两个常见的场景加深对上面提到的**换页机制**与**缺页异常**的理解。
>
> - 场景一：小明同学的笔记本电脑配有4GB的物理内存，他首先打开了应用程序Photoshop来编辑大量高清图片，共需要占用2GB物理内存，他又同时打开了魔兽世界，该游戏需要占用3GB物理内存，他发现游戏打开过程比平时直接打开要慢一些，不过最终还是成功打开了，这里操作系统之所以可以使用虚拟内存抽象使得只有4GB内存的电脑能够同时运行以上两个总共需要5GB内存的应用程序就是因为上面提到的**换页机制**，而换页过程涉及耗时的磁盘操作，因此游戏打开的速度会变慢了。
> - 场景二：小明编写了一个应用程序，但他不知道该程序在运行时实际会使用多少内存，于是在程序中向操作系统申请预先分配足够大的（虚拟）内存，但实际上其中大部分的虚拟页最终都不会被用到，操作系统此时便会使用上面提到的**按需分配机制**利用虚拟内存抽象做到根据实际使用情况分配珍贵的物理内存资源。

9. 当需要分配物理页时，若**空闲的物理页已用完或小于某个阈值**时，则操作系统将**根据页面置换算法选择一个或一些物理页换出到磁盘以便让出空间**，**当已被换出的内存页再次被访问时**，**必须重新从磁盘换入到物理内存**，十分耗时，因此，页面置换算法是**依据硬件所提供的的页访问信息**，**来猜测哪些页应该被换出**，**从而最小化缺页异常的发生次数以提升性能**。

## 2 分类

常见的页面置换算法主要有以下几种：

1. 最佳置换算法（Optimal Replacement Algorithm, OPT）。
2. 先进先出法（FIFO）。
3. 第二次机会置换法（Second Chance Replacement, SCR）。
4. 时钟置换法（Clock）。
5. 最近最少使用法（Least Recently Used, LRU）。
6. LRU-K。
7. 最不经常使用法（Least Frequently Used, LFU）。

### 2.1 最佳置换算法

1. 最佳置换算法的基本思想是**在选择被换出的页时**，**优先选择未来不会再访问的页**，**或者在最长时间内不会再访问的页**。
2. 该策略是**理论最优**的页替换策略，但在**实际场景中很难实现**，这是因为**页访问顺序取决于应用程序**，而**操作系统通常无法预先得知应用程序未来访问页的顺序**，该策略主要**用来作为一个标准**，**衡量其他页替换策略的优劣**。
3. 具体实例如下，假设物理内存中可以存放三个物理页，初始为空，某应用程序需要访问物理页1 ~ 5，访问顺序为3、2、3、1、4、3、5、4、2、3、4、3。
   ![](https://notebook.ricear.com/media/202207/2022-07-04_164642_928718.png)

### 2.2 先进先出法

1. 先进先出策略是**最简单的页替换策略之一**，同时也正因为简单所以其带来的**时间开销很低**。
2. 该策略**优先选择最先换入的页进行换出**：
   1. **操作系统维护一个队列用于记录换入内存的物理页号**，**每换入一个物理页就把其页号加到队尾**，因此**最先换入的物理页号总是处于对头位置**。
   2. 当**需要选择一个物理页换出**时，该策略总是**选择位于队列头部的物理页号所对应的物理页**。
3. 虽然该策略**直观且开销低**，但他**在实际使用中往往表现不佳**，因为**页换入顺序与使用是否频繁通常没有关联**，因此也**几乎不会被现代操作系统直接使用**。
4. 具体实例如下，假设物理内存中可以存放三个物理页，初始为空，某应用程序需要访问物理页1 ~ 5，访问顺序为3、2、3、1、4、3、5、4、2、3、4、3。
   ![](https://notebook.ricear.com/media/202207/2022-07-04_164741_155197.png)

### 2.3 第二次机会置换法

1. 第二次机会置换策略是**先进先出策略的一种改进版本**，该策略的**实现方法与FIFO策略类似**，同样**要求操作系统维护一个先进先出的队列用于记录换入物理内存的物理页号**，此外**还要为每一个物理页号维护一个访问标志位**。
2. 第二次机会置换策略的基本思想是：

1. 如果**访问的页号已经处在队列中**，则：**置上其访问标志位**。
   2. 在**寻找将要换出的内存页时**，该策略**优先查看位于队头的页号**：
      1. 如果他的**访问标志位没有被置上**，则**换出该页号所对应的内存页**。
      2. 如果他的**访问标志位已经被置上了**，则：

1. **将该标志位清零**。
         2. **将该内存页号挪到队尾**（将其当成一个最近访问的内存页的页号）。
         3. **从新的队头开始重新寻找要换出的内存页**。

> 如果**所有内存页号的访问标志位均已被置上**，那么**原本处于队头的内存页号将在再次回到队头时被换出**（彼时，其访问标志位已被清零）。
         >
3. 通常情况下，由于**考虑了页的访问信息**，第二次机会置换策略会**优于先进先出策略**，若所有内存页号的访问标志位均未被置上，那么第二次机会置换策略会暂时退化为先进先出策略。
4. 具体实例如下，假设物理内存中可以存放三个物理页，初始为空，某应用程序需要访问物理页1 ~ 5，访问顺序为3、2、3、1、4、3、5、4、2、3、4、3。
   ![](https://notebook.ricear.com/media/202207/2022-07-04_164811_699305.png)

> 什么是贝拉迪异常？
>
> - 操作系统分配给一个应用程序的物理页的数量会影响他在执行过程中发生缺页异常的次数。
> - 一般来说，对于同样的访存系列，若物理页的数量越多，则换页发生的次数越少，然而，有的时候，**更多的可用物理内存会导致更多的换页**（和更低的性能），这种现象被称为**贝拉迪异常**（Belady's Anomaly），这种现象可能在操作系统使用**先进先出策略**和**第二次机会置换策略**等页替换策略时发生。
> - 下面以**先进先出策略**来详细阐述一下贝拉迪异常，具体的实例如下：
>   - 假设物理内存中可以存放三个物理页，初始为空，某应用程序需要访问物理页1 ~ 5，访问顺序为3、2、3、1、4、3、5、4、2、3、4、3。
>   - 当物理内存中可以存放三个物理页时先进先出策略的执行流程如下图所示。
>     ![](https://notebook.ricear.com/media/202207/2022-07-04_171451_984753.png)
>     此时共发生**9次缺页异常**。
> - 当物理内存中可以存放四个物理页时先进先出策略的执行流程如下图所示。
>   ![](https://notebook.ricear.com/media/202207/2022-07-04_171654_347353.png)
>   此时共发生**10次缺页异常**。

### 2.4 时钟置换法

1. 时钟算法**将换入物理内存的页号排成一个时钟的形状**，**该时钟有一个针臂**，**指向新换入内存的页号的后一个**。
2. 同时，**也为每一个页号维护一个访问标志位**（访问位），**每次需要选择换出页号时**，**该算法从针臂所指的页号开始检查**：
   1. 如果**当前页号的访问位没有设置**（即从上次检查到这次，该页没有被访问过），则**将该页替换**。
   2. 如果**当前页号的访问位已被置上**（即被访问过），那就**将其访问位清空**，并且**针臂顺时针移动到下一个页号**，如此重复，直到找到一个**访问位未被置上**的页号。
3. 时钟算法与第二次机会置换法有相似之处，不过**第二次机会置换法需要将页号从队头移动到队尾**，而**时钟算法并不需要**，所以**后者的实现更加高效**。

### 2.5 LRU

#### 2.5.1 原理

1. 优先置换**最久未被访问**的页面。
2. 根据局部性原理，一个进程**在一段时间内要访问的指令和数据都集中在一起**，如果一个页面**很久没有被访问**，那么**将来被访问的可能性也比较小**。

#### 2.5.2 实现

##### 2.5.2.1 单链表

1. 该算法最常见的实现是**使用一个链表保存缓存数据**，具体如下：
   1. 将**新数据插入到链表头部**。
   2. 每当**缓存命中**（即缓存数据被访问），则**将数据移到链表头部**。
   3. 当**链表满的时候**，将**链表尾部的数据丢弃**。

##### 2.5.2.2 基于HashMap和双向链表

1. 整体的设计思路是**使用HashMap存储 `key`**，这样**可以做到 `save(key)`和 `get(key)`的时间都是$O(1)$**，**HashMap的 `value`指向双向链表实现的LRU的Node节点**，如下图所示：![](https://notebook.ricear.com/media/202107/2021-07-28_1039530.17124614514673764.png)
2. **LRU存储是基于双向链表的**，其中 `head`**代表双向链表的表头**，`tail`**代表双向链表的尾部**，**首先预先设置LRU的容量**，**如果存储满了**，**可以通过$O(1)$的时间淘汰掉双向链表的尾部**，**每次新增和访问数据**，**都可以通过$O(1)$的效率把新的节点增加到头部**，**或者把已经存在的节点移动到头部**。
3. **下图展示了预设大小为3的LRU存储和访问过程中的变化**，**为了简化图复杂度**，**图中没有展示HashMap的变化**，**仅仅展示了LRU中双向链表的变化**：![](https://notebook.ricear.com/media/202107/2021-07-28_1112420.6409522974374684.png)

> s = save，g = get
   >
4. 核心的操作步骤如下：

1. `save(key, value)`：首先**在HashMap中找到 `key`对应的节点**，**如果节点存在**，**更新节点的值**，**并把这个节点移动到队头**，**如果不存在**，**需要构造新的节点**，**并且尝试把节点塞到队头**，**如果LRU空间不足**，**则通过 `tail`淘汰尾部的节点**，**同时在HashMap中移除 `key`**。
   2. `get(key)`：**通过HashMap找到LRU链表节点**，**因为根据LRU原理**，**这个节点是最新访问的**，**所以需要把节点插入到头部**，**然后返回缓存的值**。

#### 2.5.3 优缺点

##### 2.5.3.2 优点

1. 实验证明**LRU 的性能较好**，能够**降低置换频率**。

##### 2.5.3.1 缺点

1. 该算法的缺点是**存在缓存污染问题**，即**由于偶发性或周期性的冷数据批量查询，热点数据被挤出去，导致缓存命中率下降**。

### 2.6 LRU-K

#### 2.6.1 原理

1. LRU-K 中的**K 代表最近的使用次数**，因此 LRU 可以认为是 LRU-1。
2. LRU 算法中因为**仅访问一次就能替代别人**，可能会造成“**缓存污染**”问题，因此提出了 LRU-K 的概念，LRU-K 其主要目的就是**为了解决 LRU 算法“缓存污染”的问题**。
3. LRU-K 的**核心思想是将“最近使用过 1 次”的判断标准扩展为“最近使用过 K 次”**。
4. 与 LRU 算法不同，LRU-K 算法需要维护两个队列，分别是**历史队列**和**缓存队列**：
   1. **历史队列：**
      1. 历史队列**保存着每次访问的页面**，当**页面访问次数达到了 K 次**，该**页面出栈**，并**保存至缓存队列**。
      2. 若**尚未达到 K 次则继续保存**，**直至历史队列也满了**，那就**根据一定的缓存策略**（FIFO、LRU、LFU）**进行淘汰**。
   2. **缓存队列：**
      1. 缓存队列则是**保存已经访问 K 次的页面**，当该**队列满了之后**，则**淘汰最后一个页面**，也就是**第 K 次访问距离现在最久的那个页面**。

#### 2.6.2 实现

![](https://notebook.ricear.com/media/202105/2021-05-23_162651.png)

1. 数据**第一次被访问**，**添加到历史队列中**。
2. 当**历史队列中的页面满了**，**根据一定的缓存策略**（FIFO、LRU、LFU）**淘汰老的页面**。
3. 当**历史队列中的某个页面第 K 次访问**时，该页面**从历史队列中出栈**，并**存放至缓存队列**。
4. **缓存队列中的页面再次被访问 K 次**时，**历史队列中该页面出栈**，并且**更新缓存队列中该页面的位置**。

#### 2.6.3 优缺点

##### 2.6.3.1 优点

1. LRU-K**降低了“缓存污染”带来的问题**，**命中率比 LRU 要高**。

##### 2.6.3.2 缺点

1. LRU-K 是一个**优先级队列**，**算法复杂度和代价比较高**。
2. 由于 LRU-K 还**需要记录那些被访问过、但还没有放入缓存的对象**，因此**内存消耗会比 LRU 要多**，当**数据量很大的时候**，**内存消耗会比较可观**。
3. LRU-K**需要基于时间进行排序**，**CPU 消耗比 LRU 要高**。

### 2.7 LFU

1. 最不经常使用法**使用一个计数器来记录条目被访问的频率**，当**队列满的时候**，**优先淘汰使用次数最少的元素**。
2. 该算法的优点是**能够避免缓存污染问题对 LRU 命中的影响**，因为在淘汰元素的时候是根据一定时间内的使用次数来决定的，所以短时间的冷数据查询不一定会导致热点数据被淘汰，进而避免缓存污染问题。
3. LFU 的缺点：在**短期的时间内，对某些缓存的访问频次很高**，这些缓存**会立刻晋升为热点数据**，而保证不会淘汰，这样**会驻留在系统内存里面**，而**实际上，这部分数据只是短暂的高频率访问**，之后**可能长期不会访问**，这样就会导致一些**新加入的缓存很容易被很快删除**，因为他们的**引用频率很低**。

> LRU 和 LFU 的区别？
>
> LRU 和 LFU 的侧重点不同，LRU 主要体现在对元素的**使用时间**上，LFU 主要体现在对元素的**使用频次**上。

![](https://notebook.ricear.com/media/202105/2021-05-23_171217.png)

## 3 颠簸现象

### 3.1 原因

1. 颠簸本质上是指**频繁的页调度行为**。
2. 如果**选择的页替换策略与实际的工作负载不匹配**，可能会导致**最近使用的内存页刚被换出又被换入**，于是**大部分CPU时间都被用来处理缺页异常以及等待缓慢的磁盘操作**，而**仅剩小部分的时间用于执行真正有意义的工作**，这种现象被称为**颠簸**（Thrashing）**现象**。
3. **操作系统的调度器可能加剧颠簸现象**，**当CPU大部分时间都在等待磁盘操作的时候**，**CPU利用率会大幅下降**，**为了提高CPU利用率**，**调度器会载入更多的应用程序**，**这又可能会触发更多的缺页异常**，**进一步降低CPU利用率**，**进而导致连锁反应**，**引发严重的性能问题**。

### 3.2 怎么避免颠簸现象

1. **工作集模型**（Working Set Model）**能够有效地避免颠簸现象的发生**。
2. 工作集的定义是**一个应用程序在时刻**$t$**的工作集**$W$**为他在时间区间**$[t - x, t]$**使用的内存集合**，也被视为他**在未来**（下一段$x$时间内）**会访问的内存页集合**。
3. 该模型认为，**应当将应用程序的工作集同时保存在物理内存中**，因此，早期工作集模型的原则是all-for-nothing，即**一个应用程序的工作集要么全部都在物理内存中**（运行时），**要么全都被换出**，**从而减少该应用程序运行时发生换页的次数**。
4. 现代操作系统很少直接采用all-for-nothing作为换页原则，但是**工作集的概念依然指导着操作系统的换页策略**，即**优先将非工作集中的页换出**。
5. 一种常见的高效追踪工作集的实现方法是**工作集时钟算法**：
   1. 操作系统设置一个**定时器**，**每经过固定的时间间隔**，**一个设置好的工作集追踪函数就会被调用**。
   2. **该追踪函数为每个内存页维护两个状态**，分别为**上次使用时间**和**访问位**，**均被初始化为0**。
   3. **每次被调用**，该函数都会**检查每个内存页的状态**：
      1. 如果**访问位是1**，则说明**在此次时间间隔内该页被访问过**，于是该函数会**把当前系统时间赋值给该内存页的上次使用时间**，该方法的**前提是CPU硬件会在程序访问某个页的时候自动地将对应的访问位设置成1**。
      2. 如果**访问位是0**，则说明**在此次时间间隔内该页没有被访问**，于是该函数会**计算该页的年龄**（当前系统时间 - 该页的上次使用时间），**若该页的年龄超过预设的时间间隔$x$**，则他**不再属于工作集**。
   4. **检查完一个页的状态之后**，工作集追踪函数**将其访问位设置为0**。
6. 通过工作集时钟算法或者具有相似设计的算法，操作系统能够**有效地预测工作集**，从而**灵活地进行页替换**。

### 3.2 解决方法

1. **修改页面置换算法**。
2. **降低同时运行的程序的数量**。
3. **终止该进程**或**增加物理内存容量**。

## 参考文献

1. [有哪些页面置换算法？](https://github.com/wolverinn/Waking-Up/blob/master/Operating%20Systems.md#%E6%9C%89%E5%93%AA%E4%BA%9B%E9%A1%B5%E9%9D%A2%E7%BD%AE%E6%8D%A2%E7%AE%97%E6%B3%95)
2. [操作系统学习(10)页面置换算法](https://houbb.github.io/2020/10/04/os-10-page-exchange)。
3. [LRU——缓存淘汰算法](https://www.cnblogs.com/X-knight/p/10650995.html)。
4. [【面试题】技术面试题汇总](https://imageslr.com/2020/07/08/tech-interview.html)。
5. [LRU 进阶之 LRU-K 和 2Q](https://segmentfault.com/a/1190000022558044)。
6. [LRU-K 和 2Q 缓存算法介绍](https://www.jianshu.com/p/c4e4d55706ff)。
7. [常用缓存淘汰算法（LFU、LRU、ARC、FIFO、MRU）](https://zhuanlan.zhihu.com/p/68733600)。
8. [LFU 的基本原理与实现](https://www.cnblogs.com/wyq178/p/11790015.html)。
9. [LRU原理和Redis实现——一个今日头条的面试题](https://zhuanlan.zhihu.com/p/34133067)。
10. 《现代操作系统：原理与实现》
11. [贝拉迪异常(Belady’s Anomaly)](http://www.srcmini.com/28384.html)。