垃圾回收器之标记擦除法

         这一次我们来简单的了解一下标记擦除法(mark-and-sweep)，标记擦除法是第一个被广泛使用的，并且可以解决循环引用问题的垃圾回收算法；

         使用标记擦除法的时候，垃圾对象并不能立即被回收，相反垃圾的回收是等到内存不够使用的时候才触发；这个时候程序的执行流程将被暂时的休眠，一旦所有的垃圾回收后，才会唤醒正常的程序执行流程。

         标记擦除法又被称为跟踪垃圾的回收器算法，因为它跟踪所有可以直接或者间接被程序访问的对象集合；这些可以被程序直接访问的对象，有局部变量和静态变量。在回收器中，这些变量被称为根对象。一个被其他对象字段引用的对象称为可被间接访问的对象。所以可以正常访问的对象，我们称为存活对象，否则就是垃圾。

         标记擦除算法包括两个阶段,在第一个节点它首先找到所有的可访问对象并进行标记，这个阶段被叫做标记阶段；第二个阶段就是扫描堆栈上的所有未标记的对象，并进行回收内存操作，这个阶段被叫做擦除节点。

         为了区别垃圾对象和正常对象，我们需要记录每个对象的状态；所以我们可以给每个对象添加一个布尔类型的字段marked。默认情况下，所有对象刚被创建的时候都是没有被标记的，因此字段marked的初始值为false；

         标记给定的对象p以及所有可以通过p间接访问的对象，我们可以通过类似以下Mark的方法实现：

         Void Mark（object p）

         {

                   If(!p.marked)

                   {

                            p.marked = true;                       

For each object q referenced by p

Mark(q);

}

}

         我们可以注意到，在这个标记的阶段，当我们遇到已经被标记的对象什么都没有做。因此，可以保证算法可以正常结束，并且只有标记了所有可访问对象后才结束。

         在第二个阶段，本算法会扫描所有的堆上的对象，来定位所有的未标记对象。在扫描的过程中，这些未标记的对象所占的内存被回收，同时每一个正常的对象的marked字段被重置为false，以便为下一次的回收做准备。

void Sweep()

{

         for each object p in the heap

                   if (p.marked)

                            p.marked = false

                   else

                            heap.Release(p);

}

整个算法的实现过程可以使用下图表示

回收算法开始之前的状态

经过标记阶段后的状态，所有可访问对象都已经被标记

经过擦除阶段后的状态，仅仅剩下正常的活动对象，并且将其marked字段重置为false

因为标记擦除法通过根对象跟踪所有的可访问对象，所以即使在循环引用的情况下也能正确的识别和回收垃圾对象。这个是其相对计数法的最大优势。

然而其劣势就是执行算法的时候，需要休眠中断程序的正常执行流程，特别是需要人机交互、需要满足苛刻的实时执行要求的系统。

另外一个问题就是内存碎片问题。其往往发生在已经运行过数次垃圾回收器的长时间运行的系统中。其具体的体现就是正常的对象被很多没有使用的小内存碎片隔离，其可能会导致可用内存满足所申请的内存，但是由于这些内存并不连续，导致不能正常分配内存的问题。