3 垃圾回收

3.1 内存管理机制

什么是空间分配？

分配器提供一组块的内存抽象

为什么动态内存分配?

程序通常不知道数据结构的大小，直到程序实际运行

动态内存分配的类型

• 显式：malloc free
  C
• 隐式/自动：应用程序分配，但不释放
  在 Java、Lisp 或 ML 中垃圾回收

垃圾回收特点

• 自动回收堆分配的存储
• 隐式内存管理（Java），不用free
• 延迟处理，仅在需要时才重新组织垃圾回收

分配器

分配器作用/功能

• 维护进程虚拟内存（称为堆）的区域
• 将堆保留为各种大小块的集合
• 显式分配
• 显式或隐式释放内存

分配器约束

• 对齐请求 / 相邻分配
• 无法确定分配内存的大小
• 立即响应
• 从可用内存分配
• 不移动已经分配的内存

优秀分配器的目标：

free掉多少内存？

• 保持块的长度
• 需要为分配的块提供额外单词

如何实现一个分配器？

0） 怎样表示内存分配?

• 位图 bitmap：由位组成的一个二进制块
  分配了的和释放了的块都可以表示
  
• 链表
  存储已分配或可用的内存
  

1）块组织 Block organization：我们如何跟踪自由块？

方法1：隐式空闲列表

	用额外 1 位，以标识是否分配；在块大小的低阶位

使用长度链接所有块

方法二：显式空闲列表

在空闲块中使用指针

方法三：Segregated free list 分离空闲链表

多个空闲链表，链接不同大小的空闲空间
对应的放置策略：First Fit（从小开始搜索，找到的块若大了，就拆分）

方法4：按大小排序的块

可以使用平衡树（例如红黑树），每个空闲块内有指针，以长度作位键值key

2） 放置 Placement：如何选择适当的空块放置新分配的块？

- First Fit: 首次适应法：碎片多
- Next Fit: 循环首次适应法（==最差的==）：从上次的后面开始找
- Best Fit: 最佳适应法（慢）

3) 拆分 Splitting：分配后，我们如何处理空闲块的其余部分？

> 当没有存在的空间块合适：
- 向内核请求更大的堆空间
- 合并相邻的内存块

4) 凝聚 Coalescing：我们如何处理刚刚释放的方块？

• immediate coalesce 立即合并
  
• deferred coalesce 推迟合并：快速分配器通常选择某种形式的延迟合并
  
• 专门应用于隐式空闲列表的：Coalescing with boundary tags 带边界标记的合并技术
  在可用块的底部复制大小
  
  
  针对上一个被free的块，其在内存中有以下四种情况
  
  1. 都是已经被分配的内存，只更新当前块header、footer的tag
     
  2. 下一个块是可用的，更新当前块的header、下一块的footer的size和tag
     
  3. 上一个块是可用的，更新前一块的header、当前块的footer的size和tag
     
  4. 前后都是可用的，更新前一块的header、后一块的footer的size和tag
     

3.2 经典GC算法

基本概念

将内存视为一个有向图，其中

• 每个块都是图中的节点
• 每个指针都是图中的边
• 有根节点、堆节点
  根节点：寄存器、堆栈上的位置、全局变量
  
  如何收集根节点？
  运行时系统需要为 GC 提供收集根列表的方法（.Net有可以枚举根节点的API）
• 有可到达节点、无法访问节点

1> 标记清除法 Mark and sweep collection

为什么说标记清除法 Mark and sweep collection是保守的conservative？
因为把所有元素都看作指针

构建在malloc/free顶部，所以集成了垃圾回收和C的malloc

额外的标记位 tag，在每个块的头部
Mark：从根开始，并在所有可到达的内存上设置标记位
Sweep： 扫描所有块，释放不可达块

怎么判断一个字word是不是存的指针？

1. 地址 & 3 = 0
2. 地址 % 4 = 0

如何找到块的开头？

• 使用平衡树跟踪所有分配的块（键 + 位置）
• 平衡树指针可以存储在标头中（另外两个单词）
  

2> 复制法 Copying collection

优点： 只遍历一次堆，所以比标记清除法块
缺点：1. 只用了一般堆空间； 2. 显示不可预知的周期性中断（标记清除法也有），因为要先停止其他所有进程

3> 引用计数法 Reference counting（显示内存分配最常用的解决方案）

跟踪指向每个对象的指针数（引用计数）；当引用计数为 0 时，对象是无法访问的垃圾

缺点：

1. 引用技术成本高、开销大
   ct. 增量和递减 —— 时间
   保留计数变量 —— 空间
2. 无法回收环形结构
   

优点：动态和增量方式，每当存在赋值或其他堆操作时都会执行
这对保持实时应用程序或系统中的响应能力非常重要。

4> 分代式垃圾收集 Generational garbage collection

经验观察
如果对象已可访问很长时间，则很可能保持
在许多语言中，大多数物体都年轻死亡

结论：经常扫描年轻对象，不经常扫描旧对象

将对象分配给不同世代 G0、G1…

• G0 包含年轻的对象，很可能是垃圾
• G0 扫描频率高于 G1
  通常两代（新的，终身的）
  
  无需变量整个树集中工作使得效率更高
  最年轻的一代包含的垃圾比例最高。
  • 老一代很少被垃圾收集
  • 最年轻的一代可以在 5 到 50 毫秒（1 毫秒 = 00.001 秒）内收集

现代垃圾回收效率

• 相对于过去的缓慢的垃圾回收程序，现代的垃圾回收程序要先进得多。
• 分代、复制回收程序在很大程度上克服了早期的标记&清除算法的低效。
• 现代垃圾回收程序进行堆紧缩。
  堆紧缩将__减少程序引用的页的数量，这意味着内存访问命中率更高，交换将更少。__

垃圾回收的优势

• 采用GC的程序不会因为内存泄漏的累积而崩溃。
• 采用 GC 的程序拥有更长期的稳定性。
• 采用GC的程序有更少的难以发现的指针错漏。
• 采用GC的程序开发和调试更快，因为不用开发、调试、测试或维护显式的释放代码。

垃圾回收的不足

• 内存回收何时运行是不可预测的，所以程序可能意外暂停。
• 运行内存回收的时间是没有上界的。尽管在实践中它的运行通常很快，但无法保证这一点。
• 除了回收程序以外的所有线程在回收进行时都会停止运行。
• 垃圾回收程序也许会留下一些本该回收的内存。