浅析垃圾回收算法

前言

第一次接触到垃圾回收算法是在朴老师的《深入浅出Node.js》上，对于 垃圾回收 这个概念，我不免抛出一些疑问。垃圾 在日常生活中我们非常熟悉，指的哪些我们用过的或者是无用的东西，那在js中哪些是垃圾呢？ 而回收的这个操作通常都是物业大妈干的事情，那在 js又是谁在做这件事情呢？

我们来举个例子回答上述的问题，

var a = { name: 'hello' }
a = 'world'

上述代码中，我们先声明了变量 a，然后将a赋值了一个对象 { name: 'hello' }，在 js引擎 分配内存的策略上，这个对象真实所占用的存储空间是在堆上的，而这个内存的地址是存放在栈上的，这就是我们 前端 常说的引用类型的存储方式。而下一行代码，我们将 world 赋值给 a 时，之前的对象就被后续引用，是不是变得有点像 垃圾 了。我们都知道内存是非常昂贵的，所以这是js引擎 就会充当一部分 物业大妈 们的角色将这些垃圾收走。

概念介绍

通过上述例子的描述我们基本上知道了 GC(Garbage Collection)，干了件什么事情。然而对于做这件事情我们需要一定的策略，下面将会介绍两种常见的算法：半区复制法和标记清除法。 半区复制法通常应用于对新生代(在内存中停留不久)对象处理，而标记清除法通常应用于对老生代(在内存中驻留)对象处理，那老生代对象是如何由来的呢？这个后面来解答一下。

这在里还有一个内存管理中行的概念需要阐述一下：可达性。就是那些以某种方式可访问或者说可用的值，它们被保证存储在内存中，反之不可访问则需回收。

半区复制法(Cheney算法)

对于新生代的对象来说，半区复制法是个不错的应对策略。Cheney算法 中将堆内存一分为二，一个是处于使用状态的空间我们暂且称之为 使用区，一个是处于闲置状态的空间我们称之为空闲区，如下图所示

新加入的对象都会存放到使用区，当使用区快被写满时，就需要执行一次垃圾清理操作。

当开始进行垃圾回收时，新生代垃圾回收器会对使用区中的活动对象做标记，标记完成之后将使用区的活动对象复制进空闲区并进行排序，随后进入垃圾清理阶段，即将非活动对象占用的空间清理掉。最后进行角色互换，把原来的使用区变成空闲区，把原来的空闲区变成使用区。

当一个对象经过多次复制后依然存活，它将会被认为是生命周期较长的对象，随后会被移动到老生代中，采用老生代的垃圾回收策略进行管理。

这里有一个疑问就是 标记 是如何实现的？有下面几种方法

1. 当变量进入执行环境时，反转某一位（通过一个二进制字符来表示标记）
2. 可以维护进入环境变量和离开环境变量这样两个列表，可以自由的把变量从一个列表转移到另一个列表

标记清除（Mark-Sweep）算法

标记清除（Mark-Sweep），目前在 JavaScript引擎 里这种算法是最常用的，到目前为止的大多数浏览器的 JavaScript引擎 都在采用标记清除算法，只是各大浏览器厂商还对此算法进行了优化加工，且不同浏览器的 JavaScript引擎 在运行垃圾回收的频率上有所差异。

此算法分为 标记 和 清除 两个阶段，标记阶段即为所有活动对象做上标记，清除阶段则把没有标记（也就是非活动对象）销毁

引擎在执行 GC（使用标记清除算法）时，需要从出发点去遍历内存中所有的对象去打标记，而这个出发点有很多，我们称之为一组 根 对象，而所谓的根对象，其实在浏览器环境中包括又不止于 全局Window对象、文档DOM树 等

标记清除的过程大致如下：

• 垃圾收集器在运行时会给内存中的所有变量都加上一个标记，假设内存中所有对象都是垃圾，全标记为0
• 然后从各个根对象开始遍历，把不是垃圾的节点改成1
• 清理所有标记为0的垃圾，销毁并回收它们所占用的内存空间
• 最后，把所有内存中对象标记修改为0，等待下一轮垃圾回收

优点

标记清除算法的优点只有一个，那就是实现比较简单，打标记也无非打与不打两种情况，这使得一位二进制位（0和1）就可以为其标记，非常简单

缺点

标记清除算法有一个很大的缺点，就是在清除之后，剩余的对象内存位置是不变的，也会导致空闲内存空间是不连续的，出现了 内存碎片（如下图），并且由于剩余空闲内存不是一整块，它是由不同大小内存组成的内存列表，这就牵扯出了内存分配的问题

假设我们新建对象分配内存时需要大小为 size，由于空闲内存是间断的、不连续的，则需要对空闲内存列表进行一次单向遍历找出大于等于 size 的块才能为其分配（如下图）

那么如何在诸多的 内存碎片碎片中找到一块合适的内存呢？这里有三种分配策略可供选择：

• First-fit，找到大于等于 size 的块立即返回

• Best-fit，遍历整个空闲列表，返回大于等于 size 的最小分块

• Worst-fit，遍历整个空闲列表，找到最大的分块，然后切成两部分，一部分 size 大小，并将该部分返回

这三种分配策略需要在各种场景中测试来找到最佳策略，本质还是如何去平衡空间和比较次数的。

标记整理（Mark-Compact）算法

标记清除算法的缺点在于清除之后剩余的对象位置不变而导致的空闲内存不连续，所以只要解决这一点，两个缺点(内存碎片化和分配速度慢)都可以完美解决了

标记整理（Mark-Compact）算法 就可以有效地解决，它的标记阶段和标记清除算法没有什么不同，只是标记结束后，标记整理算法会将活着的对象（即不需要清理的对象）向内存的一端移动，最后清理掉边界的内存（如下图），这样整合之后，内存的地址就会是连续的，这样方便了后续的内存分配。

总结

1. 通过本文了解什么是所谓的垃圾，什么是可达性。
2. 新生代常用的 半区复制法(Cheney算法) 以及 标记清除（Mark-Sweep）算法的优缺点和 标记整理（Mark-Compact）算法的优化点。
3. 此外，我们还有几个疑问：

• js是单线程的，那么 GC（Garbage Collection） 的时机是怎样的？
• 对于标记过的变量在下一次还需要继续标记吗？
• 在我们熟悉的 v8 当中这些算法到底是如何工作的？ 上述的问题我们下一次再来研究

参考文献

• 「硬核JS」你真的了解垃圾回收机制吗 (opens new window)
• 《深入浅出Node.js》 (opens new window)