1、垃圾回收基础

垃圾回收器的安全性是指：在任何时候都不能回收存活对象。

浮动垃圾（floating garbage）：如果某个对象在回收过程启动之后才变成垃圾，那么该对象只能在下一个回收周期内得到回收。

回收器在标记对象时可以使用对象中的域，也可以使用额外的数据结构如位图 bitmap；对于并发回收器或其他需要将堆分为数个独立区域的回收器，其需要额外的记忆集（remembered set）来保存赋值器所修改的指针值或者跨区域指针的位置。

赋值器：应用线程。

在类型安全的语言中，一旦某个对象在堆中不可达，赋值器在没有外部系统协助的情况下是无法访问到不可达对象的。

赋值器在工作过程中会执行三种与回收器相关的操作：创建（New）、读（Read）、写（Write）。某些特殊的内存管理器会为基本操作增加一些额外功能，即屏障（barrier），屏障操作会同步或异步地与回收器产生交互。

在新分配的对象可被赋值器操作之前，回收器都需要先对其元数据进行初始化。

任何自动内存管理系统都面临三个任务：
1、为新对象分配空间。
2、确定存活对象。
3、回收死亡对象所占用的空间。

回收空间的方法影响这分配新空间的方法。

基于指针可达性分析得到的存活对象集合中可能包含一些永远不会再被赋值器访问的对象，但是死亡对象集合中的对象却必定是死亡的。

2、标记-清扫回收

是在指针可达性递归定义指导下最直接的回收方案。它的回收过程分为两个阶段：
第一阶段追踪（trace）阶段，即回收器从根集合（寄存器、线程栈、全局变量等）开始遍历对象图，并标记（mark）所遇到的每个对象；
第二阶段为清扫（sweep）阶段，即回收器检查堆中的每一个对象，并将所有未标记的对象当作垃圾进行回收。

标记-清扫算法是一种间接回收算法，它并非直接检测垃圾本身，而是先确定所有存活对象，然后反过来判定其他对象都是垃圾。该算法每次调用都需要重新计算存活对象集合。

3、# 标记-清扫算法

New():
    ref <- allocate()
    if ref = null           // 堆中无可用空间
        collect()
        ref <- allocate()
        if ref = null       // 堆中仍然无可用空间
            error "Out of memory"
    return ref

atomic collect():
    markFromRoots()
    sweep(heapStart, heapEnd)

3.1 标记 mark

回收器在遍历对象图之前必须先构建标记过程需要用到的起始工作列表（wor klist），将根对象进行标记并将其加入工作列表。

回收器可以通过设置对象头部某个位（或字节）的方式对其进行标记，该位或字节也可位于一张额外的表中。

markFromRoots():
    initialise(worklist)
    for each fld in Roots
        ref <- *fld
        if ref != null && not isMarked(ref)
            setMarked(ref)      // 标记完后再放进去
            add(worklist, ref)
            mark()

initialise(worklist):
    worklist <- empty

mark():
    while not isEmpty(worklist)
        ref <- remove(worklist)     // ref 已经标记过
        for each fld in Pointers(ref)
            child <- *fld
            if child != null && not isMarked(child)
                setMarked(child)
                add(worklist, child)

markFromRoots 在将根对象加入 worklist 后就马上调用 mark 是为了减少工作列表的大小。从 mark 方法从循环中提出则可以加快根扫描，对于并发回收器可能只需挂起线程并扫描其栈，接下来对象图遍历则可以与赋值器并发进行。

标记阶段完成的标志是工作列表，而不是将所有已标记对象都添加到工作列表，任何没有打上标记位的对象都是垃圾。

3.2 清扫 sweep

sweep(heapStart, heapEnd):
    scan <- heapStart
    while scan < heapEnd
        if isMarked(scan)
            unsetMarked(scan)   // 存活对象，清除标记位，以便下个回收周期进行标记
        else
            free(scan)          // 未标记的是垃圾对象
        scan <- nextObject(scan)

nextObject 不仅要能获取对象的大小信息，还要能处理用于对齐的填充字节。

在 JVM 里，每个对象实例都有一个指向其所属类型 Class 的指针字段，通过 Class 可以知道对象的大小。是否填充、如何填充其实取决于具体内存管理器的实现。
JVM 也可以根据这个 Class 获取所有引用类型的字段。进而遍历这些引用所指向的对象。也可能包含将对象自身标记、并将其字结点添加到 worklist 的代码。

3.3 三色抽象

三色抽象是描述追踪式回收器的一种十分有用的方法，利用可以推演回收器的正确性。

在三色抽象中，回收器将对象图划分为黑色对象（确定存活）和白色对象（可能死亡）。任意对象在初始状态下均为白色，当回收器初次扫描到某一对象时将其着为灰色，当完成该对象的扫描并找到其所有子节点之后，回收器将其着为黑色。

一次堆遍历过程可以形象第看作是回收器以灰色对象作为“波面”（wavefront），将黑色对象和白色对象分离，不断向前推进波面，直到所有可大对象都变成黑色的过程。

一个重要的不变式：在标记过程中，对象图中将不可能存在从黑色对象指向白色对象的引用，因此在标记过程中，所有白色可达对象都只能从灰色对象可达。