GC_overview

Garbage Collection

Copying Garbage Collection

简单来说,内存分为2个区域,使用其中一个区域分配内存,直到剩余内存不足,则触发GC:遍历所有的ROOT,将可达的对象copy到另外一块内存区域中.

好处: 内存分配相当的快,只是指针的移动.

坏处: 浪费内存.

#Mark and Sweep Garbage Collection

sweep: 扫除; 打扫，清理;

标记，清理垃圾回收

伪代码：

void GC()
{
    HaltAllProcessing();
    // 枚举root
    ObjectCollection roots = GetRoots();
    for(int i = 0; i < roots.Count(); ++i)
        //标记
        Mark(roots[i]);
    //清理
    Sweep();
}

##枚举root

遍历这些地方的所有reference : registers, global or static fields, local variables on the stack, function arguments on stack。

标记

利用每个对象的header中的marked flag，进行标记

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
        }	
    }
}

利用递归的方法进行标记。

清理

通过遍历整个内存并释放未标记的内存块来开始扫描。它还会清除标记位，以便后续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);
    }
}

压缩

长期的进行GC，可能会导致内存碎片。回收后的压缩能减少碎片，但是，当内存被压缩时，对象会移动，因此必须更新对它们的所有引用以指向新位置。

溢出处理

垃圾回收面对的是一个非常巨大的对象树，之前的Mark-sweep伪代码中，使用递归的方法，容易引起stack overflow。

我们可以用一个MarkStack来代替递归，然后使用广度优先来遍历，来尽量避免overflow。但是如果溢出还是不能完全避免，如果发生了溢出，可以采取一些fallbakc 方法：

• Overflow stack

  我们会有另外一个stack，叫overflow stack。如果mark steack 满了，object会被塞入overflow stack，并且暂时不去遍历它的孩子节点。

• Overflow-arena

  对于overflow stack 都overflow的情况，使用一个链表保存溢出的对象。

优点和缺点

优点：可以处理循环引用，而且对平时的处理没有额外的开销（相对引用计数而言）

缺点：1 stw

2 需要遍历整个内存

对这两个缺点，Mark-sweep算法也有很多优化的版本，如JVM的 CMS。

Generational Garbage Collection

分代垃圾收集的思想是基于基本的垃圾回收算法之上的.

上面提到的一个mark-sweep的一个重要缺点就是会导致系统暂停。用于解决该问题的主要优化方法之一是采用分代垃圾收集。分代垃圾收集基于以下几个特点:

• 大部分对象在很年轻的时候就死了
• GC中回收的对象有90%是在上次GC之后创建的
• 如果一个对象在一次GC中存活, 它在短期内变成垃圾的概率很低

一种常见的方法是将新创建的对象视为在第0代（Gen0）中，然后如果它没有被垃圾收集循环收集，则将其提升到下一个更高代的Gen1. 更频繁地收集较低代. 这可确保降低系统暂停时间. 触发较高代的集合的次数较少. 使用了多少代，因系统而异. 在.NET中使用了3代。为简单起见，我们将考虑使用2代系统，但概念很容易扩展到2代以上.

高代到低代的引用

分代垃圾回收器(Generational garbage collectors)需要跟踪 老年代->年轻代的引用, 以便在对年轻代回收时, 不用去遍历老年代的所有对象.

为什么只用考虑老年代中指向了年轻代的引用?

因为年轻代的内存次数远大于老年代, 且老年代的内存空间一般会更大.并且经过统计信息显示，老年代持有新生代对象引用的情况不足1%.其实在对老年代GC的时候,也是需要考虑年轻代中的对老年代中对象的引用.

Write Barrier定义

如果store操作把一个老年代的引用指向了一个新的object(一般在年轻代中),系统必须保证这个位置被记录到remember set中, 这种机制,通常被叫做 write barrier 或者 store check

在非函数式语言中, store操作是很频繁的,所以一个高效的write barrier实现是很必要的.

card marking 是write barrier的一种实现.

card marking实现

堆被划分为固定大小的card,每个card都关联到一个bit vector中的一个bit. store操作如果改变了这个card中内容,对应的bit会被设置.在垃圾收集时，收集器扫描bit vector，每当找到标记位时，检查对应的堆中相应card中的所有指针。

HotSpot中的Write barrier

• dirty card

  card marking方式

• SATB

  snapshot-at-the-beginning, 被G1收集器采用.

###write barrier + card-table

首先创建一个称为卡表(card-table)的表。这本质上是一个位数组。每个位指示给定范围的内存是否脏（包含对较低生成对象的写入）。例如。我们可以使用单个位来标记4KB块。

第一次标记仅针对Gen0对象。一旦结束，它会检查卡表以找到Gen1中的脏块。然后，它将该脏块中的每个对象视为新根，并使用它标记对象。

##参考链接