內(nèi)存區(qū)域劃分篮愉，從高地址到低地址依次是

• 棧區(qū)：內(nèi)存由系統(tǒng)控制開(kāi)辟、釋放集侯。當(dāng)系統(tǒng)的棧區(qū)大小不夠分配時(shí)被啼， 系統(tǒng)會(huì)提示棧溢出。存放時(shí)按照先入先出原則棠枉，從高地址向低地址擴(kuò)展浓体。
• 堆區(qū)：內(nèi)存由程序控制開(kāi)辟、釋放辈讶。如果程序沒(méi)有釋放命浴，在程序結(jié)束時(shí)，由系統(tǒng)釋放贱除。但是在程序運(yùn)行時(shí)生闲，會(huì)出現(xiàn)內(nèi)存泄漏，內(nèi)存溢出等問(wèn)題月幌。分配方式類似于鏈表碍讯。從低地址向高地址擴(kuò)展。
• 全局靜態(tài)區(qū)：全局變量扯躺、靜態(tài)變量會(huì)存儲(chǔ)在此區(qū)域捉兴。初始化的全局變量跟靜態(tài)變量放在一片區(qū)域，未初始化的全局變量與靜態(tài)變量放在相鄰的另一片區(qū)域录语。程序結(jié)束后由系統(tǒng)釋放轴术。
• 文字常量區(qū)：在程序中使用的常量存儲(chǔ)在此區(qū)域。程序結(jié)束后钦无，由系統(tǒng)釋放逗栽。
• 程序代碼區(qū)： 存放函數(shù)體的二進(jìn)制代碼。

以上 全局靜態(tài)區(qū)失暂、文字常量區(qū)彼宠、程序代碼區(qū) 在程序運(yùn)行起來(lái)的時(shí)候就開(kāi)辟好了
棧區(qū)由系統(tǒng)控制釋放鳄虱、開(kāi)辟
垃圾回收機(jī)制主要就體現(xiàn)堆區(qū)的內(nèi)存管理方面

基本概念

• GC：Garbage Collection。垃圾回收凭峡。
• Collector拙已，用于進(jìn)行垃圾回收的線程
• Mutators，應(yīng)用程序的線程摧冀，可以修改 heap
• MS倍踪，mark-sweep 算法的簡(jiǎn)寫(xiě)
• MC，mark-compact 算法的簡(jiǎn)寫(xiě)
• RC索昂，reference-counting 的簡(jiǎn)寫(xiě)
• liveness建车，一個(gè)對(duì)象的可到達(dá)性
• 引用關(guān)系圖，由可到達(dá)對(duì)象引用形成的圖結(jié)構(gòu)
• locality椒惨，現(xiàn)代CPU在訪問(wèn)內(nèi)存時(shí)缤至，有多級(jí)緩存。緩存以 cache line （一般64字節(jié)）為最小操作單位康谆，所以當(dāng)訪問(wèn)內(nèi)存中連續(xù)的數(shù)據(jù)時(shí)會(huì)比較高效领斥，這稱為 locality
• Roots，所有根對(duì)象沃暗，比如全局對(duì)象月洛，stack 中的對(duì)象

一、手動(dòng)垃圾回收

這個(gè)沒(méi)什么好說(shuō)的孽锥，c語(yǔ)言就需要手動(dòng)垃圾回收

int *elements = malloc(10 * sizeof(int));
free(elements)

二嚼黔、引用計(jì)數(shù)（Reference Counting）

• 為每個(gè)對(duì)象存儲(chǔ)一個(gè)引用計(jì)數(shù)，新創(chuàng)建的對(duì)象忱叭，引用計(jì)數(shù)為1
• 當(dāng)有一個(gè)新的指針指向這個(gè)對(duì)象時(shí)隔崎，引用計(jì)數(shù)加1
• 當(dāng)某個(gè)指針不再指向這個(gè)對(duì)象時(shí)今艺，引用計(jì)數(shù)減1
• 當(dāng)引用計(jì)數(shù)為0時(shí)韵丑，將對(duì)象銷毀，回收內(nèi)存
  優(yōu)點(diǎn)
  1.可以保證對(duì)象引用為0時(shí)立馬得到清理虚缎，無(wú)不確定行
  2.大多數(shù)操作具有增量特性（incremental）撵彻，GC 可與應(yīng)用交替運(yùn)行，不需要暫停應(yīng)用即可完成回收功能
  3.可以用來(lái)優(yōu)化運(yùn)行時(shí)性能实牡。比如函數(shù)式編程中所推崇的「 不可變數(shù)據(jù)結(jié)構(gòu) 」的更新就能收益：運(yùn)行時(shí)知道某個(gè)對(duì)象的引用為1陌僵，這時(shí)對(duì)這個(gè)對(duì)象進(jìn)行修改，類似 str <-str+"a"创坞，那么這個(gè)修改就可以在本地進(jìn)行碗短，而不必進(jìn)行額外的 copy
  缺點(diǎn)
  1.無(wú)法解決循環(huán)引用。
  2.實(shí)現(xiàn)一個(gè)高效率的引用計(jì)數(shù) GC 比較困難题涨。每個(gè)對(duì)象需要額外的空間來(lái)存儲(chǔ)其引用次數(shù)偎谁。在增加/減少對(duì)象的引用時(shí)总滩，需要修改引用次數(shù)。修改引用次數(shù)對(duì)于棧上的賦值巡雨，影響是非常大的闰渔。因?yàn)橹爸恍枰?jiǎn)單修改寄存器里面的值，現(xiàn)在需要一個(gè)原子操作（這涉及到加鎖铐望，會(huì)浪費(fèi)幾百個(gè) CPU cycles）
  3.減少一個(gè)對(duì)象的引用計(jì)數(shù)時(shí)冈涧，會(huì)級(jí)聯(lián)減少其引用對(duì)象的計(jì)數(shù)，這就可能造成同時(shí)刪除過(guò)多的對(duì)象正蛙。在實(shí)現(xiàn)中一般會(huì)把要回收的對(duì)象放入一隊(duì)列督弓，當(dāng)程序申請(qǐng)大小為 N 的內(nèi)存時(shí)，從這個(gè)隊(duì)列取出總體積不小于 N 的一個(gè)或多個(gè)對(duì)象將其回收跟畅。

采用這類 GC 的主流語(yǔ)言有：Python/PHP/ Perl /TCL/Objective-C咽筋。

三、追蹤類（tracing）GC

3.1 MS算法：標(biāo)記-清除（Mark-Sweep）

• mark徊件，從 root 開(kāi)始進(jìn)行樹(shù)遍歷奸攻，每個(gè)訪問(wèn)的對(duì)象標(biāo)注為「使用中」
• sweep，掃描整個(gè)內(nèi)存區(qū)域虱痕，對(duì)于標(biāo)注為「使用中」的對(duì)象去掉該標(biāo)志睹耐，對(duì)于沒(méi)有該標(biāo)注的對(duì)象直接回收掉
  優(yōu)點(diǎn)
  1.用以標(biāo)注對(duì)象是否在使用中的flag 位一般放在引用變量里面，不需要額外的空間部翘。
  2.較引用計(jì)數(shù)（Reference Counting） 性能更高
  缺點(diǎn)
  1.在進(jìn)行 GC 期間硝训，整個(gè)系統(tǒng)會(huì)被掛起（暫停，Stop-the-world）新思，所以在一些實(shí)現(xiàn)中窖梁，會(huì)采用各種措施來(lái)減少這個(gè)暫停時(shí)間
  2.heap 容易出現(xiàn)碎片。實(shí)現(xiàn)中一般會(huì)進(jìn)行 move 或 compact夹囚。（需要說(shuō)明一點(diǎn)纵刘，所有 heap 回收機(jī)制都會(huì)這個(gè)問(wèn)題）
  3.回收時(shí)間與 heap 大小成正比
  4.破壞引用本地性。其實(shí)還是因?yàn)樗槠瘜?dǎo)致的荸哟。（時(shí)間局部性是指假哎，被引用一次的儲(chǔ)存器位置，在接下來(lái)的時(shí)間會(huì)經(jīng)常被引用鞍历，這樣我們就說(shuō)他有良好的時(shí)間局部性舵抹。空間局部性是指劣砍，被引用一次的儲(chǔ)存器位置惧蛹，在接下來(lái)的時(shí)間，他旁邊的儲(chǔ)存器位置也會(huì)被引用，這樣我們就說(shuō)他有良好的空間局部性）

3.2 優(yōu)化MS算法 - 優(yōu)化mark過(guò)程

在 mark 過(guò)程中香嗓，需要去標(biāo)記（mark-bits）對(duì)象的 liveness爵政，有兩種方式來(lái)實(shí)現(xiàn)：

• 在每個(gè)對(duì)象的header部分（in-object mark-bit）
• 使用一個(gè)單獨(dú)的 bitmap，每一位 bit 對(duì)應(yīng)一個(gè)對(duì)象

兩種方式各有利弊陶缺，需要結(jié)合具體場(chǎng)景進(jìn)行分析钾挟。重點(diǎn)說(shuō)一下bitmap：
對(duì)于 bitmap 來(lái)說(shuō)，需要在 bit 位與 object 之間進(jìn)行映射饱岸，這就要求 object 進(jìn)行對(duì)齊掺出，比如：heap 大小為 65536 字節(jié)，所有的對(duì)象以 16 字節(jié)對(duì)齊苫费，那么堆內(nèi)就有 4096 個(gè)地址可以作為對(duì)象的起始地址汤锨，與之對(duì)應(yīng)需要 4096 個(gè) bit 即 512 個(gè)字節(jié)。所以使sweep 操作更高效百框，這是由于 bitmap 結(jié)構(gòu)緊湊闲礼，可以一次性加載到內(nèi)存中，一次性進(jìn)行多位的檢測(cè)铐维。

3.3 優(yōu)化MS算法 - 優(yōu)化sweep過(guò)程

MS 算法有以下兩個(gè)特點(diǎn)：

• 某對(duì)象一旦被標(biāo)為garbage柬泽，它永遠(yuǎn)都會(huì)是 garbage，不會(huì)被 mutator 再訪問(wèn)
• mutator 不能修改 mark-bit

基于以上兩點(diǎn)嫁蛇，sweep 操作完全可以與 mutator 同時(shí)運(yùn)行（parallel）的锨并。
Lazy sweep 指的是把較為耗時(shí)（相對(duì) mark 來(lái)說(shuō)）的 sweep 操作放在 allocate 過(guò)程中，并且只在沒(méi)有足夠的空間時(shí)才去真正進(jìn)行回收睬棚。
核心就是第煮，把標(biāo)記為待回收的內(nèi)存塊，放入一個(gè)隊(duì)列中延遲回收抑党。當(dāng)需要開(kāi)辟空間且內(nèi)存不夠時(shí)包警，根據(jù)需要開(kāi)辟內(nèi)存的空間大小，在待回收隊(duì)列中釋放內(nèi)存底靠。

Lazy Sweep 除了降低 sweep 階段 mutator 的暫停時(shí)間外害晦，還有以下優(yōu)點(diǎn)：

• 更好的 locality。這是因?yàn)楸换厥盏?block 會(huì)盡快地重新使用
• GC 復(fù)雜度只與可到達(dá)對(duì)象（即正在使用中的對(duì)象數(shù)）成正比
• 在大部分 heap 空間為空時(shí)效率最好

3.4 優(yōu)化MS算法 - 碎片問(wèn)題 - MC算法：標(biāo)記-整理（Mark-Compact）

MC 算法與 MS 類似苛骨，先是一個(gè) mark 過(guò)程標(biāo)記可到達(dá)對(duì)象篱瞎，這里取代 sweep 的是一個(gè) compact苟呐，工作流程如下：

• 移動(dòng)（relocate）可到達(dá)對(duì)象
• 更新指向可到達(dá)對(duì)象的指針

關(guān)于第一步中的安排策略痒芝，一般有如下三種選擇：

• 任意（Arbitrary）。特點(diǎn)是快牵素，但是空間局部性較差
• 線性（Linearising）严衬。重新分配到附近有關(guān)系的（siblings/pointer/reference…）對(duì)象周邊
• 滑動(dòng)（Sliding）。所有活對(duì)象被滑動(dòng)到 heap 的一端笆呆，保證原有順序请琳，這有利于改善 locality 的情況粱挡。這是現(xiàn)在采用較多的方案

對(duì)于采用 MC 的系統(tǒng)，allocate 過(guò)程就變得較為簡(jiǎn)單俄精，只需要bump pointer 即可询筏。
但是這類算法需要多次遍歷對(duì)象，第一次遍歷算出對(duì)象將要移動(dòng)到的新位置竖慧，接下來(lái)的遍歷來(lái)真正移動(dòng)對(duì)象嫌套，并更新指針，所以MC相對(duì)MS要更耗時(shí)圾旨，這在 heap 較大時(shí)更為明顯踱讨。

這里比較有名的是 Edward 的 Two-pointer 壓縮算法。大致過(guò)程如下：

• 在 heap 兩端各準(zhǔn)備一指針砍的，由外向內(nèi) scan 尋找可整理的對(duì)象
• 自頂向下的指針尋找可到達(dá)對(duì)象痹筛，自底向上的指針尋找 heap 中的“洞”來(lái)存放可到達(dá)對(duì)象

3.5 優(yōu)化MC算法 - 效率問(wèn)題 - Copying GC算法

MC 算法雖然能解決內(nèi)存碎片問(wèn)題，但是需要多次遍歷heap空間廓鞠，這會(huì)導(dǎo)致較大性能損耗帚稠，Copying GC 采用空間換時(shí)間的方式來(lái)提升性能。
這類 GC 并不會(huì)真正去“回收”不可到達(dá)對(duì)象床佳，而是會(huì)把所有可到達(dá)對(duì)象移動(dòng)到一個(gè)區(qū)域翁锡，heap 中剩余的空間就是可用的了（因?yàn)檫@里面都是垃圾）。這里并沒(méi)有進(jìn)行 sweep/compact夕土，而是用 scavenging（凈化） 來(lái)描述回收這一過(guò)程馆衔。

Copying GC 典型的代表半空間回收器（semispace collector）。其工作過(guò)程是這樣的：

• heap 被分成2份相鄰的空間（semispace）：fromspace 與 tospace
• 在程序運(yùn)行時(shí)怨绣，只有 fromspace 會(huì)被使用（分配新對(duì)象）
• 在 fromspace 沒(méi)有足夠空間容納新對(duì)象時(shí)角溃，程序會(huì)被掛起，然后把 fromspace 的可到達(dá)對(duì)象拷貝到 tospace
• 在拷貝完成時(shí)篮撑，之前的2個(gè)空間交換身份减细，tospace 成了新一輪的 fromspace

Cheney 算法是用來(lái)解決如何遍歷引用關(guān)系圖，將之移動(dòng)到 tospace 的算法赢笨，其步驟如下：

1. 所有可直接到達(dá)的對(duì)象組成一隊(duì)列未蝌，作為寬度優(yōu)先遍歷的起點(diǎn)，同時(shí)有兩個(gè)輔助指針：scan 指針指向起始位置茧妒，free 指針指向末尾
2. 通過(guò)移動(dòng) scan 來(lái)依次遍歷隊(duì)列萧吠，當(dāng) scan 的對(duì)象存在指向 fromspace 中對(duì)象的指針時(shí)，把被指向的對(duì)象添加到隊(duì)列末端桐筏，同時(shí)更新指針纸型，使之指向新對(duì)象；
3. 更新 free 使之始終指向初始時(shí)隊(duì)列末尾所指的那個(gè)對(duì)象，重復(fù)步驟2
4. 當(dāng) scan 移動(dòng)到初始時(shí)隊(duì)列末尾所指的那個(gè)對(duì)象時(shí)狰腌，即scan與free指向同一對(duì)象時(shí)除破，算法結(jié)束。

如果按照上述算法操作琼腔，會(huì)把被指向多次的對(duì)象復(fù)制多次(類似于引用計(jì)數(shù)為N瑰枫，同一個(gè)可觸達(dá)對(duì)象在隊(duì)列中有多份)，所以在拷貝對(duì)象到 tospace 時(shí)丹莲，會(huì)在原始版本的對(duì)象上記錄一個(gè)重定向指針（forwarding pointer）躁垛，來(lái)標(biāo)明這個(gè)對(duì)象已經(jīng)被復(fù)制過(guò)了，并且告知新對(duì)象的位置圾笨；后面 scan 對(duì)象時(shí)教馆，如果發(fā)現(xiàn)具有重定向指針的對(duì)象時(shí)就會(huì)跳過(guò)復(fù)制操作，直接更新指針就可以了擂达。

3.6 優(yōu)化Copying算法 - 空間問(wèn)題 - Non-Copying Implicit GC算法

通過(guò)上述描述土铺，不難發(fā)現(xiàn)Copying GC 一最大缺點(diǎn)在于所需空間翻倍，不過(guò)現(xiàn)如今內(nèi)存已經(jīng)普遍較大板鬓，這個(gè)問(wèn)題不是很嚴(yán)重悲敷。
其次，復(fù)制的效率與可到達(dá)對(duì)象成正比俭令，如果每次 GC 時(shí)可到達(dá)對(duì)象占用的空間接近semispace空間后德，那么只能通過(guò)降低 GC 頻率減少 GC 對(duì)程序的影響。如何降低 GC 頻率呢抄腔？答案就是加大 semispace 空間瓢湃，這樣程序就需要更多的時(shí)間來(lái)填滿它。

Non-Copying Implicit GC從 Copying GC 衍化而來(lái)赫蛇，核心是绵患，semispace 不必是物理上分割的空間，可以用兩個(gè)用雙向鏈表來(lái)表示悟耘，一般稱為 ：from-set 與 to-set落蝙。為了實(shí)現(xiàn)這種策略，需要在每個(gè)對(duì)象上多加以下兩個(gè)信息：

• 兩個(gè)指針暂幼，用來(lái)形成鏈表
• 一個(gè)flag筏勒，標(biāo)明屬于哪個(gè)集合

當(dāng) from-set 耗盡時(shí)，只需遍歷 from-set旺嬉，把其中的可到達(dá)對(duì)象插入到 to-set管行，然后改變flag即可，復(fù)制操作變成了鏈表指針操作鹰服。這類 GC 的優(yōu)勢(shì)除了不用進(jìn)行真正的拷貝外病瞳，還有下面兩處優(yōu)點(diǎn)：

• 語(yǔ)言級(jí)別的指針不需要改變了（因?yàn)閷?duì)象沒(méi)動(dòng)），這對(duì)編譯器的要求更小了
• 如果一個(gè)對(duì)象不含有指針悲酷，那么就沒(méi)必要 scan 了
  缺點(diǎn)當(dāng)然也比較明顯：
• 每個(gè)對(duì)象需要而外的空間
• 碎片問(wèn)題又回來(lái)了

所以這類 GC 雖然是 Copying GC 的優(yōu)化套菜，但也只適用于某些特定的場(chǎng)景。

通過(guò)上面的介紹设易，覺(jué)得最重要的就是要分清一個(gè)算法的優(yōu)勢(shì)與劣勢(shì)逗柴，軟件工程里面沒(méi)有「銀彈」，都是有取舍的顿肺。

上面對(duì) MS 算法的優(yōu)化戏溺，基本都是在 sweep 階段，mark 階段沒(méi)怎么改進(jìn)屠尊。
但 mark 階段會(huì)導(dǎo)致應(yīng)用程序掛起旷祸，也就是常說(shuō)的：stop-the-world（STW），這嚴(yán)重影響了 Tracing GC 的應(yīng)用場(chǎng)景讼昆。

3.7 增量式 GC 思路（Incremental Collection）

增量式（incremental）GC 顧名思義托享，允許 collector 分多個(gè)小批次執(zhí)行，每次造成的 mutator 停頓都很小浸赫，達(dá)到近似實(shí)時(shí)的效果闰围。
引用計(jì)數(shù)類 GC 本身就具有增量式特性，但由于其算法自身的缺陷與效率問(wèn)題既峡，一般不會(huì)采用羡榴。而追蹤類 GC 實(shí)現(xiàn)增量式的難點(diǎn)在于：
這是一個(gè)并發(fā)問(wèn)題，collector 線程與 mutator 線程同時(shí)去讀/寫(xiě)一些共享的數(shù)據(jù)結(jié)構(gòu)（引用關(guān)系圖）运敢，這就要求把它加鎖保護(hù)起來(lái)校仑。
在 GC 期間，對(duì) mutator 改變「引用關(guān)系圖」的保守度（conservatism）是增量式 GC 一大特性传惠。如果 mutator 在 collector 遍歷某對(duì)象后將其釋放（floating garbage）肤视，那么這個(gè)對(duì)象在本次 GC 不會(huì)被回收，但在下一輪 GC 開(kāi)始時(shí)會(huì)被回收涉枫。
這種弱一致性（relaxed consistency）是允許的邢滑，因?yàn)樗粫?huì)對(duì)程序邏輯造成影響，只是延遲了垃圾對(duì)象的回收愿汰，而且一致性越弱困后，遍歷算法的實(shí)現(xiàn)就可以更靈活。

三色標(biāo)記（tricolor marking）抽象屏蔽了 GC 實(shí)現(xiàn)的算法（MS/Copying）衬廷、遍歷策略（寬度優(yōu)先/深度優(yōu)先）等細(xì)節(jié)摇予，具體來(lái)說(shuō)是在 GC 遍歷引用關(guān)系圖時(shí)，對(duì)象會(huì)被標(biāo)為三種顏色：

• 黑色black吗跋，表明對(duì)象被 collector 訪問(wèn)過(guò)侧戴，屬于可到達(dá)對(duì)象
• 灰色gray宁昭，也表明對(duì)象被訪問(wèn)過(guò)，但是它的子節(jié)點(diǎn)還沒(méi)有被 scan 到
• 白色white酗宋，表明沒(méi)有被訪問(wèn)到积仗，如果在本輪遍歷結(jié)束時(shí)還是白色，那么就會(huì)被收回

對(duì)于 MS 來(lái)說(shuō)蜕猫，設(shè)置標(biāo)記位就是著色的過(guò)程：有 mark-bit 的即為黑色寂曹。對(duì) Copying GC 來(lái)說(shuō)，把對(duì)象從 fromspace 移動(dòng)到 tospace 就是著色過(guò)程：在 fromspace 中不可到達(dá)的對(duì)象為白色回右，被移動(dòng)到 tospace 的對(duì)象為黑色隆圆。
對(duì)于增量式 GC 來(lái)說(shuō)，需要在黑白之間有個(gè)中間狀態(tài)來(lái)記錄「那些之前被 collector 標(biāo)記黑色翔烁，后來(lái)又被 mutator 改變的對(duì)象」渺氧，這就是灰色的作用。

對(duì)于 MS（3.2） 來(lái)說(shuō)蹬屹，灰色對(duì)象是用于協(xié)助遍歷 queue 里面的對(duì)象阶女，
對(duì)于 Copying GC 來(lái)說(shuō)，灰色對(duì)象就是那些在 fromspace 中還沒(méi)被 scan 的對(duì)象哩治，
如果采用 Cheney 的寬度優(yōu)先遍歷算法秃踩，那么就是 scan 與 free 指針之間的對(duì)象。

增加的中間狀態(tài)灰色要求 mutator 不會(huì)把黑色對(duì)象直接指向白色對(duì)象（這稱為三色不變性 tri-color invariant）业筏，collector 就能夠認(rèn)為黑色對(duì)象不需要在 scan憔杨，只需要遍歷灰色對(duì)象即可。但這可能存在違法三色不變性的情況蒜胖。
違法三色不變性的情況簡(jiǎn)單來(lái)說(shuō)消别，
就是有三層節(jié)點(diǎn)，第一層節(jié)點(diǎn)被scan過(guò)台谢，且第二層節(jié)點(diǎn)全都可訪問(wèn)寻狂，此時(shí)第一層節(jié)點(diǎn)被著色為黑色，第二層節(jié)點(diǎn)被著色為灰色朋沮。
因?yàn)椴l(fā)蛇券，mutator此時(shí)做了修改，把第一層節(jié)點(diǎn)直接指向第三層的節(jié)點(diǎn)樊拓，第二層的節(jié)點(diǎn)不再指向第三層節(jié)點(diǎn)
scan繼續(xù)訪問(wèn)第二層節(jié)點(diǎn)纠亚，將第二層節(jié)點(diǎn)置位黑色，第三層節(jié)點(diǎn)因?yàn)榇藭r(shí)不再連接第二層節(jié)點(diǎn)筋夏，故依舊為白色蒂胞。第一層節(jié)點(diǎn)因?yàn)橐呀?jīng)scan過(guò)為黑色，所以在此輪中不會(huì)再次被scan条篷，第三層節(jié)點(diǎn)依舊為白色骗随。
當(dāng)遍歷結(jié)束蛤织，雖然第三層節(jié)點(diǎn)依舊被第一層節(jié)點(diǎn)連接，可依舊會(huì)因?yàn)槭前咨鴮?dǎo)致被釋放鸿染。

為了解決上面的違法三色不變性的問(wèn)題指蚜，一般有兩類方式來(lái)協(xié)調(diào) mutator 與 collector 的行為：

• 讀屏障（read barrier），它會(huì)禁止 mutator 訪問(wèn)白色對(duì)象牡昆，當(dāng)檢測(cè)到 mutator 即將要訪問(wèn)白色對(duì)象時(shí)姚炕，collector 會(huì)立刻訪問(wèn)該對(duì)象并將之標(biāo)為灰色摊欠。由于 mutator 不能訪問(wèn)指向白色對(duì)象的指針丢烘，也就無(wú)法使黑色對(duì)象指向它們了
• 寫(xiě)屏障（write barrier），它會(huì)記錄下 mutator 新增的由黑色–>白色對(duì)象的指針些椒，并把該對(duì)象標(biāo)為灰色播瞳，這樣 collector 就又能訪問(wèn)有問(wèn)題的對(duì)象了

讀/寫(xiě)屏障本質(zhì)是一些同步操作——在 mutator 進(jìn)行某些操作前，它必須激活 collector 進(jìn)行一些操作免糕。
如果沒(méi)有特殊的硬件支持赢乓，寫(xiě)屏障一般來(lái)說(shuō)效率要高于讀屏障，因?yàn)閔eap 指針的讀操作要多于寫(xiě)操作石窑。

3.8 分代式 GC 思路（Generational Collection）

增量式 GC 是對(duì) mark 階段的一大優(yōu)化牌芋，可以極大避免 STW 的影響。分代式 GC 根據(jù)對(duì)象生命周期（后面稱為 age）的特點(diǎn)來(lái)優(yōu)化 GC松逊，降低其性能消耗躺屁。
雖然對(duì)象的生命周期因應(yīng)用而異，但對(duì)于大多數(shù)應(yīng)用來(lái)說(shuō)经宏，80% 的對(duì)象在創(chuàng)建不久即會(huì)成為垃圾犀暑。因此，針對(duì)不同 age 的對(duì)象「劃分不同區(qū)域烁兰，采用不同的回收策略」也就不難理解了耐亏。
對(duì)于 Copying GC 來(lái)說(shuō)，需要在兩個(gè) semispace 間移動(dòng)對(duì)象沪斟，如果移動(dòng)對(duì)象較大广辰，就會(huì)對(duì)程序造成較大影響，而分代就能解決這個(gè)問(wèn)題主之。簡(jiǎn)單情況下可以分為兩個(gè)代：younger轨域、older。

younger 用于分配新對(duì)象杀餐，在這里的對(duì)象經(jīng)過(guò)幾輪 GC 后會(huì)移動(dòng)到 older干发。younger 與 older 相比空間要小，且 GC 發(fā)生更頻繁史翘。

分代算法的首要的問(wèn)題是「如何在不回收 older 的同時(shí)安全的回收 younger 里面的對(duì)象」
由于引用關(guān)系圖是全局的屬性枉长，older 里面的對(duì)象也必須考慮的冀续。比如 younger 里面的一對(duì)象只被 older 里面的對(duì)象引用了，如何保證 GC 不會(huì)錯(cuò)誤的回收這個(gè)對(duì)象呢必峰？

避免上述問(wèn)題的一個(gè)方法是采用寫(xiě)屏障（write barrier）洪唐，在 mutator 進(jìn)行指針存儲(chǔ)時(shí)，進(jìn)行一些額外的操作（bookkeeping）吼蚁。寫(xiě)屏障的主要目的是保證所有由 older-->younger 的指針在進(jìn)行 younger 內(nèi)的 GC 時(shí)被考慮在內(nèi)凭需，并且作為 root set 進(jìn)行 copy 遍歷。需要注意的是肝匆，這里的寫(xiě)屏障與增量式 GC 同樣具有一定的保守性粒蜈。這是由于所有由 older-->younger 的指針都會(huì)被當(dāng)作 root set，但在 older 內(nèi)的對(duì)象是否存活在進(jìn)行下一次 older GC 前是不可知的旗国，這也就造成了一些 floating garbage枯怖，不過(guò)這在現(xiàn)實(shí)中并不是不能接受的。

第二個(gè)問(wèn)題是「如何在不回收 younger 的同時(shí)安全的回收 older 里面的對(duì)象」能曾。為了獨(dú)立回收 older度硝，通過(guò)記錄所有由 younger-->older 的指針也是可行的，不過(guò)這會(huì)比較消耗性能寿冕。因?yàn)樵诖蠖鄶?shù)情況下蕊程，由 younger-->older 的指針數(shù)目要遠(yuǎn)大于 older-->younger 的，這是符合程序運(yùn)行規(guī)律的——?jiǎng)?chuàng)建一個(gè)新對(duì)象驼唱，將至指向一個(gè)老對(duì)象藻茂。

即便不記錄 younger-->older 的指針，也可以在不回收 younger 的前提下回收 older曙蒸，只不過(guò)這時(shí)會(huì)把 younger 里面的所有對(duì)象作為 root set捌治。盡管這樣遍歷的時(shí)間會(huì)與 younger 里面的對(duì)象數(shù)目成正比，但考慮到 younger 內(nèi)對(duì)象數(shù)量一般都要小于 older 的纽窟，而且遍歷操作的消耗要遠(yuǎn)小于 copying肖油，所以這也是一種可以接受的方式。

除了上面交叉引用的問(wèn)題臂港，對(duì)于一個(gè)分代的 GC 來(lái)說(shuō)森枪，還需要考慮下面幾個(gè)方面：

• 提升策略（advancement policy）。在一個(gè)代內(nèi)的對(duì)象經(jīng)過(guò)多少次 GC 會(huì)晉級(jí)到下一個(gè)代
• 堆組織（heap organization）审孽。在代與代之間或者一個(gè)代內(nèi)县袱，heap 空間如何組織可以保證高的 locality 與 緩存命中率
• 代之間的交叉引用（intergenerational references）。采用哪種方式來(lái)記錄這些指針最好佑力？dirty bit or indirect table

提升策略
最簡(jiǎn)單的提升策略是在每次 GC 遍歷時(shí)式散，把 live 的對(duì)象移動(dòng)到下一代去。這樣的優(yōu)勢(shì)有：

• 實(shí)現(xiàn)簡(jiǎn)單打颤，不需要去區(qū)分一個(gè)代內(nèi)不同對(duì)象的 age暴拄。對(duì)于 copying GC 來(lái)說(shuō)漓滔，只需要用一塊連續(xù)的區(qū)域表示即可懂扼，不需要 semispace望浩，也不需要額外的 header 來(lái)保存 age 信息
• 可以盡快的把大對(duì)象提升到 GC 頻率比較小的下一代中去

當(dāng)然，這樣做的問(wèn)題也比較明顯捶码，可能會(huì)把一些 age 較小的對(duì)象移動(dòng)到下一代中去撕蔼，導(dǎo)致下一代被更快的填滿豁鲤，所以一般會(huì)讓 younger 里面的對(duì)象停留一次，即第二次 GC 時(shí)才去提升鲸沮，當(dāng)然這時(shí)就需要記錄對(duì)象的 age 了琳骡。

至于是不是需要停留兩次，這個(gè)就不好說(shuō)了诉探，這個(gè)和應(yīng)用也比較相關(guān)日熬。一般來(lái)說(shuō)棍厌，如果代分的少肾胯，比如2個(gè)，那么會(huì)傾向多停留幾次耘纱，減慢 older 被填滿的速度敬肚；如果代的數(shù)目大于2，那么就傾向于快速提升束析，因?yàn)檫@些對(duì)象很有可能在中間的某個(gè)代就會(huì)死亡艳馒，不會(huì)到達(dá)最終的 older。

堆組織
分代式 GC 需要對(duì)不同 age 的對(duì)象采取不同的處理方式员寇，所以在 GC 遍歷時(shí)弄慰，必須能夠判斷當(dāng)前對(duì)象屬于哪個(gè)代，寫(xiě)屏障也需要這個(gè)信息來(lái)識(shí)別 older-->younger 指針蝶锋。

• 對(duì)于 copying GC 來(lái)說(shuō)陆爽，一般是把不同 age 的對(duì)象放在不同的連續(xù)區(qū)域內(nèi)，這樣一個(gè)對(duì)象的代就能夠從內(nèi)存地址推斷出來(lái)了扳缕。也有一些系統(tǒng)不采用連續(xù)地址慌闭，而是采用由 page number of object-->generation 的表來(lái)輔助判斷。
• 對(duì)于 non-copying GC躯舔，一般是存放在 header 內(nèi)

Subareas in Copying
分代式 copying GC 一般會(huì)把 generation 分為幾個(gè)子區(qū)域驴剔，比如 semispace，通過(guò)來(lái)回的移動(dòng)對(duì)象讓它們一直處于當(dāng)前代中粥庄。如果一個(gè)代內(nèi)只有一個(gè)區(qū)域丧失，那么每次 GC 時(shí)都需要把對(duì)象提升到下一代（沒(méi)有可移動(dòng)的地方）。
但是 semispace 的 locality 比較差惜互，一個(gè)代的內(nèi)存只有一半可以使用布讹，且來(lái)回需要移動(dòng)科侈。

Ungar 在其論文《Generation Scavenging》 中提出一個(gè)解決方法：
一個(gè)代內(nèi)除了兩個(gè) semispace 外，還有第三個(gè)區(qū)域炒事，這里稱為T(mén)hird臀栈。在 Third 內(nèi)分配新對(duì)象，在 GC 時(shí)挠乳，Third 內(nèi) live 對(duì)象與 semispace 中的一個(gè)對(duì)象會(huì)復(fù)制到 semispace 中的另一個(gè)去权薯，GC 結(jié)束時(shí) Third 會(huì)被清空，用于再次分配對(duì)象睡扬。這樣就能夠與只有一個(gè)區(qū)域的代類似的 locality 了盟蚣。
（第三個(gè)區(qū)域即為java中的Eden，伊甸園區(qū)域卖怜。將新生代分為Eden屎开，F(xiàn)romSpace，ToSpace等幾個(gè)區(qū)域）

最后一個(gè)代（oldest generation马靠，后面稱為 oldest）在一些系統(tǒng)中有特殊處理奄抽。比如，在 Lisp Machine 中甩鳄，每次 GC 后逞度，大多數(shù)代都會(huì)被清空，并將其內(nèi)對(duì)象拷貝到下一代去妙啃，但是 oldest 后面沒(méi)有可用代了档泽，因此 oldest 內(nèi)會(huì)被分為 semispace。另一個(gè)優(yōu)化是分配一個(gè)特殊的區(qū)域揖赴，稱為 static space馆匿，用來(lái)分配 system data & compiled code 等這些基本不會(huì)變的數(shù)據(jù)，這個(gè)區(qū)域基本不會(huì)有 GC燥滑，即為永久代渐北。

在一些基于 Ungar 的 Generation Scavenging 的系統(tǒng)中，把 oldest 分為一個(gè)區(qū)域突倍，在這個(gè)區(qū)域使用 mark-compact 算法腔稀。使用一個(gè)區(qū)域可以提高內(nèi)存利用率，MC 雖然比 copying 算法成本更高羽历，但對(duì)于 oldest 來(lái)說(shuō)減少換頁(yè)（page fault）也是有價(jià)值的焊虏。

交叉引用

上面已經(jīng)介紹的，older-->younger 的交叉引用是由寫(xiě)屏障來(lái)保障的秕磷。對(duì)于某些系統(tǒng)（如 Lisp诵闭，指針存儲(chǔ)指令占全部指令的1%），這個(gè)寫(xiě)屏障的成本對(duì)分代式 GC 來(lái)說(shuō)非常嚴(yán)重，因此寫(xiě)屏障的策略就十分重要了疏尿。

常見(jiàn)的策略的核心思路有兩個(gè)

• 使用 entry table 或 Remembered Sets 記錄交叉引用的指針對(duì)象瘟芝，這種方式成本比較高
• 使用虛擬內(nèi)存頁(yè)保存交叉引用的對(duì)象，GC 時(shí)只需要對(duì)虛擬內(nèi)存頁(yè)進(jìn)行掃描即可

3.9 實(shí)例：Java 的垃圾回收原理

java的垃圾回收分為三個(gè)區(qū)域
新生代 老年代 永久代

java的垃圾回收

GC流程：

• 一個(gè)對(duì)象實(shí)例化時(shí) 先去看伊甸園有沒(méi)有足夠的空間
• 如果有 不進(jìn)行垃圾回收 ,對(duì)象直接在伊甸園存儲(chǔ).
• 如果伊甸園內(nèi)存已滿,會(huì)進(jìn)行一次minor gc
• 然后再進(jìn)行判斷伊甸園中的內(nèi)存是否足夠
• 如果不足 則去看存活區(qū)的內(nèi)存是否足夠.
• 如果內(nèi)存足夠,把伊甸園部分活躍對(duì)象保存在存活區(qū),然后把對(duì)象保存在伊甸園.
• 如果內(nèi)存不足,向老年代發(fā)送請(qǐng)求,查詢老年代的內(nèi)存是否足夠
• 如果老年代內(nèi)存足夠,將部分存活區(qū)的活躍對(duì)象存入老年代.然后把伊甸園的活躍對(duì)象放入存活區(qū),對(duì)象依舊保存在伊甸園.
• 如果老年代內(nèi)存不足,會(huì)進(jìn)行一次full gc,之后老年代會(huì)再進(jìn)行判斷 內(nèi)存是否足夠,如果足夠 同上.
• 如果不足 會(huì)拋出OutOfMemoryError.

參考鏈接：
http://ju.outofmemory.cn/entry/358715
https://liujiacai.net/blog/2018/07/08/mark-sweep/