垃圾回收机制

发表于 |
字数统计: 3.3k 字 | 阅读时长 ≈ 12 分钟

近期公司技术分享讲座十分火热，近期我做了有关垃圾回收机制的分享，整理一下文档

垃圾回收背景

John McCarthy 身为 Lisp 之父和人工智能之父，同时，他也是 GC 之父。1960 年，他在其论文中首次发布了 GC 算法（其实是委婉的提出😂）。而 Java 的前身 Oak 是在 1990 发布的，利用 JVM 实现了跨平台。GC 因此一举成名。

垃圾回收基本概念

基本概念:

  • 全集
  • 根集
  • 可达到的对象集合
  • 不可达到的对象集合

垃圾的定义

引用《垃圾回收的算法与实现》书中的话:

把分配到堆中那些不能通过程序引用的对象称为非活动对象，也就是死掉的对象，我们称为“垃圾”。

  • 程序无法访问的对象
  • GC 收集器需要能正确找到垃圾对象并销毁之

垃圾回收

因为我们期望让内存管理变得自动（只管用内存，不管内存的回收），我们就必须做两件事情：

找到内存空间里的垃圾回收垃圾，让程序员能再次利用这部分空间 [1] 只要满足这两项功能的程序，就是 GC，不论它是在 JVM 中，还是在 Ruby 的 VM 中。但这只是两个需求，并没有说明 GC 应该何时找垃圾，何时回收垃圾等等更具体的问题，各类 GC 算法就是在这些更具体问题的处理方式上施展手脚。

全集

  • 进程内存中全部对象的集合
  • 以 Python 为例:
1
gc.get_objects()

根集

  • 不用通过引用关系,可以直接访问对象的集合

可达对象集合

  • 根集的对象
  • 通过可达对象,利用引用关系遍历到的所有对象
    imag

不可达到的对象集合

  • 全集与可达对象集合差集
  • 不可达对象是垃圾
  • Python 中 gc.collect()后垃圾存在列表 gc.grabage 中

垃圾回收的优点

  • 提高编程效率
  • 避免内存泄漏
  • 野指针 (悬垂指针)
  • 释放错误的内存

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

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

垃圾回收缺点

  • 垃圾回收消耗cpu，影响程序性能

垃圾回收性能评价

  • 垃圾回收总时间
  • 进程突然的停顿
  • 空间利用 —— 减少内存碎片 - 空间连续性、时间连续性
  • 以上要求互相制衡，需要折中

主流垃圾回收策略

John McCarthy 身为 Lisp 之父和人工智能之父，同时，他也是 GC 之父。1960 年，他在其论文中首次发布了 GC 算法（其实是委婉的提出😂）。

标记-清除算法 由 John McCarthy 在 1960 年提出 引用计数法 由 George E. Collins 在 1960 年提出 此算法会有循环引用问题，Harold McBeth 1963 年指出。 复制算法 由 Marvin L. Minsky 在 1963 年提出

《垃圾回收》的作者认为：

从 50 年前 GC 算法首次发布以来，众多研究者对其进行了各种各样的研究，因此许多 GC 算法也得以发布。[2] 但事实上，这些算法只不过是把前文中提到的三种算法进行组合或应用。也可以这么说，1963 年 GC 复制算法诞生时，GC 的根本性内容就已经完成了。

引用计数法

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

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

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

标记清除

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

  • 标记
    • 标记根集中的所有对象为可达
    • 从根集中的对象遍历，将其引用的对象标记为可达
    • 迭代第二步，找到所有可达对象

  • 清除

    • 全集与可达对象集合的差集，标记为不可达对象集合
    • 销毁所有不可达对象

imag

优点

  • 思路简单，实现简单，是这个算法的一大优点.
  • 没有额外内存开销
  • 可以正确销毁循环引用的对象

缺点

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

  • 标记-清除操作时间消耗较大，程序会顿卡
  • 对象不可达后，销毁有延时

imag

复制算法

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

imag

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

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

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

重定位

  • 不可到达对象在内存中是分散的，回收对象后，空闲内存是分段的
  • 移动可到达的堆对象，保持内存连续
    imag

分代算法

  • 销毁的总是年轻的对象
    — 统计表明：80%-90%新分配的对象会在随后几百万条指令周期内销毁
  • 将堆空间分成几块
  • 新对象生成在空间1
  • 当空间1满了，将对象移动到空间2，再往上也如此类推
  • 空间序号越小，垃圾回收检测越频繁
  • Python分为三代，gc.get_threshold可以获取每一代空间的默认阈值

各语言的垃圾回收策略

Luanguage 引用计数 标记-清除 分代 重定位 复制
Python √ √ √
JavaScript √ √
Java √ √ √
Golang √

1、JavaScript 中 BOM、COM 用的是引用计数机制

2、Golang 最新用的是三色标记-清除算法，标记阶段需要 STW，清除阶段可以并发进行

Python垃圾回收实战

以 Python 为例 Python 的 gc.collect() 标记-清除需要消耗一定时间，在对象数量达到百万级别时会有秒级卡顿。有些项目对实时性要求比较高，会调用 gc.disable()关闭 gc；关闭 gc 意味着在开发阶段就要解除所有的循环引用，不然会造成内存泄漏。即使不关闭 gc，在销毁对象时解除循环引用，有利于减少 gc 卡顿时间。那如何找到循环引用的对象？如何找出引用环的情况？

gc.DEBUG_SAVEALL When set, all unreachable objects found will be appended to garbage rather than being freed. This can be useful for debugging a leaking program.

1
2
3
gc.set_debug(gc.DEBUG_SAVEALL)
gc.collect()
print(gc.garbage)

上面的方法可以找到垃圾对象，但要靠自己去找到对象间的引用情况来解除引用。利用 objgraph 可以找到对象的引用关系链并生成图。但是在实践中，进程中对象数量较大时，objgraph 经常会慢到让人想要原地自爆。也可以自己编写工具，在 gc.garbage 做图的遍历，找到所有的环引用，这样会比较全比较快。(TODO: 待分享通过gc.garbage查环工具代码)
imag

gc.garbage

A list of objects which the collector found to be unreachable but could not be freed (uncollectable objects). By default, this list contains only objects with del() methods. [1] Objects that have del() methods and are part of a reference cycle cause the entire reference cycle to be uncollectable, including objects not necessarily in the cycle but reachable only from it. Python doesn’t collect such cycles automatically because, in general, it isn’t possible for Python to guess a safe order in which to run the del() methods. If you know a safe order, you can force the issue by examining the garbage list, and explicitly breaking cycles due to your objects within the list. Note that these objects are kept alive even so by virtue of being in the garbage list, so they should be removed from garbage too. For example, after breaking cycles, do del gc.garbage[:] to empty the list. It’s generally better to avoid the issue by not creating cycles containing objects with del() methods, and garbage can be examined in that case to verify that no such cycles are being created.

If DEBUG_SAVEALL is set, then all unreachable objects will be added to this list rather than freed.

有个很重要的点，Python2 中，当对象形成环引用，即使开启 gc，实现了del方法的对象也无法被回收，因为 gc 并不知道在del方法中是否对引用的对象有操作，无法确定正确的回收顺序。在Python 中，一般而言，尽量不要实现del方法，而改用其他方法在销毁时手动调用之。