GC

标记清扫算法

标记数据

• 位图
  • 额外空间开销
  • 减少了标记阶段中的缺页错误和cache写失误的发生率
  • 速度较快
  • Dalvik 实现中是有两个bitmap，一个用于记录目前的活动对象，一个用于记录标记过程的可触及对象。然后暂停系统，对比bitmap进行释放标记。基于bitmap，实现一个根保守的栈mark操作成为可能。
• 对象
  • 具有跳跃性
    • 影响cache
  • 栈溢出(引用层次太多)
    • 显示调用栈(容易栈溢出)
    • 手工维护
      • 定量栈+遍历堆
      • 反向指针
      • 循环使用栈

清扫阶段

• 立刻清扫
• 延迟清扫
  • bdw
  • Boehm-Demers-Weiser(多层次分配器，高层次分配器将请求流转到不同的子分配器，子分配器只负责统一大小数据的分配和回收。)
    • 子分配器
      • 采用渐进式回收
      • 考虑数据组织结构
  • Hughes(每次分配时完成一定数量的清扫工作。对alloc的每次调用都会清扫堆，直到它找到一个合适的自由节点。)
    • 回收中断变短
    • 来回操作位图，不高效
    • 能够直接利用回收节点，不用交还给空闲列表
  • Zorn(也是分层次的数据组织形式，不过不是用链表串联，而是是用一个数组进行管理。)
• 遍历堆

总结

• 优点
  • 不需要移动对象
  • 利用了空间和时间的局部性
• 缺点
  • 空闲空间的组织方式
    • 这也是标记清扫算法除需要中断机器的最主要问题。 以Dalvik为例，其为了避免这个问题不是自己来管理一块大空间的内存，而是通过dlmalloc来接管下面的数据。 所以其关键就是dlmalloc对于内存布局的合理分配。
  • 碎片较多
  • 不同工作集的数据交织在一起
    • 影响了空间局部性

标记缩并

碎片现象

制作符合目标的分配器: * 伙伴系统 * 两级分配 * 堆不必连续 * 缓解碎片 * 首次匹配 * 最佳匹配

缩并的方式

考虑因素

• 处理不同大小的对象
• 为了重新安放对象和更新指针，算法需要遍历堆几次
• 算法需要多少额外的空间
• 算法是否需要对指针施加某种限制（内部指针、回指）
• 每一步需要做多少工作

单元排序方式

• 滑动的: 将活动单元滑动到堆的一端，把存活单元之间的自由单元“挤出去”，从而维持了分配是的原始次序。
• 线性: 尽可能的将原来的单元和他所指向的单元放在相邻的位置。例如：以深度优先次序复制图中的节点的节点复制器可以利用类似cdr-coding这样的技术对数据结构进行压缩
• 任意

三个阶段

1. 标记存活的数据结构
2. 通过重新安防单元来缩并这些单元构成的图
3. 更新指向被移动了的单元的指针

现有的算法

双指针算法：使用两个指针，一个指向下一个空闲的位置，另一个指向下一个要移动的存活单元。单元被移动之后，在他们原先的位置上留下一个迁移地址。这类方法一般只能适用于固定大小的单元。

迁移地址算法：在移动单元之前，把迁移地址写入每个单元的一个附加区域中。这一类方法可以用于收集不同大小的节点。

基于表的方法：在重新安放单元之前或是与之同时，在堆中构造一个存放重新安放单元的相关信息的映射表。这个表通常被称为间断表。算法将在以后查阅这个表，借助它计算指针的新值。

穿线方法：每个单元被链入一个链表，其中包含了所有原先指向他的单元。当单元转移时，算法通过这个链表做调整。

Lisp2(forward指针)

• 算法是一种滑动缩并算法，需要在每个对象的头部添加一个指针域forwarding用于存放该对象下一个新位置，并且需要进行三次堆扫描：
  1. 计算存活对象的新位置并存到forwarding：其实就是移动算法。从heap起始位置做紧凑性压缩准备，对象新地址基于当前已占用空间的大小
  2. 更新存活对象的指针域==指向对象的forwarding域
  3. 存活对象基于forwarding移动
• Forwarding指针
• 三遍扫描

穿线方法

将指向同一个地址的指针利用链表（已有链表）串联起来，然后等新数据确定后再更新数据。 1. A->P, B->P, C->P 1. P==Data 1. P-> C->B->A==Data 1. 在P更新地址后，在遍历链表更新数据。

Jonkers

• 操作本对象时涉及其他对象(工作集外面)
• 穿线工作量很大
• 该算法的限制：
  1. 指针只能指向单元的头部
  2. 单元头的大小必须足以存放一个地址
  3. 单元头必须包含能够同指向堆的指针区分开来的数据
• 具体:
  • 两次遍历：
    1. 处理前向指针(forward pointer)：较低地址指向较高地址的指针
    2. 处理后向指针(backward pointer)：较高地址指向较低地址的指针
  • 这个模型也需要看系统体系结构中数据的组织形式，是否有一个可以容纳空间的对象头。

基于表的方法

• 利用空闲区域存放: 利用堆空间自身，做迁移数据的保存。可以说是对forwarding的改进：不需要单独的存储空间。
• 间断表: 在空闲区域存放间断表，间断表记录：(存活块的起始位置，到目前空闲块时已经发现的空闲空间大小）。 在完成扫描后可以基于该表进行指针更新。

双指针算法

该算法首先标记存活数据结构，并记录存活单元的数量，结果记为nlive 1. 第一次遍历将堆中较高的部分（高于Heap[nlive]）的单元重新安放到较低部分的空洞里，并把迁移地址写入腾出的空间的第一个区域。 1. 第二次遍历扫描堆中较低的部分中的单元（到Heap[nlive]为止），更新其中的指针并使之指向新的位置。

在这里双指针的概念主要是指----算法使用两个指针： 1. free从堆的底部开始扫描，寻找自由节点 1. live则从堆的顶部开始扫描，寻找存活单元 1. 当free==live时第一次堆扫描完毕

重新安放单元的次序是随机的.

处理相同大小的数据单元

• 多次alloc，不同大小分配于不同堆区
• 将可变大小的数据缩并到堆中干净的页面中去:
  • Bartlett:
    1. 当整个堆被填满的部分超过85%时，它被用来追踪和缩并最年老的分代。
    2. 核心想法：把堆Heap分成固定大小的块block。有自由（空闲）块、和其他已经活动的块。
    3. 对象从当前的自由块中分配，为此只需要增大一个指针。
    4. 在缩并阶段，尽可能地减少在块之间移动的数据量，用轻微的碎片现象换取减少移动。其主要是缩并单个块而不是整个堆。
    5. 第一次扫描，寻找不到1/3满的块，把这些块上被标记的单元移动到当前自由块中，并留下一个迁移地址；而更满的块不会被处理。
    6. 队列中还有另外一个备用的自由块，用于防止自由块出现溢出。
    7. 第二次扫描时，和双指针算法相同进行指针更新处理。
    8. 利用自由块作为一层中间数据，缩并时先使用自由块空间。
    9. 块分为：自由块（空闲块）、刚刚进行分配使用的块（新对象）、发生了归并处理的块（对象已经移动，块中包含了迁移地址，不能被直接拿去使用）、归并处理结束包含数据已经完全没用的块
    10. Dalvik Copying算法基本上是使用了这种思想。

指针域更新问题

• 动态更新所有指针域
• 利用对象句柄

节点复制垃圾收集

如果存活数据在整个堆中只占很小的一部分，那么节点复制技术就特别有吸引力。

利用多余的连续空间，将数据从一端完整的滑向另一端，原数据的不变性也保证了指针更新。

三色法思路，scan&free指针

对象重组

主要是提高空间局部性，这主要由： * 对象访问模式 * 对象组织模式 * 对象内部数据指针指向模式等具体情况

多区域收集

大型对象区域

大型对象利用单独的存储空间进行处理，以减少移动带来的开销。

最好这些大型对象时原数据，即像图像这种不带有指针的数据。

甚至于可以和支持虚拟内存系统的OS做交互，修改页表映射做处理。

渐进的递增缩并垃圾收集

将数据分成很多小的block，然后每次只对一部分block做归并收集。

静态区域

节点复制的效率

通过扩展堆的大小，可以任意地降低节点复制垃圾收集的平均成本。

但是和标记清扫收集，其空间局部性很差。主要是由于整个数据从一个半区T移动到另外一个半区F。 可能F需要被重新换入主存，而T在主存的优势也完全丧失了。

双边收集(top&bottom)

分代垃圾收集

分代的代提升策略： * 多个分代 * 利用阈值判断 * 自适应

分代组织和年龄纪录： * 每个分代一个半区 * 创建一个附属空间 * 记录年龄 * 大型对象区域

分代间指针的管理：主要是涉及到mark时根节点集合（只会扫描该分代对象，较老分代的引用就需要作为根节点处理）： * 拦截器 * 各个分代一个入口表 * 记忆集 * 顺序保存缓冲区 * 硬件支持的页面标记 * 虚存系统支持的页面标记 * 卡片标记 * 记忆集与卡片可以相互结合

分代与对象生命周期

对象的生命周期与特定应用场景有关，并不能够通过一种简单的途径假设。

目前已经普遍存在的假设： * 强分代假设：越老的对象与不可能死亡。这种假设一般是不成立的。 * 弱分代假设：大多数对象在年轻时死亡

有些比较可观的结论： * 对象生命周期的分布是"成块"的。

目前CRuby已经在2.1.0上采用了混合MarkSweep与分代式GC的策略. Ruby2.1.0GC 其中有一些GC方面的分析技术与手段思路还是可以借见的.

渐进式和并发垃圾收集

主要是进行并发时的保护，主要是通过拦截器完成。

借助三色方案~

MarkSweep

• Dalvik MarkSweep
• Write-Barrier
  • dvmWriteBarrierField
    • dvmSetFieldObject
      • createArrayClass
      • loadClassFromDex0
      • dvmLinkClass
      • dvmInitClass
      • setInstFieldValue
      • SET_TYPE_FIELD(Jni.cpp)
      • enqueuePendingReference
      • dequeuePendingReference
      • clearReference
      • enqueueFinalizerReferences
      • DVM_OBJECT_INIT
      • dvmGenerateProxyClass
      • proxyConstructor
      • dvmPrepMainThread
      • dvmCreateInterpThread
      • dvmAttachCurrentThread
      • dvmDetachCurrentThread
      • makeStringObject
    • dvmSetFieldObjectVolatile
      • setInstFieldValue
      • SET_TYPE_FIELD(Jni.cpp)
    • dvmSetFieldStaticObject
    • dvmSetFieldStaticObjectVolatile
    • Dalvik_sun_misc_Unsafe_compareAndSwapObject
    • Dalvik_sun_misc_Unsafe_putObjectVolatile
    • Dalvik_sun_misc_Unsafe_putObject
    • Dalvik_sun_misc_Unsafe_putOrderedObject
  • dvmWriteBarrierObject
  • dvmWriteBarrierArray
    • goto_target
    • Dalvik_java_lang_System_arraycopy
    • dvmSetObjectArrayElement
  • dvmGetInterfaces

---

---

创建@

最后修改@

标签/Tags

• GC 3
• VM 5
• MarkSweep 1
• GenerationGC 1

相同类目/Categories

• VM-Group-Discuss
• 垃圾收集技术
• 虚拟机技术相关概要
• Virtual Machines