第二十七课：虚拟内存（Virtual Memory）

---

一、什么是虚拟内存？

一句话：

虚拟内存是一种让程序感觉自己拥有比实际内存更大空间的技术。

---

例如：

你的电脑：

实际：

8GB RAM

但是程序：

看到：

几十GB地址空间

为什么？

因为：

操作系统：

把一部分内容：

放内存。

一部分内容：

放硬盘。

需要时：

再调入。

---

类似：

你的书桌。

桌子：

只能放：

10本书。

但是：

你有：

100本书。

怎么办？

不会：

把100本全部摊桌上。

而是：

桌上放：

正在看的10本。

其他：

放书柜。

需要：

再换。

---

对应：

书桌 = 内存

书柜 = 外存（硬盘）

换书 = 页面调入调出

---

二、为什么需要虚拟内存？

主要有三个原因。

---

1. 运行大程序

以前：

程序必须：

全部装入内存。

现在：

不用。

---

例如：

大型软件：

100GB。

电脑：

16GB内存。

仍然：

可以运行。

因为：

只加载当前需要部分。

---

2. 提高内存利用率

如果：

10个程序。

每个：

只用20%。

以前：

全部加载：

浪费。

现在：

只加载：

需要部分。

可以：

运行更多程序。

---

3. 保护进程

每个程序：

拥有：

自己的虚拟地址空间。

互不影响。

---

三、虚拟内存的核心思想

记住：

一句话：

离散装入，按需调入。

什么意思？

---

离散装入

程序：

不用连续放。

还是：

分页。

---

按需调入

需要：

哪一页。

才：

加载：

哪一页。

---

所以：

虚拟内存：

建立在：

分页基础上。

---

四、请求分页系统（★★★★★）

现代操作系统：

主要使用：

请求分页存储管理。

名字拆开：

---

请求：

需要时：

才加载。

---

分页：

程序：

分成：

页面。

---

系统：

开始运行：

只加载：

部分页面。

---

例如：

程序：

有：

100页。

启动：

只加载：

10页。

其他：

不加载。

---

运行：

访问：

第50页。

发现：

没有。

怎么办？

产生：

缺页中断

---

五、什么是缺页中断？（重点）

缺页：

意思：

当前需要的页面：

不在内存。

---

例如：

程序：

访问：

页20。

页表：

发现：

页20

×

不在内存

于是：

发生：

缺页中断。

---

流程：

CPU访问页面

↓

检查页表

↓

发现页面不在内存

↓

缺页中断

↓

操作系统处理

↓

从硬盘调入页面

↓

更新页表

↓

继续执行

---

六、缺页中断为什么特殊？

普通中断：

例如：

键盘输入。

CPU：

暂停。

处理。

---

缺页中断：

更复杂。

因为：

它需要：

访问外存。

---

外存：

很慢。

所以：

缺页：

代价：

很高。

---

七、页表中的关键位

为了支持虚拟内存：

页表增加：

一些信息。

---

① 状态位（存在位）

表示：

页面：

是否：

在内存。

例如：

1：在内存

0：不在内存

---

② 访问字段

记录：

页面：

最近是否：

被访问。

后面：

页面置换算法：

会使用。

---

③ 修改位

表示：

页面：

是否：

被修改。

为什么重要？

因为：

如果页面：

没修改。

换出去：

不用写回硬盘。

---

八、虚拟内存工作流程

完整过程：

程序运行

↓

CPU产生逻辑地址

↓

查页表

↓

页面存在？

↓

是

↓

访问内存

否

↓

缺页中断

↓

寻找空闲页框

↓

调入页面

↓

更新页表

↓

继续运行

---

九、局部性原理（★★★★★）

为什么虚拟内存有效？

因为：

程序运行：

有规律。

这个规律：

叫：

局部性原理。

---

分两种：

---

1. 时间局部性

意思：

最近访问过的数据，很可能马上再次访问。

例如：

循环：

for(i=0;i<100;i++)
{
    sum++;
}

sum：

一直使用。

2. 空间局部性

意思：

当前访问附近的数据，也可能被访问。

例如：

数组：

a[0]

a[1]

a[2]

通常：

连续访问。

---

因为：

存在局部性。

所以：

不用一次加载全部程序。

---

十、虚拟内存的问题

虚拟内存很好。

但是：

有一个风险。

---

如果：

内存太小。

程序：

频繁：

换入换出。

会发生：

什么？

---

CPU：

大部分时间：

不是运行程序。

而是在：

搬页面。

---

这种现象：

叫：

抖动（Thrashing）

---

例如：

学生：

桌子太小。

一本书：

刚拿出来。

马上：

又放回去。

换另一本。

一直：

整理。

没有学习。

---

计算机：

也是：

一样。

---

十一、本课重点总结（★★★★★）

必须掌握：

---

虚拟内存

定义：

让程序逻辑上拥有比物理内存更大的空间。

---

核心思想：

按需调入

离散存储

---

请求分页：

需要：

哪页：

加载：

哪页。

---

缺页中断：

页面：

不在内存。

产生：

中断。

---

局部性原理：

为什么虚拟内存有效：

• 时间局部性
• 空间局部性

---

抖动：

频繁页面交换。

导致：

系统性能下降。

---

十二、口诀

虚拟内存：

程序不用全装入，需要哪页调哪页。

缺页：

页不在，产生中断，调入后继续干。

局部性：

刚用还会用，附近也可能用。

第二十八课：页面置换算法（Page Replacement Algorithm）

---

一、为什么需要页面置换？

假设：

内存：

只有：

3个页框。

现在：

已经装入：

页1

页2

页3

来了：

页4。

怎么办？

内存：

满了。

必须：

选择：

一个页面：

换出去。

这个过程：

叫：

页面置换（Page Replacement）

---

二、页面置换的目标

目标：

很简单：

尽量减少缺页次数。

为什么？

因为：

缺页：

需要访问硬盘。

而硬盘：

非常慢。

---

所以：

好的算法：

应该：

预测：

哪个页面：

以后：

最不需要。

---

三、算法一：最佳置换算法 OPT（★★★★★）

OPT：

Optimal。

中文：

最佳置换。

思想：

淘汰未来最长时间不会被访问的页面。

---

注意：

关键词：

未来。

---

例如：

当前：

内存：

1

2

3

下一次访问：

4

未来：

访问序列：

1 2 5 1 3 4

问：

换谁？

看：

三个页面：

未来什么时候再次出现。

---

页1：

马上：

出现。

---

页2：

后面：

出现。

---

页3：

较晚：

出现。

---

所以：

淘汰：

页3。

---

四、OPT的特点

优点：

理论上：

最好。

缺页次数：

最低。

---

缺点：

现实中：

无法实现。

为什么？

因为：

操作系统：

不知道：

未来。

---

所以：

OPT：

主要用于：

比较其他算法。

---

考试：

经常问：

哪个算法缺页最少？

答案：

OPT。

---

五、算法二：FIFO（★★★★★）

FIFO：

First In First Out。

中文：

先进先出。

思想：

谁最早进入内存，就淘汰谁。

---

类似：

排队买票。

最早排队的人：

先离开。

---

例如：

三个页框。

访问：

1 2 3 4

过程：

开始：

空。

---

访问1：

[1]

---

访问2：

[1 2]

---

访问3：

[1 2 3]

---

访问4：

满了。

谁最早？

页1。

淘汰：

页1。

结果：

[4 2 3]

---

六、FIFO的问题：Belady异常（★★★★★）

这是考试重点。

正常想：

内存越大。

缺页越少。

但是FIFO：

可能：

反而：

更多。

这叫：

Belady异常。

---

例如：

3个页框：

缺页：

9次。

增加到：

4个页框：

缺页：

10次。

反而：

增加。

---

为什么？

因为FIFO：

只看：

进入时间。

不看：

使用情况。

---

七、算法三：LRU（★★★★★）

LRU：

Least Recently Used。

中文：

最近最久未使用。

思想：

淘汰最长时间没有被使用的页面。

---

它比FIFO聪明。

因为：

利用：

局部性原理。

---

例如：

当前：

内存：

1

2

3

访问：

页4。

看：

最近使用情况。

如果：

页1：

很久没访问。

页2：

刚访问。

页3：

也刚访问。

淘汰：

页1。

---

八、LRU为什么有效？

因为：

程序：

具有：

时间局部性。

---

如果：

一个页面：

很久没使用。

那么：

近期：

大概率：

也不会使用。

---

所以：

LRU：

性能：

接近：

OPT。

---

九、三种算法比较（★★★★★）

算法	依据	优点	缺点
OPT	未来访问	最好	无法实现
FIFO	进入时间	简单	可能Belady异常
LRU	过去访问	效果好	实现复杂

---

口诀：

OPT看未来

FIFO看年龄

LRU看最近

---

十、缺页次数计算方法（重点）

考试：

通常：

给：

访问序列。

例如：

页访问：

7 0 1 2 0 3 0 4

页框：

3个。

问：

FIFO缺页次数。

---

步骤：

画表。

例如：

访问     7 0 1 2 0 3

框1      7 7 7 2 2 2

框2        0 0 0 0 3

框3          1 1 1 1

每次：

新页面进入：

算一次缺页。

---

十一、一个简单例子

页面：

1 2 3 1 4

三个页框。

---

访问1：

缺页。

内存：

1

---

访问2：

缺页。

1 2

---

访问3：

缺页。

1 2 3

---

访问1：

已经存在。

不缺页。

---

访问4：

没有。

缺页。

---

总缺页：

4次。

十二、LRU和FIFO容易混

这是很多人的坑。

---

FIFO：

问：

谁进去最早？

例如：

进入顺序：

1

2

3

换：

1。

---

LRU：

问：

谁最近最久没用？

例如：

最近：

3刚用

2刚用

1很久没用

换：

1。

---

可能：

结果一样。

但是：

判断方法不同。

---

十三、Clock算法（了解）

真实系统：

很少直接使用纯LRU。

因为：

记录访问时间：

成本高。

所以：

出现：

Clock算法。

思想：

模拟LRU。

---

每个页面：

有一个：

访问位：

0 / 1

访问：

设置：

1。

置换：

寻找：

访问位为0的页面。

---

408一般：

重点：

OPT、FIFO、LRU。

---

十四、本课重点总结（★★★★★）

必须掌握：

OPT

淘汰未来最长时间不用。

理论最优。

---

FIFO

淘汰最早进入内存页面。

可能产生Belady异常。

---

LRU

淘汰最近最长时间没使用页面。

利用局部性。

---

缺页次数

计算：

画表模拟。

---

十五、最终口诀

页面置换：

最佳看未来

先进看进入

最近看过去