第二十七课：虚拟内存（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看年龄 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

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

利用局部性。

缺页次数

计算：

画表模拟。

十五、最终口诀

页面置换：

最佳看未来 先进看进入 最近看过去