本篇是《垃圾回收的算法与实现》的读书笔记. 只是一种接近知识索引的形式.
GC 标记－清除算法。
最简单, 最古老的算法.
步骤
分成两步:
1.从根节点出发, 遍历所有可达的对象, 并在对象的头部添加标记.
2.遍历推, 回收所有的未标记的对象. 通常会有一个 free_list 来记录空闲的内存.
优点
- 实现简单.
- 与保守式的GC(对象不能被移动)兼容.
缺点
- 碎片化.
- 分配速度比较慢. 最坏情况下每次分配都需要遍历 free_list.
- 与写时复制不兼容(每次GC都会写内存导致复制.)
改善方式
- 多个空闲链表. 根据空闲块的大小选择存在不同的链表中.
- 合并空闲块, 在清除的时候, 如果两个空闲块可以合并, 那么就合并成一个大的空闲块. 可以减少一部分的碎片.
- BiBOP(Big Bag Of Pages) 方法. 将堆分块, 每一个块都只能分配固定大小的对象. 可以减少一些碎片, 但是降低了堆的使用效率.
- 位图标记法. 标记在一个位图中进行(通常 1 bit 代表一个字). 这个提高清除的效率, 还可以与写时复制兼容.
- 延迟清除法. 在分配的时候进行标记和清除. 可以降低最大暂停时间. 但是会导致分配的用时不稳定.
引用计数法
George E. Collins 在 1960 年提出来的. 现在 Apple 的 ARC 正式采用这种方式.
