垃圾回收 (計算機科學)

  提示：此條目頁的主題不是垃圾回收。

在計算機科學中，垃圾回收（英語：Garbage Collection，縮寫為GC）是指一種自動的記憶體管理機制。當某個程序占用的一部分內存空間不再被這個程序訪問時，這個程序會藉助垃圾回收算法向操作系統歸還這部分內存空間。垃圾回收器可以減輕程式員的負擔，也減少程序中的錯誤。垃圾回收最早起源於LISP語言。目前許多語言如Smalltalk、Java、C#、Go和D語言都支援垃圾回收器。

原理

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

1. 考慮某個物件在未來的程式執行中，將不會被存取。
2. 回收這些物件所占用的記憶體。

分類

收集器實現

引用計數收集器

主條目：引用計數

最早的也是最簡單的垃圾回收實現方法，這種方法為占用物理空間的對象附加一個計數器，當有其他對象引用這個對象時計數器加一，反之引用解除時減一。這種算法會定期檢查尚未被回收的對象的計數器，為零的話則回收其所占物理空間，因為此時的對象已經無法訪問。這種方法無法回收循環引用的存儲對象。

跟蹤收集器

主條目：追蹤垃圾回收

近現代的垃圾回收實現方法，這種算法會定期遍歷它管理的內存空間，從若干根儲存對象開始查找與之相關的存儲對象，然後標記其餘的沒有關聯的存儲對象，最後回收這些沒有關聯的存儲對象占用的內存空間。

回收算法

基於其標記和回收行為，又分為若干細緻方法。

標記－清除

先暫停整個程序的全部運行線程，讓回收線程以單線程進行掃描標記，並進行直接清除回收，然後回收完成後，恢復運行線程。這樣會產生大量的空閒空間碎片，和使大容量對象不容易獲得連續的內存空間，而造成空間浪費。

標記－壓縮

和「標記－清除」相似，不同的是，回收期間同時會將保留的存儲對象搬運匯集到連續的內存空間，從而整合空閒空間，避免內存碎片化。

複製

需要程序將所擁有的內存空間分成兩個部分。程序運行所需的存儲對象先存儲在其中一個分區（定義為「分區0」）。同樣暫停整個程序的全部運行線程，進行標記後，回收期間將保留的存儲對象搬運匯集到另一個分區（定義為「分區1」），完成回收，程序在本次回收後將接下來產生的存儲對象會存儲到「分區1」。在下一次回收時，兩個分區的角色對調。

這種方式非常簡單，但是因為只有一個「半空間」（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世代則進行標記壓縮收集。

實作

GC機制可以是由程式語言本身提供的功能（如Java、C#），也可以是程序語言以外的第三方函式庫。例如貝姆垃圾收集器就是一種可支援C/C++語言的自動記憶體管理工具。

參見

• 內存管理
• 約翰·麥卡錫