摘要：廣告位出售垃圾回收機(jī)制淺析與理解對垃圾回收進(jìn)行分析前，我們先來了解一些基本概念基本概念內(nèi)存管理內(nèi)存管理對于編程語言至關(guān)重要。里面的變量通常是局部變量函數(shù)參數(shù)等。

對垃圾回收進(jìn)行分析前，我們先來了解一些基本概念

內(nèi)存管理：內(nèi)存管理對于編程語言至關(guān)重要。匯編允許你操作所有東西，或者說要求你必須全權(quán)處理所有細(xì)節(jié)更合適。C 語言中雖然標(biāo)準(zhǔn)庫函數(shù)提供一些內(nèi)存管理支持，但是對于之前調(diào)用 malloc 申請的內(nèi)存，還是依賴于你親自 free 掉。從C++、Python、Swift 和 Java 開始，才在不同程度上支持內(nèi)存管理。

內(nèi)存壓縮：對內(nèi)存碎片進(jìn)行壓縮。（和win10的那個“內(nèi)存壓縮”不太一樣啦）

win10內(nèi)存壓縮：物理內(nèi)存已經(jīng)見底，將一部分不常使用的內(nèi)存數(shù)據(jù)打包壓縮起來，等到有程序需要訪問那些數(shù)據(jù)的時候，再解壓縮出來。

引用與指針：

引用被創(chuàng)建的同時必須被初始化（指針則可以在任何時候被初始化）。

不能有NULL 引用，引用必須與合法的存儲單元關(guān)聯(lián)（指針則可以是NULL）。

一旦引用被初始化，就不能改變引用的關(guān)系（指針則可以隨時改變所指的對象）。

引用只是某塊內(nèi)存的別名。

實(shí)際上“引用”可以做的任何事情“指針”也都能夠做，為什么還要“引用” 這東西？

答案是“用適當(dāng)?shù)墓ぞ咦銮∪缙浞值墓ぷ鳌薄１热缯f，某人需要一份證明，本來在文件上蓋                上公章的印子就行了，如果把取公章的鑰匙交給他，那么他就獲得了不該有的權(quán)利。（什么情況下，就用什么對策）
6. 為什么還要說“只有指針，沒有引用是一個重要改變？”？
 答案是雖然引用在某些情況下好用，但他也會導(dǎo)致致命錯誤。如下：
```
 char *pc = 0; // 設(shè)置指針為空值 
 char& rc = *pc; // 讓引用指向空值 
```
 這是非常有害的，毫無疑問。結(jié)果將是不確定的（編譯器能產(chǎn)生一些輸出，導(dǎo)致任何事情都有可能發(fā)生），應(yīng)該躲開寫出這樣代碼的人除非他們同意改正錯誤。如果你擔(dān)心這樣的代碼會出現(xiàn)在你的軟件里，那么你最好完全避免使用引用，要不然就去讓更優(yōu)秀的程序員去做。   
7. 最后上附圖，幫助理解

堆（heap）和棧（stack）

平常說的“堆棧”其實(shí)是棧。

棧，就是那些由編譯器在需要的時候分配，在不需要的時候自動清除的變量的存儲區(qū)。里面的變量通常是局部變量、函數(shù)參數(shù)等。

堆，就是那些由new分配的內(nèi)存塊，他們的釋放編譯器不去管，由我們的應(yīng)用程序去控 制，一般一個new就要對應(yīng)一個delete。如果程序員沒有釋放掉，那么在程序結(jié)束后，操作系統(tǒng)會自動回收。

程序的棧結(jié)構(gòu)

程序的地址空間布局： 程序運(yùn)行靠四個東西：代碼、棧、堆、數(shù)據(jù)段。代碼段主要存放的就是可執(zhí)行文件(通常可執(zhí)行文件內(nèi)，含有以二進(jìn)制編碼的微處理器指令，也因此可執(zhí)行文件有時稱為二進(jìn)制文件)中的代碼；數(shù)據(jù)段存放的就是程序中全局變量和靜態(tài)變量；堆中是程序的動態(tài)內(nèi)存區(qū)域，當(dāng)程序使用malloc或new得到的內(nèi)存是來自堆的；棧中維護(hù)的是函數(shù)調(diào)用的上下文，離開了棧就不可能實(shí)現(xiàn)函數(shù)的調(diào)用。

棧幀： 也叫活動記錄，保存的是一個函數(shù)調(diào)用所需要維護(hù)的所有信息。如下：
1.函數(shù)的返回地址和參數(shù)
2.臨時變量：包括函數(shù)的非靜態(tài)局部變量以及編譯器自動生成的其它臨時變量
3.保存的上下文：包括在函數(shù)調(diào)用前后需要保存不變的寄存器值

就是它，先上圖

]

 1.返回地址:一個main函數(shù)中斷執(zhí)行的執(zhí)行點(diǎn).
 2.ebp:指向函數(shù)活動記錄的一個固定位置，ebp又被稱為幀指針.固定位置是，這樣在函數(shù)返回的時候，ebp就可以通過這個恢復(fù)到調(diào)用前的值。
 3.esp始終指向棧頂，因此隨著函數(shù)的執(zhí)行，它總是變化的。
 4.入棧順序：先壓此次調(diào)用函數(shù)參數(shù)入棧，接著是main函數(shù)返回地址，然后是ebp等寄存器。

Link：C程序的函數(shù)棧作用機(jī)理（這個講得好，有實(shí)例，所以不再熬述）

這里我們對比了解不同的 “找到需要標(biāo)記的對象”的方法

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

給對象中添加一個引用計(jì)數(shù)器，每當(dāng)有一個地方引用它時，計(jì)數(shù)器值就加1；當(dāng)引用失效時， 計(jì)數(shù)器值就減1；任何時刻計(jì)數(shù)器為0的對象就是不可能再被使用的。如下圖所示：

優(yōu)點(diǎn)：引用計(jì)數(shù)收集器可以很快地執(zhí)行，交織在程序的運(yùn)行之中。這個特性對于程序不能被長時間打斷的實(shí)時環(huán)境很有利。
缺點(diǎn)：很難處理循環(huán)引用，比如圖中相互引用的兩個對象則無法釋放。
應(yīng)用：Python 和 Swift 采用引用計(jì)數(shù)方案。   

可達(dá)性分析算法（根搜索算法）

從GC Roots（每種具體實(shí)現(xiàn)對GC Roots有不同的定義）作為起點(diǎn)，向下搜索它們引用的對象，可以生成一棵引用樹，樹的節(jié)點(diǎn)視為可達(dá)對象，反之視為不可達(dá)。如下圖所示：

接下來補(bǔ)充幾個概念幫助理解（以java為例）：

GC Roots對象：
虛擬機(jī)棧（幀棧中的本地變量表）中引用的對象。
方法區(qū)中靜態(tài)屬性引用的對象。
方法區(qū)中常量引用的對象。
本地方法棧中JNI引用的對象。

本地方法棧則為虛擬機(jī)所使用的Native方法服務(wù)。
Native方法是指本地方法，當(dāng)在方法中調(diào)用一些不是由java語言寫的代碼或者在方法中用java語言直接操縱計(jì)算機(jī)硬件。
JNI：Java Native Interface縮寫，允許Java代碼和其他語言寫的代碼進(jìn)行交互。
上述如圖，關(guān)于root區(qū)域的詳細(xì)解釋參考這里

這里我們介紹幾種不同的 “標(biāo)記對象”的方法

保守法

將所有堆上對齊的字都認(rèn)為是指針，那么有些數(shù)據(jù)就會被誤認(rèn)為是指針。于是某些實(shí)際是數(shù)字的假指針，會背誤認(rèn)為指向活躍對象，導(dǎo)致內(nèi)存泄露（假指針指向的對象可能是死對象，但依舊有指針指向——這個假指針指向它）同時我們不能移動任何內(nèi)存區(qū)域。

編譯器提示法

如果是靜態(tài)語言，編譯器能夠告訴我們每個類當(dāng)中指針的具體位置，而一旦我們知道對象時哪個類實(shí)例化得到的，就能知道對象中所有指針。這是JVM實(shí)現(xiàn)垃圾回收的方式，但這種方式并不適合JS這樣的動態(tài)語言

標(biāo)記指針法

標(biāo)記指針法：這種方法需要在每個字末位預(yù)留一位來標(biāo)記這個字段是指針還是數(shù)據(jù)。這種方法需要編譯器支持，但實(shí)現(xiàn)簡單，而且性能不錯。V8采用的是這種方式。

位圖標(biāo)記(Go語言為例)

非侵入式標(biāo)記位定義
既然垃圾回收算法要求給對象加上垃圾回收的標(biāo)記，顯然是需要有標(biāo)記位的。一般的做法
會將對象結(jié)構(gòu)體中加上一個標(biāo)記域，一些優(yōu)化的做法會利用對象指針的低位進(jìn)行標(biāo)記，這
都只是些奇技淫巧罷了。Go沒有這么做，它的對象和C的結(jié)構(gòu)體對象完全一致，使用的是
非侵入式的標(biāo)記位。

具體實(shí)現(xiàn)
堆區(qū)域?qū)?yīng)了一個標(biāo)記位圖區(qū)域，堆中每個字(不是byte，而是word)都會在標(biāo)記位區(qū)域
中有對應(yīng)的標(biāo)記位。每個機(jī)器字(32位或64位)會對應(yīng)4位的標(biāo)記位。因此，64位系統(tǒng)中
相當(dāng)于每個標(biāo)記位圖的字節(jié)對應(yīng)16個堆中的字節(jié)。

雖然是一個堆字節(jié)對應(yīng)4位標(biāo)記位，但標(biāo)記位圖區(qū)域的內(nèi)存布局并不是按4位一組，而是
16個堆字節(jié)為一組，將它們的標(biāo)記位信息打包存儲的。每組64位的標(biāo)記位圖從上到下依
次包括：

16位的 特殊位 標(biāo)記位
16位的 垃圾回收 標(biāo)記位
16位的 無指針/塊邊界 的標(biāo)記位
16位的 已分配 標(biāo)記位

這樣設(shè)計(jì)使得對一個類型的相應(yīng)的位進(jìn)行遍歷很容易。

前面提到堆區(qū)域和堆地址的標(biāo)記位圖區(qū)域是分開存儲的，其實(shí)它們是以
mheap.arena_start地址為邊界，向上是實(shí)際使用的堆地址空間，向下則是標(biāo)記位圖區(qū)
域。以64位系統(tǒng)為例，計(jì)算堆中某個地址的標(biāo)記位的公式如下：

偏移 = 地址 - mheap.arena_start
標(biāo)記位地址 = mheap.arena_start - 偏移/16 - 1
移位 = 偏移 % 16
標(biāo)記位 = *標(biāo)記位地址 >> 移位

然后就可以通過 (標(biāo)記位 & 垃圾回收標(biāo)記位),(標(biāo)記位 & 分配位),等來測試相應(yīng)的位。

(也就是說，本來64位是一個字，需要4位標(biāo)記位。但是，為了與字長相對，16個標(biāo)記位
放一起（剛好一個字長）一起表示16個字。并且每類標(biāo)記位都放在一起
AA..AABB...BB)

接下來補(bǔ)充幾個概念幫助理解：

為什么要判斷哪些是數(shù)據(jù)，哪些是指針？
假設(shè)堆中有一個long的變量，它的值是8860225560。但是我們不知道它的類型是
long，所以在進(jìn)行垃圾回收時會把個當(dāng)作指針處理，這個指針引用到了0x2101c5018位
置。假設(shè)0x2101c5018碰巧有某個對象，那么這個對象就無法被釋放了，即使實(shí)際上已
經(jīng)沒任何地方使用它。

由于沒有類型信息，我們并不知道這個結(jié)構(gòu)體成員不包含指針，因此我們只能對結(jié)構(gòu)體
的每個字節(jié)遞歸地標(biāo)記下去，這顯然會浪費(fèi)很多時間。
（能不能清除 變成了概率事件）。

垃圾收集器（CMS收集器為例）
幾個階段：

初始標(biāo)記
并發(fā)標(biāo)記
最終標(biāo)記
篩選回收

初始標(biāo)記僅僅是標(biāo)記一下GC Roots能直接關(guān)聯(lián)到的對象，速度很快，并發(fā)標(biāo)記就是進(jìn)行
GC Roots Trancing的過程，而重新標(biāo)記階段則是為了修正并發(fā)標(biāo)記期間因用戶程序繼
續(xù)運(yùn)行而導(dǎo)致標(biāo)記產(chǎn)生變動那一部分對象的標(biāo)記記錄，這個階段的停頓時間比初始標(biāo)記稍
長一些，但遠(yuǎn)比并發(fā)標(biāo)記時間短。

stop the world
因?yàn)槔厥盏臅r候，需要整個的引用狀態(tài)保持不變，否則判定是垃圾，等我稍后回
收的時候它又被引用了，這就全亂套了。所以，GC的時候，其他所有的程序執(zhí)行處于暫停
狀態(tài)，卡住了。
這個概念提前引入，在這里進(jìn)行對比，效果會更好些。與標(biāo)記階段對比，stop the world發(fā)生在回收階段。

這里我們介紹幾種不同的垃圾回收算法

標(biāo)記清除算法 (Mark-Sweep)

標(biāo)記-清除算法分為兩個階段：標(biāo)記階段和清除階段。標(biāo)記階段的任務(wù)是標(biāo)記出所有需要被回收的對象，清除階段就是回收被標(biāo)記的對象所占用的空間。

優(yōu)點(diǎn)是簡單，容易實(shí)現(xiàn)。
缺點(diǎn)是容易產(chǎn)生內(nèi)存碎片，碎片太多可能會導(dǎo)致后續(xù)過程中需要為大對象分配空間時無法找到足夠的空間而提前觸發(fā)新的一次垃圾收集動作。（因?yàn)闆]有對不同生命周期的對象采用不同算法，所以碎片多，內(nèi)存容易滿，gc頻率高，耗時，看了后面的方法就明白了）

分代回收算法

根據(jù)對象存活的生命周期將內(nèi)存劃分為若干個不同的區(qū)域。不同區(qū)域采用不同算法（復(fù)制算法，標(biāo)記整理算法），這就是分代回收算法。

一般情況下將堆區(qū)劃分為老年代（Old Generation）和新生代（Young Generation），老年代的特點(diǎn)是每次垃圾收集時只有少量對象需要被回收，而新生代的特點(diǎn)是每次垃圾回收時都有大量的對象需要被回收，那么就可以根據(jù)不同代的特點(diǎn)采取最適合的收集算法。

1.新生代回收

新生代使用Scavenge算法進(jìn)行回收。在Scavenge算法的實(shí)現(xiàn)中，主要采用了Cheney算法。

Cheney算法是一種采用復(fù)制的方式實(shí)現(xiàn)的垃圾回收算法。
它將內(nèi)存一分為二，每一部分空間稱為semispace。在這兩個semispace中，一個處于使用狀態(tài)，另一個處于閑置狀態(tài)。
簡而言之，就是通過將存活對象在兩個semispace空間之間進(jìn)行復(fù)制。

復(fù)制過程采用的是BFS（廣度優(yōu)先遍歷）的思想，從根對象出發(fā)，廣度優(yōu)先遍歷所有能到達(dá)的對象

優(yōu)點(diǎn)：時間效率上表現(xiàn)優(yōu)異（犧牲空間換取時間）
缺點(diǎn)：只能使用堆內(nèi)存的一半

新生代的空間劃分比例為什么是比例為8：1：1（不是按照上面算法中說的1：1）？

新創(chuàng)建的對象都是放在Eden空間，這是很頻繁的，尤其是大量的局部變量產(chǎn)生的臨時對
象，這些對象絕大部分都應(yīng)該馬上被回收，能存活下來被轉(zhuǎn)移到survivor空間的往往不
多。所以，設(shè)置較大的Eden空間和較小的Survivor空間是合理的，大大提高了內(nèi)存的使
用率，緩解了Copying算法的缺點(diǎn)。

8：1：1就挺好的，當(dāng)然這個比例是可以調(diào)整的，包括上面的新生代和老年代的1：2的
比例也是可以調(diào)整的。

Eden空間和兩塊Survivor空間的工作流程是怎樣的？

具體的執(zhí)行過程是怎樣的？

假設(shè)有類似如下的引用情況：

          +----- A對象
          |
根對象----+----- B對象 ------ E對象
          |
          +----- C對象 ----+---- F對象 
                           |
                           +---- G對象 ----- H對象

    D對象

在執(zhí)行Scavenge之前，F(xiàn)rom區(qū)長這幅模樣:
```
+---+---+---+---+---+---+---+---+--------+
| A | B | C | D | E | F | G | H |        |
+---+---+---+---+---+---+---+---+--------+
```
那么首先將根對象能到達(dá)的ABC對象復(fù)制到To區(qū)，于是乎To區(qū)就變成了這個樣子：
```
     allocationPtr
             ↓ 
+---+---+---+----------------------------+
| A | B | C |                            |
+---+---+---+----------------------------+
 ↑
scanPtr  

```
接下來進(jìn)入循環(huán)，掃描scanPtr所指的A對象，發(fā)現(xiàn)其沒有指針，于是乎scanPtr移動，變成如下這樣

```
          allocationPtr
             ↓ 
+---+---+---+----------------------------+
| A | B | C |                            |
+---+---+---+----------------------------+
     ↑
  scanPtr  
```
接下來掃描B對象，發(fā)現(xiàn)其有指向E對象的指針，且E對象在From區(qū)，那么我們需要將E對象復(fù)制到allocationPtr所指的地方并移動allocationPtr指針：

```
                allocationPtr
                 ↓ 
+---+---+---+---+------------------------+
| A | B | C | E |                        |
+---+---+---+---+------------------------+
     ↑
  scanPtr  
```
中間過程省略，具體參考[新生代的垃圾回收具體的執(zhí)行過程][3]

From區(qū)和To區(qū)在復(fù)制完成后的結(jié)果：
```
//From區(qū)
+---+---+---+---+---+---+---+---+--------+
| A | B | C | D | E | F | G | H |        |
+---+---+---+---+---+---+---+---+--------+
//To區(qū)
+---+---+---+---+---+---+---+------------+
| A | B | C | E | F | G | H |            |
+---+---+---+---+---+---+---+------------+
```

最終當(dāng)scanPtr和allocationPtr重合，說明復(fù)制結(jié)束。
注意：如果指向老生代我們就不必考慮它了。（通過寫屏障）

對象何時晉升？

1.當(dāng)一個對象經(jīng)過多次新生代的清理依舊幸存。
2.如果To空間已經(jīng)被使用了超過25%（后面還要進(jìn)來許多新對象，不敢占用太多）
3.大對象
（其實(shí)這部分，包括次數(shù)，比例等，是視情況設(shè)置的。）

2.老生代回收

Mark-Sweep（標(biāo)記清除）

標(biāo)記清除分為標(biāo)記和清除兩個階段。
主要是標(biāo)記清除只清除死亡對象，而死亡對象在老生代中占用的比例很小，所以效率較高。

Mark-Compact（標(biāo)記整理）

標(biāo)記整理正是為了解決標(biāo)記清除所帶來的內(nèi)存碎片的問題。

大體過程就是 雙端隊(duì)列標(biāo)記黑（鄰接對象已經(jīng)全部處理），白（待釋放垃圾），灰（鄰
接對象尚未全部處理）三種對象.
 
標(biāo)記算法的核心就是深度優(yōu)先搜索.

補(bǔ)充概念方便理解

1.觸發(fā)GC（何時發(fā)生垃圾回收？）

一般都是內(nèi)存滿了就回收，下面列舉幾個常見原因：
GC_FOR_MALLOC: 表示是在堆上分配對象時內(nèi)存不足觸發(fā)的GC。
GC_CONCURRENT: 當(dāng)我們應(yīng)用程序的堆內(nèi)存達(dá)到一定量，或者可以理解為快要滿的時候，系統(tǒng)會自動觸發(fā)GC操作來釋放內(nèi)存。
GC_EXPLICIT: 表示是應(yīng)用程序調(diào)用System.gc、VMRuntime.gc接口或者收到SIGUSR1信號時觸發(fā)的GC。
GC_BEFORE_OOM: 表示是在準(zhǔn)備拋OOM異常之前進(jìn)行的最后努力而觸發(fā)的GC。

2.寫屏障（一個老年代的對象需要引用年輕代的對象，該怎么辦？）

如果新生代中的一個對象只有一個指向它的指針，而這個指針在老生代中，我們?nèi)绾闻袛?這個新生代的對象是否存活？為了解決這個問題，需要建立一個列表用來記錄所有老生代
對象指向新生代對象的情況。每當(dāng)有老生代對象指向新生代對象的時候，我們就記錄下
來。
當(dāng)垃圾回收發(fā)生在年輕代時，只需對這張表進(jìn)行搜索以確定是否需要進(jìn)行垃圾回收，而不
是檢查老年代中的所有對象引用。

3.深度、廣度優(yōu)先搜索（為什么新生代用廣度搜索，老生代用深度搜索）

深度優(yōu)先DFS一般采用遞歸方式實(shí)現(xiàn)，處理tracing的時候，可能會導(dǎo)致棧空間溢出，所以一般采用廣度優(yōu)先來實(shí)現(xiàn)tracing（遞歸情況下容易爆棧）。
廣度優(yōu)先的拷貝順序使得GC后對象的空間局部性（memory locality）變差（相關(guān)變量散開了）。
廣度優(yōu)先搜索法一般無回溯操作，即入棧和出棧的操作，所以運(yùn)行速度比深度優(yōu)先搜索算法法要快些。
深度優(yōu)先搜索法占內(nèi)存少但速度較慢，廣度優(yōu)先搜索算法占內(nèi)存多但速度較快。

結(jié)合深搜和廣搜的實(shí)現(xiàn)，以及新生代移動數(shù)量小，老生代數(shù)量大的情況，我們可以得到了解答。