本文用于学习安卓垃圾回收所写，关于其中java垃圾回收的基础知识，可以翻看博主前三篇关于java虚拟机的文章。本文将与下篇文章一起探讨Dalvik和ART的垃圾回收。
一、引子
在Android 2.3 之前，Dalvik虚拟使用的垃圾收集机制有以下特点：
- Stop-the-world，也就是垃圾收集线程在执行的时候，其它的线程都停止；
- Full heap collection，也就是一次收集完全部的垃圾；
- 一次垃圾收集造成的程序中止时间通常都大于100ms。
这也是为什么安卓历史名声不好，给人很”卡“的印象的原因之一。
在Android 2.3 之后，Dalvik虚拟使用的垃圾收集机制得到了改进，如下所示：
- Cocurrent，也就是大多数情况下，垃圾收集线程与其它线程是并发执行的；
- Partial collection，也就是一次可能只收集一部分垃圾；
- 一次垃圾收集造成的程序中止时间通常都小于5ms。
二、 Dalvik的堆结构
在正式进入GC阶段之前，我们需要先熟悉以下Dalvik的堆结构，只有先明白Dalvik是如何组织内存的，才能更好的学习Dalvik的GC。
Dalvik虚拟机用来分配对象的堆划分为两部分，一部分叫做Active Heap，另一部分叫做Zygote Heap。Android系统的第一个Dalvik虚拟机是由Zygote进程创建的，应用程序进程是由Zygote进程fork出来的。也就是说，应用程序进程使用了一种写时拷贝技术（COW）来复制了Zygote进程的地址空间。这意味着一开始的时候，应用程序进程和Zygote进程共享了同一个用来分配对象的堆。然而，当Zygote进程或者应用程序进程对该堆进行写操作时，内核就会执行真正的拷贝操作，使得Zygote进程和应用程序进程分别拥有自己的一份拷贝。
拷贝是一件费时费力的事情。因此，为了尽量地避免拷贝，Dalvik虚拟机将自己的堆划分为两部分。事实上，Dalvik虚拟机的堆最初是只有一个的。也就是Zygote进程在启动过程中创建Dalvik虚拟机的时候，只有一个堆。但是当Zygote进程在fork第一个应用程序进程之前，会将已经使用了的那部分堆内存划分为一部分，还没有使用的堆内存划分为另外一部分。前者就称为Zygote堆，后者就称为Active堆。以后无论是Zygote进程，还是应用程序进程，当它们需要分配对象的时候，都在Active堆上进行。这样就可以使得Zygote堆尽可能少地被执行写操作，因而就可以减少执行写时拷贝的操作。在Zygote堆里面分配的对象其实主要就是Zygote进程在启动过程中预加载的类、资源和对象了。这意味着这些预加载的类、资源和对象可以在Zygote进程和应用程序进程中做到长期共享。这样既能减少拷贝操作，还能减少对内存的需求。
此外，Dalvik中针对GC，还设计了两个Bitmap和一个Card Table，还有一个为了方便遍历内存设计的栈，整体结构如图：
图源水印，也推荐大家去学习老罗的文章。
三、Dalvik的垃圾收集
在Dalvik时代，由于内存较小，每次APP应用程序需要分配内存时，如果堆空间不能提供一个足够大的空间时就会启动Dalvik的垃圾收集器。GC收集器会遍历整个堆地址空间，然后查看每个app分配的对象，并进行相应的标记，然后进行回收过程。
Dalvik垃圾收集主要是mark sweep算法实现的。mark-sweep算法分为两个阶段，即mark阶段和sweep阶段。Dalvik的GC过程，可以大致归纳为如下过程：
- 整个标记开始之前，首先遍历一次堆地址空间。
- Mark阶段： 从对象的根集对象开始标记引用对象。
- Sweep阶段： 回收没有被标记的对象占用的内存。
3.1 Mark阶段
3.1.1 标记需要的数据结构
Mark阶段就是从根集对象开始标记被引用的对象，在完成了mark标记后，就进入sweep阶段，即回收那些没有被标记的对象占用的内存。这里涉及到的一个核心概念就是我们怎么标记对象有没有被引用的，换句说就是通过什么数据结构来描述对象有没有被引用。是的，就是之前提到的两个Heap Bitmap了。Heap Bitmap的结构如图所示：
事实上，总共使用了两个bitmap，一个是Live bitmap，一个是Mark bitmap。这个bitmap里的每一位对应一个对象，某个对象被引用了，就标1，没引用就标0。Livebitmap主要用来标记上一次GC时被引用的对象，也就是那些没有被回收的对象，而markbitmap主要用来标记当前GC有被引用的对象。因此在判断需要回收哪些对象时，就是那些在Live bitmap中标为1，而在mark bitmap中标为0的对象。
3.1.2 Concurrent GC
在Mark阶段，要求除了垃圾收集线程之外，其它的线程都停止，否则的话，就会可能导致不能正确地标记每一个对象。这种现象在垃圾收集算法中称为Stop The World，会导致程序中止执行，造成停顿的现象。为了尽可能地减少停顿，我们必须要允许在Mark阶段有条件地允许程序的其它线程执行。这种垃圾收集算法称为并行垃圾收集算法（Concurrent GC）。
在整个mark开始时，GC会先不得不中止一次程序的运行，从而对堆地址空间进行一次遍历，这次遍历可以获得每一个应用程序分配的对象，就能确认每个对象在内存堆中的大小、起始地址等等信息。这个停顿在Dalvik里是不得不做的事情，每次GC都会必须触发一次堆地址空间的遍历引起的停顿。
接下来就是真正的标记阶段了。实现时，GC将mark阶段又分为了两个子阶段：
- 一个是标记根集对象
- 一个是标记根集对象引用的对象
关于根集（Roots set）请阅读前几篇文章。
在mark的第一个阶段，标记根集对象的阶段是不允许GC线程之外的线程运行的，但是mark的第二个阶段允许其他线程运行。这样就可能带来一个问题是，在第二个阶段执行的过程中，如果某个运行的线程修改了一个对象了内容，由于很有可能引用了新的对象，所以这个对象也必须要记录起来。否则会发生被引用对象还在使用却被回收。这种情况出现在只进行部分GC的情况，这时候Card Table的作用就是用来记录非GC堆对象对GC的堆对象的引用。
Dalvik的堆空间，分为zygote heap 和 active heap。 前者主要存放一些在zygote时就分配的对象，后者主要用于之后新分配的空间，Dalvik虚拟机进行部分垃圾收集时，实际上就是只收集在Active heap上分配的对象。Card Table就是用来记录在Zygote heap上分配的对象在GC执行过程中对在Active heap上分配的对象的引用。
Card table由一系列card组成，一个card实际上就是一个字节，它的值分为clean和dirty两种。如果一个Card的值是CLEAN，就表示与它对应的对象在Mark第二个子阶段没有被程序修改过。如果一个Card的值是DIRTY，就意味着被程序修改过，对于这些被修改过的对象。需要在Mark第二子阶段结束之后，再次禁止GC线程之外的其它线程执行，以便GC线程再次根据Card Table记录的信息对被修改过的对象引用的其它对象进行重新标记。由于Mark第二子阶段执行的时间不会太长，因此在这个阶段被修改的对象不会很多，这样就可以保证第二次子阶段结束后，再次执行标记对象的过程是很快的，因而此时对程序造成的停顿非常小。
在mark阶段，主要是标记的第二个子阶段，Dalvik是采用递归的方式来遍历标记对象。但是这个递归并不是像一般的递归一样借助一个递归函数来实现，而是使用一个叫做mark stack的栈空间实现。大致过程是：一个被引用的对象在标记的过程中，先被标记，然后放在栈中，等该对象的父对象全部被标记完成后，依次弹出栈中的每一个对象，并标记其引用，然后把其引用再丢到栈中。大致相当于层次遍历的过程。
这里可能会有一个疑问，一般在递归时都采用的函数递归的方法，但是为什么这里要采用mark stack呢？
采用mark stack栈而不是函数递归的好处是：
- 首先可以采用并行的方式来做，将栈进行分段，多个线程共同将栈中的数据递归标记。
- 其次，可以避免函数堆栈占用较深。
3.2 Sweep阶段
在mark阶段已经提到过，GC时回收的是在live bitmap里标为1而在mark bitmap里标为0的对象。而这个mark bitmap实际上就是live bitmap的子集，因此在sweep阶段只需要处理二者的差集即可，在回收掉相应的对象后，只需要再把live bitmap和mark bitmap的指针调换一下，即这次的mark bitmap作为下一次GC时的live bitmap，然后清空live bitmap。
其过程和ART的没什么太大变化，而由于在android 5.0源码中已经去掉了Dalvik，这环节的具体解释就在ART部分分析，但是实际上在sweep阶段Dalvik和ART二者没有太大区别，因为主要只是处理相应的bitmap的对应的对象的内存，ART也没有什么优化的地方。
四、小结
本文学习了Dalvik的GC理论、算法和数据结构，并没有设计具体源代码，这部分将放到之后的时间补充学习。。。又挖坑了
参考：
Android GC 从Dalvik到ART的改进分析 | cruise yang (cruise1008.github.io)
老罗博客
