虚拟内存 (VM)

作用：是硬件异常、硬件地址翻译、主存、磁盘文件和内核软件的完美交互，为每个进程提供一个大的、一致的、私有的地址空间
三个优点：
- 高效：将主存看作是磁盘上的空间的高速缓存，高效利用的主存
- 简化：每个进程的地址空间都一致，便于管理
- 保护：保护每个进程的空间不被其他进程破坏
为什么是进程？
- 进程有独立的虚拟内存，一个进程的多个线程共享一个虚拟内存（线程只有比较小的独立空间，用来放栈等）
- 进程也是系统分配 (这里就是分配虚拟内存) 资源的单位（线程是CPU调度的单位）
学习
- 为什么需要学习
  - 核心
  - 强大
  - 危险
- 如何学习
  - 先了解：如何工作
  - 再了解：如何使用和管理
一些例子
- 假如程序需要4G，但你内存只有1G，能让你以为真的在4G空间里运行

物理和虚拟寻址

物理地址 (Physical Address, PA)
- 物理寻址 (physical addressing)
- 早期计算机使用
虚拟地址 (Virtual Address, VA)
- 虚拟寻址
- 现代处理器使用

虚拟寻址的原理：先转换为物理地址，这个任务叫 地址翻译 (address translation)。虚拟地址-->转换成物理地址-->访问物理内存

地址翻译的实现方式是：CPU芯片上的一个专用硬件 —— 内存管理单元 (Memory Management Unit, MMU)

地址空间 (address sapce)

keyword

线性地址空间 (linear address space)
n位地址空间：包含 $2^n$ 个地址空间
物理地址空间 (physical address space)
虚拟地址空间 (virtualaddress space)

虚拟内存三大功能

任意时刻，虚拟页面的集合都分为这些不相交的子集：

未分配页 (不会占用物理磁盘空间，C中未初始化的变量也是属于这种情况：有虚拟内存但没有相对应的物理内存)
已分配页

虚拟内存作为缓存的工具

虚拟页 (Virtual Page, VP)
物理页 (Physical Page, PP)、也叫页帧 (page frame)

任意时刻，虚拟页面的集合都分为这些不相交的子集：

未分配页 (不会占用物理磁盘空间，C中未初始化的变量也是属于这种情况：有虚拟内存但没有相对应的物理内存)
已分配页
- 缓存的
- 未缓存的

（这里有几个图很不错，一看就明白，有时间再拍照上来）

DRAM缓存的组织结构

速度由高到低

CPU位置
- 寄存器
- 三级缓存 (lscpu可以看，L1>L2>L3)
主存位置 (内存位置)
- SRAM
- DRAM (慢SRAM 10倍，DRAM的不命中比SRAM要昂贵得多，DRAM不命中就要给磁盘了，因此虚拟页通常很大，4KB~2MB)
磁盘位置 (慢DRAM 10w倍)

页表

页表项 / PTE (Page Table Entry)
有效位 (valid bit)

页替换算法

页命中

页不命中 (缺页)

有点类似 "cache miss" 了，和缓存那里的概念应该是差不多的，同理的

缺页 (page fault)
交换 (swapping)
页面调度 (paging)
按需页面调度 (demand paging)

分配页面

又是局部性救了我们

局部性 (locality)
局部性原则：……
- 工作集 (working set)
- 常驻集合 (resident set)
抖动 (thrashing)

虚拟内存作为内存管理的工具

当VM比PM更大时，VM作为缓存工具很有用。而早期VM比PM更小，但VM也同样很有用。此时VM的另一个主要作用是 —— 内存管理的工具

大大简化了内存管理

简化链接
简化加载
简化共享
简化内存分配

虚拟内存作为内存保护的工具

略

地址翻译

结合高速缓存和虚拟内存

利用TLB加速地址翻译

多级页表

综合：端到端的地址翻译

案例研究：Inter Core i7 / Linux 内存系统

Core i7 地址翻译

Linux虚拟内存系统

内存映射

内存映射 (memory mapping)
文件区 (section)
请求二进制零的页 (demand-zero page)
交换文件 (swap file)，也叫交换空间 (swap space) 或者交换区域 (swap area)

再看共享对象

再看fork函数

再看execve函数

使用mmap函数的用户级内存映射

动态内存分配

虽然可以使用低级的mmap和munmap函数来创建和删除虚拟内存的区域，
但是C程序员会觉得用动态内存分配器 (dynamic memory allocator) 更方便，移植性更好

堆 (heap)，向上 (低地址) 生长，指向堆顶的变量brk (读作"break")
分配器原理
- 将堆视为一组不同大小的块 (block) 的集合来维护
- 每个块是一个连续的虚拟内存片 (chunk)，要么已分配、要么空闲
分配器的两种风格
- 显式分配器 (explicit allocator)：C的 malloc/free，或C++的 new/delete
- 隐式分配器 (implicit allocator)：垃圾收集器 (garbage collector, GC)，垃圾收集 (garbage collection, GC)，如Lisp、ML、Java等语言

malloc 和 free 函数

更细节的底层原理见：“malloc、free和new、delete” 相关笔记

malloc

malloc，在32位和64位模式中，为8/16的倍数

malloc如果遇到问题（如要求的内存块比虚拟内存还大），则返回NULL，并设置errno

其他函数：malloc不初始化返回内存，要初始话可以使用calloc (基于malloc的瘦包装函数)，改变一个已分配块的大小：realloc函数

底层实现：malloc通过使用mmap和munmap函数，或者还可以使用sbrk函数

free

指向的位置必须是分配块的起始位置，否则出现未定义行为，且不会报错（free知道释放多大内存的原因是：malloc会多申请16Byte）

为什么要用动态内存

利用需要用户输入一个数字，然后生成对应大小的数组。

与之相反的做法就是硬编码大小来分配数组（指定数组的最大值，然后只使用一部分），缺点是无法使用超过MAX_N的数组

分配器的要求和目标

显式分配器必须在一些相当严格的约束下工作：

处理任意请求序列
立即响应请求
只使用堆
对齐块 (对齐要求)
不修改已分配的块

在这些限制条件下，分配器使用中尝试实现吞吐率最大化和内存使用率最大化，而这两个性能指标通常是冲突的

目标1 最大化吞吐率
目标2 最大化内存利用率

用来描述分配器使用堆的效率如何：

峰值利用率 (peak utilization)
- 有效载荷 (payload)
- 聚集有效载荷 (aggregate payload)
- 公式：
  $U_k = \frac{\max_{i\leq k}P_i}{H_k}\\~\\ 其中：\\U_k为前k+1个请求的峰值利用率，分配器目标是使该值最大化\\H_k为堆当前的(单调非递减的)大小，\\P_k为聚集有效载荷$
- 从公式中可以发现，两个目标是互相牵引的 (最大化吞吐率和最大化内存利用率)。很容易弄以堆利用率为代价写吞吐率最大化的分配器。
  分配器设计的一个挑战是从中找到平衡

碎片 (fragmentation)

造成堆利用率很低的主要原因：碎片

碎片有两种：

内部碎片 (internal fragmentation)
- 发生：已分配块比有效载荷大时发生，具体原因有很多（例如可能指定一个较大的数组但只使用了其中一部分）
- 量化：比较简单，已分配块大小和有效载荷大小差的和
外部碎片 (external fragmentation)
- 发生：空闲内存总和满足一个内存分配，但没有一个单独的空闲块足够大
- 量化：困难得多，且不可预测
- 避免：分配器通常采用启发式策略，来试图维持少量大空闲块，而不是维持大量的小空闲块

实现问题

吞吐量和利用率之间的平衡，考虑以下问题：

空闲块组织
放置
分割
合并

隐式空闲链表 (及堆块的格式)

任何分配器都需要一些数据结构，来区分块边界、区分已分配块和空闲块（对应的物理地址信息不存在这，也没必要，MMU会处理）

堆块的格式：

头部
- 块大小 (free通过这里知道释放多少，free处理的指针必须是块的起始指针，否则是未定义行为(而非报错))
- 已分配 / 空闲的 (后三位)
有效载荷 (只包含已分配的块)
填充 (可选，填充原因可能是分配器策略的一部分，用来对付外部碎片，或对齐要求等。块大小不知道包含填充部分不？)

隐式空闲链表：将堆组织为一个连续的已分配块和空闲块序列（通过头部的大小）

放置已分配的块 (放置策略)

当应用请求一个k字节块，分配器搜索空闲链表，查找一个足够大可以放置的空闲块，这个搜索是由 放置策略 确定的

常见的放置策略 (placement policy)：

首次适配 (first fit)
- 方法：从头开始搜索，选择第一个合适的空闲块
- 优点：趋向于将大空闲块保留在链表后
- 缺点：在靠近链表起始处留下很多小空闲块的 “碎片”，增大了对大块的搜索时间
下一次适配 (next fit)
- 方法：类似首次适配，但每次从上一次搜索结束的位置开始
- 优点：Donald Knuth 作为首次适配的代替品提出，运行速度加快
- 缺点：但一些研究表明，利用率要比首次适配低得多
最佳适配 (best fit)
- 选择适合请求大小的最小空闲块
- 优点：利用率
- 缺点：要求对堆进行彻底的搜索，慢

分隔空闲块

分配器找到匹配的空闲块后，需要决定分配这个空闲块多少空间

获取额外的堆空间

一个选择是通过合并那些在内存中物理相邻的空闲块来创建一个更大的空闲块（下一节描述）
当空闲块最大程度合并了，还是无法生成。则另一个选择是向核请求额外的堆内存

合并空闲块 (合并策略)

当分配器释放一个分配块后，可能会有假碎片 (fault fragmentation)：即相邻的空闲块没有合并在一起

解决：任何实际的分配器都必须合并相邻的空闲块，这个过程为合并 (coalescing)

这又分合并策略：

立即合并 (immediate coalescing)
- 方法：每次一个块被释放，就合并所有相邻的块
- 缺点：对于某些请求模式，会产生一种形式的抖动，块会反复合并然后马上分割。例如在只剩6字大小空间时，反复分配和释放一个三个字的块
推迟合并 (deferred coalescing)
- 方法：等到某个稍晚的时间再合并（例如等到某个分配请求失败，然后扫描整个堆，合并所有的空闲块。这里只是例如，情况可能有所不同）
- 优点：解决立即合并的缺点，通常采用

带边界标记的合并

分配器如何实现合并的

边界标记 (boundary tag)
- 方法：Knuth提出，在每个块的结尾添加一个脚部 (footer，边界标记)

综合：实现一个简单的分配器

显式空闲链表

分离的空闲链表

垃圾收集

介绍：略

垃圾收集器 (garbage collector)：一种动态内存分配器，显式分配块但从不显示释放他们
垃圾 (garbage)：程序不再需要的已分配块
垃圾收集 (garbage collection)
垃圾分类算法：很多。重点讨论 Mark&Sweep (标记清除法) 方法，也因为它可以建立在malloc包的基础上

垃圾收集器的基本知识 (可达图)

有向可达图 (reachability graph)：垃圾收集器将内存视为一张有向可达图
- 节点：节点分被分一组根节点 (root node) 和一组堆节点 (heap node)，每个堆节点对应堆中的一个已分配块
- 可达：当存在一条任意节点出发并到达p的又向路径时，我们说p是可达的 (reachable)
- 回收：在任何时刻，不可达节点对应于垃圾
有GC语言：像ML、Java这种语言，对如何创建和使用指针有严格的控制，能够维护精确的可达图，因此能回收所有垃圾
无GC语言：通常不能维持精确的可达图，这种收集器也叫做保守的垃圾收集器 (conservative garbage collector)。
保守的意思是：每个可达块都被正确标记为可达，而一些不可达节点却可能被错误地标记为可达

Mark&Sweep垃圾收集器 (标记清除法)

Mark&Sweep (标记清除法) 方法，可以建立在malloc包的基础上
（和C++的shared_ptr的引用次数的原理是不同的，这个是要使用堆头信息的，且只记录是否被标记，而不记录引用次数）

由标记 (mark) 和清除 (sweep) 阶段组成

标记阶段：记出根节点的所有可达和已分配的后继
清除阶段：释放每个未被标记的已分配块
（其中块头部中空闲的低位中的一位用来表示这个块是否被清除）

一些所需方法：

ptr isPtr(ptr p);			// 是否指向一个已经分配块的某个字
int blockMarked(ptr p);		// 是否已标记
int blockAllocated(ptr b);	// 是否已分配
int length(ptr b);			// 返回块b的以字为单位的长度 (不含头部)
void markBlock(ptr b);		// 设为已标记
void unmarkBlock(ptr b);	// 设为未标记
ptr nextBloc(ptr b);		// 返回堆中块b的后续

图示：

(略)

C程序的保守Mark&Sweep

Mark&Sweep 对C程序的垃圾回收是一种合适的方法，因为可以就地工作，而不需要移动任何块。

然而，C语言为isPtr函数的实现造成了一些有趣的挑战

C不会用任何类型信息来标记内存位置
就算我们知道p是指针，isPtr也没有明显方法来判断p是否指向一个已分配块的有效载荷中的某个位置
解决方法：将已分配块集合维护成一棵平衡二叉树