3.3 記憶體管理：垃圾回收演算法（標記清除、複製、分代）#

為何虛擬機需要垃圾回收#

程序虛擬機幾乎都內建垃圾回收（Garbage Collection, GC），這不是偶然。第一，位元碼 ISA 通常直接提供 new 類指令（JVM 的 new、Lua 的建表），語言層不暴露手動釋放，記憶體安全承諾才能貫徹（見 2.3 節：驗證器能證明位元碼不偽造指標，前提是懸垂指標根本不可能存在）。第二，GC 需要知道所有指標的位置，這要求精確的執行時期型別資訊——由 VM 統一管理物件佈局，比讓每個語言各自處理要可靠得多。歷史上 GC 的發明甚至早於虛擬機普及：John McCarthy 為了 Lisp（1958-1960，IBM 704）發明標記清除法，因為 Lisp 的 cons cell 程式如果手動釋放，正確性幾乎不可能由程式設計師保證。1960 年 Communications of the ACM 同一期刊出了三篇 GC 奠基論文：McCarthy 的標記清除、福島系統（Newell 等人）的參照計數、以及 Marvin Minsky 的複製演算法。此後六十餘年的 GC 演化，都是在為「吞吐量、延遲、空間開銷」這三角做工程折衷。

標記—清除（Mark-Sweep）#

最基礎的追蹤式 GC。從根集合（全域變數、執行緒堆疊、暫存器中的指標）出發，標記所有可達物件，再線性掃描堆積清除未標記者：

mark(root):
  worklist := {root}
  while worklist 非空:
    obj := worklist.pop()
    if obj 未標記:
      obj.marked := true
      for child in obj.references: worklist.push(child)

sweep():
  for obj in heap:
    if obj 未標記: 回收至 free list
    else: obj.marked := false   // 為下一輪準備

優點：實作簡單、不搬移物件（對 C/C++ 嵌入、與不支援指標更新的語言關鍵）。缺點：停頓時間與堆積大小成正比（全堆掃描）、清除後產生碎片、以及 free list 分配的區域性差。CPython 的引用計數為主、標記清除為輔（僅處理循環參照）屬於混合策略。

複製式回收（Copying / Semispace）#

Minsky 的想法：把堆積分成兩個等大的半空間（semispace），回收時把存活物件從 from-space 複製到 to-space，複製順序即成為緊密排列——分配只需一個指標前移（bump allocation），碎片問題消失，掃描成本只與存活量成正比（死物件不用掃）。Cheney 演算法（C.J. Cheney, 1970）以 to-space 本身當佇列，優雅地完成廣度優先複製：

cheneys:
  free := scan := to_space 開頭
  for root in roots: root := forward(root)
  while scan < free:
    for child in scan 的引用: child := forward(child)
    scan := 下一個物件
  交換 from/to 空間

forward(obj):
  if obj 已搬到 to-space: return obj.forwarded
  new := free; *new := *obj; obj.forwarded := new; free += size(obj)
  return new

代價：空間使用率只有 50%，且每次回收所有存活物件都要搬移。這個「以空間換時間與區域性」的取捨，成為後續所有演化型演算法的基礎。

分代假說與分代 GC#

1980 年代前後，兩個關鍵的實證觀察改變了 GC 設計：大多數物件朝生暮死（弱分代假說，weak generational hypothesis），且老物件很少引用新物件。David Ungar 在 1984 年的 Generation Scavenging（為 Smalltalk 設計）把複製式回收縮小到年輕代，徹底確立了分代架構：

+-----------+-----------+----------------------------+
| 新生代     |           |   老年代                    |
| eden | s0 | s1        |   （標記清除/標記整理）        |
+-----------+-----------+----------------------------+

新物件 → eden
eden 滿 → minor GC：存活者複製到 s0/s1（年齡+1）
年齡超過門檻 → 晉升（promotion）到老年代
老年代滿 → major/full GC（昂貴，機率低）

minor GC 只掃新生代，加上記憶集（remembered set / card table）處理老年代到新生代的跨代指標（否則得掃全堆找根），使絕大多數回收的停頓降到毫秒級。HotSpot 的 Serial、Parallel、G1、ZGC/Shenandoah，.NET 的 GC，以及幾乎所有現代 VM 都建立在分代骨架上。後續的演化主要在對付老年代大、停頓要低的雲端需求：G1（2004 論文、JDK 7 2012 年正式）把堆切成 region、增量回收；ZGC 與 Shenandoah（JDK 11-15 時代，2018-2020）以讀取屏障（load barrier）實現幾乎全程併發的搬移，把停頓壓到亞毫秒——技術代價是每次指標讀取都多一道屏障指令，這再次說明 GC 設計是 VM 指令集、編譯器（屏障內聯）與硬體（屏障代價）的三方妥協。

其他路線：引用計數與即時性#

參照計數（Collins, 1960）：每個物件記錄被引用次數，歸零即回收。優點是回收及時、分佈式（無全域停頓）；缺點是無法回收循環（CPython 因此輔以循環偵測器）、以及賦值操作的計數更新在高併發下成本高昂（需要原子操作）。近年 Swift、Rust 的取舍顯示引用計數在系統語言仍有生命力。

即時 GC（real-time GC）：嵌入式與音訊/遊戲領域要求停頓有嚴格上界，促成增量式 GC（Henry Baker 1978 的增量標記、Tarditi 1990 年代後的實務化）與寫入屏障（write barrier）技術，讓回收與程式執行交錯。這些技術後來成為併發收集器（Dijkstra 1978 的 on-the-fly 標記為理論起點）的基礎。

與作業系統的關聯#

GC 與 OS 的記憶體管理共享深刻的結構相似性：複製式 GC 的 semispace 對應分頁系統的工作集模型；分代 GC 對應作業系統的局部性原理與 LRU 近似（時鐘演算法）；而「頁面遷移」與「物件搬移」都仰賴「讓舊位址重定向到新位址」的間接層——分頁表之於頁面，如同轉發指標之於物件。現代 VM 甚至直接與 OS 合作：巨型堆積以 mmap 透明大頁配置、GC 觸發時機參考 OS 的可用記憶體信號、記憶體回還（uncommit）讓 VM 成為 OS 記憶體資源的好公民。可以說，GC 是在用戶空間中重建了作業系統的記憶體抽象，只是這次的「頁」換成了「物件」。

小結#

GC 的三塊基石——標記清除（簡單通用）、複製（緊湊快速但耗空間）、分代（以弱分代假說分而治之）——組合出現代 VM 的記憶體管理體系。設計空間的每個取捨都對應具體的工作負載證據與硬體約束；理解 GC 不僅是理解 VM，也是理解「以實測的物件生命週期統計來指導系統分層」這一工程方法論的絕佳案例。