第二十五课：分页存储管理（Paging）

---

一、为什么需要分页？

先回顾动态分区。

假设内存：

高地址

----------------
程序A

----------------
空闲10MB

----------------
程序B

----------------
空闲20MB

----------------
程序C

----------------
空闲30MB

现在来了一个程序：

需要：

50MB

怎么办？

虽然：

空闲：

10+20+30=60MB

但是：

没有连续50MB。

所以：

放不进去。

---

这就是：

外部碎片问题。

---

分页的思想：

不要要求连续。

例如：

程序需要：

50MB。

拆成：

5个10MB。

可以：

放：

内存：

第1块

第7块

第20块

第35块

第100块

只要：

有空间：

就可以。

---

二、分页的基本思想

分页：

把：

两个东西：

都切小。

---

① 程序切成：

页（Page）

也叫：

页面。

---

例如：

程序：

大小：

16KB。

规定：

每页：

4KB。

那么：

分成：

4页。

程序

页0

页1

页2

页3

---

② 内存切成：

页框（Frame）

也叫：

物理块。

---

例如：

内存：

切成：

4KB一块。

内存：

块0

块1

块2

块3

...

---

注意：

非常重要：

页大小 = 页框大小

为什么？

因为：

这样：

一页：

刚好：

放入：

一个页框。

---

三、页和页框的关系

程序：

看到：

页

内存：

实际：

存放：

页框

关系：

程序

页0

↓

内存

页框5

程序

页1

↓

内存

页框9

---

所以：

必须：

有一个表：

记录：

对应关系。

这个表：

叫：

页表（Page Table）

---

四、页表是什么？

简单理解：

就是：

一个：

地址转换表。

例如：

程序：

认为：

自己：

有：

4页。

页表：

记录：

页号      页框号

0   →     5

1   →     9

2   →     3

3   →     8

---

意思：

程序访问：

页0。

操作系统：

查页表。

发现：

页0：

在：

页框5。

于是：

去：

物理内存：

第5块：

找。

---

五、逻辑地址如何转换？（★★★★★）

这是分页最重要内容。

CPU产生：

不是：

物理地址。

而是：

逻辑地址。

逻辑地址：

分成：

两个部分：

逻辑地址

=
页号 + 页内偏移

---

例如：

逻辑地址：

页号 = 2

偏移量 = 100

意思：

访问：

第2页：

里面：

第100个字节。

---

转换：

第一步：

查页表。

找到：

页2：

对应：

页框。

例如：

页2

↓

页框8

---

第二步：

组成：

物理地址：

物理地址

=

页框号 + 页内偏移

所以：

得到：

页框8

+

偏移100

---

六、一个完整例子（重点）

假设：

页面大小：

4KB

某逻辑地址：

8196

问：

页号？

偏移？

---

第一步：计算页号

公式：

页号 = 逻辑地址 ÷ 页面大小

也就是：

8196 ÷ 4096

因为：

4KB：

=4096字节。

结果：

页号=2

---

第二步：计算偏移

公式：

偏移 = 地址 mod 页面大小

所以：

8196 mod 4096

得到：

偏移=4

---

所以：

逻辑地址：

8196

↓

页号2

偏移4

---

七、为什么分页没有外部碎片？

因为：

所有空间：

都是：

固定大小。

例如：

每页：

4KB。

内存：

全部：

4KB块。

---

不会出现：

10MB

20MB

30MB

这种：

不连续空洞。

---

但是：

分页有：

新的问题。

八、分页的缺点：内部碎片

例如：

页面大小：

4KB。

程序：

大小：

10KB。

需要：

多少页？

---

计算：

10÷4=2.5

必须：

向上取整：

3页。

占：

3×4=12KB

实际：

需要：

10KB。

浪费：

2KB。

---

这就是：

分页产生：

内部碎片。

---

九、分页 vs 分区（★★★★★）

	连续分配	分页
要求连续	需要	不需要
碎片	外部碎片	内部碎片
管理单位	分区	页
灵活性	低	高

---

十、页表为什么重要？

因为：

分页之后：

程序地址：

不能：

直接：

找到内存。

必须：

转换：

逻辑地址

↓

页表

↓

物理地址

---

没有页表：

操作系统：

不知道：

页放在哪里。

---

十一、分页系统运行流程

完整过程：

CPU产生逻辑地址

↓

分成：

页号 + 页内偏移

↓

查页表

↓

得到页框号

↓

组合：

页框号 + 偏移

↓

访问内存

---

十二、本课重点（★★★★★）

今天必须掌握：

1. 分页思想

把程序分成页，把内存分成页框。

---

2. 页和页框

关系：

页大小 = 页框大小

---

3. 页表

作用：

记录：

页号 → 页框号

---

4. 地址转换

逻辑地址：

页号 + 页内偏移

物理地址：

页框号 + 页内偏移

---

5. 碎片

分页：

没有：

外部碎片。

但是：

有：

内部碎片。

---

第二十六课：快表（TLB）与多级页表

---

一、为什么需要快表 TLB？

先回顾：

分页系统。

CPU产生：

逻辑地址：

页号 + 页内偏移

然后：

查页表。

例如：

页表：

页号	页框号
0	5
1	9
2	3
3	8

CPU：

访问：

页2。

查：

页2 → 页框3

然后：

访问：

页框3。

---

问题：

页表在哪里？

答案：

也在内存。

所以：

过程：

CPU

↓

内存（查页表）

↓

得到地址

↓

内存（取数据）

需要：

两次内存访问。

---

二、TLB是什么？

TLB：

全称：

Translation Lookaside Buffer

中文：

快表

它是什么？

一句话：

存放最近常用页表项的小型高速缓存。

---

注意：

TLB不是替代页表。

而是：

页表的缓存。

---

类似：

生活例子：

你家：

有一本：

通讯录。

里面：

有所有人的电话。

但是：

你经常联系的人：

号码：

你直接记脑子里。

---

对应：

通讯录 = 页表

脑中记忆 = TLB

---

三、使用TLB后的地址转换

流程：

变成：

CPU产生逻辑地址

↓

查询TLB

↓

找到？

↓

是

↓

直接得到页框号

↓

访问内存

---

如果：

TLB没有找到：

怎么办？

再查：

页表。

---

完整流程：

CPU

↓

TLB

↓

命中？

↓

是 → 得到页框

↓

否

↓

查页表

↓

更新TLB

---

四、TLB命中率（考试重点）

定义：

CPU访问的页号，在TLB中找到的概率。

叫：

命中率。

记作：

α。

---

例如：

命中率：

α=80%

意思：

100次访问：

80次：

TLB找到。

20次：

查页表。

---

五、地址转换时间计算（★★★★★）

这是考试常考计算。

假设：

条件：

• TLB访问时间：20ns
• 内存访问时间：100ns
• TLB命中率：80%

求：

平均访问时间。

---

情况1：TLB命中

流程：

访问TLB

↓

访问内存

时间：

20 + 100

=

120ns

---

情况2：TLB未命中

流程：

访问TLB

↓

访问页表

↓

访问数据

时间：

20 + 100 + 100

=

220ns

---

平均时间

公式：

有效访问时间

=

命中率×命中时间

+

未命中率×未命中时间

代入：

=0.8×120

+

0.2×220

计算：

=96+44

=140ns

所以：

平均访问时间：

140ns

---

六、为什么需要多级页表？

现在：

又出现一个问题。

页表本身：

太大。

---

举例：

一个程序：

地址空间：

32位。

页面大小：

4KB。

---

计算：

页数量：

2^32 / 2^12

=

2^20页

也就是：

约：

100万个页。

---

一个进程：

页表：

可能：

非常巨大。

但是：

很多地址：

根本没有使用。

---

例如：

程序：

实际：

只用了：

几个区域。

代码区

↓

堆

↓

栈

中间：

大量空白。

---

如果：

建立完整页表：

浪费：

巨大。

---

所以：

出现：

多级页表

---

七、二级页表思想

核心：

不要一次建立全部页表，只建立需要的部分。

---

以前：

一级页表：

页号

↓

页表

↓

页框

---

二级页表：

拆开。

例如：

32位地址：

分成：

一级页号

二级页号

页内偏移

---

结构：

逻辑地址

↓

一级页表

↓

二级页表

↓

页框

---

八、为什么多级页表节省空间？

假设：

程序：

只用了：

一小部分地址。

那么：

一级页表：

只保存：

存在的二级页表地址。

没有使用的：

不创建。

---

类似：

目录。

---

一本书：

如果：

每一页：

都建立目录。

很浪费。

---

所以：

先：

一级目录。

需要：

再：

展开：

二级目录。

九、页表项里面有什么？

考试可能问。

一个页表项：

通常包括：

页框号

+

状态位

+

访问权限

+

修改位

---

例如：

状态位

表示：

页面：

是否：

在内存。

---

权限位

表示：

能否：

读写执行。

---

修改位

表示：

页面：

是否：

被修改。

用于：

页面置换。

后面会讲。

---

十、本课核心总结

1. TLB是什么？

页表项的高速缓存。

作用：

提高地址转换速度。

---

2. 地址转换顺序

有TLB：

CPU

↓

TLB

↓

页表

↓

内存

---

3. TLB命中

一次：

访问：

TLB + 内存。

---

4. TLB未命中

需要：

TLB

+

页表

+

数据

---

5. 多级页表

目的：

减少页表占用空间。

思想：

用多少，建多少。

---

十一、口诀（★★★★★）

TLB：

先查快表，命中直接走；没命中，再查页表。

多级页表：

页表太大，分级保存。