垃圾回收 (電腦科學)
提示：此條目的主題不是垃圾回收。在電腦科學中，垃圾回收（英語：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：
- Eden：存放新生物件。
- Survivor：存放經過垃圾回收沒有被清除的物件。
- 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]
實作
GC機制可以是由程式語言本身提供的功能（如Java、C#），也可以是程式語言以外的第三方函式庫。例如貝姆垃圾收集器就是一種可支援C/C++語言的自動記憶體管理工具。
參見
參考文獻
- ^ Recursive functions of symbolic expressions and their computation by machine, Part I. Portal.acm.org. [29 March 2009].
- ^ Recursive functions of symbolic expressions and their computation by machine, Part I. [29 May 2009]. （原始內容存檔於2013-10-04）.
- ^ 3.0 3.1 吳, 昊; 季, 振洲. 一种基于半空间的不完全拷贝垃圾回收机制. 哈爾濱工業大學學報. 2011, 43 (11): 60–64 [2020-03-27]. ISSN 0367-6234. （原始內容存檔於2020-05-28）.
- ^ 分代-JVM文档. [2020-03-28]. （原始內容存檔於2020-03-28） （英語）.
