垃圾回收 (計算機科學)

在計算機科學中，垃圾回收（英語：Garbage Collection，縮寫為GC）是指一種自動的記憶體管理機制。当某个程序占用的一部分内存空间不再被这个程序访问时，这个程序会借助垃圾回收算法向操作系统归还这部分内存空间。垃圾回收器可以减轻程式員的負擔，也減少程序中的错误。垃圾回收最早起源于LISP语言。^[1]^[2]目前許多語言如Smalltalk、Java、C#、Go和D语言都支援垃圾回收器。

原理

垃圾回收器有兩個基本的原理：

考慮某個物件在未来的程式執行中，將不會被存取。
回收這些物件所占用的記憶體。^[3]

分类

收集器实现

引用计数收集器

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

跟踪收集器

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

回收算法

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

标记－清除

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

标记－压缩

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

复制

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

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

增量回收器

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

分代

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

現今的GC（如Java和.NET）使用分代收集（generation collection），依照物件存活時間的長短使用不同的垃圾收集演算法，以達到最好的收集效能。

以Java為例，由内存管理程序管理的堆可以切割成為两個部分：

Young：
1. Eden：存放新生物件。
2. Survivor：存放經過垃圾回收沒有被清除的物件。
3. semi-Spaces：和Survivor做Copying collection。
Tenured：物件多次回收沒有被清除，則移到該區塊。

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

Minor collection：
YOUNG世代使用將Eden還有Survivor內的資料利用semi-space做複製收集（Copying collection），

並將原本Survivor內經過多次垃圾收集仍然存活的物件移動到Tenured。
Major collection則會進行Minor collection，Tenured世代則進行標記壓縮收集。^[4]