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

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

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

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

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

引用與指針：

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

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

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

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

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

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

堆（heap）和棧（stack）

平常說的“堆棧”其實是棧。

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

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

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

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

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

就是它，先上圖

]

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

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

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

引用計數(shù)法

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

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

可達性分析算法（根搜索算法）

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

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

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

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

這里我們介紹幾種不同的 “標記對象”的方法

保守法

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

編譯器提示法

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

標記指針法

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

位圖標記(Go語言為例)

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

具體實現(xiàn)
堆區(qū)域?qū)艘粋€標記位圖區(qū)域，堆中每個字(不是byte，而是word)都會在標記位區(qū)域
中有對應的標記位。每個機器字(32位或64位)會對應4位的標記位。因此，64位系統(tǒng)中
相當于每個標記位圖的字節(jié)對應16個堆中的字節(jié)。

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

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

這樣設計使得對一個類型的相應的位進行遍歷很容易。

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

偏移 = 地址 - mheap.arena_start
標記位地址 = mheap.arena_start - 偏移/16 - 1
移位 = 偏移 % 16
標記位 = *標記位地址 >> 移位

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

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

接下來補充幾個概念幫助理解：

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

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

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

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

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

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

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

標記清除算法 (Mark-Sweep)

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

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

分代回收算法

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

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

1.新生代回收

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

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

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

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

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

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

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

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

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

假設有類似如下的引用情況：

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

    D對象

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

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

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

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

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

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

對象何時晉升？

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

2.老生代回收

Mark-Sweep（標記清除）

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

Mark-Compact（標記整理）

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

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

補充概念方便理解

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

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

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

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

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

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

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