把事做成的才是赢家，在口头上压倒对手，真的没有那么重要！

Whirlwind introduce

当对象不再被引用时，对象不会立即被垃圾回收。也不存在任何子系统来专门记录使用的内存情况。

当系统没有内存空间时，触发GC处理。它首先会枚举所有的Root对象，然后递归的遍历根对象的引用关系。给遍历到的对象设置一个特殊标记，表明该对象是可达的，空间不能被回收。

当标记结束后，GC进入清洗阶段，任何在内存中没有被这次垃圾回收标记的对象都会被系统回收。

The algorithm

程序主要包含3个阶段：列举所有Root对象、标记起始于Root的对象引用、清除无效的对象。

void GC()
{
    HaltAllProcessing();
    ObjectCollection roots = GetRoots();
    for(int i = 0; i < roots.Count(); ++i)
        Mark(roots[i]);
    Sweep();
}

Root Enumeration

Root Enumeration会列举系统所有对象引用。运行系统需要为GC提供一种获取Root对象列表的机制。比如，在.NET中JIT维护了当前活跃的root对象，提供了获取根对象列表的API。

一个函数接受一个指针类型的参数，当方法返回时，jitter会识别出该参数不会再被使用，而将其从root中移除。

Mark

每个对象在创建时创建额外的空间，用于去mark这个对象，这个过程也是递归的

void Mark(Object* pObj)
{
    if (!Marked(pObj)) // Marked returns the marked flag from object header
    {
        MarkBit(pObj); // Marks the flag in obj header

        // Get list of references that the current object has
        // and recursively mark them as well


        ObjectCollection children = pObj->GetChildren();
        for(int i = 0; i < children.Count(); ++i)
        {

            Mark(children[i]); // recursively call mark
        }	
    }
}

递归的结束条件是：

1. 任何一个对象都不再有孩子节点
2. 如果一个对象已经标记过了，要避免出现循环引用的情况

sweep

sweep会遍历整个内存空间，释放没有被标记的内存。同时，它会清除标记的bit位，以便下次GC的正常标记。

void Sweep()
{
    Object *pHeap = pHeapStart;
    while(pHeap < pHeapEnd)
    {
        if (!Marked(pHeap))
            Free(pHeap); // put it to the free object list
        else
            UnMarkBit(pHeap);


        pHeap = GetNext(pHeap);
    }
}

总结

Mark-sweep天然适合清除循环引用的情况，然而它每次的循环遍历回收操作，会导致整个系统短暂的暂停，影响系统的正常交互。

参考文章：

1. Mark and Sweep Garbage Collection