深入了解GC原理

垃圾定位算法

（1）引用計數法 （Reference Counting）。  如 python  php

      通常C++通過指針引用計數來回收對象，但是這不能處理循環引用，原理是在每個對象内部維護一個引用計數，當對象被引用時引用計數加一，當對象不被引用時引用計數減一。當引用計數為 0 時，自動銷毀對象。

      例如：誰想用驢幹活的時候，就在驢身上畫個圈圈，用一次畫一個，用完了把代表本次使用的圈圈擦掉。當這頭驢身上沒圈圈的時候，就可以卸磨殺驢了，身上有圈圈的驢不能殺。

      這個辦法的優點是：用驢的人清楚自己用了哪頭驢，一旦用驢的人忘了，當事驢自己也清楚。找不到主人，驢可以自己清除圈圈，洗白白再上路。

      缺點也很明顯：畫圈圈也是體力活，需要時間；另一方面，驢皮就那麼點面積，好幾個圈圈畫重疊了也是麻煩，再加上有可能圈圈套圈圈，驢也很惆怅啊。

（2）根可達算法

      從GC Roots向下搜尋，搜尋所走過的路徑稱為引用鍊，當一個對象到GC Roots沒有任何引用鍊（即GC Roots到對象不可達）時，則證明此對象是不可用的，向JAVA、Go這種帶有GC功能的進階語言使用的都是這種定位算法，簡單來講，從根對象往下查找引用，可以查找到的引用标記成可達，直到算法結束之後，沒有被标記的對象就是不可達的，就會被GC回收。

垃圾回收算法

（1）标記-清除 （Mark-Sweep）

        例如：想用某驢幹活，就拍張這頭驢的照片貼牆上，驢去幹活就行了。驢幹完活，去牆上把照片摘下來。有其他人用驢，也是拍照片貼牆上，以此類推。當牆上沒有某頭驢的照片時，這頭驢就可以殺了吃肉了。

        這個辦法的優點是：驢沒啥負擔，隻管幹活；牆可以很寬，貼多少照片問題不大。

        缺點是：找照片是個技術活，太笨的話，光是找照片就得很長時間。而且找照片的時候，最好别貼新的照片，不然就亂了，還得重新找。

（2）複制 (copy and collection)  

（3）标記-壓縮

      以上三種算法是傳統的垃圾回收算法，第一種容易産生記憶體碎片，第二種不會生成記憶體碎片，但是由于是整塊複制，是以STW較長，效率太低，第三種是前兩種的結合

（4）分代模型

     JVM做垃圾回收時常用的GC算法，分為年輕代和老年代，年輕代使用複制算法，老年代使用标記壓縮或者标記清除。

在分代模型中，年輕代的回收算法有ParNew、Serial、Parallel Scavenge，老年代的回收算法有CMS、Serial Old、Parallel Old，年輕代和老年代的回收算法一定是成對出現的，常見的回收對是ParNew-CMS、Serial-Serial Old、Parallel Scavenge-Parallel Old（jdk1.8預設）

     例如：驢多了不能放一起，短工驢放一個地方，長工驢放另一個地方。短工驢總是幹活不休息，就更新成長工驢。殺驢的時候，一個人專殺幹完短工的驢，短工驢不會擺資格，殺就殺了；另一個人專殺幹完長工的驢，長工驢資格老，脾氣暴，殺之前要點蚊香放音樂，搞點儀式感。

     這個辦法的優點是：非常驢性化，充分照顧了驢的感受；另一方面，多幾個人殺驢，效率比較高。

     缺點一樣很明顯：驢會更新，短工驢更新到長工驢，總是很矯情，兩邊殺手必須做好交接工作，不然有驢忘了殺就麻煩了。

（5）三色标記法

      三色标記法是傳統 Mark-Sweep 的一個改進，它是一個并發的 GC 算法。其實大部分的工作還是在标記垃圾，基本原理基于根可達

Golang 的三色标記法

golang 的垃圾回收(GC)是基于标記清掃算法，因為這種方式關注點很簡單，隻要找驢照片足夠快，其他都好辦。

但是因為低版本的Golang，找驢照片的工作不熟練，再加上這種找驢方式本身的特點，就造成了Golang經常被人诟病的兩個槽點：

1、Golang的GC速度慢。

這個在各個版本，一直是golang改進的重點。到目前為止（1.14），經過超級多版本的演進，特别是在1.14版本中實作了基于信号的真搶占式排程，目前的gc速度已經相當快了。不能跟純手動記憶體管理比，隻能說在同樣使用​​gc機制​​

的程式設計語言裡，達到了應有的水準（之前确實有幾個版本，達不到及格線）。

2、Golang的GC的STW（STOP THE WORLD）噩夢。

前面提到過，找驢照片的時候，不能有新的照片貼牆上。這就造成了找驢的過程中，整個世界都停止了（其實有點誇張，畢竟隻是照片牆不接受新照片，驢其實還在幹活或者等死）。這個從根本上說，是機制問題。隻要還用這個機制，那世界還是會時間停止。隻不過，随着找驢速度的加快，這個時間裂縫，已經壓縮到一個非常非常短的瞬間。當然，Golang本身的演進過程中，采用了很多細節技術，不但讓這個STW的時間越來越短，而且還盡量的減少了這個停止世界的大小，把影響範圍收窄。

一輪完整的 GC，總是從 Off，如果不是 Off 狀态，則代表上一輪GC還未完成，如果這時修改指針的值，是直接修改的。

Stack scan: 收集根對象（全局變量和 goroutine 棧上的變量），該階段會開啟寫屏障(Write Barrier)。

Mark: 标記對象，直到标記完所有根對象和根對象可達對象。此時寫屏障會記錄所有指針的更改(通過 mutator)。

Mark Termination: 重新掃描部分全局變量和發生更改的棧變量，完成标記，該階段會STW(Stop The World)，也是 gc 時造成 go 程式停頓的主要階段。

Sweep: 并發的清除未标記的對象。

通過三色标記清掃法與寫屏障來減少 STW 的時間.

三色标記法的流程如下，它将對象通過白、灰、黑進行标記

1.所有對象最開始都是白色.

2.從 root 開始找到所有可達對象，标記為灰色，放入待處理隊列。

3.周遊灰色對象隊列，将其引用對象标記為灰色放入待處理隊列，自身标記為黑色。

4.循環步驟3直到灰色隊列為空為止，此時所有引用對象都被标記為黑色，所有不可達的對象依然為白色，白色的就是需要進行回收的對象。

三色标記法相對于普通标記清掃，減少了 STW 時間. 這主要得益于标記過程是 “on-the-fly” 的，在标記過程中是不需要 STW 的，它與程式是并發執行的，這就大大縮短了 STW 的時間.

标記垃圾會産生的問題

A對象已經标記并且引用的對象B也已經被标記，是以A放到黑色集合裡，B對象被标記但是C對象還沒标記，是以B是灰色

（1）浮動垃圾

如果B到C的引用斷開，那麼B找不到引用會被标黑，此時C就成了浮動垃圾，這種情況不礙事，大不了下次GC再收集

（2）漏标或者錯标或者稱作懸挂指針

      但是如果此時使用者goroutine建立對象A對對象C的引用，也就是從已經被标記成黑色的對象建立了引用指向了白色對象，因為A已經标黑，此時C将作為白色不可達對象被收集，這就出大問題了，程式裡面A對象還正在引用C對象，

但是GC把C對象看成垃圾給回收了，造成空指針異常。

寫屏障 (Write Barrier)

為了解決漏标的問題，需要使用寫屏障，原理就是當A對象被标黑，此時A又引用C，就把C變灰入隊

寫屏障一定是在進行記憶體寫操作之前執行的。

強三色不變性：黑色對象不會指向白色對象，隻會指向灰色對象或者黑色對象；

是以​

​新生成的對象，一律都标位灰色！​

​

弱三色不變性 ：黑色節點允許引用白色節點，但是該白色節點有其他灰色節點間接的引用（確定不會被遺漏）當白色節點被删除了一個引用時，悲觀地認為它一定會被一個黑色節點新增引用，是以将它置為灰色

Go 語言中使用兩種寫屏障技術，分别是 Dijkstra 提出的插入寫屏障和 Yuasa 提出的删除寫屏障。

GC 觸發條件

    主動觸發，使用者代碼中調用 ​

​runtime.GC​

​ 會主動觸發 GC