演算法標記法

Ⅰ NI Vision：二值圖像連通域標記演算法

前面說到，要使用Labwindows + NI Vision（IMAQ Vision）這套商用開發框架來做數圖課設。很明顯，這套虛擬儀器開發平台由NI Instrument（美國國家儀器公司）開發的。大名鼎鼎的Labview軟體就是這個公司開發的。相比較而言，Labwindows使用ANSI C開發，但應用場景是差不多的。

在做課程作業的時候，遇到了一個很有趣的應用。輸入是米粒，比背景灰度要低，目的是輸出米粒的顆數、面積、周長和孔數，這是工業上的一個很常見的應用。具體處理過程是二值化後使用低通濾波，並計算各種性質。

界面設計如下，可以看到米粒的詳細情況。

讓我感興趣的，是通過怎樣的演算法能夠得到米粒的數量？之前曾經用過OpenCV中找最大外界矩形這個函數，但沒有具體了解演算法實現。直覺告訴我原理應該是相似的。

可以看到，每一個米粒之間都是不連通的。這里就就提出了一個概念。 連通區域（Connected Component） 是指圖像中相鄰並有相同像素值的圖像區域。 連通區域分析（Connected Component Analysis,Connected Component Labeling） 是指將圖像中的各個連通區域找出並標記。

二值圖像分析最重要的方法就是連通區域標記，它是所有二值圖像分析的基礎，它通過對二值圖像中白色像素（目標）的標記，讓每個單獨的連通區域形成一個被標識的塊，進一步的我們就可以獲取這些塊的輪廓、外接矩形、質心、不變矩等幾何參數。如果要得到米粒的數量，那麼通過連通區域分析（這里是二值圖像的連通區域分析），就可以得到標記的數量，從而得到米粒的數量。

下面這幅圖中，如果考慮4鄰接，則有3個連通區域，8鄰接則是2個。

從連通區域的定義可以知道，一個連通區域是由具有相同像素值的相鄰像素組成像素集合，因此，我們就可以通過這兩個條件在圖像中尋找連通區域，對於找到的每個連通區域，我們賦予其一個唯一的 標識（Label） ，以區別其他連通區域。

連通區域分析的基本演算法有兩種：1）Two-Pass兩便掃描法 2）Seed-Filling種子填充法 。

兩遍掃描法（Two-Pass），正如其名，指的就是通過掃描兩遍圖像，就可以將圖像中存在的所有連通區域找出並標記。

說了一堆數學語言，其實用圖很好理解

種子填充方法來源於計算機圖形學，常用於對某個圖形進行填充。它基於區域生長演算法。至於區域生長演算法是什麼，可以參照我的這篇 文章 。

同樣的，上動圖

NI Vision 中的運算元定義如下

OpenCV中也有相應的運算元

這里參照其他博客實現一下Two-Pass演算法，Seed-Filling演算法就偷懶不搞了。

Reference:
OpenCV實現圖像連通組件標記與分析
OpenCV-二值圖像連通域分析
數字圖像處理技術 ——鄧繼忠（我的任課老師）

Ⅱ GC垃圾回收（3）- 三色標記演算法

CMS過程在上篇文章 GC垃圾回收（2） 中已經寫過。
它分為四個階段：

其中 並發標記 階段會有漏標的問題，為解決這個問題，採用了 "三色標記演算法"

G1 GC（Garbage First Garbage Collector）是一種服務端應用使用的垃圾收集器，目標是用在 多核、大內存 的機器上，它在大多數情況下可以實現指定的GC暫停時間，同時還能保持較高的吞吐量。它的吞吐量相較PS+PO降低了大概10%~15%，但是大大降低了響應時間，大概200ms的程度

G1內存模型如下:

G1相較之前其它的垃圾回收器，對模型進行了改變，不再進行物理分代，採用邏輯分代。

它不再將連續內存分為Eden區和Old區，而是將內存分為一個個的Region。一塊Region(分區)在邏輯上依然分代，分為四種：Eden，Old，Survivor，Humongous（大對象，跨多個連續的Region）。

它的每個分區都可能是年輕代也可能是老年代，但是在同一時刻只能屬於某個代。

年輕代、倖存區、老年代這些概念還存在，成為了邏輯上的概念，這樣方便復用之前分代框架的邏輯。在物理上不需要連續，這帶來了額外的好處——有的分區內垃圾對象特別多，有的分區內垃圾對象很少，G1會優先回收垃圾對象特別多的分區，這樣可以花費較少的時間來回收這些分區的垃圾，這也就是G1名字的由來，即首先回收垃圾最多的分區。

新生代其實並不適用於這種演算法，依然是在新生代滿了的時候，對整個新生代進行回收——整個新生代中的對象，要麼被回收、要麼晉升，至於新生代也採取分區機制的原因，則是因為這樣跟老年代的策略統一，方便調整代的大小。

G1還是一種帶壓縮的收集器，在回收老年代的分區時，是將存活的對象從一個分區拷貝到另一個可用分區，這個拷貝的過程就實現了局部的壓縮。每個分區的大小從1M到32M不等，但都是2的冪次方。

特點：

G1與CMS在並發收集時的演算法沒太大區別，用的是 三色標記 演算法。但ZGC和Shenandoah使用的是 顏色指針 Colored Pointers。

主要用於分代模型中幫助垃圾回收。

為什麼需要 card table ？
尋找存活對象並不是一件容易的事。從一個GC root對象尋找，可能被Old區對象引用，這個Old區對象又被Eden區對象引用，那麼判斷Eden區對象是否存活就需要遍歷整個Old區存活對象看是否被Old區對象引用。這樣的話每進行一次YGC就要掃描整個Old區。

所以JVM內部，將內存區域分為一個個的card，對象存在一個個的card里。當老年代某個card中的對象指向了年輕代，就會將這個card標記為 Dirty 。這么多card具體哪個是 Dirty的，用點陣圖BitMap來代表（如0110010010，1表示Dirty），這就是Card Table。

Card Table ：由於做YGC時，需要掃描整個Old區，效率非常低，所以JVM設計了Card Table， 如果一個Old區Card Table中有對象指向Y區，就將它設為Dirty，下次掃描時，只需要掃描Dirty Card。 在結構上，Card Table用BitMap來實現。

RSet會佔用一定的空間，所以ZGC又做了改進，不使用RSet，用顏色指針來標記。

Rset與賦值的效率：

5% ~ 60%（新生代）

G1能跟蹤STW停頓時間，根據停頓時間動態調整新生代（Y區）比例

超過單個region的 50% 就是一個大對象，也可跨越多個region。

注意： G1也是存在FGC的，並且一定會被觸發。當對象分配不下是會產生FGC。

回收時不分新生代還是老年代什麼的，region滿了就回收。

MixedGC過程：

跟CMS非常像，MixedGC最後是篩選回收，多了個篩選步驟。篩選就是找出垃圾最多的region。篩選後將存活對象復制到其他region，再將之前的region清空。

CMS和G1在並發標記時使用的是同一個演算法： 三色標記法 ，使用白灰黑三種顏色標記對象。白色是未標記；灰色自身被標記，引用的對象未標記；黑色自身與引用對象都已標記。

在remark過程中，黑色指向了白色，如果不對黑色重新掃描，則會漏標。會把白色D對象當作沒有新引用指向從而回收掉。

並發標記過程中，Mutator刪除了所有從灰色到白色的引用，會產生漏標。此時白色對象應該被回收

產生漏標問題的條件有兩個：
1.黑色對象指向了白色對象
2.灰色對象指向白色對象的引用消失

所以要解決漏標問題，打破兩個條件之一即可：

為什麼G1採用SATB而不用incremental update？
因為採用incremental update把黑色重新標記為灰色後，之前掃描過的還要再掃描一遍，效率太低。
G1有RSet與SATB相配合。Card Table里記錄了RSet，RSet里記錄了其他對象指向自己的引用，這樣就不需要再掃描其他區域，只要掃描RSet就可以了。
也就是說 灰色-->白色 引用消失時，如果沒有 黑色-->白色，引用會被push到堆棧，下次掃描時拿到這個引用，由於有RSet的存在，不需要掃描整個堆去查找指向白色的引用，效率比較高。SATB配合RSet渾然天成。

Ⅲ 三色標記法與垃圾回收器（CMS、G1）

JVM中的CMS、G1垃圾回收器所使用垃圾回收演算法即為三色標記法。

三色標記法將對象的顏色分為了黑、灰、白，三種顏色。

存在問題：

浮動垃圾：並發標記的過程中，若一個已經被標記成黑色或者灰色的對象，突然變成了垃圾，此時，此對象不是白色的不會被清除，重新標記也不能從GC Root中去找到，所以成為了浮動垃圾，這種情況對系統的影響不大，留給下一次GC進行處理即可。
對象漏標問題（需要的對象被回收）：並發標記的過程中，一個業務線程將一個未被掃描過的白色對象斷開引用成為垃圾（刪除引用），同時黑色對象引用了該對象（增加引用）（這兩部可以不分先後順序）；因為黑色對象的含義為其屬性都已經被標記過了，重新標記也不會從黑色對象中去找，導致該對象被程序所需要，卻又要被GC回收，此問題會導致系統出現問題，而CMS與G1，兩種回收器在使用三色標記法時，都採取了一些措施來應對這些問題，CMS對增加引用環節進行處理（Increment Update），G1則對刪除引用環節進行處理(SATB)。

在JVM虛擬機中有兩種常見垃圾回收器使用了該演算法：

CMS(Concurrent Mark Sweep)

CMS，是非常有名的JVM垃圾回收器，它起到了承上啟下的作用，開啟了並發回收的篇章。
但是CMS由於許多小問題，現在基本已經被淘汰。

增量更新(Increment Update)
在應對漏標問題時，CMS使用了Increment Update方法來做：
在一個未被標記的對象（白色對象）被重新引用後，==引用它的對象==，若為黑色則要變成灰色，在下次二次標記時讓GC線程繼續標記它的屬性對象。
但是就算時這樣，其仍然是存在漏標的問題：

在一個灰色對象正在被一個GC線程回收時，當它已經被標記過的屬性指向了一個白色對象（垃圾）
而這個對象的屬性對象本身還未全部標記結束，則為灰色不變
而這個GC線程在標記完最後一個屬性後，認為已經將所有的屬性標記結束了，將這個灰色對象標記為黑色，被重新引用的白色對象，無法被標記

補充，CMS除了這個缺陷外，仍然存在兩個個較為致命的缺陷：

解決方案：使用Mark-Sweep-Compact演算法，減少垃圾碎片

當JVM認為內存不夠了，再使用CMS進行並發清理內存可能會發生OOM的問題，而不得不進行Serial Old GC，Serial Old是單線程垃圾回收，效率低

解決方案：降低觸發CMS GC的閾值，讓浮動垃圾不那麼容易占滿老年代

G1(Garbage First)

從G1垃圾回收器開始，G1的物理內存不再分代，而是由一塊一塊的Region組成；邏輯分代仍然存在。

前置知識 — Card Table（多種垃圾回收器均具備）

由於在進行YoungGC時，我們在進行對一個對象是否被引用的過程，需要掃描整個Old區，所以JVM設計了CardTable，將Old區分為一個一個Card，一個Card有多個對象；如果一個Card中的對象有引用指向Young區，則將其標記為Dirty Card，下次需要進行YoungGC時，只需要去掃描Dirty Card即可。

Card Table 在底層數據結構以 Bit Map實現。

CSet(Collection Set)

SATB(Snapshot At The Beginning)
在應對漏標問題時，CMS使用了SATB方法來做：

因為SATB在重新標記環節只需要去重新掃描那些被推到堆棧中的引用，並配合Rset來判斷當前對象是否被引用來進行回收；

並且在最後G1並不會選擇回收所有垃圾對象，而是根據Region的垃圾多少來判斷與預估回收價值（指回收的垃圾與回收的STW時間的一個預估值），將一個或者多個Region放到CSet中，最後將這些Region中的存活對象壓縮並復制到新的Region中，清空原來的Region。

問題：G1會不會進行Full GC?
會，當內存滿了的時候就會進行Full GC；且JDK10之前的Full GC，為單線程的，所以使用G1需要避免Full GC的產生。
解決方案：

加大內存；
提高CPU性能，加快GC回收速度，而對象增加速度趕不上回收速度，則Full GC可以避免；
降低進行Mixed GC觸發的閾值，讓Mixed GC提早發生（默認45%）

G1的第一篇paper（附錄1）發表於2004年，在2012年才在jdk1.7u4中可用。oracle官方計劃在jdk9中將G1變成默認的垃圾收集器，以替代CMS。為何oracle要極力推薦G1呢，G1有哪些優點？

首先，G1的設計原則就是簡單可行的性能調優

開發人員僅僅需要聲明以下參數即可：

其中-XX:+UseG1GC為開啟G1垃圾收集器，-Xmx32g 設計堆內存的最大內存為32G，-XX:MaxGCPauseMillis=200設置GC的最大暫停時間為200ms。如果我們需要調優，在內存大小一定的情況下，我們只需要修改最大暫停時間即可。

其次，G1將新生代，老年代的物理空間劃分取消了。

這樣我們再也不用單獨的空間對每個代進行設置了，不用擔心每個代內存是否足夠。

取而代之的是，G1演算法將堆劃分為若干個區域（Region），它仍然屬於分代收集器。不過，這些區域的一部分包含新生代，新生代的垃圾收集依然採用暫停所有應用線程的方式，將存活對象拷貝到老年代或者Survivor空間。老年代也分成很多區域，G1收集器通過將對象從一個區域復制到另外一個區域，完成了清理工作。這就意味著，在正常的處理過程中，G1完成了堆的壓縮（至少是部分堆的壓縮），這樣也就不會有cms內存碎片問題的存在了。

在G1中，還有一種特殊的區域，叫Humongous區域。 如果一個對象佔用的空間超過了分區容量50%以上，G1收集器就認為這是一個巨型對象。這些巨型對象，默認直接會被分配在年老代，但是如果它是一個短期存在的巨型對象，就會對垃圾收集器造成負面影響。為了解決這個問題，G1劃分了一個Humongous區，它用來專門存放巨型對象。如果一個H區裝不下一個巨型對象，那麼G1會尋找連續的H分區來存儲。為了能找到連續的H區，有時候不得不啟動Full GC。

PS：在java 8中，持久代也移動到了普通的堆內存空間中，改為元空間。

對象分配策略

說起大對象的分配，我們不得不談談對象的分配策略。它分為3個階段：

對TLAB空間中無法分配的對象，JVM會嘗試在Eden空間中進行分配。如果Eden空間無法容納該對象，就只能在老年代中進行分配空間。

最後，G1提供了兩種GC模式，Young GC和Mixed GC，兩種都是Stop The World(STW)的。下面我們將分別介紹一下這2種模式。

Young GC主要是對Eden區進行GC，它在Eden空間耗盡時會被觸發。在這種情況下，Eden空間的數據移動到Survivor空間中，如果Survivor空間不夠，Eden空間的部分數據會直接晉升到年老代空間。Survivor區的數據移動到新的Survivor區中，也有部分數據晉升到老年代空間中。最終Eden空間的數據為空，GC停止工作，應用線程繼續執行。

這時，我們需要考慮一個問題，如果僅僅GC 新生代對象，我們如何找到所有的根對象呢？ 老年代的所有對象都是根么？那這樣掃描下來會耗費大量的時間。於是，G1引進了RSet的概念。它的全稱是Remembered Set，作用是跟蹤指向某個heap區內的對象引用。

在CMS中，也有RSet的概念，在老年代中有一塊區域用來記錄指向新生代的引用。這是一種point-out，在進行Young GC時，掃描根時，僅僅需要掃描這一塊區域，而不需要掃描整個老年代。

但在G1中，並沒有使用point-out，這是由於一個分區太小，分區數量太多，如果是用point-out的話，會造成大量的掃描浪費，有些根本不需要GC的分區引用也掃描了。於是G1中使用point-in來解決。point-in的意思是哪些分區引用了當前分區中的對象。這樣，僅僅將這些對象當做根來掃描就避免了無效的掃描。由於新生代有多個，那麼我們需要在新生代之間記錄引用嗎？這是不必要的，原因在於每次GC時，所有新生代都會被掃描，所以只需要記錄老年代到新生代之間的引用即可。

需要注意的是，如果引用的對象很多，賦值器需要對每個引用做處理，賦值器開銷會很大，為了解決賦值器開銷這個問題，在G1 中又引入了另外一個概念，卡表（Card Table）。一個Card Table將一個分區在邏輯上劃分為固定大小的連續區域，每個區域稱之為卡。卡通常較小，介於128到512位元組之間。Card Table通常為位元組數組，由Card的索引（即數組下標）來標識每個分區的空間地址。默認情況下，每個卡都未被引用。當一個地址空間被引用時，這個地址空間對應的數組索引的值被標記為」0″，即標記為臟被引用，此外RSet也將這個數組下標記錄下來。一般情況下，這個RSet其實是一個Hash Table，Key是別的Region的起始地址，Value是一個集合，裡面的元素是Card Table的Index。

Young GC 階段：

Mix GC不僅進行正常的新生代垃圾收集，同時也回收部分後台掃描線程標記的老年代分區。

它的GC步驟分2步：

全局並發標記（global concurrent marking）
拷貝存活對象（evacuation）
在進行Mix GC之前，會先進行global concurrent marking（全局並發標記）。 global concurrent marking的執行過程是怎樣的呢？

在G1 GC中，它主要是為Mixed GC提供標記服務的，並不是一次GC過程的一個必須環節。global concurrent marking的執行過程分為五個步驟：

初始標記（initial mark，STW）
在此階段，G1 GC 對根進行標記。該階段與常規的 (STW) 年輕代垃圾回收密切相關。
根區域掃描（root region scan）
G1 GC 在初始標記的存活區掃描對老年代的引用，並標記被引用的對象。該階段與應用程序（非 STW）同時運行，並且只有完成該階段後，才能開始下一次 STW 年輕代垃圾回收。
並發標記（Concurrent Marking）
G1 GC 在整個堆中查找可訪問的（存活的）對象。該階段與應用程序同時運行，可以被 STW 年輕代垃圾回收中斷
最終標記（Remark，STW）
該階段是 STW 回收，幫助完成標記周期。G1 GC 清空 SATB 緩沖區，跟蹤未被訪問的存活對象，並執行引用處理。
清除垃圾（Cleanup，STW）
在這個最後階段，G1 GC 執行統計和 RSet 凈化的 STW 操作。在統計期間，G1 GC 會識別完全空閑的區域和可供進行混合垃圾回收的區域。清理階段在將空白區域重置並返回到空閑列表時為部分並發。

提到並發標記，我們不得不了解並發標記的三色標記演算法。它是描述追蹤式回收器的一種有用的方法，利用它可以推演回收器的正確性。 首先，我們將對象分成三種類型的。

根對象被置為黑色，子對象被置為灰色。

繼續由灰色遍歷,將已掃描了子對象的對象置為黑色。

遍歷了所有可達的對象後，所有可達的對象都變成了黑色。不可達的對象即為白色，需要被清理。

這看起來很美好，但是如果在標記過程中，應用程序也在運行，那麼對象的指針就有可能改變。這樣的話，我們就會遇到一個問題：對象丟失問題

我們看下面一種情況，當垃圾收集器掃描到下面情況時：

這時候應用程序執行了以下操作：

這樣，對象的狀態圖變成如下情形：

這時候垃圾收集器再標記掃描的時候就會下圖成這樣：

很顯然，此時C是白色，被認為是垃圾需要清理掉，顯然這是不合理的。那麼我們如何保證應用程序在運行的時候，GC標記的對象不丟失呢？有如下2中可行的方式：

在插入的時候記錄對象
在刪除的時候記錄對象
剛好這對應CMS和G1的2種不同實現方式：

在CMS採用的是增量更新（Incremental update），只要在寫屏障（write barrier）里發現要有一個白對象的引用被賦值到一個黑對象 的欄位里，那就把這個白對象變成灰色的。即插入的時候記錄下來。

在G1中，使用的是STAB（snapshot-at-the-beginning）的方式，刪除的時候記錄所有的對象，它有3個步驟：

這樣，G1到現在可以知道哪些老的分區可回收垃圾最多。 當全局並發標記完成後，在某個時刻，就開始了Mix GC。這些垃圾回收被稱作「混合式」是因為他們不僅僅進行正常的新生代垃圾收集，同時也回收部分後台掃描線程標記的分區。混合式垃圾收集如下圖：

混合式GC也是採用的復制的清理策略，當GC完成後，會重新釋放空間。

至此，混合式GC告一段落了。下一小節我們講進入調優實踐。

MaxGCPauseMillis調優

前面介紹過使用GC的最基本的參數：

前面2個參數都好理解，後面這個MaxGCPauseMillis參數該怎麼配置呢？這個參數從字面的意思上看，就是允許的GC最大的暫停時間。G1盡量確保每次GC暫停的時間都在設置的MaxGCPauseMillis范圍內。 那G1是如何做到最大暫停時間的呢？這涉及到另一個概念，CSet(collection set)。它的意思是在一次垃圾收集器中被收集的區域集合。

Young GC：選定所有新生代里的region。通過控制新生代的region個數來控制young GC的開銷。
Mixed GC：選定所有新生代里的region，外加根據global concurrent marking統計得出收集收益高的若干老年代region。在用戶指定的開銷目標范圍內盡可能選擇收益高的老年代region。
在理解了這些後，我們再設置最大暫停時間就好辦了。 首先，我們能容忍的最大暫停時間是有一個限度的，我們需要在這個限度范圍內設置。但是應該設置的值是多少呢？我們需要在吞吐量跟MaxGCPauseMillis之間做一個平衡。如果MaxGCPauseMillis設置的過小，那麼GC就會頻繁，吞吐量就會下降。如果MaxGCPauseMillis設置的過大，應用程序暫停時間就會變長。G1的默認暫停時間是200毫秒，我們可以從這里入手，調整合適的時間。

其他調優參數

避免使用以下參數：

避免使用 -Xmn 選項或 -XX:NewRatio 等其他相關選項顯式設置年輕代大小。固定年輕代的大小會覆蓋暫停時間目標。

觸發Full GC

在某些情況下，G1觸發了Full GC，這時G1會退化使用Serial收集器來完成垃圾的清理工作，它僅僅使用單線程來完成GC工作，GC暫停時間將達到秒級別的。整個應用處於假死狀態，不能處理任何請求，我們的程序當然不希望看到這些。那麼發生Full GC的情況有哪些呢？

並發模式失敗
G1啟動標記周期，但在Mix GC之前，老年代就被填滿，這時候G1會放棄標記周期。這種情形下，需要增加堆大小，或者調整周期（例如增加線程數-XX:ConcGCThreads等）。

晉升失敗或者疏散失敗
G1在進行GC的時候沒有足夠的內存供存活對象或晉升對象使用，由此觸發了Full GC。可以在日誌中看到(to-space exhausted)或者（to-space overflow）。解決這種問題的方式是：

巨型對象分配失敗
當巨型對象找不到合適的空間進行分配時，就會啟動Full GC，來釋放空間。這種情況下，應該避免分配大量的巨型對象，增加內存或者增大-XX:G1HeapRegionSize，使巨型對象不再是巨型對象。

由於篇幅有限，G1還有很多調優實踐，在此就不一一列出了，大家在平常的實踐中可以慢慢探索。最後，期待java 9能正式發布，默認使用G1為垃圾收集器的java性能會不會又提高呢？

G1處理和傳統的垃圾收集策略是不同的，關鍵的因素是它將所有的內存進行了子區域的劃分。

總結

G1是一款非常優秀的垃圾收集器，不僅適合堆內存大的應用，同時也簡化了調優的工作。通過主要的參數初始和最大堆空間、以及最大容忍的GC暫停目標，就能得到不錯的性能；同時，我們也看到G1對內存空間的浪費較高，但通過**首先收集盡可能多的垃圾(Garbage First)的設計原則，可以及時發現過期對象，從而讓內存佔用處於合理的水平。

參考鏈接：
https://juejin.cn/post/6859931488352370702
https://blog.csdn.net/qq_39276448/article/details/104470796