你也能看懂的垃圾回收

垃圾回收（Garbage Collection）作为一门实用而又重要的技术，可以说拯救了无数苦于内存管理的程序员。尽管很多人认为，GC技术走进大众的视野，多是源于Java语言的崛起，但是GC技术本身却相当的古老。早在1960年，Lisp之父John McCarthy已经在其论文中发布了GC算法，Lisp语言也是第一个实现GC的语言。

为什么需要垃圾回收

在程序执行的过程中，会产生一系列的对象（占用内存的代表），这些都会存储在内存中。一部分对象在生命周期结束后，依然会占用一部分内存。这些占用内存却没有再次使用的对象，我们称之为“垃圾”，而对“垃圾”占用的内存的回收，就是垃圾回收。

在没有垃圾回收的世界里，内存的管理需要由程序员手工来执行。手工往往意味着麻烦，以及潜藏的错误。以下是在手工释放内存时，常见的错误：

• 内存泄露：忘记释放了某一部分内存，会导致那部分内存不可用，并占用总的内存空间。如果这一现象持续发生，会引起内存被占满，系统崩溃
• 悬垂指针：忘记初始化指向释放了的内存的指针。这会导致再次调用指针时，该指针指向空内存，引起bug
• 释放错误的内存：人为的操作难免会发生错误，如果释放了错误的内存，也会导致程序发生莫名其妙的bug

由此可见垃圾回收的重要性，既可以减少程序员的工作量，更重要的是可以避免很多不必要的错误。

垃圾回收算法

尽管垃圾回收十分的重要，垃圾回收的概念也十分古老，但是在漫长的岁月里，垃圾回收算法的进步着实有限。最基本的垃圾回收算法早在上世纪60年代就已经提出了，分别是：标记清除、引用计数、复制算法，后续的垃圾回收算法，都是基于这三大算法做的组合与优化。

这三种垃圾回收算法的思想都十分简单，在这里我们只关注算法的思想是什么，隐去了算法的具体实现部分。

标记清除

上文所提到的John McCarthy在其论文中首次提出了垃圾回收的概念，同时提到的垃圾回收算法，就是标记清除法。

正如算法的名字，标记清除法可以划分成两个阶段，标记和清除：

1. 标记：在标记阶段，所做的事情，就是遍历所有的对象，在活动的对象头打上活动的标记
2. 清除：再次遍历对象，检查对象头，对于没有活动标记的对象，将其内存空间释放；对于有活动标记的对象，去掉标记

下图简单描述了标记清除算法中，内存的变化情况：

标记清除

思路简单，实现简单，是这个算法的一大优点。但是简单也意味着在其他部分有所牺牲，从上图我们可以看出一些端倪：

1. 碎片化：由于只是将垃圾对象清除掉，对于存活对象不做处理，所以由于存活对象分布的不连续性，会导致可用内存被分割成一块块的。如果有一个新的对象请求内存，需要去内存中寻找，哪一个空闲块（可用一个链表来维护空闲块的位置）足够满足这个对象的需求。更极端的情况，空闲的总内存大于对象请求的空间，却没有足够的连续空闲空间，来完成内存的分配。
2. 与写时复制技术不兼容：写时复制（Copy On Write）是一个很重要的思想，可以优化内存占用或者提升并发环境下的性能。顾名思义，这一技术是在有写入的时候，对内存进行复制，以达到一定的优化目的。而标记清除算法的标记过程，就是一次对内存（对象头）的写入，会不断地引起内存复制。因此标记清除算法与此技术并不互相兼容

引用计数

同样是1960年，George E. Collins在其论文中提出了另一种垃圾回收算法，引用计数法。

垃圾回收关注的是对于不会再次被使用的对象的内存回收，换一种说法，对于会被垃圾回收清理的对象（内存），不会再次的被其他对象引用。那么可以为每一个对象引入一个计数器，对于任意一个对象，每有一次对这个对象的引用，就将计数器加1；结束对这个对象的引用，再将计数器减1；一旦计数器归0，则表示这个对象可以被清除。这就是引用计数法。

此处没图

由于在计数器归0后，可以立即知道这个对象成为了垃圾，所以引用计数法有着即使回收的优点。同样，这个算法也不是完美的，存在着一定的缺点：

1. 占用资源：因为每个对象都需要维护一个计数器，每次指针有更新都伴随着计数器的更新，一定程度上占用了计算资源
2. 占用内存：计数器需要占用一定的内存，为了安全起见，计数器值的上限要大于所有对象的上限，这也是一笔不小的开销
3. 实现复杂：虽然引用计数的思想简单，但是实现起来却不那么容易。各位可以思考下，如果自己编写这一算法，该如何实现？
4. 无法解决循环引用：就像会有狗狗喜欢咬自己的尾巴，把自己咬成环，对象也会存在循环的引用。假设两个对象a和b，a有指向b的指针，b有指向a的指针。二者可能一起成为垃圾，一旦这种情况发生，由于存在对对方的引用，它们的计数器永远都不会归0，它们也不会被回收

复制算法

1963年，Marvin L. Minsky在其论文中发表了复制算法。至此，GC的三大基本算法全部被提出。

在复制算法中，先将内存分为两个部分，From区和To区，两部分大小相等。对象分配时，只会在From区进行分配。复制算法可以分两步，第一步为类似标记清除算法的标记，在From区中，找出所有活动的对象。区别在于第二步。复制算法会把这些活动的对象，复制到To区中，再将原有的From区全部清空，并交换两部分内存的职责，即一次GC后，原有的From区会成为To区，To区相反。

一次复制算法之行后，内存变化情况如下图：

复制算法

复制算法的优点相比于另外两个算法还是多一些的：

1. 效率快：相比于标记清除算法，复制算法在标记阶段，只需要标记哪些对象是活动的就可以了，相比于标记清除算法需要遍历所有的对象，性能上有提升
2. 不会发生碎片化：同样相比于标记清除算法，由于存活下来的对象会在To区中连续的分配，因此不会像标记清除算法那样，需要维护碎片空间
3. 分配速度快：由于不会发生碎片化，如果有一个新的对象请求内存，那么分配时可以直接追加在From区已用内存之后，分配的速度快

同样复制算法也不是十全十美，它也有着如下的缺点：

1. 内存使用率低：由于复制算法把内存分成了两块，那么对于对象的可用空间来说，仅仅是其他算法的一半
2. 自对象的递归复制：一个对象通常会关联一些自对象。在复制这些对象的时候，还需要递归的去处理它的自对象，这通常会产生一定的开销。同时，在递归调用时，存在着函数栈的消耗，潜藏着栈溢出的风险

小结

现代的编程语言中，通常都会内置了垃圾回收，可以说这一功能也算是检验一门编程语言是否是比较现代的语言的标准。

垃圾回收概念古老，垃圾回收的基本算法也早早的被提出。但是如上文所述，这些基本的算法还是存在着一定的问题。后人们对这三种算法也提出了很多的优化；也尝试结合多种垃圾回收算法，组合成新的垃圾回收算法，并且应用在了Java等语言中。不过这掌握着三种最基础的算法仍然很有必要，它可以帮助我们更好地去理解更新的垃圾回收算法。了解垃圾回收的机制，也会帮助我们编写出有益于GC的程序，来提升程序的运行效率。

后续还会开文介绍下Java中是如何进行垃圾回收，并且Java中几种垃圾收集器是如何演进的。

推荐参考资料：

1. 《垃圾回收的算法与实现》，中村成洋，相川光（著），竹内郁雄（审校）
2. 《深入理解Java虚拟机》，周志明

其他一些

打算写一个名为“你也能看懂”系列的文章，希望可以用最简单通俗的语言，写一些技术入门的文章，争取保证每一个人都能够理解所讲的技术。初次写，读着感觉有些生硬，等写多了之后在来进行重构吧，你懂的。

这篇文章写的时候，我也拿去给我女票看了一眼，她表示完全看不懂。不过，谁又能期待生物化学专业的妹子能懂垃圾回收呢？