GC 首先不是JVM虛擬機器獨有，C 裡面很早就就有了GC的概念，包括當前的GO 都是有GO的概念。 使用C語言開發需要不停申請記憶體，釋放記憶體，所以很在就有人覺得是否可以有一個通用的模組來管理記憶體的申請和釋放，這就是最初GC設計的原始訴求。

以下的內容會不是直接從JVM的虛擬垃圾回收器開始講起，而是從一個極其簡單的虛擬模型垃圾回收器講起，我們自己開發一個VM，同時為其開發一個垃圾回收器。從最基礎的環節瞭解GC的原理。

C 簡單例項

//申請記憶體

int

*

p

=

（

int

*

）

malloc

（

4

）；

//釋放記憶體

free

（

p

）；

//設定為空指標

p

=

NULL

；

物件回收

垃圾回收就是要回收不再使用的物件，那麼首先就要明確 “使用中”具體是指什麼狀態。

仍在作用域中的變數所引用的任何物件都在使用中。

被在使用中的物件所引用的物件，也是處於在使用中。

第二個規則是遞迴規則。 如果物件A是由變數引用的，並且它具有引用物件B的某個欄位，則B處於使用狀態，因為您可以透過A來訪問它。

標記清除

您可以採用多種方法來實現查詢和回收所有未使用的物件的過程，但是為此發明的第一個最簡單演算法稱為“標記-清楚” 法。

它的工作原理幾乎與我們對可達性的定義類似

從根開始，遍歷整個物件圖。 每次到達物體時，將其上的“ mark”位設定為true

完成後，找到所有未設定標記位的物件並將其刪除

以下例項就像我們正在為一種小語言編寫解析器。 它是動態型別的，具有兩種型別的物件：ints and pairs。 這是一個定義物件型別的列舉：

typedef

enum

{

OBJ_INT

，

OBJ_PAIR

}

ObjectType

；

一個Pair可以是任何東西對，兩個int，一個int和另一個Pair， 由於VM中的物件可以是這些物件中的任何一個，因此C中實現該物件的典型方法是使用標記聯合

typedef

struct

sObject

{

ObjectType

type

；

union

{

/* OBJ_INT */

int

value

；

/* OBJ_PAIR */

struct

{

struct

sObject

*

head

；

struct

sObject

*

tail

；

}；

}；

}

Object

；

主物件結構具有一個型別欄位，該型別欄位標識它是什麼型別的值（整數或Pair）。它具有一個union來儲存int或pair的資料。 由於給定的物件只能是一個int或一個Pair，因此不會三個欄位都存在資料。

極簡虛擬機器

現在，我們可以將其封裝在一個小的虛擬機器結構中。 它在此故事中的作用是擁有一個堆疊，該堆疊儲存當前範圍內的變數。 大多數語言VM都是基於堆疊的（如JVM和CLR）或基於暫存器的（如Lua）。 以兩種方式都有有一個堆疊， 用於儲存表示式中間所需的區域性變數和臨時變數

模型結構如以下程式碼：

#define STACK_MAX 256

//最大運算元棧長度

//虛擬機器結構，運算元棧最大值是256，這裡沒有設計最大棧貞

//的概念，只有一個棧貞。

typedef

struct

{

Object

*

stack

［

STACK_MAX

］；

//運算元棧

int

stackSize

；

//當前運算元棧長度

}

VM

；

現在我們已經有了基本的資料結構，讓我們編寫一點程式碼來建立一些東西。 首先，讓我們編寫一個用於建立和初始化VM的函式：

VM

*

newVM

（）

{

VM

*

vm

=

malloc

（

sizeof

（

VM

））；

vm

->

stackSize

=

0

；

return

vm

；

}

擁有虛擬機器後，我們需要能夠操縱其運算元棧：

void

push

（

VM

*

vm

，

Object

*

value

）

{

assert

（

vm

->

stackSize

<

STACK_MAX

，

“Stack overflow！”

）；

vm

->

stack

［

vm

->

stackSize

++

］

=

value

；

}

Object

*

pop

（

VM

*

vm

）

{

assert

（

vm

->

stackSize

>

0

，

“Stack underflow！”

）；

return

vm

->

stack

［

——

vm

->

stackSize

］；

}

好的，當前我們實現了“變數”，我們需要能夠實際建立物件。首先我們建立一個工具函式：

Object

*

newObject

（

VM

*

vm

，

ObjectType

type

）

{

Object

*

object

=

malloc

（

sizeof

（

Object

））；

object

->

type

=

type

；

return

object

；

}

當前分配的實際記憶體分配並沒有進行標記， 這一點我們稍後再討論。 使用以下的函式，我們可以各種物件推送到VM的運算元棧中：

void

pushInt

（

VM

*

vm

，

int

intValue

）

{

Object

*

object

=

newObject

（

vm

，

OBJ_INT

）；

object

->

value

=

intValue

；

push

（

vm

，

object

）；

}

Object

*

pushPair

（

VM

*

vm

）

{

Object

*

object

=

newObject

（

vm

，

OBJ_PAIR

）；

object

->

tail

=

pop

（

vm

）；

object

->

head

=

pop

（

vm

）；

push

（

vm

，

object

）；

return

object

；

}

這就是我們的小型虛擬機器。 如果我們有一個解析器和一個呼叫這些功能的編譯器，這個VM就可以運轉起來。 如果我們擁有無限的記憶體，它甚至可以執行實際程式。 實際情況我們是沒有到，讓我們開始“垃圾回收”。

記憶體標記

第一階段是記憶體標記。 我們需要遍歷所有可及物件並設定它們的標記位。 當前我們需要做的第一件事是在物件上新增一個標記位：

typedef

struct

sObject

{

unsigned

char

marked

；

/* Previous stuff。。。 */

}

Object

；

我們將修改newObject（）在建立新物件時將標記初始化為零。 為了標記所有可到達的物件，我們從記憶體中的變數開始，這意味著遍歷堆疊， 看起來像這樣：

void

markAll

（

VM

*

vm

）

{

for

（

int

i

=

0

；

i

<

vm

->

stackSize

；

i

++

）

{

mark

（

vm

->

stack

［

i

］）；

}

}

mark 方法會一次呼叫，首先我們來建立這個方法。

void

mark

（

Object

*

object

）

{

object

->

marked

=

1

；

}

我們已將物件本身標記為可訪問，但請記住，我們還需要處理物件中的引用：可訪問性是遞迴的。 如果物件是pair，則其兩個欄位也可以訪問。 處理很簡單：

void

mark

（

Object

*

object

）

{

object

->

marked

=

1

；

if

（

object

->

type

==

OBJ_PAIR

）

{

mark

（

object

->

head

）；

mark

（

object

->

tail

）；

}

}

但是這裡有一個BUG。 你看到了嗎？ 我們現在要遞迴，但是我們沒有檢查迴圈呼叫。 如果有paris成對指向一個迴圈，這將使堆疊溢位並崩潰。

為了解決這個問題，只要到達已經處理過的物件，我們只需要判斷是否已經進行了標識。 因此完整的mark（）函式為：

void

mark

（

Object

*

object

）

{

/* If already marked， we‘re done。 Check this first

to avoid recursing on cycles in the object graph。 */

if

（

object

->

marked

）

return

；

object

->

marked

=

1

；

if

（

object

->

type

==

OBJ_PAIR

）

{

mark

（

object

->

head

）；

mark

（

object

->

tail

）；

}

}

記憶體清理

下一階段是瀏覽所有我們分配的物件，並釋放所有未標記的物件。 但是這裡有一個問題：根據定義，所有未標記的物件都是不可訪問的！ 我們無法找到他們！

VM已實現物件引用的語言語義：因此我們僅將指向物件的指標儲存在變數和pair元素中。 一旦其中一個變數不再指向某個物件，我們將完全丟失該物件，這樣實際上發生了記憶體洩漏。

解決這個問題的技巧是，VM可以擁有自己的物件引用，這些引用對程式設計使用者是不可見的。 換句話說，我們可以自己跟蹤它們。

最簡單的方法是維護我們分配過的每個物件的連結串列。 我們將物件本身擴充套件為該列表中的節點：

typedef

struct

sObject

{

/* The next object in the list of all objects。 */

struct

sObject

*

next

；

/* Previous stuff。。。 */

}

Object

；

VM 持有頭部物件的引用。

typedef

struct

{

/* The first object in the list of all objects。 */

Object

*

firstObject

；

/* Previous stuff。。。 */

}

VM

；

在newVM（）中，確保將firstObject初始化為NULL。 每當建立物件時，都會將其新增到列表中：

Object

*

newObject

（

VM

*

vm

，

ObjectType

type

）

{

Object

*

object

=

malloc

（

sizeof

（

Object

））；

object

->

type

=

type

；

object

->

marked

=

0

；

/* Insert it into the list of allocated objects。 */

object

->

next

=

vm

->

firstObject

；

vm

->

firstObject

=

object

；

return

object

；

}

這樣，即使“開發語言”中找不到物件，“開發語言”實現仍然可以。 要瀏覽並刪除未標記的物件，我們只需要遍歷列表：

//清楚不可達物件記憶體

void

sweep

（

VM

*

vm

）

{

//遍歷VM所有建立物件

Object

**

object

=

&

vm

->

firstObject

；

while

（

*

object

）

{

//如果沒有標記需要進行清理

if

（

！

（

*

object

）

->

marked

）

{

/* This object wasn’t reached， so remove it from the list

and free it。 */

Object

*

unreached

=

*

object

；

*

object

=

unreached

->

next

；

free

（

unreached

）；

}

else

{

/* This object was reached， so unmark it （for the next GC）

and move on to the next。 */

（

*

object

）

->

marked

=

0

；

object

=

&

（

*

object

）

->

next

；

}

}

}

由於該指標指向一個指標，因此閱讀該程式碼有些棘手，但是如果您仔細研究它，就會發現它非常簡單。 它只是遍歷整個連結串列， 碰到未標記物件，它就會釋放其記憶體並將其從列表中刪除。 完成此操作後，我們將刪除所有無法訪問的物件。

恭喜你！ 我們有一個垃圾收集器！ 現在只差一件事情：就是如何呼叫它。 首先，讓我們將兩個階段封裝在一起：

void

gc

（

VM

*

vm

）

{

markAll

（

vm

）；

sweep

（

vm

）；

}

您無法要求更明顯的標記掃描實現。 最棘手的部分是弄清楚什麼實際進行GC。 “記憶體不足”甚至意味著什麼，尤其是在虛擬記憶體接近無限的現代計算機上。

事實證明，這裡沒有正確或錯誤的答案。 這實際上取決於您使用VM的目的以及執行的硬體型別。 為了簡化此示例，我們將在分配一定數量後進行收集。 這實際上是某些語言實現的工作方式，並且易於實現。

我們將擴充套件VM以記錄已建立的數量：

typedef

struct

{

/* The total number of currently allocated objects。 */

int

numObjects

；

/* The number of objects required to trigger a GC。 */

int

maxObjects

；

/* Previous stuff。。。 */

}

VM

；

然後初始化它們

VM

*

newVM

（）

{

/* Previous stuff。。。 */

vm

->

numObjects

=

0

；

vm

->

maxObjects

=

INITIAL_GC_THRESHOLD

；

return

vm

；

}

INITIAL_GC_THRESHOLD將是您啟動第一個GC的物件數量閾值。 較小的數字對記憶體更保守，較大的數字執行垃圾回收的次數更少。更具實際情況進行調整。

無論何時建立一個物件，我們都會增加numObjects，並在它達到最大值時執行一次“垃圾回收”

void

gc

（

VM

*

vm

）

{

int

numObjects

=

vm

->

numObjects

；

markAll

（

vm

）；

sweep

（

vm

）；

vm

->

maxObjects

=

vm

->

numObjects

*

2

；

}

不需要每次建立物件的時候都進行GC，進行GC後更新 最大值。

void

gc

（

VM

*

vm

）

{

int

numObjects

=

vm

->

numObjects

；

markAll

（

vm

）；

sweep

（

vm

）；

vm

->

maxObjects

=

vm

->

numObjects

*

2

；

}

每次收集後，我們都會根據收集後剩餘的活動物件數來更新maxObjects。 那裡的乘數使我們的堆隨著活動物件數量的增加而增長。 同樣，如果一堆物件最終被釋放，它將自動收縮

修改sweep方法：

void

sweep

（

VM

*

vm

）

{

Object

**

object

=

&

vm

->

firstObject

；

while

（

*

object

）

{

if

（

！

（

*

object

）

->

marked

）

{

/* This object wasn‘t reached， so remove it from the list and free it。 */

Object

*

unreached

=

*

object

；

*

object

=

unreached

->

next

；

free

（

unreached

）；

// 物件被回收後，物件數量統計減去1

vm

->

numObjects

——

；

}

else

{

/* This object was reached， so unmark it （for the next GC） and move on to

the next。 */

（

*

object

）

->

marked

=

0

；

object

=

&

（

*

object

）

->

next

；

}

}

}

如此簡單

你做到了！ 如果您遵循了所有這些步驟，那麼現在您已經掌握了簡單的垃圾回收演算法。 在此讓我強調，雖然這個垃圾回器很簡單，但它不是玩具。 您可以在此基礎上進行大量最佳化（在GC和程式語言等方面，最佳化需要90％的努力），但是此處的核心程式碼是有效的真實GC演算法。 其與直到Ruby和Lua中的垃圾回收器非常相似。 你可以用這個例子優化出更成熟的屬於你自己的垃圾回收器。