GC-标记清除算法

自己的思维提纲和读书笔记，不详细，推荐自己读GC相关的书

标记阶段

• 标记根直接引用的对象（递归），避免重复标记
• 思想：遍历对象并标记
• DFS，容易压低内存使用

清除阶段

• 遍历对象并回收
• 取消活动对象标记，回收非活动对象
• 所费时间和堆大小成正比

分配

• first fit（比较好用）
• best fit
• worst fit

合并

优缺点

• 优点
  • 实现简单
  • 与保守式GC算法兼容（对象不能被移动）
• 缺点
  • 碎片化
  • 分配速度（分块不连续，最坏遍历整个free_list）【BiBOP技术】
  • 不兼容COW技术（算法机制导致的频繁设置标志位，以致不必要的复制） 【bitmap】

注：COW技术重写时复制私有空间数据，复制后不再访问共享空间

多个空闲链表

• 改进分配速度
• 思路：创建只链接大分块和只链接小分块的空闲链表
• 实现注意：设定上限，大分块需求极为罕见，不必太在意大分块分配效率，着重考虑小分块
• 算法部分：添加寻找链表序号的部分

BiBOP(Big Bag of Page)

• 把堆分成固定大小的块，让每块只能配置同样大小的对象（比如某一空闲链表均配置2个字大小的块）
• 作用：提高内存使用效率
• 这种方法不能完全消除碎片化，可能会有多个分块中都会有相同大小的碎片（比如两个字大小的内存块中）

位图标记(Bitmap)

• 只收集标志位并利用位图管理管理（不涉及对象，修改时只修改位图中的标志位）
• bitmap可用数组、散列、树等实现，一般一个字分配一个位
• 一般需要obj_num(序号)，index(行号)，offset(列号)
• 优点
  1. 与COW技术兼容
  2. 清除操作更高效
     同样遍历堆，同时遍历bitmap，将所有非活动对象回收至free_list之后，将bitmap每位均置0，以达到清除活动对象标志位的效果（没有立即消除标志位）
• Note
  此方法利用位运算计算对象对应的标志位，对象地址不连续时，单纯的位运算无法计算对象标志位的位置。因此有多个堆时，一般为每个堆准备一个bitmap。

延迟清除

• 缩减因清除操作而导致的mutator最大暂停时间
• 分配
  利用清除(lazy_sweep)操作分配，成功即返回，否则执行一次mark_phase()做标记，继续调用lazy_sweep()分配
• lazy_sweep()
  1. 遍历的开始位置位于上一次清除操作中发现分块的右侧（$sweeping是全局变量）
  2. 延迟清除不遍历整个堆，只在分配时执行必要的遍历，压缩因清除导致的mutator暂停时间
• Note：如果垃圾变成垃圾堆，活动对象变成活动对象堆，会导致延迟清除效果不均衡。遍历至垃圾堆部分获得分块速度较快，遍历至活动对象堆分配变慢。

（这部分后续还会有更详细的相关知识）