六種主要的垃圾回收算法和思想

首發于 https://www.amoshuang.com/archives/1911

Java語言的一大特點就是可以自動進行垃圾回收處理，無需開發人員過于關注系統資源的釋放情況。自動垃圾收集雖然大大減輕了開發人員的工作量，但是也增加了軟體系統的負擔。一個不合适的垃圾回收方法和政策将會對系統性能造成不良影響。

1. 引用計數法

引用計數法是最經典古老的一種垃圾收集方法，它的實作也很簡單：對于一個對象A，隻要有任何一個對象引用了A，則A的計數器就加1，當引用失效時，引用計數器就減1.隻要對象A的引用計數器的值為0，則對象A就不可能再被使用。

引用計數法實作簡單，隻需要為每一個對象配備一個整型計數器即可。但是，它存在一個很嚴重的問題，即無法處理循環引用的情況，是以在Java的垃圾回收器中沒有使用這種算法。

一個簡單的循環引用示例如下：

對象A和對象B循環引用，此時他們的引用計數器都不為0，但是在系統中已經找不到第三個對象引用了A或者B，也就是說，A和B應該是被回收的垃圾。但是因為循環引用而無法被識别，最終可能會導緻記憶體洩漏。

2. 标記-清除法

标記-清除法是現代垃圾回收算法的基礎。

它将垃圾回收分為兩個階段：标記階段和清除階段。一種可行的實作是：

1. 在标記階段，标記所有從根節點出發的可達對象。是以，所有未被标記的對象就是未被引用的垃圾對象。
2. 在清除階段，清除所有未被标記的對象。

而标記-清除法可能産生的最大問題就是空間碎片。回收之後的空間不是連續的，不連續的記憶體空間的工作效率要低于連續的空間，這是标記-清除法最大的缺點。

3.複制算法

與标記-清除法相比，複制算法是一種相對高效的回收算法。

它的核心思想是：将記憶體分為兩部分，每次隻使用其中一部分。在垃圾回收時，将正在使用的記憶體中的存貨對象複制到未使用的記憶體塊中，之後清除正在使用的記憶體塊中的所有對象，交換兩個記憶體的角色，完成垃圾回收。

如果系統中的垃圾對象很多，那麼複制算法需要複制的存活對象的數量也不會很多，是以當需要使用複制算法時還是比較高效的。又因為所有對象都會被統一複制到新的記憶體空間中，是以可以保證回收後的記憶體空間是沒有碎片的。

雖然有以上兩大有點，但是複制算法的代價缺點是将系統記憶體折半。是以單純的複制算法會讓人無法接受。

在Java的新生代串行垃圾回收器中，使用了複制算法。新生代分為eden空間、from空間和to空間三個部分。其中from和to空間可以視為用于複制的兩塊大小相同、地位相等，且角色可以互換的空間塊，它們也被稱為survivor空間，即幸存者空間，用于存放未被回收的對象。

在垃圾回收時，eden空間中的存活對象會被複制到未使用的survivor空間中（假設為to），正在使用的survivor空間（假設為from）中的年輕對象也會被複制到to空間中（大對象或者老年對象會直接進入老年代，如果to空間已經滿了，則對象也會直接進入老年代）。此時eden和from空間中的剩餘對象将都是垃圾對象，可以直接清空，to空間則存放此次回收後存活的對象。

這樣改進後的複制算法既保證了空間的連續性，又避免大量記憶體空間被浪費。

4. 标記-壓縮算法

複制算法的高效性是建立在存活對象少，垃圾對象多的前提下。這種情況普遍存在于年輕代，但是在老年代，更常見的情況是大部分對象都是存活對象，如果使用複制算法，由于存活對象多，複制的成本也會很高。

基于老年代垃圾回收的特性，需要使用新的算法，而标記-壓縮算法是老年代的一種回收算法，它在标記-清除算法之上做了一些優化。

它和标記-清除算法不同之處在于：在清除階段，它會将所有的存活對象壓縮到記憶體的另一端。之後清理邊界之外的所有空間。這種算法既避免了碎片的産生，又不需要兩塊相同的記憶體空間，是以成本效益較高。

5. 增量算法

對大部分的垃圾回收算法而言，在垃圾回收的過程中，應用軟體的所有線程都會挂起，暫停一切正常工作，等待來回收的完成。如果垃圾回收時間很長，則應用程式會被挂起很久，這會嚴重影響使用者體驗和系統穩定性。

增量算法的基本思想就是，讓垃圾回收線程和應用線程交替執行，每次隻收集一小片區域的記憶體空間，接着切換應用程式線程。如此往複知道垃圾回收完成。

使用這種方式進行垃圾回收可以減少系統的停頓時間，但是因為線程切換和上下文轉換的消耗，會使得垃圾回收的總體成本上升，造成系統吞吐量的下降。

6.分代

前面介紹的幾種垃圾回收算法沒有哪一種可以完全替代其他算法，它們有各自的優點和缺點。是以，根據垃圾回收對象的特性，使用合适的算法回收，才是明智的選擇。

分代就是基于這種思想，它将記憶體區域根據對象特點分為幾塊，根據每塊記憶體區間的特點，使用不同的回收算法，提高垃圾回收的效率。