GC书籍笔记
1. 垃圾回收评价标准
垃圾回收的目的是回收程序不在使用的对象所占用的空间。任何自动内存管理系统都面临三个任务：
-
为新对象分配空间
-
确定存活对象
-
回收死亡对象所占用的空间
安全性
这是首要考虑的因素，即在任何时候都不能回收存活的对象。
吞吐量
也就是说，即便是同一 GC 算法，其吞吐量也是受 mutator 的动作左右的。评价 GC 算法
的吞吐量时，有必要把 mutator （生成对象，更新指针）的动作也考虑在内。
停顿时间
最大暂停时间指的是“因执行 GC 而暂停执行 mutator 的最长时间”。这么说可能比较难理解，请再看一遍图 1.7。最大暂停时间是 A～C 的最大值，也就是 B。
这种情况下就需要缩短最大暂停时间。然而不管尝试哪种 GC 算法，我们都会发现较大的吞吐量和较短的最大暂停时间不可兼得。所以应根据执行的应用所重视的指标的不同，来分别采用不同的 GC 算法。
空间开销
某些垃圾回收器需要再每个对象内部（引用计数法）占用一定的空间，也可能引入堆级别的空间开销（标记-复制法），还有些需要额外的辅助的数据结构（bitmap）。
因为 GC 是自动内存管理功能，所以过量占用堆就成了本末倒置。堆使用效率和吞吐量，以及最大暂停时间不可兼得。简单地说就是：可用的堆越大，GC 运行越快；相反，越想有效地利用有限的堆，GC 花费的时间就越长。
完整性与及时性
理想情况下，垃圾回收应当是完整的，即堆中的所有垃圾最终都应当回收，但是这通常是不现实的，甚至是不可取的。衡量完整性更好的方法是统计所有的垃圾的最终回收情况，而不是单个回收周期的回收情况。
2. 回收算法
标记-清扫（mark-sweep）,标记-复制（mark-copy），标记-整理（mark-compact），引用计数法是4中最基本的垃圾回收策略，大多数回收器可能会以不同的方式堆这些进行组合。
标记-清扫
回收过程分两个阶段。
第一阶段：追踪阶段（trace），即回收器从根集合（全局变量，寄存器等）开始遍历对象图，并标记（mark）所遇到的每个对象。
第二阶段：清扫阶段，即回收器检查堆中的每个对象，并将所有未标记的对象当做垃圾进行回收。
此方法是一种间接回收算法，它并非直接检测垃圾本身，而是先确定所有的存活对象，反过来判定其他对象都是垃圾。直接回收的算法的例子是引用计数法。
该算法的每次调用都需要重新计算存活对象的集合。
伪代码
mark_sweep()
{
mark_phase()
sweep_phase()
}
mark_phase(){
for(r : $roots)
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 = FALSE
}
else
{
if(sweeping == $free_list + $free_list.size)//发现分块连续
{
$free_list.size += sweeping.size //合并两个分块
}
else
{
sweeping.next = $free_list
$free_list = sweeping
}
}
sweeping += sweeping.size
}
优缺点
优点：
实现简单，易于其他算法相结合使用。与保守式算法兼容
缺点：
碎片化；
分配速度慢：因为每次都必须遍历空闲链表，也每次都需要查找垃圾；
与cow（写时复制）不兼容
BiBOP
BiBOP法，Big Bag Of Pages，将大小相近的对象整理成固定大小的块进行管理的做法。有点像重新聚合。
我们可以用这个方法：把堆分割成固定大小的块，让每个块只能配置同样大小的对象。示意如下：
位图标记法
标记的位分配到各个对象的头中（存在一定的风险），最好使用一个独立的位图维护标记位，即将数据与用户数据分开单独存放。位图可以有一个，也可以有多个。数据结构可以用数组，散列表，树等表示。
优点：与写时复制兼容，不再需要遍历整个堆
伪代码
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)
}
延迟清除法
标记过程的时间复杂度是O（L），L是堆中存活对象的数量；
清扫过程中的时间复杂度是O（H），其中H为堆空间的大小。
由于H>L,很容易误认为清扫阶段的开销是整个标记-清扫过程的主要部分，但实际情况并非如此。标记阶段的指针桌子的内存访问模式是不可预测的，清扫过程中的可预测性则要高的多。
通过对象及其标记位存在两个特征：
第一：一旦某个对象成为垃圾，那么永远是垃圾
第二：赋值器永远不会访问对象的标记位，因此在赋值器工作的同时，清扫器可以并行修改标记位。
所以可以使用懒惰清扫法。主要流程如下：在回收过程，回收器依然将堆中的所有存活对象标记，但标记完成之后并不给予清扫整个堆，而是简单的将完全为空的内存块归还给分配器，同时将其他的内存块添加到其岁对于的空间代销分级的回收队列中。可与清除-复制算法结合使用。
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)
{
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
}
//lazy_sweep() 函数会一直遍历堆，直到找到大于等于所申请大小的分块为止。在找到
//合适分块时会将其返回。但是在这里 $sweeping 变量是全局变量。也就是说，遍历的开始位
//置位于上一次清除操作中发现的分块的右边。
延迟清除法不是一下遍历整个堆，它只在分配时执行必要的遍历，所以可以压缩因清除操作而导致的 mutator 的暂停时间。这就是“延迟”清除操作的意思。