GC的历史
-
GC 标记-清除算法
- 1960，John McCarthy
- GC之父
- 1960，John McCarthy
-
引用计数
- 1960，George E. Collins
- 1963，Harold McBeth指出：循环引用
-
GC 复制算法
- 1963，Marvin L. Minsky
- 人工智能之父
1963年GC复制算法诞生时，GC的根本性内容已经完成了。后续算法基本都是从这三种算法衍生而来。
- 1963，Marvin L. Minsky
使用GC机制的编程语言：
LispJavaRubyPythonPerlHaskell
GC 算法
基本概念
- 对象
- GC的基本单位
- 由几个部分组成：
- 头（header）
- 对象的大小
- 对象的种类
- GC所需的信息
- 域（field）
- 指针
- 指向内存空间中某块区域的值
- 非指针
- 指的是在编程中直接使用值本身
- 指针
- 头（header）
- mutator
- Edsger Dijkstra提出的概念
- 改变某物
- 实际进行以下操作：
- 生成对象
- 更新指针
- 伴随这些变化会产生垃圾，GC机制负责回收这些垃圾
- Edsger Dijkstra提出的概念
- 堆
- 用于动态（执行程序时）存放对象的内存空间
- 当mutator存放对象时，所需的内存空间就会从这个堆中被分配给mutator
- GC是管理堆中已分配对象的机制
- 活动对象 / 非活动对象
- 活动对象
- 通过mutator引用的对象
- 非活动对象
- 不能通过程序引用的对象
- 活动对象
- 分配
- allocation
- 指的是在内存空间中分配对象
- 当mutator需要新对象时，向**分配器（allocator）**申请一个大小合适的空间
- 分配器（allocator）在堆的可用空间中寻找满足空间的要求
- 返回给mutator
- 分块
- chunk
- 事先准备出来的空间
- 内存里各个区块都重复着分块 -> 活动对象 -> 垃圾（非活动对象） -> 分块 -> …… 的过程
- 根
- root
- 是指向对象的指针的起点
- 通过mutatur直接引用调用栈（call stack）和寄存器
- 调用栈、寄存器、全局变量空间都是根
- 评价标准
- 吞吐量
- throughput
- 在单位时间内的处理能力
HEAP_SIZE / SUM( GC_TIME )- 还需考虑mutator动作的影响
- 最大暂停时间
- 因执行GC而暂停执行mutator的最长时间
- 较大的吞吐量和较短的最大暂停时间不可兼得
- 根据不同的区域，不同的场景，选择不同的权重指标，采用不同的GC算法
- 堆使用效率
- 头的大小
- 堆中信息越多，GC的效率越高，吞吐量也随之改善
- 头越小越好
- 堆的用法
- 分区
- 可用的堆越大，GC运行越快；相反，越想有效地利用有限的堆，GC花费的时间就越长
- 头的大小
- 访问的局部性
- PC上的4种存储器
寄存器- register
缓存- 多级: L1,L2,L3…… cache
内存- 主存：memory
辅助存储器- 硬盘
- cache line
- 连续访问
- 把具有引用关系的对象安排在堆中较近的位置，就能提高在缓存中读取到所需数据的概率
- 令：mutator可以高速运行
- PC上的4种存储器
- 吞吐量
GC 标记-清除算法
两个阶段：
- 标记阶段
- 把所有活动对象都做上标记的阶段
- 标记所花费的时间与活动对象的总数成正比
- 算法：
- 深度优先算法
- 广度优先算法
- 两个算法操作步骤不会有差别
- 但是深度优先算法比广度优先搜索更能减少使用内存
- 清除阶段
- 回收那些没有标记的对象（非活动对象）
mark_sweep(){
mark_phase()
sweep_phase()
}
标记阶段
mark_phase(){
for(r : $root)
mark(*r)
}
mark(obj){
if(obj.mark == FALSE)
obj.mark = TRUE
for(child : children(obj))
mark(*child)
}
清除阶段
sweep_phase(){
sweeping = $heap_start
while(sweeping < $heap_end)
if(sweeping.mark == TRUE)
sweeping.mark = FLASE
else
sweeping.next = $free_list
$free_list = sweeping
sweeping += sweeping.size
}
分配
将回收的垃圾进行再利用
new_obj(size){
chunk = pickup_chunk(size, $free_list) //遍历$free_list,寻找大于等于size的分块
if(chunk != NULL)
return chunk
else
allocation_fail()
}
三种分配策略：
Fist-fit- 最初发现大于等于size的分块，立即返回
Best-fit- 遍历空闲链表
- 返回大于等于size的最小分块
Worst-fit- 找出空闲链表中最大的分块
- 将其分割成mutator申请的大小，和分割后剩余的大小
- 目的：将分割后剩余的分块最大化
- 容易产生大量小的分块
合并
将不同分配策略产生的小分块连在一起，形成一个大块。 合并（coalescing），在清除阶段进行。
sweep_phase(){
sweeping = $heap_start
while(sweeping < $heap_end)
if(sweeping.mark == TRUE)
sweeping.mark = FLASE
else
if(sweeping == $free_list + $free_list.size)
$free_list.size += sweeping.size
else
sweeping.next = $free_list
$free_list = sweeping
sweeping += sweeping.size
}
优点
- 实现简单
- 与保守式GC算法兼容
缺点
- 碎片化
- 增加mutator负担
- 分配速度
- 分块不是连续的
- 每次分配都必须遍历空闲链表
- 改进：
- 多个空闲链表（multiple free-list）
- BiBOP
- 与写时复制技术不兼容
- Linux的虚拟存储中高速化方法：写时复制（copy-on-write）
- 改进：
- 位图标记（bitmap marking）
多个空闲链表
- 按分块大小不同创建不同的空闲链表
- 每次按照mutator申请的分块大小选择不同的空闲链表
- 优点：
- 节约了分配所需的时间
- 缺点
- 需要对块大小进行预判
new_obj(size){
index = size / (WORD_LENGTH / BYTE_LENGTH)
if(index <= 100)
if($free_list[index] != NULL)
chunk = $free_list[index]
$free_list[index] = $free_list[index].next
return chunk
else
chunk = pickup_chunk(size, $free_list[101)
if(chunk != NULL)
return chunk
allocation_fail()
}
sweep_phase(){
for(i : 2..101)
$free_list[i] = NULL
sweeping = $heap_start
while(sweeping < $heap_end)
if(sweeping.mark = TRUE)
sweeping.mark = FALSE
else
index = size / (WORD_LENGTH / BYTE_LENGTH)
if(index <= 100)
sweeping.next = $free_list[index]
$free_list[index] = sweeping
else
sweeping.next = $free_list[101]
$free_list[101] = sweeping
sweeping += sweeping.size
}
BiBOP
- Big Bag Of Pages
- 将大小相近的对象整理成固定大小的块进行管理的做法
- 不能完全消除碎片化
位图标记、
- 用于标记的位是被分配到各个对象的头中
- 算法把对象和头一并处理
- 只收集各个对象的标志位并表格化（和对象分开管理）
- 标记的时候，不在对象的头里面置位
- 而是在这个表格中的特定场所置位
- 位图表格（bitmap table）
- 只收集各个对象的标志位并表格化（和对象分开管理）
mark(obj){
obj_num = (obj - $heap_start) / WORD_LENGTH
index = obj_num / WORD_LENGTH
offset = obj_num % WORD_LENGTH
if(($bitmap_tbl[index] & (1 << offset)) == 0)
$bitmap_tbl[index] |= (1 << offset)
for(child : children(obj))
mark(*child)
}
sweep_phase(){
sweeping = $heap_start
index = 0
offset = 0
while(sweeping < $heap_end)
if($bitmap_tbl[index] & (1 << offset) == 0)
sweeping.next = $free_list
$free_list = sweeping
index += (offset + sweeping.size) / WORD_LENGTH
offset = (offset + sweeping.size) % WORD_LENGTH
sweeping += sweeping.size
for(i : 0..(HEAP_SIZE / WORD_LENGTH -1))
$bitmap_tbl[i] = 0
}
优点
- 与写时复制技术兼容
- 清除操作更高效
延迟清除法
清除操作所花费的时间是与堆大小成正比
- 处理的堆越大，GC所花费的时间就越长
- 会妨碍到mutator的处理
延迟清除法（Lazy Sweep）
- 缩减因清除操作而导致的mutator最大暂停时间的方法
- 在标记操作结束后，不一并进行清除操作，而是延后
- 为了不让清除的暂停导致mutator长时间暂停
new_obj(size){
chunk = lazy_sweep(size)
if(chunk != NULL)
return chunk
mark_phase()
chunk = lazy_sweep(size)
if(chunk != NULL)
return chunk
allocation_fail()
}
lazy_sweep(size){
while($sweeping < $heap_end) // $sweeping是全局变量，每一次从上一次清除操作中之后的位置开始查找（分块的右边）
if($sweeping.mark == TRUE)
$sweeping.mark = FALSE
else if($sweeping.size >= size)
chunk = $sweeping
$sweeping += $sweeping.size
return chunk
$sweeping += $sweeping.size
$sweeping = $heap_start
return NULL
}
不足
由于每一次从上一次清除操作的位置开始查找，如果垃圾分布不平均（比如：都在上一次清除位置的左边（之前的位置）），那么，此次查找找到end位置也找不到合适的块
引用计数法
Reference Counting
- George E. Collins , 1960
算法
对象中包含一个计数器
计数器的增减
在引用计数法中并没有mutator明确启动GC的语句。
在两种情况下计数器的值会发生增减：
new_obj()update_ptr()
new_obj()函数
new_obj(size){
obj = pickup_chunk(size, $free_list)
if(obj == NULL)
allocation_fail()
else
obj.ref_cnt = 1
return obj
}
update_ptr()函数
update_ptr()函数用于更新指针ptr，使其指向对象obj，同时进行计数器值的增减
update_ptr(ptr, obj){
// 内存管理
// 注意次序，要考虑*ptr和obj是同一对象的情况
inc_ref_cnt(obj) // 1. 对指针ptr新引用的对象（obj）的计数器进行增量操作
dec_ref_cnt(*ptr) // 2. 对指针ptr之前引用的对象（*ptr）的计数器进行减量操作
// 指针更新
*ptr = obj
}
inc_ref_cnt(obj){
obj.ref_cnt++
}
dec_ref_cnt(obj){
obj.ref_cnt--
// 垃圾处理
if(obj.ref_cnt == 0)
for(child : children(obj))
dec_ref_cnt(*child)
// 将obj连接到空闲链表
reclaim(obj)
}
特征：
- 内存管理和mutator同时运行
- 监督在更新指针的时候是否有产生垃圾，从而在产生垃圾时可以立刻回收
优点
- 可即刻回收垃圾
- 当引用数为0时，对象立刻将自己作为空闲空间连接到空闲链表（回收）
- 其他GC算法中，对象成为垃圾，程序无法立刻判别，只能等待扫描
- 最大暂停时间短
- 没有必要沿指针查找
- 减少沿指针查找的次数
缺点
-
计数器值的增减处理繁重
- 如：根对象的引用数会非常频繁的变化
-
计数器需要占用很多位
- 计数器的值范围
-
实现繁琐复杂
- 算法本身很简单，但实现起来不容易
-
循环引用无法回收
- 如：互相引用
纵使有以上缺点，但仍然非常具有实用性。特别是一些改良后的引用计数算法。
延迟引用计数法
Deferred Reference Counting
- 为了改善计算器值频繁增减
- L. Peter Deutsch & Daniel G. Bobrow
频繁增减的原因：
- 根的引用变化频繁
做法：
- 引用变化不直接反映在计数器上
- 使用ZCT（Zero Count Table）
- 表中记录通过
dec_ref_cnt()变为0的对象 - 计数器为0就不一定是垃圾
- 表中暂时保留这些对象
- 表中记录通过
dec_ref_cnt(obj){
obj.ref_cnt-- // 减少引用数
if(obj.ref_cnt == 0)
if(is_fnull($zct) == TRUE) // 如果ZCT满了，就开始扫描
scan_zct()
push($zct, obj) // ZCT未满，就先放入ZCT
}
new_obj(size){
obj = pickup_chunk(size, $free_list)
if(obj == NULL)
scan_zct() // 无法分配块时，扫描一轮ZCT
obj = pickup_chunk(size, $free_list)
if(obj == NULL)
allocation_fail() // 如果还不能得到空闲块，则失败
obj.ref_cnt = 1
return obj
}
scan_zct(){
for(r : $roots)
(*r).ref_cnt++
for(obj : $zct)
if(obj.ref_cnt == 0)
remove($zct, obj) //
delete(obj) // 清空垃圾
for(r : $roots)
(*r).ref_cnt--
}
delete(obj){
for(child : children(obj))
(*child).ref_cnt--
if((*child).ref_cnt == 0)
delete(*child) // 子节点不使用ZCT，直接清理
reclaim(obj) // 将obj连接到空闲链表
}
优点
减轻了根引用的频繁变化带来的引用数频繁增减
缺点
- 垃圾不能立刻回收
- 垃圾会压迫堆
- 失去了引用计数一大优点（可立即回收垃圾）
scan_zct()函数导致最大暂停时间延长$zct越大，要搜索的对象就越多- 降低了吞吐量
Sticky引用计数法
用来减少计数器位宽
对于，计数器数值溢出，主要有两种应对策略：
- 什么都不做
- 那么当引用计数器为0时，也无法断定为垃圾对象
- 不过绝大多数场景下，对象的生命很短
- 使用GC标记 - 清除算法进行管理
- 当到达最大值时，改用GC标记 - 清除算法的变种来弥补，具体算法如下：
使用GC标记 - 清除算法进行管理
作为备用的GC标记-清除算法：
mark_sweep_for_counter_overflow(){
// 1. 一开始把所有对象的计数器值设为0
reset_all_ref_cnt()
// 2. 不标记对象，而是对计数器进行增量操作
mark_phase()
// 3. 搜索整个堆，回收计数器为0的对象
sweep_phase()
}
标记阶段：
mark_phase(){
// 从根直接引用的对象开始扫描
for(r : $roots)
push(*r, $mark_stack)
while(is_empty($mark_stack) == FALSE)
obj = pop($mark_stack)
// 对计数器进行增量
obj.ref_cnt++
if(obj.ref_cnt == 1)
for(child : children(obj))
push(*child, $mark_stack)
}
清除阶段：
sweep_phase(){
sweeping = $heap_top
// 搜索整个堆
while(sweeping < $heap_end)
// 回收计数器为0的对象
if(sweeping.ref_cnt == 0)
reclaim(sweeping)
sweeping += sweeping.size
}
缺点：
- 算法对活动对象进行了不止一次的搜索
- 吞吐量下降
优点
- 解决了计数器溢出问题
- 可以回收循环引用的垃圾
1位引用计数法
提出者：W.R.Stoye、T.J.W.Clarke、A.C.Norman
1bit Reference Counting
- 是Sticky引用计数法的一个极端例子
- 大部分对象的生命周期很短
- 用1位来表示某个对象的被引用数是1个还是多个
- 让指针持有计数器
- 称为：“标签（tag）”更为妥当
- 对象引用数为1时，标签位为0
UNIQUE状态- UNIQUE指针
- 对象引用数为复数时，标签位为1
MULTIPLE状态- MULTIPLE指针
- 对象引用数为1时，标签位为0
使用指针来存放标签位，也存在几个问题：
- 指针4字节对齐
- 更新指针所带来的问题
为了避免这两个问题，需要通过复制某个指针来达到更新的效果：
// copy_ptr()函数
copy_ptr(dest_ptr, src_ptr){
// 删除目的指针
// 也即，尝试回收dest_ptr引用的对象
delete_ptr(dest_ptr)
// 复制
*dest_ptr = *src_ptr
// 更新为MULTIPLE指针
set_multiple_tag(dest_ptr)
if(tag(src_ptr) == UNIQUE)
set_multiple_tag(src_ptr)
}
// delete_ptr()函数
delete_ptr(ptr){
if(tag(ptr) == UNIQUE)
// 如果清理的指针是一个UNIQUE，说明只有此次修改的对象持有指针指向的对象
// 所以此时可以直接清理
reclaim(*ptr)
}
优点
- 不容易出现高速缓存缺失
- 以往的引用计数法会在增减计数器值的时候读取引用对象，从而导致高速缓存缺失
- 引用对象的地址，与自身对象地址相隔很远，不在一个cache line，甚至不在一页
- 1位计数法，不需要更新引用对象的信息
- 以往的引用计数法会在增减计数器值的时候读取引用对象，从而导致高速缓存缺失
- 没有额外的计数器，节省了内存消耗量
缺点
- 需要考虑计数器溢出
- 大量的计数器溢出对象，导致更多的内存碎片
- 增加了堆区的维护量
部分标记-清除算法
引用计数法，最大的问题：不能回收循环引用的垃圾。 而GC 标记 - 清除就不会有这种问题。
两者结合使用，只对可能有循环引用的对象群使用GC 标记 - 清除；对其他对象使用引用计数法。
而这就是：部分标记-清除算法（Partial Mark & Sweep）。
- 目的：查找出非活动对象
- Rafael D. Lins, 1992
着色
通过4种颜色来进行管理：
- 黑（BLACK）
- 绝对不是垃圾的对象
- 对象产生时的初始颜色
- 白（WHITE）
- 绝对是垃圾的对象
- 灰（GRAY）
- 搜索完毕的对象
- 阴影（HATCH）
- 可能是循环垃圾的对象
4种颜色，使用对象头中2位的空间来表示：00~~11
dec_ref_cnt()函数：
dec_ref_cnt(obj){
obj.ref_cnt--
if(obj.ref_cnt == 0)
delete(obj)
else if(obj.color != HATCH)
// 着色
obj.color = HATCH
// 阴影对象的引用会被 $hatch_queue 持有
enqueue(obj, $hatch_queue)
}
new_obj()函数
new_obj(size){
obj = pickup_chunk(size)
if(obj != NULL)
// 初始着色
obj.color = BLACK
obj.ref_cnt = 1
return obj
else if(is_empty($hatch_queue) == FALSE)
// 搜索队列
scan_hatch_queue()
// 再次尝试分配
return new_obj(size)
else
allocation_fail()
}
scan_hatch_queue() 函数
scan_hatch_queue(){
obj = dequeue($hatch_queue)
if(obj.color == HATCH)
// 探索，着色灰色
paint_gray(obj)
// 对已探索到的对象（灰色）进行扫描，将灰色对象并且计数器为0的对象，着色为白色
// 经过这一步，队列中的对象非黑即白
scan_gray(obj)
// 回收白色对象
collect_white(obj)
else if(is_empty($hatch_queue) == FALSE)
scan_hatch_queue()
}
paint_gray() 函数
paint_gray(obj){
// 找出阴影或者黑色的对象
if(obj.color == (BLACK | HATCH))
// 着色成灰色，表示已经搜索过
obj.color = GRAY
// 对子对象引用数减量，并没有对obj自身引用数减一
// 也即是：这一次探索的root对象不能减少引用数，否则可能错误回收
for(child : children(obj))
(*child).ref_cnt--
//递归深度探索
paint_gray(*child)
}
scan_gray() 函数
scan_gray(obj){
if(obj.color == GRAY)
if(obj.ref_cnt > 0)
// 经过灰色着色，引用数减量后，引用数还大于0，说明不是垃圾，重新恢复黑色
paint_black(obj)
else
// 灰色，并且引用计数为0，说明一定是垃圾，标记成白色
obj.color = WHITE
for(child : children(obj))
//递归深度扫描
scan_gray(*child)
}
paint_black() 函数
paint_black(obj){
obj.color = BLACK
for(child : children(obj))
// 恢复黑色对象的子对象的引用数
(*child).ref_cnt++
if((*child).color != BLACK)
//递归深度扫描
paint_black(*child)
}
collect_white() 对象
collect_white(obj){
if(obj.color == WHITE)
// 还原初始值（对象头）
obj.color = BLACK
for(child : children(obj))
//递归深度扫描
collect_white(*child)
// 回收空间
reclaim(obj)
}
优点
- 把需要搜索的对象限定在阴影对象及其子对象范围内
- 可以回收循环引用的对象空间
缺点
- 着色的过程，涉及到几次递归深度扫描，成本代价太大
