一般来说，程序使用内存的方式遵循先向操作系统申请一块内存，使用内存，使用完毕之后释放内存归还给操作系统。然而在传统的C/C++等要求显式释放内存的编程语言中，记得在合适的时候释放内存是一个很有难度的工作，因此Java等编程语言都提供了基于垃圾回收算法的内存管理机制：
常见的垃圾回收算法有引用计数法（Reference Counting）、标注并清理（Mark and Sweep GC）、拷贝（Copying GC）和逐代回收（Generational GC）等算法，其中Android系统采用的是标注并删除和拷贝GC，并不是大多数JVM实现里采用的逐代回收算法。由于几个算法各有优缺点，所以在很多垃圾回收实现中，常常可以看到将几种算法合并使用的场景，本节将一一讲解这几个算法。
引用计数法的原理很简单，即记录每个对象被引用的次数。每当创建一个新的对象，或者将其它指针指向该对象时，引用计数都会累加一次；而每当将指向对象的指针移除时，引用计数都会递减一次，当引用次数降为0时，删除对象并回收内存。采用这种算法的较出名的框架有微软的COM框架，如代码清单14 - 1演示了一个对象引用计数的增减方式。
代码清单14 - 1 引用计数增减方式演示伪码
| Object *obj1 = new Object(); // obj1的引用计数为1 Object *obj2 = obj1; // obj1的引用技术为2 Object *obj3 = new Object();
obj2 = NULL; // obj1的引用计数递减1次为1。 obj1 = obj3; // obj1的引用计数递减1次为0，可以回收其内存。 |
通常对象的引用计数都会跟对象放在一起，系统在分配完对象的内存后，返回的对象指针会跳过引用计数部分，如代码清单14 - 1所示：
图 14 - 1 采用引用计数对象的内存布局示例
然而引用计数回收算法有一个很大的弱点，就是无法有效处理循环引用的问题，由于Android系统没有使用该算法，所以这里不做过多的描述，请有兴趣的读者自行查阅相关文档。
在这个算法中，程序在运行的过程中不停的创建新的对象并消耗内存，直到内存用光，这时再要创建新对象时，系统暂停其它组件的运行，触发GC线程启动垃圾回收过程。内存回收的原理很简单，就是从所谓的"GC Roots"集合开始，将内存整个遍历一次，保留所有可以被GC Roots直接或间接引用到的对象，而剩下的对象都当作垃圾对待并回收，如代码清单14 - 3：
代码清单14 - 2 标注并清理算法伪码
| void GC() { SuspendAllThreads();
List<Object> roots = GetRoots(); foreach ( Object root : roots ) { Mark(root); }
Sweep();
ResumeAllThreads(); } |
算法通常分为两个主要的步骤：
代码清单14 - 3 标注并清理的标注阶段伪码
4. pObj->Mark(); 5. // 深度优先遍历对象引用到的所有对象 6. List<Object *> fields = pObj->GetFields(); 7. foreach ( Object* field : fields ) { 8. Make(field); // 递归处理引用到的对象 9. } 10. } 11. } |
如果对象引用的层次过深，递归调用消耗完虚拟机内GC线程的栈空间，从而导致栈空间溢出（StackOverflow）异常，为了避免这种情况的发生，在具体实现时，通常是用一个叫做标注栈（Mark Stack）的数据结构来分解递归调用。一开始，标注栈（Mark Stack）的大小是固定的，但在一些极端情况下，如果标注栈的空间也不够的话，则会分配一个新的标注栈（Mark Stack），并将新老栈用链表连接起来。
与引用计数法中对象的内存布局类似，对象是否被标注的标志也是保存在对象头里的，如图 14 - 2所示。
图 14 - 2 标注和清理算法中的对象布局
如图 14 - 2是垃圾回收前的对象之间的引用关系；GC线程遍历完整个内存堆之后，标识出所以可以被"GC Roots"引用到的对象－即代码清单14 - 2中的第4行，结果如图 14 - 3中高亮的部分，对于所有未被引用到（即未被标注）的对象，都将其作为垃圾收集。
图 14 - 3 回收内存垃圾之前的对象引用关系
图 14 - 4 GC线程标识出所有不能被回收的对象实例
代码清单14 - 4 标注和清理法中的清理过程伪码
9. pIter = MoveNext(pIter); 10. } 11. } |
图 14 - 5 GC线程执行完垃圾回收过程后的对象图
这个方法的优点是很好地处理了引用计数中的循环引用问题，而且在内存足够的前提下，对程序几乎没有任何额外的性能开支（如不需要维护引用计数的代码等），然而它的一个很大的缺点就是在执行垃圾回收过程中，需要中断进程内其它组件的执行。
这个是前面标注并清理法的一个变种，系统在长时间运行的过程中，反复分配和释放内存很有可能会导致内存堆里的碎片过多，从而影响分配效率，因此有些采用此算法的实现（Android系统中并没有采用这个做法），在清理（SWEEP）过程中，还会执行内存中移动存活的对象，使其排列的更紧凑。在这种算法中，，虚拟机在内存中依次排列和保存对象，可以想象GC组件在内部保存了一个虚拟的指针 – 下个对象分配的起始位置 ，如图 14 - 6中演示的示例应用，其GC内存堆中已经分配有3个对象，因此"下个对象分配的起始位置"指向已分配对象的末尾，新的对象"object 4"（虚线部分）的起始位置将从这里开始。
这个内存分配机制和C/C++的malloc分配机制有很大的区别，在C/C++中分配一块内存时，通常malloc函数需要遍历一个"可用内存空间"链表，采取"first-first"（即返回第一块大于内存分配请求大小的内存块）或"best-fit"（ 即返回大于内存分配请求大小的最小内存块），无论是哪种机制，这个遍历过程相对来说都是一个较为耗时的时间。然而在Java语言中，理论上，为一个对象分配内存的速度甚至可能比C/C++更快一些，这是因为其只需要调整指针"下个对象分配的起始位置"的位置即可，据Sun的工程师估计，这个过程大概只需要执行10个左右的机器指令。
图 14 - 6 在GC中为对象分配内存
由于虚拟机在给对象分配内存时，一直不停地向后递增指针"下个对象分配的起始位置"，潜台词就是将GC堆当做一个无限大的内存对待的，为了满足这个要求，GC线程在收集完垃圾内存之后，还需要压缩内存 – 即移动存活的对象，将它们紧凑的排列在GC内存堆中，如图 14 - 7是Java进程内GC前的内存布局，执行回收过程时，GC线程从进程中所有的Java线程对象、各线程堆栈里的局部变量、所有的静态变量和JNI引用等GC Root开始遍历。
图 14 - 7中，可以被GC Root访问到的对象有A、C、D、E、F、H六个对象，为了避免内存碎片问题，和满足快速分配对象的要求，GC线程移动这六个对象，使内存使用更为紧凑，如图 14 - 7所示。由于GC线程移动了存活下来对象的内存位置，其必须更新其他线程中对这些对象的引用，如图 14 - 7中，由于A引用了E，移动之后，就必须更新这个引用，在更新过程中，必须中断正在使用A的线程，防止其访问到错误的内存位置而导致无法预料的错误。
图 14 - 7 垃圾回收前的GC堆上的对象布局及引用关系
图 14 - 8 GC线程移动存活的对象使内存布局更为紧凑
注意现代操作系统中，针对C/C++的内存分配算法已经做了大量的改进，例如在Windows中，堆管理器提供了一个叫做"Look Aside List"的缓存针对大部分程序都是频繁分配小块内存的情形做的优化，具体技术细节请可以参阅笔者的在线付费技术视频：
这也是标注法的一个变种， GC内存堆实际上分成乒（ping）和乓（pong）两部分。一开始，所有的内存分配请求都有乒（ping）部分满足，其维护"下个对象分配的起始位置"指针，分配内存仅仅就是操作下这个指针而已，当乒（ping）的内存快用完时，采用标注（Mark）算法识别出存活的对象，如图 14 - 9所示，并将它们拷贝到乓（pong）部分，后续的内存分配请求都在乓（pong）部分完成，如图 14 - 10。而乓（pong）里的内存用完后，再切换回乒（ping）部分，使用内存就跟打乒乓球一样。
图 14 - 9 拷贝回收法中的乒乓内存块
图 14 - 10 拷贝回收法中的切换乒乓内存块以满足内存分配请求
回收算法的优点在于内存分配速度快，而且还有可能实现低中断，因为在垃圾回收过程中，从一块内存拷贝存活对象到另一块内存的同时，还可以满足新的内存分配请求，但其缺点是需要有额外的一个内存空间。不过对于回收算法的缺点，也可以通过操作系统地虚拟内存提供的地址空间申请和提交分布操作的方式实现优化，因此在一些JVM实现中，其Eden区域内的垃圾回收采用此算法。
也是标注法的一个变种，标注法最大的问题就是中断的时间过长，此算法是对标注法的优化基于下面几个发现：
可以将逐代回收法看成拷贝GC算法的一个扩展，一开始所有的对象都是分配在"年轻一代对象池" 中 – 在JVM中其被称为Young，如图 14 - 11：
图 14 - 11 逐代（generational） GC中开始对象都是分配在年轻一代对象池（Young generation）中
第一次垃圾回收过后，垃圾回收算法一般采用标注并清理算法，存活的对象会移动到"老一代对象池"中– 在JVM中其被称为Tenured，如图 14 - 12，而后面新创建的对象仍然在"年轻一代对象池"中创建，这样进程不停地重复前面两个步骤。等到"老一代对象池"也快要被填满时，虚拟机此时再在"老一代对象池"中执行垃圾回收过程释放内存。在逐代GC算法中，由于"年轻一代对象池"中的回收过程很快 – 只有很少的对象会存活，而执行时间较长的"老一代对象池"中的垃圾回收过程执行不频繁，实现了很好的平衡，因此大部分虚拟机，如JVM、.NET的CLR都采用这种算法。
图 14 - 12 逐代GC中将存活的对象挪到老一代对象池
在逐代GC中，有一个较棘手的问题需要处理 – 即如何处理老一代对象引用新一代对象的问题，如图 14 - 13中。由于每次GC都是在单独的对象池中执行的，当GC Root之一R3被释放后，在"年轻一代对象池"中执行GC过程时，R3所引用的对象f、g、h、i和j都会被当做垃圾回收掉，这样就导致"老一代对象池"中的对象c有一个无效引用。
图 14 - 13 逐代GC中老一代对象引用新对象的问题
为了避免这种情况，在"年轻一代对象池"中执行GC过程时，也需要将对象C当做GC Root之一。一个名为"Card Table"的数据结构就是专门设计用来处理这种情况的，"Card Table"是一个位数组，每一个位都表示"老一代对象池"内存中一块4KB的区域 – 之所以取4KB，是因为大部分计算机系统中，内存页大小就是4KB。当用户代码执行一个引用赋值（reference assignment）时，虚拟机（通常是JIT组件）不会直接修改内存，而是先将被赋值的内存地址与"老一代对象池"的地址空间做一次比较，如果要修改的内存地址是"老一代对象池"中的地址，虚拟机会修改"Card Table"对应的位为 1，表示其对应的内存页已经修改过 - 不干净（dirty）了，如图 14 - 14。
图 14 - 14 逐代GC中Card Table数据结构示意图
当需要在 "年轻一代对象池"中执行GC时， GC线程先查看"Card Table"中的位，找到不干净的内存页，将该内存页中的所有对象都加入GC Root。虽然初看起来，有点浪费， 但是据统计，通常从老一代的对象引用新一代对象的几率不超过1%，因此"Card Table"的算法是一小部分的时间损失换取空间。
在Android中 ，实现了标注与清理（Mark and Sweep）和拷贝GC，但是具体使用什么算法是在编译期决定的，无法在运行的时候动态更换 – 至少在目前的版本上（4.2）还是这样。在Android的dalvik虚拟机源码的Android.mk文件（路径是/dalvik/vm/Dvm.mk）里，有类似代码清单14 - 5的代码，即如果在编译dalvik虚拟机的命令中指明了"WITH_COPYING_GC"选项，则编译"/dalvik/vm/alloc/Copying.cpp"源码 – 此是Android中拷贝GC算法的实现，否则编译"/dalvik/vm/alloc/HeapSource.cpp" – 其实现了标注与清理GC算法，也就是本节分析的重点。
代码清单14 - 5 编译器指定使用拷贝GC还是标注与清理GC算法
| WITH_COPYING_GC := $(strip $(WITH_COPYING_GC))
ifeq ($(WITH_COPYING_GC),true) LOCAL_CFLAGS += -DWITH_COPYING_GC LOCAL_SRC_FILES += \ alloc/Copying.cpp.arm else LOCAL_SRC_FILES += \ alloc/DlMalloc.cpp \ alloc/HeapSource.cpp \ alloc/MarkSweep.cpp.arm endif |
注意本节中分析的Android源码，可以在网址：http://androidxref.com/source/xref/ 中在线浏览。
在Android源码中，这个过程分为下面几步：
代码清单14 - 6 dvmHeapStartup初始化GC内存堆
| 75 bool dvmHeapStartup() 76 { 77 GcHeap *gcHeap; 78 79 if (gDvm.heapGrowthLimit == 0) { 80 gDvm.heapGrowthLimit = gDvm.heapMaximumSize; 81 } 82 83 gcHeap = dvmHeapSourceStartup(gDvm.heapStartingSize, 84 gDvm.heapMaximumSize, 85 gDvm.heapGrowthLimit); 86 if (gcHeap == NULL) { 87 return false; 88 } 89 gcHeap->ddmHpifWhen = 0; 90 gcHeap->ddmHpsgWhen = 0; 91 gcHeap->ddmHpsgWhat = 0; 92 gcHeap->ddmNhsgWhen = 0; 93 gcHeap->ddmNhsgWhat = 0; 94 gDvm.gcHeap = gcHeap; 95 96 /* Set up the lists we'll use for cleared reference objects. 97 */ 98 gcHeap->clearedReferences = NULL; 99 100 if (!dvmCardTableStartup(gDvm.heapMaximumSize, gDvm.heapGrowthLimit)) { 101 LOGE_HEAP("card table startup failed."); 102 return false; 103 } 104 105 return true; 106 } |
除了创建和初始化用于存储普通Java对象的内存堆，Android还创建三个额外的内存堆：用来存放堆上内存被占用情况的位图索引"livebits"、在GC时用于标注存活对象的位图索引"markbits"，和用来在GC中遍历存活对象引用的标注栈（Mark Stack）。
dvmHeapSourceStartup函数运行完成后，HeapSource、Heap、livebits、markbits以及mark stack等数据结构的关系如图 14 - 15所示。
图 14 - 15 GC堆上HeapSource、Heap等数据结构的关系
其中虚拟机通过一个名为gHs的全局HeapSource变量来操控GC内存堆，而HeapSource里通过heaps数组可以管理多个堆（Heap），以满足动态调整GC内存堆大小的要求。另外HeapSource里还维护一个名为"livebits"的位图索引，以跟踪各个堆（Heap）的内存使用情况。剩下两个数据结构"markstack"和"markbits"都是用在垃圾回收阶段，后面会讲解。
图 14 - 16 GC向操作系统申请地址空间和内存
代码清单14 - 7 在虚拟机中通过dvmVisitRoot遍历GC Roots
| // // visitor是一个回调函数，dvmHeapMarkRootSet传进来的是rootMarkObjectVisitors // （位于/dalvik/vm/alloc/MarkSweep.cpp:145），这个回调函数的作用就是标注（Mark） // 所有的GC root，并将它们的指针压入标注栈（Mark Stack）中。 // // 第二个参数arg实际上是GcMarkContext对象，用于找到GC Roots后，回传给回调函数visitor // 的参数。 // void dvmVisitRoots(RootVisitor *visitor, void *arg) { assert(visitor != NULL); // 所有已加载的类型都是GC Roots，这也意味着类型中所有的静态变量都是GC Roots visitHashTable(visitor, gDvm.loadedClasses, ROOT_STICKY_CLASS, arg);
// 基本类型也是GC Roots，包括 // void, boolean, byte, short, char, int, long, float, double visitPrimitiveTypes(visitor, arg);
// 调试器对象注册表中的对象（debugger object registry），这些对象 // 基本上是调试器创建的，因此不能把它们当作垃圾回收了，否则调试器 // 就无法正常工作了。 if (gDvm.dbgRegistry != NULL) { visitHashTable(visitor, gDvm.dbgRegistry, ROOT_DEBUGGER, arg); }
// 所有interned的字符串，interned string是虚拟机中保证的只有唯一一份拷贝的字符串 if (gDvm.literalStrings != NULL) { visitHashTable(visitor, gDvm.literalStrings, ROOT_INTERNED_STRING, arg); }
// 所有的JNI全局引用对象（JNI global references），JNI全局引用对象是 // JNI代码中，通过NewGlobalRef函数创建的对象 dvmLockMutex(&gDvm.jniGlobalRefLock); visitIndirectRefTable(visitor, &gDvm.jniGlobalRefTable,, ROOT_JNI_GLOBAL, arg); dvmUnlockMutex(&gDvm.jniGlobalRefLock);
// 所有的JNI局部引用对象（JNI local references） // 关于JNI局部和全部变量的使用，可以参考下面的网页链接： // http://journals.ecs.soton.ac.uk/java/tutorial/native1.1/implementing/refs.html dvmLockMutex(&gDvm.jniPinRefLock); visitReferenceTable(visitor, &gDvm.jniPinRefTable,, ROOT_VM_INTERNAL, arg); dvmUnlockMutex(&gDvm.jniPinRefLock);
// 所有线程堆栈上的局部变量和其它对象，如线程本地存储里的对象等等 visitThreads(visitor, arg);
// 特殊的异常对象，如OOM异常对象需要在内存不够的时候创建，为了防止内存不够而无法创建 // OOM对象，因此虚拟机会在启动时事先创建这些对象。 (*visitor)(&gDvm.outOfMemoryObj,, ROOT_VM_INTERNAL, arg); (*visitor)(&gDvm.internalErrorObj,, ROOT_VM_INTERNAL, arg); (*visitor)(&gDvm.noClassDefFoundErrorObj,, ROOT_VM_INTERNAL, arg); } |
dvmHeapMarkRootSet是执行标注过程的主要代码，在前文说过，通常的实现会在对象实例前面放置一个对象头，里面会存放是否标注过的标志，而在Android系统里，采取的是分离式策略，而是将标注用的标志位放到HeapSource里的"markbits"这个位图索引结构，笔者猜测这么做的目的是为了节省内存。图 14 - 17是dvmHeapMarkRootSet函数快要标注完存活对象时（正在标注最后一个对象H），GC内存堆的数据结构。
图 14 - 17 GC执行完标注过程后的HeapSource结构
其中"livebits"位图索引还是维护堆上已用的内存信息；而"markbits"这个位图索引则指向存活的对象，在图 14 - 17中， A、C、F、G、H对象需要保留，因此"markbits"分别指向他们（最后的H对象尚在标注过程中，因此没有指针指向它）；而"markstack"就是在标注过程中跟踪当前需要处理的对象要用到的标志栈了，此时其保存了正在处理的对象F、G和H。
图 14 - 18 GC清理完内存后堆上的数据结构
如代码清单14 - 1是一个实现finalize函数的对象，在Java中，finalize对象定义在System.Object类中，即意味着所有对象都有这个函数，当子类重载了这个函数，即向虚拟机表明自己需要与其他类型区别对待。
代码清单14 - 8 实现finalize函数的简单对象
| 1 class DemoClass { 2 public int X; 3 4 public void testMethod() { 5 System.out.println("X: " + new Integer(X).toString()); 6 } 7 8 @Override 9 protected void finalize () throws Throwable { 10 System.out.println("finalize函数被调用了！"); 11 // 实现自定义的资源清除逻辑！ 12 super.finalize(); 13 } 14 } |
一些有C++编程经验的读者可能很容易将finalize函数与析构函数对应起来，但是两者是完全不同的东西，在C++中，调用了析构函数之后，对象就被释放了，然而在Java中，如果一个类型实现了finalize函数，其会带来一些不利影响，首先对象的存活周期会更长，至少需要两次垃圾回收才能销毁对象；第二对象同时会延长其所引用到的对象存活周期。如代码清单14 - 2中（示例代码javagc-simple）在第3行创建并使用了DemoClass以在内存中生成一些垃圾，并执行三次GC。
代码清单14 - 9 实现finalize函数的简单对象
| 1 public class gcdemo { 2 public static void main(String[] args) throws Exception { 3 generateGarbage(); 4 System.gc(); 5 Thread.sleep(1000); 6 7 System.gc(); 8 Thread.sleep(1000); 9 10 System.gc(); 11 Thread.sleep(1000); 12 } 13 14 public static void generateGarbage() { 15 DemoClass g = new DemoClass(); 16 g.X =123; 17 g.testMethod(); 18 } 19 } |
连接好设备，打开logcat日志，并执行示例代码根目录中的run.sh，得到的输出类似图 14 - 8，每一行输出对应代码清单14 - 2中的一次System.gc调用，可以看到第一次GC过程中释放了223个对象，如果运行示例程序javagc，会发现第一次GC之后，DemoClass的finalize函数就会被调用 – 为了避免System.out.println中的字符串对象影响GC的输出，图 14 - 8是javagc-simple的输出结果。第二次GC过程中又释放了34个对象，其中就有DemoClass的实例，以及其所引用到的其它对象。这时所有垃圾对象都被回收了，因此在执行第三次GC过程时，没有回收到任何内存。
图 14 - 19 程序中使用了实现finalize函数对象之后实施三次GC的结果
前文讲到Android源码中通过dvmHeapScanMarkedObjects函数在GC堆上扫描垃圾对象，并将finalizable对象添加到finalize队列中，其具体过程如下：
微信关注我们
转载内容版权归作者及来源网站所有！
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
近一个月的开发和优化，本站点的第一个app全新上线。该app采用极致压缩，本体才4.36MB。系统里面做了大量数据访问、缓存优化。方便用户在手机上查看文章。后续会推出HarmonyOS的适配版本。
马里奥是站在游戏界顶峰的超人气多面角色。马里奥靠吃蘑菇成长，特征是大鼻子、头戴帽子、身穿背带裤，还留着胡子。与他的双胞胎兄弟路易基一起，长年担任任天堂的招牌角色。
Spring框架（Spring Framework）是由Rod Johnson于2002年提出的开源Java企业级应用框架，旨在通过使用JavaBean替代传统EJB实现方式降低企业级编程开发的复杂性。该框架基于简单性、可测试性和松耦合性设计理念，提供核心容器、应用上下文、数据访问集成等模块，支持整合Hibernate、Struts等第三方框架，其适用范围不仅限于服务器端开发，绝大多数Java应用均可从中受益。
Rocky Linux（中文名：洛基）是由Gregory Kurtzer于2020年12月发起的企业级Linux发行版，作为CentOS稳定版停止维护后与RHEL（Red Hat Enterprise Linux）完全兼容的开源替代方案，由社区拥有并管理，支持x86_64、aarch64等架构。其通过重新编译RHEL源代码提供长期稳定性，采用模块化包装和SELinux安全架构，默认包含GNOME桌面环境及XFS文件系统，支持十年生命周期更新。
扫码在手机上查看文章
扫描二维码，手机阅读更方便
有任何问题或合作意向欢迎联系我们
Email: 99873273@qq.com
QQ: 99873273