你應該聽說過這麼一句話：免費的其實是最貴的。
Java 虛拟機的自動記憶體管理，将原本需要由開發人員手動回收的記憶體，交給垃圾回收器來自動回收。不過既然是自動機制，肯定沒法做到像手動回收那般精準高效[1] ，而且還會帶來不少與垃圾回收實作相關的問題。
接下來的兩篇，我們會深入探索 Java 虛拟機中的垃圾回收器。今天這一篇，我們來回顧一下垃圾回收的基礎知識。
- 引用計數法與可達性分析
- 引用計數法
- 可達性分析算法
- Stop-the-world 以及安全點
- 垃圾回收的三種方式
- 清楚
- 壓縮
- 複制
- 總結與實踐
引用計數法與可達性分析
垃圾回收，顧名思義，便是将已經配置設定出去的，但卻不再使用的記憶體回收回來，以便能夠再次配置設定。在 Java 虛拟機的語境下，垃圾指的是死亡的對象所占據的堆空間。這裡便涉及了一個關鍵的問題：如何辨識一個對象是存是亡？
引用計數法
我們先來講一種古老的辨識方法：引用計數法（reference counting）。它的做法是為每個對象添加一個引用計數器，用來統計指向該對象的引用個數。一旦某個對象的引用計數器為 0，則說明該對象已經死亡，便可以被回收了。
它的具體實作是這樣子的：如果有一個引用，被指派為某一對象，那麼将該對象的引用計數器 +1。如果一個指向某一對象的引用，被指派為其他值，那麼将該對象的引用計數器 -1。也就是說，我們需要截獲所有的引用更新操作，并且相應地增減目标對象的引用計數器。
除了需要額外的空間來存儲計數器，以及繁瑣的更新操作，引用計數法還有一個重大的漏洞，那便是無法處理循環引用對象。
舉個例子，假設對象 a 與 b 互相引用，除此之外沒有其他引用指向 a 或者 b。在這種情況下，a 和 b 實際上已經死了，但由于它們的引用計數器皆不為 0，在引用計數法的心中，這兩個對象還活着。是以，這些循環引用對象所占據的空間将不可回收，進而造成了記憶體洩露。
可達性分析算法
目前 Java 虛拟機的主流垃圾回收器采取的是可達性分析算法。這個算法的實質在于将一系列 GC Roots 作為初始的存活對象合集（live set），然後從該合集出發，探索所有能夠被該集合引用到的對象，并将其加入到該集合中，這個過程我們也稱之為标記（mark）。最終，未被探索到的對象便是死亡的，是可以回收的。
那麼什麼是 GC Roots 呢？我們可以暫時了解為由堆外指向堆内的引用，一般而言，GC Roots 包括（但不限于）如下幾種：
- Java 方法棧桢中的局部變量；
- 已加載類的靜态變量；
- JNI handles；
- 已啟動且未停止的 Java 線程。
可達性分析可以解決引用計數法所不能解決的循環引用問題。舉例來說，即便對象 a 和 b 互相引用，隻要從 GC Roots 出發無法到達 a 或者 b，那麼可達性分析便不會将它們加入存活對象合集之中。
雖然可達性分析的算法本身很簡明，但是在實踐中還是有不少其他問題需要解決的。
比如說，在多線程環境下，其他線程可能會更新已經通路過的對象中的引用，進而造成誤報（将引用設定為 null）或者漏報（将引用設定為未被通路過的對象）。
誤報并沒有什麼傷害，Java 虛拟機至多損失了部分垃圾回收的機會。漏報則比較麻煩，因為垃圾回收器可能回收事實上仍被引用的對象記憶體。一旦從原引用通路已經被回收了的對象，則很有可能會直接導緻 Java 虛拟機崩潰。
Stop-the-world 以及安全點
怎麼解決這個問題呢？在 Java 虛拟機裡，傳統的垃圾回收算法采用的是一種簡單粗暴的方式，那便是 Stop-the-world，停止其他非垃圾回收線程的工作，直到完成垃圾回收。這也就造成了垃圾回收所謂的暫停時間（GC pause）。
Java 虛拟機中的 Stop-the-world 是通過安全點（safepoint）機制來實作的。當 Java 虛拟機收到 Stop-the-world 請求，它便會等待所有的線程都到達安全點，才允許請求 Stop-the-world 的線程進行獨占的工作。
這篇部落格[2]還提到了一種比較另類的解釋：安全詞。一旦垃圾回收線程喊出了安全詞，其他非垃圾回收線程便會一一停下。
當然，安全點的初始目的并不是讓其他線程停下，而是找到一個穩定的執行狀态。在這個執行狀态下，Java 虛拟機的堆棧不會發生變化。這麼一來，垃圾回收器便能夠“安全”地執行可達性分析。
舉個例子，當 Java 程式通過 JNI 執行本地代碼時，如果這段代碼不通路 Java 對象、調用 Java 方法或者傳回至原 Java 方法，那麼 Java 虛拟機的堆棧不會發生改變，也就代表着這段本地代碼可以作為同一個安全點。
隻要不離開這個安全點，Java 虛拟機便能夠在垃圾回收的同時，繼續運作這段本地代碼。
由于本地代碼需要通過 JNI 的 API 來完成上述三個操作，是以 Java 虛拟機僅需在 API 的入口處進行安全點檢測（safepoint poll），測試是否有其他線程請求停留在安全點裡，便可以在必要的時候挂起目前線程。
除了執行 JNI 本地代碼外，Java 線程還有其他幾種狀态：解釋執行位元組碼、執行即時編譯器生成的機器碼和線程阻塞。阻塞的線程由于處于 Java 虛拟機線程排程器的掌控之下，是以屬于安全點。
其他幾種狀态則是運作狀态，需要虛拟機保證在可預見的時間内進入安全點。否則，垃圾回收線程可能長期處于等待所有線程進入安全點的狀态，進而變相地提高了垃圾回收的暫停時間。
對于解釋執行來說，位元組碼與位元組碼之間皆可作為安全點。Java 虛拟機采取的做法是，當有安全點請求時，執行一條位元組碼便進行一次安全點檢測。
執行即時編譯器生成的機器碼則比較複雜。由于這些代碼直接運作在底層硬體之上，不受 Java 虛拟機掌控，是以在生成機器碼時，即時編譯器需要插入安全點檢測，以避免機器碼長時間沒有安全點檢測的情況。HotSpot 虛拟機的做法便是在生成代碼的方法出口以及非計數循環的循環回邊（back-edge）處插入安全點檢測。
那麼為什麼不在每一條機器碼或者每一個機器碼基本塊處插入安全點檢測呢？原因主要有兩個。
第一，安全點檢測本身也有一定的開銷。不過 HotSpot 虛拟機已經将機器碼中安全點檢測簡化為一個記憶體通路操作。在有安全點請求的情況下，Java 虛拟機會将安全點檢測通路的記憶體所在的頁設定為不可讀，并且定義一個 segfault 處理器，來截獲因通路該不可讀記憶體而觸發 segfault 的線程，并将它們挂起。
第二，即時編譯器生成的機器碼打亂了原本棧桢上的對象分布狀況。在進入安全點時，機器碼還需提供一些額外的資訊，來表明哪些寄存器，或者目前棧幀上的哪些記憶體空間存放着指向對象的引用，以便垃圾回收器能夠枚舉 GC Roots。
由于這些資訊需要不少空間來存儲，是以即時編譯器會盡量避免過多的安全點檢測。
不過，不同的即時編譯器插入安全點檢測的位置也可能不同。以 Graal 為例，除了上述位置外，它還會在計數循環的循環回邊處插入安全點檢測。其他的虛拟機也可能選取方法入口而非方法出口來插入安全點檢測。
不管如何，其目的都是在可接受的性能開銷以及記憶體開銷之内，避免機器碼長時間不進入安全點的情況，間接地減少垃圾回收的暫停時間。
除了垃圾回收之外，Java 虛拟機其他一些對堆棧内容的一緻性有要求的操作也會用到安全點這一機制。我會在涉及的時侯再進行具體的講解。
垃圾回收的三種方式
當标記完所有的存活對象時，我們便可以進行死亡對象的回收工作了。主流的基礎回收方式可分為三種。
清楚
第一種是清除（sweep），即把死亡對象所占據的記憶體标記為空閑記憶體，并記錄在一個空閑清單（free list）之中。當需要建立對象時，記憶體管理子產品便會從該空閑清單中尋找空閑記憶體，并劃分給建立的對象。
清除這種回收方式的原理及其簡單，但是有兩個缺點。一是會造成記憶體碎片。由于 Java 虛拟機的堆中對象必須是連續分布的，是以可能出現總空閑記憶體足夠，但是無法配置設定的極端情況。
另一個則是配置設定效率較低。如果是一塊連續的記憶體空間，那麼我們可以通過指針加法（pointer bumping）來做配置設定。而對于空閑清單，Java 虛拟機則需要逐個通路清單中的項，來查找能夠放入建立對象的空閑記憶體。
壓縮
第二種是壓縮（compact），即把存活的對象聚集到記憶體區域的起始位置，進而留下一段連續的記憶體空間。這種做法能夠解決記憶體碎片化的問題，但代價是壓縮算法的性能開銷。
複制
第三種則是複制（copy），即把記憶體區域分為兩等分，分别用兩個指針 from 和 to 來維護，并且隻是用 from 指針指向的記憶體區域來配置設定記憶體。當發生垃圾回收時，便把存活的對象複制到 to 指針指向的記憶體區域中，并且交換 from 指針和 to 指針的内容。複制這種回收方式同樣能夠解決記憶體碎片化的問題，但是它的缺點也極其明顯，即堆空間的使用效率極其低下。
當然，現代的垃圾回收器往往會綜合上述幾種回收方式，綜合它們優點的同時規避它們的缺點。在下一篇中我們會詳細介紹 Java 虛拟機中垃圾回收算法的具體實作。
總結與實踐
今天我介紹了垃圾回收的一些基礎知識。
Java 虛拟機中的垃圾回收器采用可達性分析來探索所有存活的對象。它從一系列 GC Roots 出發，邊标記邊探索所有被引用的對象。
為了防止在标記過程中堆棧的狀态發生改變，Java 虛拟機采取安全點機制來實作 Stop-the-world 操作，暫停其他非垃圾回收線程。
回收死亡對象的記憶體共有三種方式，分别為：會造成記憶體碎片的清除、性能開銷較大的壓縮、以及堆使用效率較低的複制。
今天的實踐環節，你可以體驗一下無安全點檢測的計數循環帶來的長暫停。你可以分别測單獨跑 foo 方法或者 bar 方法的時間，然後與合起來跑的時間比較一下。
/*
* time java SafepointTestp
* 你還可以使用如下幾個選項
* -XX:+PrintGC
* -XX:+PrintGCApplicationStoppedTime
* -XX:+PrintSafepointStatistics
* -XX:+UseCountedLoopSafepoints
*/
public class SafepointTest {
static double sum = 0;
public static void foo() {
for (int i = 0; i < 0x77777777; i++) {
sum += Math.sqrt(i);
}
}
public static void bar() {
for (int i = 0; i < 50_000_000; i++) {
new Object().hashCode();
}
}
public static void main(String[] args) {
new Thread(SafepointTest::foo).start();
new Thread(SafepointTest::bar).start();
}
}
作者：PP傑
博學之，審問之，慎思之，明辨之，笃行之。