该算法又被称为“标记-清除”算法，依赖于对所有存活对象进行一次全局遍历来确定哪些对象可以回收，遍历的过程从根出发，找到所有可到达对象，其他不可到达的对象就是垃圾对象，可被回收。正如其名称所暗示的那样，这个算法分为两大阶段：Mark和Sweep。这种分步执行的思路构成了现代垃圾收集算法的思想基础。与引用计数算法不同的是，Mark-Sweep算法不需要监测每一次内存分配和指针操作，只需要在标记阶段进行一次统计就可以了。Mark-Sweep算法可以非常自然地处理环形问题，另外在创建对象和销毁对象时少了操作引用计数值的开销。不过该算法也有一个缺点，就是需要在标记和清除阶段中把所有对象停止执行。在垃圾回收器运行过程中，应用程序必须暂时停止，并等到垃圾回收器全部运行完成后，才能重新启动应用程序运行。

Dalvik虚拟机最常用的算法便是Mark Sweep算法，该算法一般分Mark阶段（标记出活动对象），Sweep阶段（回收垃圾内存）和可选的Compact阶段（减少堆中的碎片）。Dalvik虚拟机的实现不进行可选的Compact阶段。

（1）Mark阶段

垃圾收集的第一步是标记出活动对象，因为没有办法识别那些不可访问的对象（Unreachableobjects），因此只能标记出活动对象，这样所有未被标记的对象就是可以回收的垃圾。

当进行垃圾收集时，需要停止Dalvik虚拟机的运行（当然，除了垃圾收集之外）。因此垃圾收集又被称作STW（Stop The World）。Dalvik虚拟机在运行过程中要维护一些状态信息，这些信息包括：每个线程所保存的寄存器，Java类中的静态字段，局部和全局的JNI引用，JVM中的所有函数调用会对应一个相应的C语言的栈帧。每一个栈帧里可能包含对对象的引用，比如包含对象引用的局部变量和参数。

所有这些引用信息被加入到一个集合中，叫作根集合。然后从根集合开始，递归地查找可以从根集合出发访问的对象。因此，Mark过程又被称为追踪，追踪所有可被访问的对象。如图7-1所示，假定从根集合{a}开始，可以访问的对象集合为{a，b，c，d}，这样就追踪出所有可被访问的对象集合。

(www.daowen.com)

图7-1 Mark过程

垃圾收集使用栈来保存根集合，然后对栈中的每一个元素，递归追踪所有可访问的对象，对于所有可访问的对象，在markBits位图中将该对象的内存起始地址对应的位设为1。这样当栈为空时，markBits位图就是所有可访问的对象集合。

（2）Sweep阶段

垃圾收集的第二步就是回收内存，在Mark阶段通过markBits位图可以得到所有可访问的对象集合，而liveBits位图表示所有已经分配的对象集合。因此通过比较这两个位图，liveBits位图和markBits位图的差异就是所有可回收的对象集合。Sweep阶段调用free函数来释放这些内存给堆。

（3）Concurrent Mark（并发标记）

为了运行垃圾收集，需要停止虚拟机的运行，这可能会导致程序较长时间的停顿。垃圾收集的主要工作位于Mark阶段，Dalvik虚拟机使用了Concurrent Mark技术以缩短停顿时间。在Concurrent Mark中引入一个单独的gc线程，由该线程去跟踪自己的根集合中所有可访问的对象，同时所有其他的线程也在运行。这也是Concurrent一词的含义。但是为了回收内存，即运行Sweep阶段，必须停止虚拟机的运行。这会导入一个问题，即在gc线程标记对象的时候，其他线程的运行又引入了新的访问对象。因此在Sweep阶段，又重新运行Mark阶段，但是在这个阶段对于已经标记的对象来说，可以不用继续递归追踪了，这样从一定程度上降低了程序的停顿时间。