垃圾回收 (计算机科学)

在计算机科学中,垃圾回收(英语:Garbage Collection,缩写为GC)是指一种自动的存储器管理机制。当某个程序占用的一部分内存空间不再被这个程序访问时,这个程序会借助垃圾回收算法向操作系统归还这部分内存空间。垃圾回收器可以减轻程序员的负担,也减少程序中的错误。垃圾回收最早起源于LISP语言。[1][2]目前许多语言如SmalltalkJavaC#GoD语言都支持垃圾回收器。

原理

垃圾回收器有两个基本的原理:

  1. 考虑某个对象在未来的程序执行中,将不会被访问。
  2. 回收这些对象所占用的存储器。[3]

分类

收集器实现

引用计数收集器

最早的也是最简单的垃圾回收实现方法,这种方法为占用物理空间的对象附加一个计数器,当有其他对象引用这个对象时计数器加一,反之引用解除时减一。这种算法会定期检查尚未被回收的对象的计数器,为零的话则回收其所占物理空间,因为此时的对象已经无法访问。这种方法无法回收循环引用的存储对象。

跟踪收集器

近现代的垃圾回收实现方法,这种算法会定期遍历它管理的内存空间,从若干根储存对象开始查找与之相关的存储对象,然后标记其余的没有关联的存储对象,最后回收这些没有关联的存储对象占用的内存空间。

回收算法

基于其标记和回收行为,又分为若干细致方法。

标记-清除

先暂停整个程序的全部运行线程,让回收线程以单线程进行扫描标记,并进行直接清除回收,然后回收完成后,恢复运行线程。这样会产生大量的空闲空间碎片,和使大容量对象不容易获得连续的内存空间,而造成空间浪费。

标记-压缩

和“标记-清除”相似,不同的是,回收期间同时会将保留的存储对象搬运汇集到连续的内存空间,从而整合空闲空间,避免内存碎片化。

复制

需要程序将所拥有的内存空间分成两个部分。程序运行所需的存储对象先存储在其中一个分区(定义为“分区0”)。同样暂停整个程序的全部运行线程,进行标记后,回收期间将保留的存储对象搬运汇集到另一个分区(定义为“分区1”),完成回收,程序在本次回收后将接下来产生的存储对象会存储到“分区1”。在下一次回收时,两个分区的角色对调。[3]

这种方式非常简单,但是因为只有一个“半空间”(semi-space)被用于分配对象,内存使用相较于其他算法是其两倍。这种技术也叫做“停止并复制”。Cheney算法是改进的半空间分配器。

增量回收器

需要程序将所拥有的内存空间分成若干分区。程序运行所需的存储对象会分布在这些分区中,每次只对其中一个分区进行回收操作,从而避免暂停所有正在运行的线程来进行回收,允许部分线程在不影响回收行为下保持运行,并且降低回收时间,增加程序响应速度。

分代

由于“复制”算法对于存活时间长,大容量的储存对象需要耗费更多的移动时间,和存在储存对象的存活时间的差异。需要程序将所拥有的内存空间分成若干分区,并标记为年轻代空间和年老代空间。程序运行所需的存储对象会先存放在年轻代分区,年轻代分区会较为频密进行较为激进垃圾回收行为,每次回收完成幸存的存储对象内的寿命计数器加一。当年轻代分区存储对象的寿命计数器达到一定阈值或存储对象的占用空间超过一定阈值时,则被移动到年老代空间,年老代空间会较少运行垃圾回收行为。一般情况下,还有永久代的空间,用于涉及程序整个运行生命周期的对象存储,例如运行代码、数据常量等,该空间通常不进行垃圾回收的操作。 通过分代,存活在局限域,小容量,寿命短的存储对象会被快速回收;存活在全局域,大容量,寿命长的存储对象就较少被回收行为处理干扰。

现今的GC(如Java.NET)使用分代收集(generation collection),依照对象存活时间的长短使用不同的垃圾收集算法,以达到最好的收集性能。

以Java为例,由内存管理程序管理的堆可以切割成为两个部分:

  1. Young:
    1. Eden:存放新生对象。
    2. Survivor:存放经过垃圾回收没有被清除的对象。
    3. semi-Spaces:和Survivor做Copying collection。
  2. Tenured:对象多次回收没有被清除,则移到该区块。

JVM对不同的世代使用不同的GC算法。

  1. Minor collection:
    YOUNG世代使用将Eden还有Survivor内的资料利用semi-space做复制收集(Copying collection),
    并将原本Survivor内经过多次垃圾收集仍然存活的对象移动到Tenured。
  2. Major collection则会进行Minor collection,Tenured世代则进行标记压缩收集。[4]

实现

GC机制可以是由编程语言本身提供的功能(如Java、C#),也可以是程序语言以外的第三方库。例如贝姆垃圾收集器就是一种可支持C/C++语言的自动存储器管理工具。

参见

  • 内存管理
  • 约翰·麦卡锡

参考文献

  1. ^ Recursive functions of symbolic expressions and their computation by machine, Part I. Portal.acm.org. [29 March 2009]. 
  2. ^ Recursive functions of symbolic expressions and their computation by machine, Part I. [29 May 2009]. (原始内容存档于2013-10-04). 
  3. ^ 3.0 3.1 吴, 昊; 季, 振洲. 一种基于半空间的不完全拷贝垃圾回收机制. 哈尔滨工业大学学报. 2011, 43 (11): 60–64 [2020-03-27]. ISSN 0367-6234. (原始内容存档于2020-05-28). 
  4. ^ 分代-JVM文档. [2020-03-28]. (原始内容存档于2020-03-28) (英语).