# 8.12 垃圾回收統一理論 所有的 GC 算法其存在形式可以歸結為追蹤（Tracing）和引用計數（Reference Counting）這兩種形式的混合運用。 * 追蹤式 GC：從根對象出發，根據對象之間的引用信息，一步步推進直到掃描完畢整個堆并確定需要保留的對象，從而回收所有可回收的對象。 * 引用計數式 GC：每個對象自身包含一個被引用的計數器，當計數器歸零時自動得到回收。因為此方法缺陷較多，在追求高性能時通常不被應用。 目前比較常見的 GC 實現方式包括： * 追蹤式，分為多種不同類型，例如： * 標記清掃：從根對象出發，將確定存活的對象進行標記，并清掃可以回收的對象。 * 標記整理：為了解決內存碎片問題而提出，在標記過程中，將對象盡可能整理到一塊連續的內存上。 * 增量式：將標記與清掃的過程分批執行，每次執行很小的部分，從而增量的推進垃圾回收，達到近似實時、幾乎無停頓的目的。 * 增量整理：在增量式的基礎上，增加對對象的整理過程。 * 分代式：將對象根據存活時間的長短進行分類，存活時間小于某個值的為年輕代，存活時間大于某個值的為老年代，永遠不會參與回收的對象為永久代。并根據分代假設（如果一個對象存活時間不長則傾向于被回收，如果一個對象已經存活很長時間則傾向于存活更長時間）對對象進行回收。 * 引用計數：根據對象自身的引用計數來回收，當引用計數歸零時立即回收。 ## 追蹤式 GC TODO: ## 引用計數式 GC TODO: ## 垃圾回收統一定理 雖然在實踐中我們有追蹤式和引用計數式兩種 GC 的形式，但在理論上我們能夠對其進行統一描述， 這就是**垃圾回收統一定理**（Unified Theory of GC） \[Bacon et al. 2004\]。 內存中對象及其指針所組成了一個對象圖，我們不妨令所有對象組成的集合為VV， 設指針所指鏈接對象的多重集為EE。由于我們不應該釋放一個會在未來會被使用的對象， 如果我們不對任何賦值器進行分析而是進行保守地估計，則如果從棧或寄存器出發存在到達對象的路徑， 則該對象將在未來被使用，記這些路徑的起始對象組成的集合為根集合RR。則對象的引用計數ρ(v)ρ(v)（其中v∈Vv∈V）可以由下述的遞歸定點表示進行計算： ρ(v)\=|\[v:v∈R\]|+|\[(w,v):(w,v)∈E∧ρ(w)\>0\]|ρ(v)\=|\[v:v∈R\]|+|\[(w,v):(w,v)∈E∧ρ(w)\>0\]| TODO: 將 追蹤式和引用計數式 GC 用定點表示進行描述 TODO: 討論統一定理的指導意義 ## 進一步閱讀的參考文獻 * \[Bacon et al. 2004\] Bacon, David F., Perry Cheng, and V. T. Rajan. “A unified theory of garbage collection.” ACM SIGPLAN Notices 39.10 (2004): 50-68.