美文网首页
GC-标记清除算法

GC-标记清除算法

作者: 夜莺纪事 | 来源:发表于2018-12-30 23:39 被阅读0次

    自己的思维提纲和读书笔记,不详细,推荐自己读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:如果垃圾变成垃圾堆,活动对象变成活动对象堆,会导致延迟清除效果不均衡。遍历至垃圾堆部分获得分块速度较快,遍历至活动对象堆分配变慢。

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

    相关文章

      网友评论

          本文标题:GC-标记清除算法

          本文链接:https://www.haomeiwen.com/subject/sltvlqtx.html