動(dòng)圖圖解GC算法-讓垃圾回收動(dòng)起來(lái)！
提到Java中的垃圾回收，我相信很多小伙伴和我一樣，第一反應(yīng)就是面試必問(wèn)了，你要是沒(méi)背過(guò)點(diǎn)GC算法、收集器什么的知識(shí)，出門都不敢說(shuō)自己背過(guò)八股文。說(shuō)起來(lái)還真是有點(diǎn)尷尬，工作中實(shí)際用到這方面知識(shí)的場(chǎng)景真是不多，并且這東西學(xué)起來(lái)也很枯燥，但是奈何面試官就是愛(ài)問(wèn)，我們能有什么辦法呢?
既然已經(jīng)卷成了這樣，不學(xué)也沒(méi)有辦法，Hydra犧牲了周末時(shí)間，給大家畫了幾張動(dòng)圖，希望通過(guò)這幾張圖，能夠幫助大家對(duì)垃圾收集算法有個(gè)更好的理解。廢話不多說(shuō)，首先還是從基礎(chǔ)問(wèn)題開(kāi)始，看看怎么判斷一個(gè)對(duì)象是否應(yīng)該被回收。
判斷對(duì)象存活
垃圾回收的根本目的是利用一些算法進(jìn)行內(nèi)存的管理，從而有效的利用內(nèi)存空間，在進(jìn)行垃圾回收前，需要判斷對(duì)象的存活情況，在jvm中有兩種判斷對(duì)象的存活算法，下面分別進(jìn)行介紹。
1、引用計(jì)數(shù)算法
在對(duì)象中添加一個(gè)引用計(jì)數(shù)器，每當(dāng)有一個(gè)地方引用它時(shí)計(jì)數(shù)器就加 1，當(dāng)引用失效時(shí)計(jì)數(shù)器減 1。當(dāng)計(jì)數(shù)器為0的時(shí)候，表示當(dāng)前對(duì)象可以被回收。
這種方法的原理很簡(jiǎn)單，判斷起來(lái)也很高效，但是存在兩個(gè)問(wèn)題：
- 堆中對(duì)象每一次被引用和引用清除時(shí)，都需要進(jìn)行計(jì)數(shù)器的加減法操作，會(huì)帶來(lái)性能損耗
- 當(dāng)兩個(gè)對(duì)象相互引用時(shí)，計(jì)數(shù)器永遠(yuǎn)不會(huì)0。也就是說(shuō)，即使這兩個(gè)對(duì)象不再被程序使用，仍然沒(méi)有辦法被回收，通過(guò)下面的例子看一下循環(huán)引用時(shí)的計(jì)數(shù)問(wèn)題：
- public void reference(){
- A a = new A();
- B b = new B();
- a.instance = b;
- b.instance = a;
- }
引用計(jì)數(shù)的變化過(guò)程如下圖所示：
可以看到，在方法執(zhí)行完成后，棧中的引用被釋放，但是留下了兩個(gè)對(duì)象在堆內(nèi)存中循環(huán)引用，導(dǎo)致了兩個(gè)實(shí)例最后的引用計(jì)數(shù)都不為0，最終這兩個(gè)對(duì)象的內(nèi)存將一直得不到釋放，也正是因?yàn)檫@一缺陷，使引用計(jì)數(shù)算法并沒(méi)有被實(shí)際應(yīng)用在gc過(guò)程中。
2、可達(dá)性分析算法
可達(dá)性分析算法是jvm默認(rèn)使用的尋找垃圾的算法，需要注意的是，雖然說(shuō)的是尋找垃圾，但實(shí)際上可達(dá)性分析算法尋找的是仍然存活的對(duì)象。至于這樣設(shè)計(jì)的理由，是因?yàn)槿绻苯訉ふ覜](méi)有被引用的垃圾對(duì)象，實(shí)現(xiàn)起來(lái)相對(duì)復(fù)雜、耗時(shí)也會(huì)比較長(zhǎng)，反過(guò)來(lái)標(biāo)記存活的對(duì)象會(huì)更加省時(shí)。
可達(dá)性分析算法的基本思路就是，以一系列被稱為GC Roots的對(duì)象作為起始點(diǎn)，從這些節(jié)點(diǎn)開(kāi)始向下搜索，搜索所走過(guò)的路徑稱為引用鏈，當(dāng)一個(gè)對(duì)象到GC Roots沒(méi)有任何引用鏈相連時(shí)，證明該對(duì)象不再存活，可以作為垃圾被回收。
在java中，可作為GC Roots的對(duì)象有以下幾種：
- 在虛擬機(jī)棧(棧幀的本地變量表)中引用的對(duì)象
- 在方法區(qū)中靜態(tài)屬性引用的對(duì)象
- 在方法區(qū)中常量引用的對(duì)象
- 在本地方法棧中JNI(native方法)引用的對(duì)象
- jvm內(nèi)部的引用，如基本數(shù)據(jù)類型對(duì)應(yīng)的Class對(duì)象、一些常駐異常對(duì)象等，及系統(tǒng)類加載器
- 被同步鎖synchronized持有的對(duì)象引用
- 反映jvm內(nèi)部情況的 JMXBean、JVMTI中注冊(cè)的回調(diào)本地代碼緩存等
- 此外還有一些臨時(shí)性的GC Roots，這是因?yàn)槔占蠖嗖捎梅执占途植炕厥眨紤]到跨代或跨區(qū)域引用的對(duì)象時(shí)，就需要將這部分關(guān)聯(lián)的對(duì)象也添加到GC Roots中以確保準(zhǔn)確性
其中比較重要、同時(shí)提到的比較多的還是前面4種，其他的簡(jiǎn)單了解一下即可。在了解了jvm是如何尋找垃圾對(duì)象之后，我們來(lái)看一看不同的垃圾收集算法的執(zhí)行過(guò)程是怎樣的。
垃圾收集算法
1、標(biāo)記-清除算法
標(biāo)記清除算法是一種非常基礎(chǔ)的垃圾收集算法，當(dāng)堆中的有效內(nèi)存空間耗盡時(shí)，會(huì)觸發(fā)STW(stop the world)，然后分標(biāo)記和清除兩階段來(lái)進(jìn)行垃圾收集工作：
- 標(biāo)記：從GC Roots的節(jié)點(diǎn)開(kāi)始進(jìn)行掃描，對(duì)所有存活的對(duì)象進(jìn)行標(biāo)記，將其記錄為可達(dá)對(duì)象
- 清除：對(duì)整個(gè)堆內(nèi)存空間進(jìn)行掃描，如果發(fā)現(xiàn)某個(gè)對(duì)象未被標(biāo)記為可達(dá)對(duì)象，那么將其回收
通過(guò)下面的圖，簡(jiǎn)單的看一下兩階段的執(zhí)行過(guò)程：
但是這種算法會(huì)帶來(lái)幾個(gè)問(wèn)題：
- 在進(jìn)行GC時(shí)會(huì)產(chǎn)生STW，停止整個(gè)應(yīng)用程序，造成用戶體驗(yàn)較差
- 標(biāo)記和清除兩個(gè)階段的效率都比較低，標(biāo)記階段需要從根集合進(jìn)行掃描，清除階段需要對(duì)堆內(nèi)所有的對(duì)象進(jìn)行遍歷
- 僅對(duì)非存活的對(duì)象進(jìn)行處理，清除之后會(huì)產(chǎn)生大量不連續(xù)的內(nèi)存碎片。導(dǎo)致之后程序在運(yùn)行時(shí)需要分配較大的對(duì)象時(shí)，無(wú)法找到足夠的連續(xù)內(nèi)存，會(huì)再觸發(fā)一次新的垃圾收集動(dòng)作
此外，jvm并不是真正的把垃圾對(duì)象進(jìn)行了遍歷，把內(nèi)部的數(shù)據(jù)都刪除了，而是把垃圾對(duì)象的首地址和尾地址進(jìn)行了保存，等到再次分配內(nèi)存時(shí)，直接去地址列表中分配，通過(guò)這一措施提高了一些標(biāo)記清除算法的效率。
2、復(fù)制算法
復(fù)制算法主要被應(yīng)用于新生代，它將內(nèi)存分為大小相同的兩塊，每次只使用其中的一塊。在任意時(shí)間點(diǎn)，所有動(dòng)態(tài)分配的對(duì)象都只能分配在其中一個(gè)內(nèi)存空間，而另外一個(gè)內(nèi)存空間則是空閑的。復(fù)制算法可以分為兩步：
- 當(dāng)其中一塊內(nèi)存的有效內(nèi)存空間耗盡后，jvm會(huì)停止應(yīng)用程序運(yùn)行，開(kāi)啟復(fù)制算法的gc線程，將還存活的對(duì)象復(fù)制到另一塊空閑的內(nèi)存空間。復(fù)制后的對(duì)象會(huì)嚴(yán)格按照內(nèi)存地址依次排列，同時(shí)gc線程會(huì)更新存活對(duì)象的內(nèi)存引用地址，指向新的內(nèi)存地址
- 在復(fù)制完成后，再把使用過(guò)的空間一次性清理掉，這樣就完成了使用的內(nèi)存空間和空閑內(nèi)存空間的對(duì)調(diào)，使每次的內(nèi)存回收都是對(duì)內(nèi)存空間的一半進(jìn)行回收
通過(guò)下面的圖來(lái)看一下復(fù)制算法的執(zhí)行過(guò)程：
復(fù)制算法的的優(yōu)點(diǎn)是彌補(bǔ)了標(biāo)記清除算法中，會(huì)出現(xiàn)內(nèi)存碎片的缺點(diǎn)，但是它也同樣存在一些問(wèn)題：
只使用了一半的內(nèi)存，所以內(nèi)存的利用率較低，造成了浪費(fèi)
如果對(duì)象的存活率很高，那么需要將很多對(duì)象復(fù)制一遍，并且更新它們的應(yīng)用地址，這一過(guò)程花費(fèi)的時(shí)間會(huì)非常的長(zhǎng)
從上面的缺點(diǎn)可以看出，如果需要使用復(fù)制算法，那么有一個(gè)前提就是要求對(duì)象的存活率要比較低才可以，因此，復(fù)制算法更多的被用于對(duì)象“朝生暮死”發(fā)生更多的新生代中。
3、標(biāo)記-整理算法
標(biāo)記整理算法和標(biāo)記清除算法非常的類似，主要被應(yīng)用于老年代中。可分為以下兩步：
標(biāo)記：和標(biāo)記清除算法一樣，先進(jìn)行對(duì)象的標(biāo)記，通過(guò)GC Roots節(jié)點(diǎn)掃描存活對(duì)象進(jìn)行標(biāo)記
整理：將所有存活對(duì)象往一端空閑空間移動(dòng)，按照內(nèi)存地址依次排序，并更新對(duì)應(yīng)引用的指針，然后清理末端內(nèi)存地址以外的全部?jī)?nèi)存空間
標(biāo)記整理算法的執(zhí)行過(guò)程如下圖所示：
可以看到，標(biāo)記整理算法對(duì)前面的兩種算法進(jìn)行了改進(jìn)，一定程度上彌補(bǔ)了它們的缺點(diǎn)：
- 相對(duì)于標(biāo)記清除算法，彌補(bǔ)了出現(xiàn)內(nèi)存空間碎片的缺點(diǎn)
- 相對(duì)于復(fù)制算法，彌補(bǔ)了浪費(fèi)一半內(nèi)存空間的缺點(diǎn)
但是同樣，標(biāo)記整理算法也有它的缺點(diǎn)，一方面它要標(biāo)記所有存活對(duì)象，另一方面還添加了對(duì)象的移動(dòng)操作以及更新引用地址的操作，因此標(biāo)記整理算法具有更高的使用成本。
4、分代收集算法
實(shí)際上，java中的垃圾回收器并不是只使用的一種垃圾收集算法，當(dāng)前大多采用的都是分代收集算法。jvm一般根據(jù)對(duì)象存活周期的不同，將內(nèi)存分為幾塊，一般是把堆內(nèi)存分為新生代和老年代，再根據(jù)各個(gè)年代的特點(diǎn)選擇最佳的垃圾收集算法。主要思想如下：
新生代中，每次收集都會(huì)有大量對(duì)象死去，所以可以選擇復(fù)制算法，只需要復(fù)制少量對(duì)象以及更改引用，就可以完成垃圾收集
老年代中，對(duì)象存活率比較高，使用復(fù)制算法不能很好的提高性能和效率。另外，沒(méi)有額外的空間對(duì)它進(jìn)行分配擔(dān)保，因此選擇標(biāo)記清除或標(biāo)記整理算法進(jìn)行垃圾收集
通過(guò)圖來(lái)簡(jiǎn)單看一下各種算法的主要應(yīng)用區(qū)域：
至于為什么在某一區(qū)域選擇某種算法，還是和三種算法的特點(diǎn)息息相關(guān)的，再?gòu)?個(gè)維度進(jìn)行一下對(duì)比：
- 執(zhí)行效率：從算法的時(shí)間復(fù)雜度來(lái)看，復(fù)制算法最優(yōu)，標(biāo)記清除次之，標(biāo)記整理最低
- 內(nèi)存利用率：標(biāo)記整理算法和標(biāo)記清除算法較高，復(fù)制算法最差
- 內(nèi)存整齊程度：復(fù)制算法和標(biāo)記整理算法較整齊，標(biāo)記清除算法最差
盡管具有很多差異，但是除了都需要進(jìn)行標(biāo)記外，還有一個(gè)相同點(diǎn)，就是在gc線程開(kāi)始工作時(shí)，都需要STW暫停所有工作線程。
總結(jié)
本文中，我們先介紹了垃圾收集的基本問(wèn)題，什么樣的對(duì)象可以作為垃圾被回收?jvm中通過(guò)可達(dá)性分析算法解決了這一關(guān)鍵問(wèn)題，并在它的基礎(chǔ)上衍生出了多種常用的垃圾收集算法，不同算法具有各自的優(yōu)缺點(diǎn)，根據(jù)其特點(diǎn)被應(yīng)用于各個(gè)年代。
雖然這篇文章嘮嘮叨叨了這么多，不過(guò)這些都還是基礎(chǔ)的知識(shí)，如果想要徹底的掌握jvm中的垃圾收集，后續(xù)還有垃圾收集器、內(nèi)存分配等很多的知識(shí)需要理解，不過(guò)我們今天就介紹到這里啦，希望通過(guò)這一篇圖解，能夠幫助大家更好的理解垃圾收集算法。
本文轉(zhuǎn)載自微信公眾號(hào)「碼農(nóng)參上」，可以通過(guò)以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系碼農(nóng)參上公眾號(hào)。
