盘点垃圾回收机制

转载请注明出处 ：）

语言	是否面向对象	是否有垃圾回收机制	机制原理
C	面向过程	无	手动管理
C++	面向对象	无	手动管理
Java	面向对象	有	根搜索算法
Python	面向对象（并不强制）	有	引用计数机制
JavaScript	面向对象	有	标记清除
Ruby	面向对象	有	标记清除
Objective-C	面向对象	有	引用计数机制
Php	面向对象	有	引用计数机制

上表仅仅罗列出一小部分主流语言的垃圾回收机制，'机制原理'只说明该语言主要使用的机制，不代表完全。

引用计数基本知识

《Clean Code》一书的作者Bob大叔，曾在一次演讲中提到过，国外有一些程序员是 [Language Oriented Programming] ,什么意思呢？这些程序员根本不挑剔编程语言，管你php,python,java,js,还是ruby，哪个火就用哪个，哪个工资高就转哪个。真相是当你具备相对完善的计算机理论知识体系，并对一门语言有较深的掌握之后，切换到新语言的成本比大多数人想象的要低的多。

拿php来举例：
每个php变量存在一个叫"zval"的变量容器中。一个zval变量容器，除了包含变量的类型和值，还包括两个字节的额外信息。第一个是"is_ref"，是个bool值，用来标识这个变量是否是属于引用集合(reference set)。通过这个字节，php引擎才能把普通变量和引用变量区分开来，由于php允许用户通过使用&来使用自定义引用，zval变量容器中还有一个内部引用计数机制，来优化内存使用。第二个额外字节是"refcount"，用以表示指向这个zval变量容器的变量(也称符号即symbol)个数。所有的符号存在一个符号表中，其中每个符号都有作用域(scope)，那些主脚本(比如：通过浏览器请求的的脚本)和每个函数或者方法也都有作用域。

当一个变量被赋常量值时，就会生成一个zval变量容器，如下例这样

<?php
$a = "new string";
?>

使用Xdebug工具调用函数 xdebug_debug_zval()显示"refcount"和"is_ref"的值，

a: (refcount=1, is_ref=0)='new string'

把一个变量赋值给另一变量将增加引用次数(refcount).

<?php
$a = "new string";
$b = $a;
xdebug_debug_zval( 'a' );
?>

上例会输出：

a: (refcount=2, is_ref=0)='new string'

这时，引用次数是2，因为同一个变量容器被变量 a和变量 b关联。当没必要时，php不会去复制已生成的变量容器。变量容器在”refcount“变成0时就被销毁。当任何关联到某个变量容器的变量离开它的作用域(比如：函数执行结束)，或者对变量调用了函数 unset()时，”refcount“就会减1，下面的例子就能说明:

<?php
$a = "new string";
$c = $b = $a;
xdebug_debug_zval( 'a' );
unset( $b, $c );
xdebug_debug_zval( 'a' );
?>

上例会输出：

a: (refcount=3, is_ref=0)='new string'
a: (refcount=1, is_ref=0)='new string'

如果我们现在执行 unset($a);，包含类型和值的这个变量容器就会从内存中删除。

以上内容来自PHP官方参考手册

可以看到基于引用计数的垃圾回收机制是通过对象的引用计数器来决定是否进行回收的。

例如Python：

typedef struct_object {
 int ob_refcnt;
 struct_typeobject *ob_type;
} PyObject;

每一个python对象都是有一个结构体组成，结构体中的ob_refcnt参数代表当前对象的引用计数，ob_refcnt的值随着新对象对它的引用与否而发生改变，当有一个新对象引用它时，它的ob_refcnt值自加一。当前对象对它不在引用时，它的ob_refcnt值自减一。当ob_refcnt的值减到0时，垃圾回收机制回收内存。

当一个函数体执行完毕之后，其内部的局部变量引用计数全部清零释放，借用微信小程序的概念：用完即走。省的占着茅坑。。。

优缺点

所有具有垃圾回收机制的编程语言并不是只有一种垃圾回收机制，引用计数机制这么简单为什么不全部使用这个机制呢，下面来谈谈引用计数的优缺点。

优点	缺点
1.机制简单 2.实时性：一旦没有引用，内存就直接释放了。不用像其他机制等到特定时机。实时性还带来一个好处：处理回收内存的时间分摊到了平时，资源利用率较高。	1.容易产生循环引用，导致内存泄露 2.循环引用计数器消耗内存（每个对象内部留一些空间来处理引用计数） 3.循环引用计数器消耗资源（不停地更新着众多引用数值。特别是当你不再使用一个大数据结构的时候，比如一个包含很多元素的列表，必须一次性释放大量对象。减少引用数就成了一项复杂的递归过程了）

循环引用的例子（自己引用自己）：

<?php
$a = array( 'one' );
$a[] =& $a;
xdebug_debug_zval( 'a' );
?>

上例会输出：

a: (refcount=2, is_ref=1)=array (
   0 => (refcount=1, is_ref=0)='one',
   1 => (refcount=2, is_ref=1)=...
)

这时如果让$a指向null,它在内存上的是这样的：

(refcount=1, is_ref=1)=array (
   0 => (refcount=1, is_ref=0)='one',
   1 => (refcount=1, is_ref=1)=...
)

就是说它还有引用，所以内存不会释放，就造成了内存泄露。这件事对于那些大型的服务器程序来说是致命的，因为它们会一直在服务端运行，如果产生微小的内存泄露，日积月累会导致服务器因内存爆满而崩溃。

标记清除基本知识

拿Ruby举例：
在Ruby中，申请一个对象时，ruby并不会立即向操作系统请求内存，而是在代码开始之前就创建成千上百个对象，在指针将其串联成一个链表

Snip20170210_7.png

object = Node.new('ddd');

当程序申请一个对象时，链表就将头结点释放出来，（绿色代表已分配，蓝色代表未分配）

Snip20170210_9.png

当程序多次调用下面同一条语句时，会得到多个对象，并且之前申请的对象不会释放，就是所谓的垃圾

object = Node.new('ddd');

Snip20170210_10.png

总会有一个时刻，使得ruby预先申请好的对象空间使用完毕，这时如果再申请对象，就会没有空间，而此时此刻内存中装的是一堆没有用的垃圾，亟待释放。ruby的解决方式是，将程序暂停下来，并开始轮询所有的指针、变量和代码产生别的引用对象和其他值，在内存中不在使用的空间标记为M。

Snip20170210_11.png

之后再将那些可以释放的空间用指针的形式串接成一个可用链表，为下一分配做准备。

Snip20170210_12.png

不同的标记清除法采用类似的方法，在垃圾回收机制的时机选择上可能会有不同。Ruby的垃圾回收机制已经53岁高龄了。

根搜索算法

以下内容出自 浅析JAVA的垃圾回收机制（GC）

首先了解一个概念：根集(Root Set)
所谓根集(Root Set)就是正在执行的Java程序可以访问的引用变量（注意：不是对象）的集合(包括局部变量、参数、类变量)，程序可以使用引用变量访问对象的属性和调用对象的方法。
这种算法的基本思路：
（1）通过一系列名为“GC Roots”的对象作为起始点，寻找对应的引用节点。
（2）找到这些引用节点后，从这些节点开始向下继续寻找它们的引用节点。
（3）重复（2）。
（4）搜索所走过的路径称为引用链，当一个对象到GC Roots没有任何引用链相连时，就证明此对象是不可用的。
Java和C#中都是采用根搜索算法来判定对象是否存活的。
标记可达对象：
JVM中用到的所有现代GC算法在回收前都会先找出所有仍存活的对象。根搜索算法是从离散数学中的图论引入的，程序把所有的引用关系看作一张图。下图3.0中所展示的JVM中的内存布局可以用来很好地阐释这一概念：

图 3.0 标记（marking）对象

首先，垃圾回收器将某些特殊的对象定义为GC根对象。所谓的GC根对象包括：
（1）虚拟机栈中引用的对象（栈帧中的本地变量表）；
（2）方法区中的常量引用的对象；
（3）方法区中的类静态属性引用的对象；
（4）本地方法栈中JNI（Native方法）的引用对象。
（5）活跃线程。
接下来，垃圾回收器会对内存中的整个对象图进行遍历，它先从GC根对象开始，然后是根对象引用的其它对象，比如实例变量。回收器将访问到的所有对象都标记为存活。
存活对象在上图中被标记为蓝色。当标记阶段完成了之后，所有的存活对象都已经被标记完了。其它的那些（上图中灰色的那些）也就是GC根对象不可达的对象，也就是说你的应用不会再用到它们了。这些就是垃圾对象，回收器将会在接下来的阶段中清除它们。
关于标记阶段有几个关键点是值得注意的：
（1）开始进行标记前，需要先暂停应用线程，否则如果对象图一直在变化的话是无法真正去遍历它的。暂停应用线程以便JVM可以尽情地收拾家务的这种情况又被称之为安全点（Safe Point），这会触发一次Stop The World(STW)暂停。触发安全点的原因有许多，但最常见的应该就是垃圾回收了。
（2）暂停时间的长短并不取决于堆内对象的多少也不是堆的大小，而是存活对象的多少。因此，调高堆的大小并不会影响到标记阶段的时间长短。
（3）在根搜索算法中，要真正宣告一个对象死亡，至少要经历两次标记过程：
1.如果对象在进行根搜索后发现没有与GC Roots相连接的引用链，那它会被第一次标记并且进行一次筛选。筛选的条件是此对象是否有必要执行 finalize（）方法（可看作析构函数，类似于OC中的dealloc，Swift中的deinit）。当对象没有覆盖finalize（）方法，或finalize（）方法已经被虚拟机调用过，虚拟机将这两种情况都视为没有必要执行。
2.如果该对象被判定为有必要执行finalize（）方法，那么这个对象将会被放置在一个名为F-Queue队列中，并在稍后由一条由虚拟机自动建立的、低优先级的Finalizer线程去执行finalize（）方法。finalize（）方法是对象逃脱死亡命运的最后一次机会（因为一个对象的finalize（）方法最多只会被系统自动调用一次），稍后GC将对F-Queue中的对象进行第二次小规模的标记，如果要在finalize（）方法中成功拯救自己，只要在finalize（）方法中让该对象重新引用链上的任何一个对象建立关联即可。而如果对象这时还没有关联到任何链上的引用，那它就会被回收掉。
（4）实际上GC判断对象是否可达看的是强引用。
当标记阶段完成后，GC开始进入下一阶段，删除不可达对象。
4.回收垃圾对象内存的算法
4.1 Tracing算法（Tracing Collector） 或 标记—清除算法
标记—清除算法是最基础的收集算法，为了解决引用计数法的问题而提出。它使用了根集的概念，它分为“标记”和“清除”两个阶段：首先标记出所需回收的对象，在标记完成后统一回收掉所有被标记的对象，它的标记过程其实就是前面的根搜索算法中判定垃圾对象的标记过程。
优点：不需要进行对象的移动，并且仅对不存活的对象进行处理，在存活对象比较多的情况下极为高效。
缺点：（1）标记和清除过程的效率都不高。（这种方法需要使用一个空闲列表来记录所有的空闲区域以及大小。对空闲列表的管理会增加分配对象时的工作量。如图4.1所示。）。（2）标记清除后会产生大量不连续的内存碎片。虽然空闲区域的大小是足够的，但却可能没有一个单一区域能够满足这次分配所需的大小，因此本次分配还是会失败（在Java中就是一次OutOfMemoryError）不得不触发另一次垃圾收集动作。如图4.2所示。
算法示意图：

图 4.0 标记—清除算法

欢迎各位大神批评指正，感激不尽！喜欢就给我颗❤️吧。