以下為《垃圾回收的算法與實現(xiàn)》中序章及相關概念讀書筆記
1.GC 定義
GC: Garbage Collection， “垃圾回收”
垃圾: GC把程序中不用的內(nèi)存空間視為垃圾。
1.1 GC所做的兩件事：
- 找到內(nèi)存空間里的垃圾
- 回收垃圾，讓程序能再次利用這部分空間
滿足以上兩項功能的程序就是GC。
1.2 沒有GC會導致哪些問題？
- 內(nèi)存泄漏：內(nèi)存空間使用完畢后未釋放。手動進行內(nèi)存管理時，如果忘記釋放內(nèi)存空間，會發(fā)生內(nèi)存泄漏，最終導致內(nèi)存被占滿。
- 垂懸指針（dangling pointer）：指向曾經(jīng)的對象，但是該對象已經(jīng)不再存在。
int *p = NULL;
void fun() {
int i = 10;
p = &I;
}
int main() {
fun();
printf("\n*p = %d", *p); // *p = 10
printf("\n*p = %d", *p); // 臨時變量i已經(jīng)銷毀，*p = 1774530512
return 0;
}
- 錯誤釋放了使用中的內(nèi)存空間。
1.3 GC 歷史：
- GC標記-清除算法（mark-sweep）：
John McCarthy身為Lisp之父和人工智能之父，是一名非常有名的黑客，事實上他同時也是GC之父。1960年，McCarthy在其論文 中首次發(fā)布了GC算法。
- 引用計數(shù)法：
1960年，George E. Collins在論文中發(fā)布了叫作引用計數(shù)的GC算法。當時Collins可能沒有注意到，引用計數(shù)法有個缺點，就是它不能回收“循環(huán)引用”。Harold McBeth 在1963年指出了這個缺點。
- GC復制算法:
1963年，也有“人工智能之父”之稱的Marvin L. Minsky在論文[7]中發(fā)布了復制算法。
目前為止發(fā)布的所有GC算法都只是以上三種算法的組合。
2.算法相關概念
2.1 對象/頭/域
對象：GC世界中，對象表示“通過應用程序利用的數(shù)據(jù)集合”。（與面向對象編程中表示“具有屬性和行為的事物”概念不同）。
對象配置在內(nèi)存空間里。GC根據(jù)情況將配置好對象進行移動或銷毀操作。因此對象是GC的基本單位。對象由頭（head）和域（field）構成。
2.1.2 頭
對象中保存對象本身信息的部分稱為“頭”。主要包含以下信息：
- 對象的大小
- 對象的種類
通過頭來判別內(nèi)存中存儲的對象的邊界。
2.1.3 域
對象使用者在對象中可訪問的部分。類似于C中結構體的成員。對象使用者會引用或替換對象的域值。另一方面，對象使用者基本無法直接更改頭的信息。
域中數(shù)據(jù)類型分為以下兩種：
- 指針
- 非指針 （值本身：數(shù)值、字符及布爾）
對象內(nèi)部，頭之后存在1個及1個以上的域。
2.2 指針
GC 根據(jù)對象的指針去搜尋其他對象。GC對非指針不進行任何操。
注意點：
1.語言處理程序是否能判別指針和非指針。
2.指針指向對象的哪個部分。大多數(shù)語言處理程序中，指針都默認指向對象首地址。如果指針指向對象首地址以外的部分，GC就會變得非常復雜。
2.3 mutator
mutator "改變某物"的意思，主要是改變GC對象間的引用關系。其實體是“應用程序”,GC在mutator內(nèi)部進行工作。
mutator實際進行的操作：
- 生成對象
- 更新指針
2.4 堆 Heap
動態(tài)（執(zhí)行程序時）存放對象的內(nèi)存空間。當mutator申請存放對象時，所需內(nèi)存空間從這個堆中被分配給mutator。
GC是管理堆中已分配對象的機制。在開始執(zhí)行mutator前，GC要分配用于堆的內(nèi)存空間。一旦開始執(zhí)行mutator，程序就會按照mutator的要求在堆中存放對象。等到堆被對象占滿后，GC就會啟動，從而分配可用空間。如果不能分配足夠的可用空間，一般情況下我們就要擴大堆。
在《垃圾回收的算法與實現(xiàn)》一書“算法篇”中把堆的大小固定為常量
HEAP_SIZE，不會進行擴大。此外，把$heap_start定為指向堆首地址的指針，把$heap_end定為指向堆末尾下一個地址的指針。也就是說，$heap_end等于$heap_start + HEAP_SIZE。
堆
2.5 活動對象
活動對象：分配到內(nèi)存空間中能通過mutator引用的對象。
非活動對象：分配到內(nèi)存空間中不能通過mutator引用的對象 （需要回收的垃圾）。
2.6 分配（allocation）
分配（allocation）：在內(nèi)存空間中分配對象。當mutator需要新對象時，向分配器申請一個大型合適的空間。
分配器（allocator）：在堆的可用空間中尋找滿足要求的空間，返回給mutator。
當堆被所有活動對象占滿時，再也無法分配可用空間，此時有兩種選擇：
- 銷毀至今為止的所有計算結果，輸出錯誤信息。
- 擴大堆，分配可用空間。
2.6 分塊（chunk）
分塊在GC中指為利用對象而事先準備出來的空間。
初始狀態(tài)下，堆被一個大的分塊占據(jù)。然后根據(jù)mutator要求分割成合適大小的塊，作為（活動）對象使用?；顒訉ο筠D為垃圾被回收后，這部分被回收的內(nèi)存空間再次成為分塊，為下次被利用做準備。即內(nèi)存中的各區(qū)塊都重復著分塊 --> 活動對象 --> 垃圾（非活動對象） --> 分塊 ... 的過程
2.7 根 Root
GC中，根是指向對象指針的“起點”部分。能通過mutator直接引用的空間。
$obj= Object.new
$obj.field1 = Object.new
說明： 在這里$obj是全局變量。首先，我們在第1行分配一個對象（對象A），然后把$obj代入指向這個對象的指針。在第2行我們也分配一個對象（對象B），然后把$obj.field1代入指向這個對象的指針。在執(zhí)行完第2行后，全局變量空間及堆如圖所示。在這里我們可以使用$obj直接從偽代碼中引用對象A，也就是說A是活動對象。此外，因為可以通過$obj經(jīng)由對象A引用對象B，所以對象B也是活動對象。因此GC必須保護這些對象。
GC把上述這樣可以直接或間接從全局變量空間中引用的對象視為活動對象。
與全局變量空間相同，我們也可以通過mutator直接引用調(diào)用棧（call stack）和寄存器。也就是說，調(diào)用棧、寄存器以及全局變量空間都是根。
3.GC評價標準
3.1 評價GC算法性能的四個標準
- 吞吐量
- 最大暫停時間
- 堆使用效率
- 訪問的局部性
3.1.1 吞吐量
單位時間內(nèi)處理能力
如圖，mutator執(zhí)行過程中，GC啟動3次，耗時分別為分別為A、B、C。則總耗時(A+B+C)。 假設堆大小為HEAP_SIZE，則吞吐量為HEAP_SIZE/ (A+B+C)。
吞吐量也受到mutator動作影響。
當然，人們通常都喜歡吞吐量高的GC算法。然而判斷各算法吞吐量的好壞時不能一概而論。打個比方，眾所周知GC復制算法和GC標記-清除算法相比，活動對象越少吞吐量越高。這是因為GC復制算法只檢查活動對象，而GC標記-清除算法則會檢查所有的活動和非活動對象。然而，隨著活動對象的增多，各GC算法表現(xiàn)出的吞吐量也會相應地變化。極端情況下，甚至會出現(xiàn)GC標記-清除算法比GC復制算法表現(xiàn)的吞吐量更高的情況。
3.1.2 最大暫停時間
指“因為執(zhí)行GC而暫停執(zhí)行mutator的最長時間”。（圖1.7中最大暫停時間是B）
3.1.3 堆使用效率
影響因素：
頭大?。?br> 在堆中堆放的信息越多，GC的效率也就越高，吞吐量也就隨之得到改善。但毋庸置疑，頭越小越好。因此為了執(zhí)行GC，需要把在頭中堆放的信息控制在最小限度。
堆的用法
根據(jù)堆的用法，堆使用效率也會出現(xiàn)巨大的差異。舉個例子，GC復制算法中將堆二等分，每次只使用一半，交替進行，因此總是只能利用堆的一半。相對而言，GC標記-清除算法和引用計數(shù)法就能利用整個堆。
堆使用效率和吞吐量以及最大暫停時間不可兼得。即：可用堆越大，GC運行越快；相反，越想有效利用有限的堆，GC花費時間越長。
3.1.3 訪問的局部性
PC上四種存儲器：寄存器、緩存、內(nèi)存、輔助存儲器（磁盤）。存取速度一般與存儲容量成反比。
一般我們會把所有的數(shù)據(jù)都放在內(nèi)存里，當CPU訪問數(shù)據(jù)時，僅把要使用的數(shù)據(jù)從內(nèi)存讀取到緩存。與此同時，我們還將它附近的所有數(shù)據(jù)都讀取到緩存中，從而壓縮讀取數(shù)據(jù)所需要的時間。
另一方面，具有引用關系的對象之間通常很可能存在連續(xù)訪問的情況。這在多數(shù)程序中都很常見，稱為“訪問的局部性”。考慮到訪問的局部性，把具有引用關系的對象安排在堆中較近的位 置，就能提高在緩存中讀取到想利用的數(shù)據(jù)的概率，令mutator高速運行。
