建站
咨詢
售后
建站咨詢
新聞中心
我們都知道， 當(dāng)JVM判斷對(duì)象不再存活的時(shí)候，便會(huì)在下一次GC時(shí)候?qū)⒃搶?duì)象回收掉，為堆騰出空間，而JVM判斷對(duì)象存活的算法大家比較熟知的有兩種，分別是引用計(jì)數(shù)法和可達(dá)性分析算法
- 引用計(jì)數(shù)法：給對(duì)象中添加一個(gè)引用計(jì)數(shù)器，每當(dāng)有一個(gè)地方引用它，計(jì)數(shù)器就加 1；當(dāng)引用失效，計(jì)數(shù)器就減 1；任何時(shí)候計(jì)數(shù)器為 0 的對(duì)象就是不可能再被使用的。這個(gè)方法實(shí)現(xiàn)簡(jiǎn)單，效率高，但是目前主流的虛擬機(jī)中并沒有選擇這個(gè)算法來管理內(nèi)存，其最主要的原因是它很難解決對(duì)象之間相互循環(huán)引用的問題。
- 可達(dá)性分析算法：這個(gè)算法的基本思想就是通過一系列的稱為 “GC Roots” 的對(duì)象作為起點(diǎn)，從這些節(jié)點(diǎn)開始向下搜索，節(jié)點(diǎn)所走過的路徑稱為引用鏈，當(dāng)一個(gè)對(duì)象到 GC Roots 沒有任何引用鏈相連的話，則證明此對(duì)象是不可用的。
但是這兩種算法其實(shí)并不完美，主要存在以下問題：
1、循環(huán)引用問題，如果兩個(gè)對(duì)象互相引用，就形成了一個(gè)環(huán)形結(jié)構(gòu)，如果采用引用計(jì)數(shù)法的話，那么這兩個(gè)對(duì)象將用于無法被回收。
2、誤標(biāo)記的問題，在多線程環(huán)境下，如果一個(gè)線程正在遍歷對(duì)象圖，而另一個(gè)線程在同時(shí)修改對(duì)象圖，就會(huì)導(dǎo)致遍歷結(jié)果不準(zhǔn)確。
3、STW時(shí)間長(zhǎng)，可達(dá)性分析的整個(gè)過程都需要STW，以避免對(duì)象的狀態(tài)發(fā)生改變，這就導(dǎo)致GC停頓時(shí)長(zhǎng)很長(zhǎng)，大大影響應(yīng)用的整體性能。
為了解決上面這些問題，就引入了三色標(biāo)記算法
什么是三色標(biāo)記法
三色標(biāo)記法將對(duì)象分為三種狀態(tài)：白色、灰色和黑色。
白色：該對(duì)象沒有被標(biāo)記過。
灰色：該對(duì)象已經(jīng)被標(biāo)記過了，但該對(duì)象的引用對(duì)象還沒標(biāo)記完。
黑色：該對(duì)象已經(jīng)被標(biāo)記過了，并且他的全部引用對(duì)象也都標(biāo)記完了。
三色標(biāo)記法的標(biāo)記過程可以分為三個(gè)階段：初始標(biāo)記（Initial Marking）、并發(fā)標(biāo)記（Concurrent Marking）和重新標(biāo)記（Remark）。
這三個(gè)階段看上去是不是很熟悉，這不就是CMS的四個(gè)階段中的前三個(gè)么？沒錯(cuò)，就是他們。
- 初始標(biāo)記：遍歷所有的根對(duì)象，將根對(duì)象和直接引用的對(duì)象標(biāo)記為灰色。在這個(gè)階段中，垃圾回收器只會(huì)掃描被直接或者間接引用的對(duì)象，而不會(huì)掃描整個(gè)堆。因此，初始標(biāo)記階段的時(shí)間比較短。（Stop The World）
- 并發(fā)標(biāo)記：在這個(gè)過程中，垃圾回收器會(huì)從灰色對(duì)象開始遍歷整個(gè)對(duì)象圖，將被引用的對(duì)象標(biāo)記為灰色，并將已經(jīng)遍歷過的對(duì)象標(biāo)記為黑色。并發(fā)標(biāo)記過程中，應(yīng)用程序線程可能會(huì)修改對(duì)象圖，因此垃圾回收器需要使用寫屏障（Write Barrier）技術(shù)來保證并發(fā)標(biāo)記的正確性。（不需要STW）
- 重新標(biāo)記：重新標(biāo)記的主要作用是標(biāo)記在并發(fā)標(biāo)記階段中被修改的對(duì)象以及未被遍歷到的對(duì)象。這個(gè)過程中，垃圾回收器會(huì)從灰色對(duì)象重新開始遍歷對(duì)象圖，將被引用的對(duì)象標(biāo)記為灰色，并將已經(jīng)遍歷過的對(duì)象標(biāo)記為黑色。（Stop The World）
在重新標(biāo)記階段結(jié)束之后，垃圾回收器會(huì)執(zhí)行清除操作，將未被標(biāo)記為可達(dá)對(duì)象的對(duì)象進(jìn)行回收，從而釋放內(nèi)存空間。這個(gè)過程中，垃圾回收器會(huì)將所有未被標(biāo)記的對(duì)象標(biāo)記為白色（White）。
以上三個(gè)標(biāo)記階段中，初始標(biāo)記和重新標(biāo)記是需要STW的，而并發(fā)標(biāo)記是不需要STW的。其中最耗時(shí)的其實(shí)就是并發(fā)標(biāo)記的這個(gè)階段，因?yàn)檫@個(gè)階段需要遍歷整個(gè)對(duì)象樹，而三色標(biāo)記把這個(gè)階段做到了和應(yīng)用線程并發(fā)執(zhí)行，大大降低了GC的停頓時(shí)長(zhǎng)。
寫屏障
并發(fā)標(biāo)記過程中，應(yīng)用程序線程可能會(huì)修改對(duì)象圖，因此垃圾回收器需要使用寫屏障（Write Barrier）技術(shù)來保證并發(fā)標(biāo)記的正確性。
寫屏障是一種在對(duì)象引用被修改時(shí)，將其新的引用信息記錄在特殊數(shù)據(jù)結(jié)構(gòu)中的機(jī)制。在三色標(biāo)記法中，寫屏障技術(shù)被用于記錄對(duì)象的標(biāo)記狀態(tài)，并且只對(duì)未被標(biāo)記過的對(duì)象進(jìn)行標(biāo)記。
當(dāng)應(yīng)用程序線程修改了一個(gè)對(duì)象的引用時(shí)，寫屏障會(huì)記錄該對(duì)象的新標(biāo)記狀態(tài)。如果該對(duì)象未被標(biāo)記過，那么它會(huì)被標(biāo)記為灰色，以便在垃圾回收器的下一次遍歷中進(jìn)行標(biāo)記。如果該對(duì)象已經(jīng)被標(biāo)記為可達(dá)對(duì)象，那么寫屏障不會(huì)對(duì)該對(duì)象進(jìn)行任何操作。
通過使用寫屏障技術(shù)，三色標(biāo)記法能夠確保垃圾回收器能夠準(zhǔn)確地標(biāo)記所有可達(dá)對(duì)象，并且避免了多次標(biāo)記同一對(duì)象的情況。同時(shí)，寫屏障技術(shù)也會(huì)帶來一定的性能開銷，因?yàn)槊看我帽恍薷臅r(shí)都需要記錄新的標(biāo)記狀態(tài)。為了減少性能開銷，垃圾回收器通常會(huì)使用基于插入式寫屏障的優(yōu)化技術(shù)，來降低寫屏障的開銷。
多標(biāo)的問題
所謂多標(biāo)，其實(shí)就是這個(gè)對(duì)象原本應(yīng)該被回收掉的白色對(duì)象，但是被錯(cuò)誤的標(biāo)記成了黑色的存活對(duì)象。從而導(dǎo)致這個(gè)對(duì)象沒有被GC回收掉。
這個(gè)一般發(fā)生在并發(fā)標(biāo)記過程中，該對(duì)象還是有引用的，但是在過程中，應(yīng)用程序執(zhí)行過程中把他的引用關(guān)系刪除了，導(dǎo)致他變成了一個(gè)垃圾對(duì)象。
多標(biāo)的話，會(huì)產(chǎn)生浮動(dòng)垃圾，這個(gè)問題一般都不太需要解決，因?yàn)檫@種垃圾一般都不會(huì)太多，另外在下一次GC的時(shí)候也都能被回收掉。
多標(biāo)的問題
所謂漏標(biāo)，和多標(biāo)剛好相反，就是說一個(gè)對(duì)象本來應(yīng)該是黑色存活對(duì)象，但是沒有被正確的標(biāo)記上，導(dǎo)致被錯(cuò)誤的垃圾回收掉了。
這種情況一旦發(fā)生是很危險(xiǎn)的，一個(gè)正常使用的對(duì)象被垃圾回收掉了，這對(duì)系統(tǒng)來說是災(zāi)難性的問題，那么如何解決呢？
具體的解決方式，在CSM和G1中也不太一樣。CMS采用的是增量更新方案，G1則采用的是原始快照的方案。
漏標(biāo)的問題想要發(fā)生，需要同時(shí)滿足兩個(gè)充要條件：
1、至少有一個(gè)黑色對(duì)象在自己被標(biāo)記之后指向了這個(gè)白色對(duì)象
2、所有的灰色對(duì)象在自己引用掃描完成之前刪除了對(duì)白色對(duì)象的引用
那么，增量更新方案就是破壞了第一個(gè)條件，而原始快照方案就是破壞了第二個(gè)條件。
增量更新
“至少有一個(gè)黑色對(duì)象在自己被標(biāo)記之后指向了這個(gè)白色對(duì)象”，這個(gè)條件如果被破壞了，那么就不會(huì)出現(xiàn)漏標(biāo)的問題。所以：
如果有黑色對(duì)象在自己標(biāo)記后，又重新指向了白色對(duì)象。那么我就把這個(gè)黑色對(duì)象的引用記錄下來，在后續(xù)「重新標(biāo)記」階段再以這個(gè)黑色對(duì)象為根，對(duì)其引用進(jìn)行重新掃描。通過這種方式，被黑色對(duì)象引用的白色對(duì)象就會(huì)變成灰色，從而變?yōu)榇婊顮顟B(tài)。
這種方式有個(gè)缺點(diǎn)，就是會(huì)重新掃描新增的這部分黑色對(duì)象，會(huì)浪費(fèi)多一些時(shí)間。但是其實(shí)這個(gè)浪費(fèi)還好，因?yàn)楸緛磉@種漏標(biāo)的情況就并不是特別常見，所以這部分需要重新掃描的黑色對(duì)象也并不多。
原始快照
“所有的灰色對(duì)象在自己引用掃描完成之前刪除了對(duì)白色對(duì)象的引用”，這個(gè)條件如果被破壞了，那么就不會(huì)出現(xiàn)漏標(biāo)的問題。所以：
如果灰色對(duì)象在掃描完成前刪除了對(duì)白色對(duì)象的引用，那么我們就在灰色對(duì)象取消引用之前，先將灰色對(duì)象引用的白色對(duì)象記錄下來。
在后續(xù)「重新標(biāo)記」階段再以這些白色對(duì)象為根，對(duì)它的引用進(jìn)行掃描，從而避免了漏標(biāo)的問題。通過這種方式，原本漏標(biāo)的對(duì)象就會(huì)被重新掃描變成灰色，從而變?yōu)榇婊顮顟B(tài)。
但是這種放回寺可能會(huì)把本來真的要取消引用的對(duì)象給錯(cuò)誤的復(fù)活了，從而產(chǎn)生浮動(dòng)垃圾。但是就像前面說的，多標(biāo)的問題是可以忽略的。
總結(jié)
為了解決傳統(tǒng)的引用計(jì)數(shù)法和可達(dá)性分析算法存在的循環(huán)引用問題、誤標(biāo)記問題以及STW時(shí)間長(zhǎng)的問題，咋CMS和G1中引入了三色標(biāo)記算法，其實(shí)就是在標(biāo)記過程中將對(duì)象的狀態(tài)劃分為白色、灰色、和黑色三種狀態(tài)。
同時(shí)把一次標(biāo)記拆分成初始標(biāo)記、并發(fā)標(biāo)記以及重新標(biāo)記三個(gè)階段。并且只有初始標(biāo)記和重新標(biāo)記是STW的，而耗時(shí)最長(zhǎng)的重新標(biāo)記不需要STW，可以和應(yīng)用線程并行。
但是因?yàn)椴l(fā)標(biāo)記過程中是不需要STW的，這就需要采用寫屏障的方式避免并發(fā)。但是還是會(huì)存在漏標(biāo)和多標(biāo)的問題。
多標(biāo)的問題我們一般可以忽略，因?yàn)橄麓蜧C還是可以回收掉的。但是漏標(biāo)的問題還是要解決的，避免對(duì)象使用過程中被回收了，為了解決這個(gè)問題，CMS和G1分別采用了增量更新和原始快照兩種方案來實(shí)現(xiàn)的，都能幫助我們解決漏標(biāo)的問題。
當(dāng)前名稱：CMS和G1改用三色標(biāo)記法，可達(dá)性分析到底做錯(cuò)了什么？
轉(zhuǎn)載注明：http://m.5511xx.com/article/dpjpesp.html
