扣丁书屋

Dalvik虚拟机垃圾收集机制简要介绍和学习计划

伴随着"Dalvik is dead,long live Dalvik"这行AOSP代码提交日志,在Android5.0中,ART运行时取代了Dalvik虚拟机。虽然Dalvik虚拟机不再使用,但是它曾经的作用是不可磨灭的。因此,在研究ART运行时的垃圾收集机制之前,先理解Dalvik虚拟机的垃圾收集机制也是很重要和有帮助的。因此,本文就对Dalvik虚拟机的垃圾收集机进行简要介绍和制定学习计划。

之所以说理解Dalvik虚拟机的垃圾收集机制对学习ART运行时的垃圾收集机制有帮助,是因为两者都使用到了一些共同或者相通的技术,并且前者的实现相对简单一些。这样我们就可以从简单的学起。等到有了一定的基础之后,再学习复杂的就会容易理解很多。

好了,废话不多说,我们开始介绍Dalvik虚拟机的垃圾收集机制涉及到的基本概念或者说术语,如图1所示:

图1 Dalvik虚拟机垃圾收集机制的基本概念

Dalvik虚拟机用来分配对象的堆划分为两部分,一部分叫做Active Heap,另一部分叫做Zygote Heap。从前面Dalvik虚拟机的启动过程分析这篇文章可以知道,Android系统的第一个Dalvik虚拟机是由Zygote进程创建的。再结合Android应用程序进程启动过程的源代码分析这篇文章,我们可以知道,应用程序进程是由Zygote进程fork出来的。也就是说,应用程序进程使用了一种写时拷贝技术(COW)来复制了Zygote进程的地址空间。这意味着一开始的时候,应用程序进程和Zygote进程共享了同一个用来分配对象的堆。然而,当Zygote进程或者应用程序进程对该堆进行写操作时,内核就会执行真正的拷贝操作,使得Zygote进程和应用程序进程分别拥有自己的一份拷贝。

拷贝是一件费时费力的事情。因此,为了尽量地避免拷贝,Dalvik虚拟机将自己的堆划分为两部分。事实上,Dalvik虚拟机的堆最初是只有一个的。也就是Zygote进程在启动过程中创建Dalvik虚拟机的时候,只有一个堆。但是当Zygote进程在fork第一个应用程序进程之前,会将已经使用了的那部分堆内存划分为一部分,还没有使用的堆内存划分为另外一部分。前者就称为Zygote堆,后者就称为Active堆。以后无论是Zygote进程,还是应用程序进程,当它们需要分配对象的时候,都在Active堆上进行。这样就可以使得Zygote堆尽可能少地被执行写操作,因而就可以减少执行写时拷贝的操作。在Zygote堆里面分配的对象其实主要就是Zygote进程在启动过程中预加载的类、资源和对象了。这意味着这些预加载的类、资源和对象可以在Zygote进程和应用程序进程中做到长期共享。这样既能减少拷贝操作,还能减少对内存的需求。

明白了Dalvik虚拟机为什么要把用来分配对象的堆划分为Active堆和Zygote堆之后,我们再看到底堆是个什么东西,请看图2:

图2 Dalvik虚拟机的堆

在Dalvik虚拟机中,堆实际上就是一块匿名共享内存。关于Android系统的匿名共享内存,可以参考Android系统匿名共享内存Ashmem(Anonymous Shared Memory)简要介绍和学习计划这个系列的文章。Dalvik虚拟机并不是直接管理这块匿名共享内存,而是将它封装成一个mspace,交给C库来管理。mspace是libc中的概念,我们可以通过libc提供的函数create_mspace_with_base创建一个mspace,然后再通过mspace_开头的函数管理该mspace。例如,我们可以通过mspace_malloc和mspace_bulk_free来在指定的mspace中分配和释放内存。实际上,我们在使用libc提供的函数malloc和free分配和释放内存时,也是在一个mspace进行的,只不过这个mspace是由libc默认创建的。

Dalvik虚拟机除了要给应用层分配对象之外,最重要的还是要对这些已经分配出去的对象进行管理,也就是要在对象不再被使用的时候,对其进行自动回收。没吃过猪肉,也见过猪跑,自动回收对象(也就是垃圾收集)的算法不用多说,就是耳熟能详的Mark-Sweep算法。

顾名思义,Mark-Sweep垃圾收集算法主要分为两个阶段:Mark和Sweep。Mark阶段从对象的根集开始标记被引用的对象。标记完成后,就进入到Sweep阶段,而Sweep阶段所做的事情就是回收没有被标记的对象占用的内存。这里涉及到的一个核心概念就是我们怎么标记对象有没有被引用的,换句说就是通过什么数据结构来描述对象有没有被引用。是的,就是图1中的Heap Bitmap了。Heap Bitmap的结构如图3所示:

图3 Heap Bitmap

从名字就可以推断出,Heap Bitmap使用位图来标记对象是否被使用。如果一个对象被引用,那么在Bitmap中与它对应的那一位就会被设置为1。否则的话,就设置为0。在Dalvik虚拟机中,使用一个unsigned long数组来描述一个Heap Bitmap。我们假设堆的大小为Max Heap Size。我们使用libc提供的函数mspace_malloc来从堆里面分配内存时,得到的内存的地址总是对齐到HB_OBJECT_ALIGNMENT的。HB_OBJECT_ALIGNMENT的值等于8,也就是说,我们分配的对象的地址的最低三位总是0。这意味着我们在考虑Bitmap中的位与对象的对应关系时,可以不考虑这最低三位的值。这样可以大大地减少Bitmap的大小。例如,在32位设备上,每一个对象的地址都有32位,除去最低的三位,我们在考虑Bitmap与对象的对应关系时,只需要考虑高29位就可以了。因此,在计算所需要的Bitmap的大小时,就可以将堆的大小值除以HB_OBJECT_ALIGNMENT,即除以8。

假设一个unsigned long数占HB_BITS_PER_WORD个位,那么,我们就需要一个大小为(Max Heap Size / HB_OBJECT_ALIGNMENT / HB_BITS_PER_WORD)的unsigned long数组来描述一个大小为Max Heap Size的堆。在32位设备上,一个unsigned long数占用32位,即HB_BITS_PER_WORD的值等于32。综合上面的描述,我们就可以知道,一个大小为Max Heap Size的堆需要一个大小为(Max Heap Size / 8 / 32)的unsigned long数组来描述,即需要一块字节数等于(Max Heap Size / 8 / 32)× 4的内存来描述。

在图1中,我们使用了两个Bitmap来描述堆的对象,一个称为Live Bitmap,另一个称为Mark Bitmap。Live Bitmap用来标记上一次GC时被引用的对象,也就是没有被回收的对象,而Mark Bitmap用来标记当前GC有被引用的对象。有了这两个信息之后,我们就可以很容易地知道哪些对象是需要被回收的,即在Live Bitmap在标记为1,但是在Mark Bitmap中标记为0的对象。

在垃圾收集的Mark阶段,要求除了垃圾收集线程之外,其它的线程都停止,否则的话,就会可能导致不能正确地标记每一个对象。这种现象在垃圾收集算法中称为Stop The World,会导致程序中止执行,造成停顿的现象。为了尽可能地减少停顿,我们必须要允许在Mark阶段有条件地允许程序的其它线程执行。这种垃圾收集算法称为并行垃圾收集算法(Concurrent GC)。

为了实现Concurrent GC,Mark阶段又划分两个子阶段。第一个子阶段只负责标记根集对象。所谓的根集对象,就是指在GC开始的瞬间,被全局变量、栈变量和寄存器等引用的对象。有了这些根集变量之后,我们就可以顺着它们找到其余的被引用变量。例如,一个栈变量引了一个对象,而这个对象又通过成员变量引用了另外一个对象,那该被引用的对象也会同时标记为正在使用。这个标记被根集对象引用的对象的过程就是第二个子阶段。在Concurrent GC,第一个子阶段是不允许垃圾收集线程之外的线程运行的,但是第二个子阶段是允许的。不过,在第二个子阶段执行的过程中,如果一个线程修改了一个对象,那么该对象必须要记录起来,因为它很有可能引用了新的对象,或者引用了之前未引用过的对象。如果不这样做的话,那么就会导致被引用对象还在使用然而却被回收。这种情况出现在只进行部分垃圾收集的情况,这时候Card Table的作用就是用来记录非垃圾收集堆对象对垃圾收集堆对象的引用。Dalvik虚拟机进行部分垃圾收集时,实际上就是只收集在Active堆上分配的对象。因此对Dalvik虚拟机来说,Card Table就是用来记录在Zygote堆上分配的对象在部收垃圾收集执行过程中对在Active堆上分配的对象的引用。

我们是不是想到再用一个Bitmap在描述上述第二个子阶段被修改的对象呢?虽然我们尽大努力减少了用来标记对象的Bitmap的大小,不过还是比较可观的。因此,为了减少内存的消耗,我们使用另外一种技术来标记Mark第二子阶段被修改的对象。这种技术使用到了一种称为Card Table的数据结构,如图4所示:

图4 Card Table

从名字可以看出,Card Table由Card组成,一个Card实际上就是一个字节,它的值要么是CLEAN,要么是DIRTY。如果一个Card的值是CLEAN,就表示与它对应的对象在Mark第二子阶段没有被程序修改过。否则的话,就意味着被程序修改过,对于这些被修改过的对象。需要在Mark第二子阶段结束之后,再次禁止垃圾收集线程之外的其它线程执行,以便垃圾收集线程再次根据Card Table记录的信息对被修改过的对象引用的其它对象进行重新标记。由于Mark第二子阶段执行的时间不会太长,因此在该阶段被修改的对象不会很多,这样就可以保证第二次子阶段结束后,再次执行标记对象的过程是很快的,因而此时对程序造成的停顿非常小。

在Card Table中,在连续GC_CARD_SIZE地址中的对象共用一个Card。Dalvik虚拟机将GC_CARD_SIZE的值设置为128。因此,假设堆的大小为Max Heap Size,那么我们只需要一块字节数为(Max Heap Size / 128)的Card Table。相比大小为(Max Heap Size / 8 / 32)× 4的Bitmap,减少了一半的内存需求。

在Mark阶段,Dalvik虚拟机能过递归方式来标记对象。但是,这不是通过函数的递归调用来实现的,而是借助一个称为Mark Stack的栈来实现的。具体来说,当我们标记完成根集对象之后,就按照它们的地址从小到大的顺序标记它们所引用的其它对象。假设有A、B、C和D四个对象,它的地址大小关系为A < B < C < D,其中,B和D是根集对象,A被D引用,C没有被B和D引用。那么我们将依次遍历B和D。当遍历到B的时候,没有发现它引用其它对象,然后就继续向前遍历D对象。发现它引用了A对象。按照递归的算法,这时候除了标记A对象是正在使用之外,还应该去检查A对象有没有引用其它对象,然后又再检查它引用的对象有没有又引用其它的对象,一直这样遍历下去。这样就跟函数递归一样。更好的做法是将对象A记录在一个Mark Stack中,然后继续检查地址值比对象D大的其它对象。对于地址值比对象D大的其它对象,如果它们引用了一个地址值比它们小的其它对象,那么这些其它对象同样要记录在Mark Stack中。等到该轮检查结束之后,再回过头来检查记录在Mark Stack里面的对象。然后又重复上述过程,直到Mark Stack等于空为止。

这就是我们在图1中显示的Mark Stack的作用,它的具体结构如图5所示:

图5 Mark Stack

在Dalvik虚拟机中,每一个对象都是从Object类继承下来的,也就是说,每一个对象占用的内存大小都至少等于sizeof(Object)。此外,我们通过libc提供的函数mspace_malloc为对象分配内存时,libc需要额外的内存来记录被分配出去的内存的信息。例如,需要记录被分配出去的内存的大小。每一块分配出去的内存需要额外的HEAP_SOURCE_CHUNK_OVERHEAD内存来记录上述的管理信息。因此,在Dalvik虚拟机中,每一个对象的大小都至少为sizeof(Object) + HEAP_SOURCE_CHUNK_OVERHEAD。这就意味着对于一个大小为Max Heap Size的堆来说,最多可以分配Max Heap Size / (sizeof(Object) + HEAP_SOURCE_CHUNK_OVERHEAD)个对象。于是,在最坏情况下,我们就需要一个大小为(Max Heap Size / (sizeof(Object) + HEAP_SOURCE_CHUNK_OVERHEAD))的Object*数组来描述Mark Stack,以便可以实现上述的非递归函数调用的递归标记算法。

至此,我们就对Dalvik虚拟机的垃圾收集机制中涉及到的基础概念分析完成了。没有结合代码来分析,可能这些概念一时还难以理解通透。不过不要紧,接下来我们将按照以下三个情景来结合源码深入分析上述的概念:

1. Dalvik虚拟机堆的创建过程

2. Dalvik虚拟机的对象分配过程

3. Dalvik虚拟机的垃圾收集过程

按照这三个情景学习Davlik虚拟机的垃圾收集机制之后,我们就会对上面涉及的概念有一个清晰的认识了,同时也会我们后面学习ART运行时的垃圾收集机集打下坚实的基础。敬请关注!想了解更多信息,也可以关注老罗的新浪微博:http://weibo.com/shengyangluo

ART运行时Compacting GC堆创建过程分析

发布于:2年以前  |  3155次阅读  |  详细内容 »

Android系统进程间通信Binder机制在应用程序框架层的Java接口源代码分析

在前面几篇文章中,我们详细介绍了Android系统进程间通信机制Binder的原理,并且深入分析了系统提供的Binder运行库和驱动程序的源代码。细心的读者会发现,这几篇文章分析...

发布于:2年以前  |  1972次阅读  |  详细内容 »

Android应用程序窗口(Activity)的运行上下文环境(Context)的创建过程分析

在前文中,我们简要介绍了Android应用程序窗口的框架。Android应用程序窗口在运行的过程中,需要访问一些特定的资源或者类。这些特定的资源或者类构成了Android应用程序的...

发布于:2年以前  |  1685次阅读  |  详细内容 »

解开Android应用程序组件Activity的"singleTask"之谜

在Android应用程序中,可以配置Activity以四种方式来启动,其中最令人迷惑的就是&quot;singleTask&quot;这种方式了,官方文档称以这种方式启动的Activity总是属于一个任务的根Activit...

发布于:2年以前  |  1366次阅读  |  详细内容 »

ART运行时Mark-Compact( MC)GC执行过程分析

除了Semi-Space(SS)GC和Generational Semi-Space(GSS)GC,ART运行时还引入了第三种Compacting GC:Mark-Compact(MC)GC。这三种GC虽然都是Compacting GC,不过它们的...

发布于:2年以前  |  2413次阅读  |  详细内容 »

Android系统匿名共享内存Ashmem(Anonymous Shared Memory)在进程间共享的原理分析

在前面一篇文章Android系统匿名共享内存Ashmem(Anonymous Shared Memory)驱动程序源代码分析中,我们系统地介绍了Android系统匿名共享内存的实现原理,其中着重介绍了它...

发布于:2年以前  |  2549次阅读  |  详细内容 »

Android窗口管理服务WindowManagerService的简要介绍和学习计划

在前一个系列文章中,我们从个体的角度来分析了Android应用程序窗口的实现框架。事实上,如果我们从整体的角度来看,Android应用程序窗口的实现要更复杂,因为它们的类型和...

发布于:2年以前  |  3665次阅读  |  详细内容 »

Android应用程序组件Content Provider的共享数据更新通知机制分析

在Android系统中,应用程序组件Content Provider为不同的应用程序实现数据共享提供了基础设施,它主要通过Binder进程间通信机制和匿名共享内存机制来实现的。关于数据共享...

发布于:2年以前  |  2994次阅读  |  详细内容 »

Dalvik虚拟机为新创建对象分配内存的过程分析

在前面一文中,我们分析了Dalvik虚拟机创建Java堆的过程。有了Java堆之后,Dalvik虚拟机就可以在上面为对象分配内存了。在Java堆为对象分配内存需要解决内存碎片和内存不足...

发布于:2年以前  |  1611次阅读  |  详细内容 »

Dalvik虚拟机JNI方法的注册过程分析

在前面一文中,我们分析了Dalvik虚拟机的运行过程。从中可以知道,Dalvik虚拟机在调用一个成员函数的时候,如果发现该成员函数是一个JNI方法,那么就会直接跳到它的地址去...

发布于:2年以前  |  3268次阅读  |  详细内容 »

Android日志系统Logcat源代码简要分析

在前面两篇文章Android日志系统驱动程序Logger源代码分析和Android应用程序框架层和系统运行库层日志系统源代码中,介绍了Android内核空间层、系统运行库层和应用程序框架...

发布于:2年以前  |  2230次阅读  |  详细内容 »

Dalvik虚拟机Java堆创建过程分析

发布于:2年以前  |  3036次阅读  |  详细内容 »

ART运行时Java堆创建过程分析

发布于:2年以前  |  3020次阅读  |  详细内容 »

Android应用程序注册广播接收器(registerReceiver)的过程分析

前面我们介绍了Android系统的广播机制,从本质来说,它是一种消息订阅/发布机制,因此,使用这种消息驱动模型的第一步便是订阅消息;而对Android应用程序来说,订阅消息其...

发布于:2年以前  |  2287次阅读  |  详细内容 »

Android应用程序启动过程源代码分析

前文简要介绍了Android应用程序的Activity的启动过程。在Android系统中,应用程序是由Activity组成的,因此,应用程序的启动过程实际上就是应用程序中的默认Activity的启动...

发布于:2年以前  |  3830次阅读  |  详细内容 »

Android源代码仓库及其管理工具Repo分析

发布于:2年以前  |  2088次阅读  |  详细内容 »

最多阅读

Android包管理框架:APK的打包流程 2年以前  |  4481次阅读
Android应用程序启动过程源代码分析 2年以前  |  3830次阅读
Android包管理框架:APK的安装流程 2年以前  |  3675次阅读
Android应用程序安装过程源代码分析 2年以前  |  3658次阅读
Dalvik虚拟机垃圾收集(GC)过程分析 2年以前  |  3506次阅读
Android应用优化:启动优化 2年以前  |  3319次阅读
Dalvik虚拟机JNI方法的注册过程分析 2年以前  |  3268次阅读

手机扫码阅读