内存虚拟化

内存隔离

第十三章抽象：地址空间

1 早期系统

操作系统、进程的资源等都在内存中，操作系统几乎没有提供抽象

2 需求1：提高效率——多道程序系统

多个进程在给定时间准备运行
一个进程在IO时，操作系统切换进程

3 需求2：希望提高计算机使用的交互性——分时系统

分时系统——时分共享——CPU虚拟化
需要比多道程序系统更多的进程切换
如果进程的状态信息保存到磁盘上，切换过程会很慢
故将状态信息保存在内存里
多个进程共享内存

4 需求3：进程内存需要被保护——地址空间

地址空间是运行的程序看到的系统中的内存
进程的地址空间包含了运行的程序的所有内存状态
- 程序代码（指令）
- 栈：函数调用信息、局部变量
- 堆：动态内存
程序运行时，堆、栈可能增长或收缩

5 地址空间是操作系统提供给运行程序的抽象

如何虚拟化内存？即让程序认为自己使用的是 0~16KB 的内存，但实际上，对应的物理内存的位置并非是 0~16KB

6 隔离原则

操作系统力求让进程彼此隔离，从而进程间的误操作
内存隔离可以确保运行程序不影响底层操作系统的操作

7 内存虚拟化的目标

透明：即让运行程序感觉不到操作系统对地址空间的抽象
效率：在追求虚拟化的同时保证时间上和空间上的高效
保护：让进程与进程之间隔离、进程与操作系统之间隔离

第十四章插叙：内存操作API

本章核心问题：如何分配和管理内存

1 内存类型

栈内存：编译器在生成汇编时，保证申请内存和释放内存是一对，自动内存
堆内存：编译器在生成汇编时，在申请内存时分配内存，只有程序员写出来释放内存的代码，才会释放内存

2 `malloc()` 调用

1 2	// 堆空间分配成功返回指向该空间的指针分配失败返回 NULL void malloc(size_t size); // void 指针可以通过类型转换为任意类型指针

3 `sizeof()` 编译时操作符

int x[10];
// sizeof(x)为数组的大小
int *y = malloc(10 * sizeof(int));
// sizeof(y)为指针的大小

4 为字符串声明空间时需要加1

因为 C 风格字符串以空字符串结尾

1	// malloc(strlen(s) + 1)

5 `free()` 调用

free() 调用接受一个由 malloc 返回的指针

分配的内存大小由内存分配库本身记录追踪
1
2
int *y = malloc(10 * sizeof(int));
free(y);

6 常见错误

忘记分配内存：定义了一个指针，但是没有分配内存
分配内存不够：上述的字符串分配内存
忘记初始化分配的内存
忘记释放内存
在用完之前释放内存——悬挂指针
反复释放内存
错误调用 free

7 为什么在进程退出时没有内存泄漏？

系统存在两级内存管理

第一级：操作系统执行的内存管理
- 操作系统在进程运行时将内存交给进程、在进程退出时将其收回
第二级：进程的内存管理
- 进程如果需要长期执行，如果出现内存泄漏，就会导致程序崩溃

8 其他调用

calloc()：配的内存在返回指针之前会被初始化为全零
realloc()：创建一个更大的内存区域，将旧区域复制到其中
mmap()

第十五章机制：地址转换

受限直接访问的扩展——地址转换

本章核心问题：如何高效、灵活地虚拟化内存——基于硬件的地址转换

高效：利用硬件的支持，即尽量让程序自己访问
控制：确保应用程序只能访问自己的内存空间，即操作系统在提供一些访问限制
灵活性：程序能以任何方式访问自己的内存

本章小点总结

1 什么是基于硬件的地址转换
2 一些逐步放宽的假设
3 举例说明什么是地址转换
4 什么是动态重定位
5 什么是静态重定向
6 空闲列表记录空闲内存
7 内存虚拟化需要的硬件支持
8 操作系统提供的支持
9 总结

1 什么是基于硬件的地址转换

每次内存访问时，硬件将指令中的虚拟地址（进程的内存地址）转换为数据实际存储的物理地址（实际内存地址）

操作系统控制硬件，以便完成正确的地址转换——管理内存，记录被占用和空闲的内存地址

从而实现——每个程序有私有内存的假象

2 一些逐步放宽的假设

地址空间必须连续地放在物理空间
地址空间小于物理内存
每个地址空间的大小完全一样

3 举例说明什么是地址转换

程序访问的是左图中的地址空间这个地址空间的实际物理地址是右侧图的重定位的地方

4 什么是动态重定位

基址加界限机制（动态重定位）

进程访问到的是左侧的虚拟地址，在访问时，硬件自动定位到地址空间的起始地址，通过该起始地址和虚拟地址计算出物理地址，然后返回给进程物理地址的值（由于这个过程是运行时发生的，所以被称为动态重定向）

1	physical address = virtual address + base

其中，起始地址记录在基址寄存器中，此外还需要判断访问是否越界，所以用界限寄存器来限定界限，一般在求和前检查界限，以防计算越界
基址寄存器和界限寄存器的硬件结构是芯片上的，每个 CPU 一对——称为内存管理单元 MMU

5 什么是静态重定向

程序编译、链接或配置时就已经确定

6 空闲列表记录空闲内存

操作系统利用空闲列表的数据结构记录内存中空闲的范围

7 内存虚拟化需要的硬件支持

8 操作系统提供的支持

进程创建时，操作系统为进程寻找空1的内存，将其标记为已用
进程终止时，回收内存，标记为空闲
上下文切换时，需要保存恢复基址寄存器和界限寄存器
异常处理

9 总结

硬件为进程提供虚拟地址到物理地址的转换
操作系统管理物理地址的内存——分配内存
基址加界限提供了保护

缺点：

内存区域利用率不高——空间碎片

第十六章分段

本章核心问题：怎样支持大地址空间？
本章小点总结：

1 思考地址转换的问题所在
2 分段：泛化的基址/界限
3 可爱的段错误 segmentation fault
4 如何让硬件知道引用的段以及偏移量
5 段的反向增长
6 地址空间中某些内存段的共享
7 细粒度和粗粒度的分段
8 操作系统支持

1 思考地址转换的问题所在

地址转换使用基址寄存器和界限寄存器，当地址空间较大时

栈和堆之间空间未被进程使用
若剩余地址无法提供这么长的物理内存，则进程无法运行
不够灵活

2 分段：泛化的基址/界限

地址空间有代码段、栈段、堆段

每个逻辑段给定基址和界限寄存器
每一个逻辑段单独找物理内存来存放值，不要求连续
避免了虚拟地址空间中未使用部分占用物理内存
堆的虚拟地址为 4200 ，先求堆内部的偏移量 4200 - 4096 = 104
堆的物理基址为 34KB = 34816
再求堆的物理地址 104 + 34816 = 34920

3 可爱的段错误 `segmentation fault`

4 如何让硬件知道引用的段以及偏移量

显式方式：用虚拟地址的开头几位标识不同段

00 代码段
01 堆段
11 栈段
01 0000 0110 1000 为 4200 的二进制表示
用 01 选择段， 0000 0110 1000 为段内偏移
隐式方式：通过地址产生的方式确定段

5 段的反向增长

用一个位来标识段的增长方向
由虚拟地址计算段内反向偏移量，再加上物理基址，得到正确物理地址

6 地址空间中某些内存段的共享

提供一个保护位，防止代码段在程序运行时被更改，那么就可以多个进程共享一个代码段

7 细粒度和粗粒度的分段

粗粒度：只有很少的几个段
细粒度：可以有很多段；需要保存段表

8 操作系统支持

上下文切换：各个段寄存器中的内容必须保存和恢复
管理物理内存的空闲空间：企图有更多连续分配的空间
- 1紧凑物理内存，将内存的内容移动，从而得到较大的连续物理空间
- 2空闲列表管理算法，试图保留大的内存块用于分配

9 分段总结

分段的好处
- 更高效的虚拟内存，避免地址空间内部的内存浪费
- 代码共享
分段的坏处：内存碎片

第十七章空闲空间管理

本章核心问题：如何让碎片最小化？

1 一些假设

以 malloc 和 free 作为内存管理的直接操作者
主要关心外部碎片，即分配给程序之后剩下的空闲部分内存
内存被分配后，不可以被重定位到其他位置
分配内存所管理的是连续的

2 什么是分割与合并

分割：当分配程序要分配一块内存时，如果有连续的空闲空间满足分配条件，则分配程序在空闲列表的某个连续段中切割出需要的段，留下剩下的部分，继续放在空闲列表

合并：在分配程序释放内存时，会寻找邻近的内存，如果刚好是相邻，则合并这些空闲内存
3 如何追踪已分配空间的大小？

malloc 分配内存时，会额外分配一部分——头块，用于保存分配空间的大小等额外信息
free 释放内存时，会通过指针回溯，找到头块，然后释放头块记录的内存大小以及头块

Memory Layout:
+------------+----------------+
| Block Header | User Memory  |
+------------+----------------+
^              ^
|              |
Hidden        malloc returns this pointer

4 空闲空间中简历空闲空间列表

mmap 来获得分配一部分内存，以 4KB 为例，初始化后，列表内记录的空闲内存为 4096 ，还有八个字节被用作记录空闲空间列表的头块，不算在 4KB 里面

5 空间耗尽时，向操作系统申请更大的空间

6 基本策略 1 ：最优匹配

基本思路：选择最接它用户请求大小的块，从而尽量避免空间浪费
实现过程：首先遍历整个空闲列表，选择合适的空闲块里面最小的。
缺点：简单的实现在遍历查找正确的空闲块时，要付出较高的性能代价

7 基本策略 2 ：最差匹配

基本思路：尝试在空闲列表中保留较大的块
实现过程：尝试找最大的空闲块，分割并满足用户需求后，将剩余的块（很大）加入空闲列表
缺点：大多数研究表明它的表现非常差，导致过量的碎片，同时还有很高的开销

8 基本策略 3 ：首次匹配

基本思路：首次匹配有速度优势
实现过程：找到第一个足够大的块，将请求的空间返回给用户
缺点：有时会让空闲列表开头的部分有很多小块

9 基本策略 4 ：下次匹配

基本思路：将对空闲空间的查找操作扩散到整个列表中去，避免对列表开头频繁的分割
实现过程：下次匹配（next fit）算法多维护一个指针，指向上一次查找结束的位置
缺点：

10 基本策略 5 ：分离空闲列表

基本思路：如果某个应用程序经常申请一种（或几种）大小的内存空间，那就用一个独立的列表，只管理这样大小的对象。
实现过程：厚块分配程序（slab allocator）
缺点：

11 基本策略 6 ：伙伴系统

基本思路：递归合并
实现过程：空闲空间被递归地一分为二，直到刚好可以满足请求的大小
缺点：有内部碎片

12 总结

在本章中，我们讨论了最基本的内存分配程序形式。这样的分配程序存在于所有地方，与你编写的每个 C 程序链接，也和管理其自身数据结构的内存的底层操作系统链接。与许多系统一样，在构建这样一个系统时需要这许多折中。对分配程序提供的确切工作负载了解得越多，就越能调整它以更好地处理这种工作负载。在现代计算机系统中，构建一个适用于各种工作负载、快速、空间高效、可扩展的分配程序仍然是一个持续的挑战。

第十八章分页：介绍

如何通过页来实现虚拟内存？

解决空间管理问题（如何给空间分块）

分割成不同长度的分片：空间碎片化，难以分配内存
分割成固定长度的分片：分页——我们考虑的方向

1 举例说明分页的相关概念

地址空间：如上述左图，操作系统为进程提供的抽象，让进程以为它独占了这么多内存
分页：将进程的地址空间分割成固定大小的单元，每个单元为一页
物理内存：如上述右图，物理内存分成槽块分布的页帧，与进程的页大小一致
页表：将（进程地址空间的页）映射到（物理内存的页帧），只有这样才可以对应
- 每个进程的页表相互独立

2 页表的作用举例

页表的作用：将虚拟地址的 VPN 映射到 PFN

虚拟地址空间 64 字节（ 6 位表示）
将虚拟地址划分为 4 页，则可以用前两位表示页号
后四位表示每个页内偏移量
FPN 加上偏移量得到物理地址

3 考虑页表的大小

一个 32 位虚拟地址空间，分为 4KB 的页，则页内偏移为 12 位，页表需要 20 位，假设一个页表条目需要 4 字节来存放映射，那就需要 4 个字节，则每个页表需要 $2^{20} * 4 = 2^{22}$ 字节， 4MB 内存

4 页表的采用的数据结构

页表可以采用不同的数据结构来存放数据

线性页表：采用数组存放

5 页表记录了什么

页表包括页对应的页表项PTE（page table entry）
每个页表项包括 PFN 和位，举例x86的页表项（不同操作系统不一样）

V 有效位：记录当前页表项是否被使用，即对应到物理地址，标记为未使用可以暂不分配物理内存，节省空间
R/W/E 保护位：读、写、执行
存在位：表示页在内存还是磁盘上
脏位：表明页面载入内存后是否被修改过
参考位：追踪页是否被访问

6 分页带来的速度问题

虚拟地址到物理地址的映射并非简单的映射，需要很多计算

从虚拟地址提取 VPN
用 VPN 索引页表基址寄存器指向的位置的 PTE 数组，得到 PTE
从 PTE 提取 FPN
FPN 与虚拟地址的偏移量连接
最终形成物理地址

7 分页带来的两个缺陷

页表可能会很大（所以本身存放在内存里，而不是硬件上）
- 解决方案：第二十章分页：较小的表
页表导致系统运行速度过慢
- 解决方案：第十九章分页：快速地址转换（TLB）

8 内存追踪（举例）

0x1024 movl $0x0,(%edi,%eax,4) 
0x1028 incl %eax 
0x102c cmpl $0x03e8,%eax 
0x1030 jne 0x1024

上述汇编指令，在指向指令时（访问代码的内存，即页表[1]，即第二页）
在访问数组时，访问数组内存，即页表[39]
下图中，左侧为虚拟空间地址，右侧为物理地址