今天，我爭(zhēng)取用三分鐘，說清楚JVM中的垃圾回收和三色標(biāo)記，倒計(jì)時(shí)，開始。

什么是垃圾

什么是垃圾

垃圾的定義

垃圾，在我們?nèi)粘Ｉ钪?，就是使用過后不再需要的東西。并且隨著時(shí)間的推移，你產(chǎn)生的垃圾會(huì)越來越多。怎么清理垃圾，何時(shí)清理垃圾，就顯得尤為重要，畢竟你也不希望你的家里充滿了垃圾吧？

而在計(jì)算機(jī)的世界里也是一樣，不管我給你一塊128m，256m，還是4g，8g，16g的內(nèi)存，它都是一個(gè)有限的空間，就像我們的房子，70平，80平，100平就這么大。我們的程序在運(yùn)行中也會(huì)產(chǎn)生垃圾，計(jì)算機(jī)中有無數(shù)的內(nèi)存對(duì)象，每一塊邏輯，每一個(gè)行為，都有可能產(chǎn)生新的對(duì)象，當(dāng)這些對(duì)象不再使用的時(shí)候，就變成了垃圾。這些垃圾，如果不及時(shí)合理的清理，計(jì)算機(jī)的內(nèi)存一樣會(huì)被吃滿，導(dǎo)致最終無法再正常運(yùn)行。

尋找垃圾

那么，計(jì)算機(jī)是怎么找垃圾的呢？
一般來說，有兩種算法能找出哪些內(nèi)存對(duì)象是垃圾——引用計(jì)數(shù)法和可達(dá)性分析法

引用計(jì)數(shù)法

想象一下，你爸媽買了一個(gè)玩具回家，這個(gè)玩具，你要玩，你哥哥要玩，你妹妹要玩，你們?nèi)齻€(gè)人都要玩，如果把這個(gè)玩具對(duì)比計(jì)算機(jī)中的內(nèi)存對(duì)象，那么這個(gè)對(duì)象的引用計(jì)數(shù)就是3。
假如有一天，你妹妹買了別的玩具，不再跟你們一塊玩你們的玩具，這個(gè)時(shí)候，這個(gè)玩具的引用計(jì)數(shù)就是2。
又過了幾天，你哥哥要上學(xué)去了，他也不再玩玩具了，這個(gè)玩具的引用計(jì)數(shù)就是1。
最后，你長大了，對(duì)玩具也沒興趣了，這個(gè)玩具的引用計(jì)數(shù)就變成了0。
這個(gè)時(shí)候，它就成了垃圾，是一個(gè)可以被扔掉，被清理掉的垃圾。

當(dāng)然了，引用計(jì)數(shù)法有什么問題嗎？有的！
男生小時(shí)候玩過四驅(qū)車吧，假如有一天，你媽媽跟你說，來，我們收拾一下，把你不用的四驅(qū)車零件扔了。
她拿起了一個(gè)輪圈問你，這個(gè)有用嗎，你說這個(gè)輪圈要套在輪轂上。于是她又拿起了你的輪轂問，這個(gè)有用嗎，你說這個(gè)輪轂要裝在輪圈里。
你媽啪的一巴掌就呼過來了，說，你的四驅(qū)車不是都有輪胎嗎，這倆多出來的你還要它干嘛？

這個(gè)問題就顯而易見了，對(duì)于輪圈來說，輪轂要用它，那么它的引用計(jì)數(shù)就是1，而對(duì)于輪轂來說，輪圈要用它，那么它的引用計(jì)數(shù)也是1。但是，這兄弟倆都是多出來的零件，所有的四驅(qū)車都有輪胎了，這倆多出來的零件誰也不需要了。對(duì)這倆的整體來說，它倆都是垃圾。

當(dāng)然了，對(duì)于我們?nèi)藖碚f，我們肯定輕而易舉就能知道，我不管你倆都用誰，你倆現(xiàn)在都是垃圾，都得扔掉。而對(duì)于計(jì)算機(jī)來說，就很困難了，在引用計(jì)數(shù)法里，計(jì)算機(jī)只看你身上的引用計(jì)數(shù)是不是0，只要不是0，我就不認(rèn)為你是垃圾，就不能清理你。這樣一來，這種垃圾就會(huì)越堆越多。這就是常說的引用計(jì)數(shù)法中的循環(huán)引用的問題，不止是兩個(gè)對(duì)象相互引用，甚至?xí)腥齻€(gè)四個(gè)對(duì)象循環(huán)引用。

可達(dá)性分析法

相比于引用計(jì)數(shù)法，可達(dá)性分析法就更能精確的找出誰是垃圾，誰不是垃圾了?？蛇_(dá)性分析法可以用一句話就概括了
順著根對(duì)象，找出所有有引用的對(duì)象，不在根對(duì)象的引用范圍內(nèi)的，都是垃圾

四驅(qū)車

這次，她不一個(gè)一個(gè)問你有沒有用了，她順著你的四驅(qū)車的車架子一個(gè)一個(gè)找零件，這個(gè)輪圈歸車A，這個(gè)軸承歸車B，那個(gè)馬達(dá)歸車C， 那個(gè)電池歸車D，就這樣，你媽媽就從ABCD四輛車找齊了所有他們用到的零件。

這時(shí)候，她再回頭看，誒？這個(gè)輪圈和輪轂，是不是多出來的？你說是。于是這倆，就成了垃圾。
再一看，這個(gè)馬達(dá)，那個(gè)電池，通通沒有用，全都是垃圾。

怎么清理垃圾

找到了垃圾，那么我們?cè)趺辞謇砝?？垃圾回收算法有很多，這里簡(jiǎn)單說說常見的幾種垃圾回收算法，以下算法均是基于可行性分析法尋找垃圾的

就拿我們小時(shí)候玩的游戲王卡片舉例吧，假如在你的房間整整齊齊的擺放一堆的卡片，你的小伙伴又不斷的送你新的卡片，這是你需要看看，把哪些卡片扔掉，哪些卡片留下

卡片

標(biāo)記-清除

標(biāo)記清除就很簡(jiǎn)單暴力。你就直接從你的卡片堆里找哪些不要的卡片，找到了，就扔掉。
扔完之后，你可能會(huì)發(fā)現(xiàn)，整整齊齊排列的卡片中，這里缺一塊，那里缺一塊，很難看。

標(biāo)記清除

如果這個(gè)時(shí)候，你有五張黑暗大法師的卡片（男生都懂得吧，五張卡片可以合成一個(gè)黑暗大法師），你想把它們放一塊，你就只能往最后面放，而不能插入到中間。（內(nèi)存空間碎片化）

標(biāo)記-復(fù)制

你把你的房間分成兩片區(qū)域，新來的卡片，你先把它扔在區(qū)域A，你看著差不多快堆滿的時(shí)候，想要清理一些不要的，你就會(huì)先把區(qū)域A里要用的卡片，一個(gè)一個(gè)拿出來，挨個(gè)整齊的擺放在區(qū)域B，完事之后，你再把區(qū)域A剩下的卡片全部扔掉。
這時(shí)候又不斷的來了一些新的卡片，你把他們繼續(xù)扔在區(qū)域B，你看著差不多快堆滿的時(shí)候，再把區(qū)域B要用的卡片一個(gè)一個(gè)拿出來，挨個(gè)整齊的擺放在區(qū)域A，完事之后，再把區(qū)域B剩下的卡片全部扔掉。如此往復(fù)。

標(biāo)記復(fù)制

這樣一來，你的這個(gè)房間的卡片中，不會(huì)有一個(gè)一個(gè)的洞，所有的卡片也都能整齊擺放。當(dāng)然了，你很快就會(huì)發(fā)現(xiàn)，這樣問題也很明顯，就是我能裝1000張卡片的房間，現(xiàn)在最多只能裝500張了，另一半要用來清理垃圾。（內(nèi)存空間利用率減半）

標(biāo)記-整理

你把房間里的卡片，一個(gè)一個(gè)的整理，把有用的排前面，沒用的扔后面，最后再把沒用的扔掉。這樣最后你也可以得到一個(gè)整齊擺放的干凈的房間，但是你會(huì)發(fā)現(xiàn)，要清理一次不用的卡片，會(huì)花費(fèi)你很多時(shí)間。

標(biāo)記整理

分代收集

這個(gè)算法其實(shí)沒有什么新鮮的東西，它只是在房間的規(guī)劃上更復(fù)雜了。它把房間分成了初始區(qū)（Eden），活躍A區(qū)（Survivor0），活躍B區(qū)（Survivor1）和老年區(qū)（Old）。

分代收集

簡(jiǎn)單來說，新來的卡片，你都會(huì)把它扔在初始區(qū)，你會(huì)不斷對(duì)初始區(qū)和兩個(gè)活躍區(qū)進(jìn)行掃描，看哪些卡片是不要的。

首先你會(huì)看初始區(qū)和活躍A區(qū)，把要用的卡片都一個(gè)一個(gè)放到活躍B區(qū)，然后再把初始區(qū)和活躍A區(qū)剩下的卡片都扔掉。這個(gè)過程其實(shí)就是上面說到的標(biāo)記復(fù)制算法，不同的是，我把卡片整理扔過去之后，需要在卡片的上面記個(gè)數(shù)。
好，再來一次掃描，你會(huì)看初始區(qū)和活躍B區(qū)，把要用的卡片都扔到活躍A區(qū)，然后把初始區(qū)和活躍B區(qū)剩下的卡片都扔掉，然后你再把這些卡片的計(jì)數(shù)加一。(YoungGC)

就這樣反反復(fù)復(fù)的折騰，直到有一次你再整理的時(shí)候，你發(fā)現(xiàn)有一堆卡片，它身上的計(jì)數(shù)都是達(dá)到15次了，也就是你整理了15次，它都是有用的，那么你毫不猶豫的把它們?nèi)拥搅死夏陞^(qū)，處于這個(gè)區(qū)域的卡片，掃描的頻率就會(huì)很低了，因?yàn)槟阒溃@些你都是要常用的。（升代）

又過了很久很久，你發(fā)現(xiàn)你的老年區(qū)的卡片堆到百分之七八十了，你覺得把老年區(qū)也一塊掃描了吧，于是你來了一次大清理，把老年區(qū)不要的卡片也都扔掉，這個(gè)期間，你告訴你的小伙伴（用戶線程），你等一會(huì)給我卡片，等我清理完了（標(biāo)記清除算法），你再給我。（Full GC）

又過了很久很久，你發(fā)現(xiàn)不管你整理初始區(qū)和兩個(gè)活躍區(qū)，還是老年區(qū)，你的卡片都是有用的，這個(gè)時(shí)候，你很難過的告訴你的小伙伴，你的卡堆滿了，再送也裝不下了（OOM）。

一邊產(chǎn)生垃圾一邊清理垃圾

我們每次在整理垃圾的時(shí)候，都需要用戶線程暫停，也就是一個(gè)很酷的單詞（STW——Stop The World），因?yàn)閮?nèi)存對(duì)象的引用關(guān)系是在不斷變化的，不暫停用戶線程，很難正確的進(jìn)行垃圾回收，像原來的Serial和Serial Old，PS（Parallel Scavenge）和PO（Parallel Old），其實(shí)都是需要STW來回收垃圾的。

很顯然，這對(duì)響應(yīng)要求高的程序是不能接受的，不能因?yàn)槟阍谇謇砝?，我就什么都不能干了吧？于是，三色?biāo)記算法誕生了。

三色標(biāo)記

別看它名字叫三色標(biāo)記，聽起來挺高大上，實(shí)際上它就是把對(duì)象分成了三個(gè)不同的狀態(tài)，掃描標(biāo)記垃圾的時(shí)候，會(huì)根據(jù)它的狀態(tài)來掃描。
三色分為黑白灰三個(gè)顏色，當(dāng)然，叫什么顏色無所謂，你要叫它紅綠藍(lán)，或青橙紫，都沒問題，它代表的就是三種狀態(tài)。

• 白色：還沒有被掃描到的對(duì)象。這樣對(duì)象，會(huì)被從頭掃描。
• 黑色：自己和自己的所有引用都被掃描完了的對(duì)象。這樣的對(duì)象，不會(huì)再被掃描。
• 灰色：自己和自己的所有引用中，一部分被掃描了，但還沒掃描完。這樣的對(duì)象，還需要繼續(xù)掃描。

在并發(fā)標(biāo)記的情況下，由于多線程在CPU時(shí)間片的分配是不確定的，很可能垃圾回收線程掃描到一半，CPU就切換到用戶線程了，所以用三色標(biāo)記法，可以記錄下當(dāng)前掃描的情況，以便于下次切回來的時(shí)候繼續(xù)掃描。

三色標(biāo)記的Bug

其實(shí)只要涉及到并發(fā)了，難免就會(huì)產(chǎn)生一些令人頭疼的Bug。
假如班級(jí)組織春游，老師（垃圾回收器）把班里的同學(xué)（內(nèi)存對(duì)象）分成了ABC三個(gè)小組，每個(gè)小組有一個(gè)小組長。
出發(fā)之前，老師開始點(diǎn)名，把A組的同學(xué)全部點(diǎn)完了，開始點(diǎn)B組，B組同學(xué)剛點(diǎn)完一半，老師想去上廁所，這時(shí)候老師跟三個(gè)組長分別說了一句話

跟A組的組長說，一會(huì)回來提醒我一下你們組點(diǎn)完了（黑色）
跟B組的組長說，一會(huì)回來提醒我，你們組點(diǎn)了一半，點(diǎn)到了誰誰誰（灰色）
跟C組的組長說，一會(huì)回來提醒我，你們組還沒開始點(diǎn)（白色）

于是當(dāng)前的三色標(biāo)記狀態(tài)如下：

三色標(biāo)記

多標(biāo)

即已經(jīng)標(biāo)記完的對(duì)象，有一個(gè)引用消失了

在老師上廁所的時(shí)候，A組有一位同學(xué)X（已經(jīng)點(diǎn)完名的那組），家里有點(diǎn)事，他的爸爸媽媽來學(xué)校把他接走了。
過了幾分鐘，老師回來了，老師繼續(xù)點(diǎn)名，點(diǎn)完了B組，點(diǎn)完了C組。好，大家一塊出發(fā)了。

X同學(xué)呢，就已經(jīng)回家了，但是老師還不知道，名單上依然有這么一個(gè)人（如果集體買雪糕或者集體買門票的話，就會(huì)始終多出來一個(gè)），因?yàn)樗诘腁組點(diǎn)名已經(jīng)點(diǎn)完了，所以等老師再回來的時(shí)候，也不會(huì)再點(diǎn)他的名字了，所以直到最后大家出發(fā)，老師也沒有發(fā)現(xiàn)少了一個(gè)人。

多標(biāo)

這就是三色標(biāo)記算法產(chǎn)生的浮動(dòng)垃圾。這部分的垃圾對(duì)程序的正確并不會(huì)產(chǎn)生什么影響，并且在老師下次點(diǎn)名的時(shí)候（下一次垃圾標(biāo)記），就能把X同學(xué)（浮動(dòng)垃圾）從名單上劃掉

漏標(biāo)

還是上面的情形，老師還是去上廁所了，這時(shí)候，B組有一位Y同學(xué)和他們組的一個(gè)同學(xué)產(chǎn)生矛盾了，一怒之下離開了B組（與B的小組長斷開引用），并加入了A組（與A的小組長建立引用）。
過了幾分鐘，老師回來了，老師繼續(xù)點(diǎn)名......由于Y同學(xué)離開了B組，所以老師點(diǎn)B名單的時(shí)候，不會(huì)點(diǎn)到Y(jié)，而老師已經(jīng)點(diǎn)過了A組的名單，因此也不會(huì)再回去點(diǎn)A組的同學(xué)了。這樣的話，Y同學(xué)就變得多余了（變成垃圾了），春游時(shí)老師買門票的時(shí)候，就不會(huì)給Y同學(xué)買門票。

漏標(biāo)

這個(gè)bug，可比浮動(dòng)垃圾的bug嚴(yán)重多了，這會(huì)直接導(dǎo)致程序出現(xiàn)bug，大家開發(fā)中引用的好好的對(duì)象，突然就null了，還一臉懵逼。

各種并發(fā)的垃圾回收器的算法，其實(shí)最主要需要解決的，就是這個(gè)bug

CMS的漏標(biāo)解決方案

CMS全稱是Concurrent Mark Sweep，即并發(fā)標(biāo)記清除，它主要分四個(gè)階段——初始標(biāo)記（掃描根節(jié)點(diǎn)，STW，但很快），并發(fā)標(biāo)記，重新標(biāo)記（STW，停頓最長），并發(fā)清除，它的誕生其實(shí)就是開辟一條并發(fā)垃圾回收的道路，起著承上啟下的作用，CMS就不過多展開了，這里主要說說它對(duì)于并發(fā)標(biāo)記的漏標(biāo)的處理方式——Increament Update增量更新。
其實(shí)理解起來非常簡(jiǎn)單，就是當(dāng)一個(gè)黑色的對(duì)象下面，產(chǎn)生了一個(gè)新的引用的時(shí)候，這個(gè)黑色的對(duì)象就變灰（寫屏障）。

還拿上面的例子舉例，當(dāng)Y同學(xué)要從B組跑到A組的時(shí)候，A組已經(jīng)是點(diǎn)完名的了，但是當(dāng)老師回來的時(shí)候，A組的組長報(bào)告老師說，我們組還有一個(gè)Y同學(xué)沒有點(diǎn)名，這時(shí)候，老師就能把這個(gè)Y同學(xué)點(diǎn)上了。

這樣一來，漏標(biāo)問題看似就解決了?？此平鉀Q了，看似解決了。

沒錯(cuò)，這里面還有相當(dāng)隱蔽的一個(gè)bug。
還是上面的例子，B組點(diǎn)了一半， 老師還是去上廁所了，這時(shí)候，C組還沒點(diǎn)名呢，C組有一個(gè)Z同學(xué)，跑B組來了，并且坐在已經(jīng)點(diǎn)完名的那片同學(xué)當(dāng)中，這時(shí)候老師回來了，接著點(diǎn)名，點(diǎn)完B組還沒點(diǎn)的同學(xué)和C組的同學(xué)，但是Z同學(xué)點(diǎn)不到名了，因?yàn)樗卦诹薆組已經(jīng)點(diǎn)完的那部分當(dāng)中，這種情況下，Z同學(xué)就不會(huì)被點(diǎn)上名。

CMS

這個(gè)比喻稍有不恰當(dāng)?shù)牡胤剑夯疑珜?duì)象中，假如有已經(jīng)掃描完的引用A和未掃描的引用B，垃圾回收線程暫停的時(shí)候，引用A指向了一個(gè)白色對(duì)象，這時(shí)候垃圾回收線程恢復(fù)的時(shí)候，不會(huì)再掃描A了，因?yàn)锳已經(jīng)掃描過了，這時(shí)候，A依然會(huì)被漏標(biāo)。

那CMS對(duì)于這樣的情況怎么解決的呢？嗯，就是STW，重新掃描一遍（重新標(biāo)記）。大家都別活了，從頭屢！
雖然說CMS的誕生就是為了解決STW的問題，但是STW時(shí)間最長的也是它。

G1的漏標(biāo)解決方案

G1，即Garbage first，是jdk1.8以后的主流垃圾回收器，后面有時(shí)間，可以再詳細(xì)講講G1的垃圾回收機(jī)制（基本上可以淘汰掉CMS了），這里還是以漏標(biāo)問題解決為主。G1對(duì)于漏標(biāo)問題的解決方案是SATB（Snapshot At Begining），即原始快照。當(dāng)灰色對(duì)象指向一個(gè)白色對(duì)象的引用消失時(shí)，我們會(huì)把這個(gè)引用記錄在GC堆棧中。三色標(biāo)記+SATB其實(shí)就是G1核心算法中的一部分了。

還是以上面的例子來說，老師上廁所去了，B組同學(xué)Y還是跑到了A組，同時(shí)，這位同學(xué)在黑板上寫，B組的Y。等老師回來的時(shí)候，老師看到了就會(huì)問Y，你現(xiàn)在到哪組了啊，Y說我到A組了，那么老師就會(huì)記上Y的名字（標(biāo)灰）。

G1

這樣的解決方法，其實(shí)就可以比較完美的解決了漏標(biāo)問題，雖然也有產(chǎn)生浮動(dòng)垃圾的bug，但是至少既能保證程序的正確性，又能保證垃圾回收的效率。

關(guān)于G1，其實(shí)還有很多不同于CMS的優(yōu)化算法，有時(shí)間再研究研究，寫一篇G1的分析

看到這里，不知道大家有沒有計(jì)時(shí)，有沒有三分鐘內(nèi)看完，如果沒有的話，那我下次再節(jié)省一點(diǎn)篇幅，爭(zhēng)取用最簡(jiǎn)單語言，最形象的比喻，描述最晦澀的技術(shù)點(diǎn)。

對(duì)于JVM的垃圾定義，垃圾回收，以及三色標(biāo)記，網(wǎng)上其實(shí)能搜到的文章教程一大堆，但是我發(fā)現(xiàn)很少有人能把它們和實(shí)際生活作比喻。所以我想，或許我可以嘗試用自己的理解，根據(jù)實(shí)際情況，用形象的比喻來表達(dá)晦澀難懂的技術(shù)細(xì)節(jié)。用白話文表達(dá)出來，既能把復(fù)雜的東西簡(jiǎn)單化，對(duì)自己來說也能把核心點(diǎn)理解的更透徹。

如果每一個(gè)晦澀的知識(shí)點(diǎn)，都能通過形象的比喻，用三分鐘把它描述清楚，那么相信大家理解起來也會(huì)非常容易，看技術(shù)文章也能像看故事一樣。