C語言中的垃圾回收分析

沈俊慧

摘要：C語言沒有運行時庫，無法自動壓縮使用中的內存，縮小堆棧所需內存空間。若只申請內存，沒有釋放，勢必造成系統內存不斷減少、丟失。長時間的運行，最終導致系統死機。文章闡述了C語言垃圾產生的原因，并從引用計數、標記一清除算法兩方面提出如何實現C語言的垃圾回收。

關鍵詞：C語言；垃圾回收；引用計數；標記一清除算法

一般來說，操作系統記錄了所有進程使用的全部資源，當系統進程結束時，操作系統會將其所有資源回收，包括內存、寄存器和CPU等所使用的資源。對于許多大型系統來說，一個進程或者程序往往會運行很長時間，如網站進程、守護進程等。操作系統不會主動釋放這種進程所占用的資源。如果進程在使用完后內存資源卻沒有及時釋放，就會造成系統內存不斷減少、丟失，累積到一定程度，會導致系統無內存可用，進而導致系統無法運行或者錯誤，嚴重的甚至死機。

C語言是一種可以直接與操作系統底層交互的語言，它沒有運行時庫。運行時庫可以壓縮使用中的內存，縮小堆棧所需內存空間。因此C語言編程中的內存管理依賴程序編寫人員。因此，本文將詳細闡述C語言中的垃圾回收問題，并闡明其產生原因和常用的回收技術等，以幫助基于C語言的程序開發者更好地設計和實現高效的垃圾回收機制。

1 C語言中垃圾產生的原因

在C語言開發中，內存分配有3種方式：一是函數體內的局部變量，在棧上創建。如void fun（）{int a；……}，變量a在函數fun（）執行結束時會自動釋放。二是靜態存儲區域分配。如static int x=1；變量x為靜態變量，生存期較長，從第1次使用就始終存在，直到整個程序結束時自動釋放。三是動態內存分配，在堆上分配，通過malloc或calloc申請，通過free釋放。此種方式比前2種在內存使用上更加靈活，是編寫大型程序不可缺少的內存分配方式。但是它卻存在一個致命的風險。在一個函數體內通過malloc或calloc申請的動態內存由另外一個函數體使用，程序員很容易忘記在使用后通過free釋放，該內存塊將保持在系統內并一直處于被分配狀態，導致后面程序可申請的內存空間嚴重不足。并且這種情況下，也很難查找出內存泄露發生在什么地方。這些內存塊被稱為垃圾。因此在C語言程序中，引入了垃圾收集器概念，它是一種動態存儲分配器，可定期識別垃圾塊，并相應地調用free函數，將這些垃圾塊回收到空閑的內存鏈表中。

2 C語言中垃圾回收基本原理

垃圾回收因高級編程語言迅猛發展而得到廣大程序員的重視，但實際上垃圾回收的歷史最早始于1960年的Lisp語言。Lisp語言高度依賴動態內存分配，所有數據幾乎都是在堆上分配的。程序設計者必須找到一種方法來自動管理每一塊內存，否則程序員會被數不清的“申請內存”和“釋放內存”淹沒，或者計算機內存很快被消耗殆盡，這促使垃圾回收技術的產生。

一個垃圾回收模塊有3個基本要求：無內存泄漏；能夠自動回收無用內存；能夠內存整理或內存緊縮。

程序中所有已分配的內存都有其對應的指針指向它，若一塊內存沒有任何指針指向它，稱為內存泄漏，即該塊內存是無用內存塊且不可達。在程序運行的任意狀態中，寄存器（考慮多核CPU在多線程下）、程序棧和靜態數據段中所有指針的集合叫根集。可達指的是這塊內存從根集出發，可以找到一個指向它的指針，不可達就是找不到指向它的指針。垃圾回收器首先從根集出發，沿著指針指向和傳遞的方向進行掃描，當找到了地址可用的內存時給它做一個標記。然后掃描整個鏈表內存，并給其作標記。當掃描結束后，對現有內存塊進行檢查，如果存在沒有被標記的內存塊，則說明其不在被引用鏈表中，則將其回收。

3 C語言中垃圾回收的常用算法及實現

目前，內存垃圾回收機制有多種處理機制，如引用計數、標記清除算法、復制算法、標記整理算法、增量收集算法、分代收集算法等。無論何種機制，垃圾回收技術所解決的只有2個重要問題：第一，如何識別當前內存中未被引用的內存；第二，如何將失去管理的內存進行回收。下面本文將從引用計數和標記清除算法2種機制出發闡述C語言如何實現垃圾回收。

3.1 引用計數

引用計數的原理非常簡單：對于一個內存塊，除內存塊本身外增加一個引用計數，每當這個內存塊被外部的指針或內存塊所引用的時候，引用計數加1；當引用它的指針釋放了對它的引用的時候，則引用計數減1，同時檢查引用計數的值，當引用計數為0時，就銷毀該內存塊并釋放其所占用的內存。引用計數機制需要2個函數，一個是增加引用計數，一個是減少引用計數并當計數減少到0時釋放內存。實現代碼如下：

引用計數算法有兩大優點：第一是其垃圾回收過程無需打斷進程運行，內存管理的開銷分布于整個應用程序運行期間，應用程序在正常運行狀態下即可完成內存垃圾回收；第二是在于空間上的引用局部性比較好，當某個內存塊的引用計數值變為0時，系統就可以立刻回，收內存塊而無需二次遍歷，相比其他的算法，引用計數簡單快捷。引用計數機制很簡單，而且是很有效的資源管理方法，在資源充足的條件下，可以在很多場景中都得到有效的應用。

但是，引用計數也存在一些缺點：首先是環形引用。比如現在內存塊X引用內存塊Y，Y內存塊的計數器加1，然后Y內存塊引用Z內存塊，Z的計數加1，后來z又引用Y，Y的計數加1得到2。假如現在X不再引用Y了，Y的計數器成為1。而由于Y，Z互相引用，形成一個環回導致內存塊Y，Z永遠無法被回收。即無法釋放作為循環數據結構的一部分的結構。其次，每次在內存塊創建或者釋放時，都要計算引用計數值，增加系統運行時間。由于每個內存塊要保持自己被引用的數量，必須分配一定的變量空間來存放計數器，增加額外的內存。第三，引用計數占用了結構中的第1個位置，而大部分機器中最快可以訪問到的就是這個位置。

3.2 標記一清除算法

標記清除（Mark Sweep）算法是Lisp的語言設計者提出并應用于Lisp語言的算法。該算法分成2個階段：標記階段和清除階段。在標記階段，垃圾回收器掃描每個內存塊，對被引用的內存塊進行標記。在標記完成后，統一檢測內存集中所有內存，將未被標記的內存塊進行回收。

標記清除算法的核心問題是如何標記所有已經被引用的內存塊。當內存分配時，可能超過某個閥值，然后觸發垃圾回收。首先垃圾回收器建立一些根集合在靜態數據段、寄存器和棧中。然后垃圾回收器會從根集出發查找所有的內存塊引用，然后在被引用的內存塊上作標記（mark），當垃圾回收器遇上一個已經被標記的對象后就不再掃描了，以防止造成環回。這個階段就是所謂的標記階段（Mark Phase）。當標記階段結束后，所有被標記的內存塊就稱為可達對象（Reachable Object）或活對象（Live Object），而所有沒有被標記的內存塊則被認為是垃圾，可以被回收。這個階段進行完就進入了清除階段（Sweep Phase）。垃圾回收器檢測內存集，逐一釋放未被標記的內存。整個過程分為2個階段：找到所有存活內存塊的標記階段；清除所有未標記的內存塊的清除階段。

標記階段實現代碼如下所示：

相比較引用計數算法，標記清除算法可以避免環回引用問題，同時也減少了在操作引用計數上帶來的時間開銷。但是標記清除算法是一種“停止啟動”算法，在垃圾回收器運行過程中，應用程序必須暫時停止。此外，標記清除算法在標記階段需要遍歷所有的存活內存塊，會造成一定的時間開銷。在清除階段，清除垃圾對象后會造成大量的內存碎片。因此標記清除算法的主要研究問題在于如何減少程序停頓時間和對內存碎片的整理。

4 結語

本文詳細闡述了C語言垃圾產生的原理，分析了垃圾回收的基本原理，在此原理上詳細闡述實現垃圾回收的2種算法的優缺點以及實現的代碼。希望通過詳細分析2種算法的機制，幫助開發人員應對實際問題，開發出高效的C程序。