SLP(Chapter 6):内存布局和分配(part 3)垃圾回收
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的块,其在内存中有以下四种情况
- 都是已经被分配的内存,只更新当前块header、footer的tag
- 下一个块是可用的,更新当前块的header、下一块的footer的size和tag
- 上一个块是可用的,更新前一块的header、当前块的footer的size和tag
- 前后都是可用的,更新前一块的header、后一块的footer的size和tag
- 都是已经被分配的内存,只更新当前块header、footer的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是不是存的指针?
- 地址 & 3 = 0
- 地址 % 4 = 0
如何找到块的开头?
- 使用平衡树跟踪所有分配的块(键 + 位置)
- 平衡树指针可以存储在标头中(另外两个单词)
2> 复制法 Copying collection
优点: 只遍历一次堆,所以比标记清除法块
缺点:1. 只用了一般堆空间; 2. 显示不可预知的周期性中断(标记清除法也有),因为要先停止其他所有进程
3> 引用计数法 Reference counting(显示内存分配最常用的解决方案)
跟踪指向每个对象的指针数(引用计数);当引用计数为 0 时,对象是无法访问的垃圾
缺点:
- 引用技术成本高、开销大
ct. 增量和递减 —— 时间
保留计数变量 —— 空间 - 无法回收环形结构
优点:动态和增量方式,每当存在赋值或其他堆操作时都会执行
这对保持实时应用程序或系统中的响应能力非常重要。
4> 分代式垃圾收集 Generational garbage collection
经验观察
如果对象已可访问很长时间,则很可能保持
在许多语言中,大多数物体都年轻死亡
结论:经常扫描年轻对象,不经常扫描旧对象
将对象分配给不同世代 G0、G1…
- G0 包含年轻的对象,很可能是垃圾
- G0 扫描频率高于 G1
通常两代(新的,终身的)
无需变量整个树集中工作使得效率更高
最年轻的一代包含的垃圾比例最高。- 老一代很少被垃圾收集
- 最年轻的一代可以在 5 到 50 毫秒(1 毫秒 = 00.001 秒)内收集
现代垃圾回收效率
- 相对于过去的缓慢的垃圾回收程序,现代的垃圾回收程序要先进得多。
- 分代、复制回收程序在很大程度上克服了早期的标记&清除算法的低效。
- 现代垃圾回收程序进行堆紧缩。
堆紧缩将__减少程序引用的页的数量,这意味着内存访问命中率更高,交换将更少。__
垃圾回收的优势
- 采用GC的程序不会因为内存泄漏的累积而崩溃。
- 采用 GC 的程序拥有更长期的稳定性。
- 采用GC的程序有更少的难以发现的指针错漏。
- 采用GC的程序开发和调试更快,因为不用开发、调试、测试或维护显式的释放代码。
垃圾回收的不足
- 内存回收何时运行是不可预测的,所以程序可能意外暂停。
- 运行内存回收的时间是没有上界的。尽管在实践中它的运行通常很快,但无法保证这一点。
- 除了回收程序以外的所有线程在回收进行时都会停止运行。
- 垃圾回收程序也许会留下一些本该回收的内存。
版权声明:本文为wowhahaha原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。