沈俊慧

摘要：C語(yǔ)言沒(méi)有運(yùn)行時(shí)庫(kù)，無(wú)法自動(dòng)壓縮使用中的內(nèi)存，縮小堆棧所需內(nèi)存空間。若只申請(qǐng)內(nèi)存，沒(méi)有釋放，勢(shì)必造成系統(tǒng)內(nèi)存不斷減少、丟失。長(zhǎng)時(shí)間的運(yùn)行，最終導(dǎo)致系統(tǒng)死機(jī)。文章闡述了C語(yǔ)言垃圾產(chǎn)生的原因，并從引用計(jì)數(shù)、標(biāo)記一清除算法兩方面提出如何實(shí)現(xiàn)C語(yǔ)言的垃圾回收。

關(guān)鍵詞：C語(yǔ)言；垃圾回收；引用計(jì)數(shù)；標(biāo)記一清除算法

一般來(lái)說(shuō)，操作系統(tǒng)記錄了所有進(jìn)程使用的全部資源，當(dāng)系統(tǒng)進(jìn)程結(jié)束時(shí)，操作系統(tǒng)會(huì)將其所有資源回收，包括內(nèi)存、寄存器和CPU等所使用的資源。對(duì)于許多大型系統(tǒng)來(lái)說(shuō)，一個(gè)進(jìn)程或者程序往往會(huì)運(yùn)行很長(zhǎng)時(shí)間，如網(wǎng)站進(jìn)程、守護(hù)進(jìn)程等。操作系統(tǒng)不會(huì)主動(dòng)釋放這種進(jìn)程所占用的資源。如果進(jìn)程在使用完后內(nèi)存資源卻沒(méi)有及時(shí)釋放，就會(huì)造成系統(tǒng)內(nèi)存不斷減少、丟失，累積到一定程度，會(huì)導(dǎo)致系統(tǒng)無(wú)內(nèi)存可用，進(jìn)而導(dǎo)致系統(tǒng)無(wú)法運(yùn)行或者錯(cuò)誤，嚴(yán)重的甚至死機(jī)。

C語(yǔ)言是一種可以直接與操作系統(tǒng)底層交互的語(yǔ)言，它沒(méi)有運(yùn)行時(shí)庫(kù)。運(yùn)行時(shí)庫(kù)可以壓縮使用中的內(nèi)存，縮小堆棧所需內(nèi)存空間。因此C語(yǔ)言編程中的內(nèi)存管理依賴(lài)程序編寫(xiě)人員。因此，本文將詳細(xì)闡述C語(yǔ)言中的垃圾回收問(wèn)題，并闡明其產(chǎn)生原因和常用的回收技術(shù)等，以幫助基于C語(yǔ)言的程序開(kāi)發(fā)者更好地設(shè)計(jì)和實(shí)現(xiàn)高效的垃圾回收機(jī)制。

1 C語(yǔ)言中垃圾產(chǎn)生的原因

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

2 C語(yǔ)言中垃圾回收基本原理

垃圾回收因高級(jí)編程語(yǔ)言迅猛發(fā)展而得到廣大程序員的重視，但實(shí)際上垃圾回收的歷史最早始于1960年的Lisp語(yǔ)言。Lisp語(yǔ)言高度依賴(lài)動(dòng)態(tài)內(nèi)存分配，所有數(shù)據(jù)幾乎都是在堆上分配的。程序設(shè)計(jì)者必須找到一種方法來(lái)自動(dòng)管理每一塊內(nèi)存，否則程序員會(huì)被數(shù)不清的“申請(qǐng)內(nèi)存”和“釋放內(nèi)存”淹沒(méi)，或者計(jì)算機(jī)內(nèi)存很快被消耗殆盡，這促使垃圾回收技術(shù)的產(chǎn)生。

一個(gè)垃圾回收模塊有3個(gè)基本要求：無(wú)內(nèi)存泄漏；能夠自動(dòng)回收無(wú)用內(nèi)存；能夠內(nèi)存整理或內(nèi)存緊縮。

程序中所有已分配的內(nèi)存都有其對(duì)應(yīng)的指針指向它，若一塊內(nèi)存沒(méi)有任何指針指向它，稱(chēng)為內(nèi)存泄漏，即該塊內(nèi)存是無(wú)用內(nèi)存塊且不可達(dá)。在程序運(yùn)行的任意狀態(tài)中，寄存器（考慮多核CPU在多線(xiàn)程下）、程序棧和靜態(tài)數(shù)據(jù)段中所有指針的集合叫根集?？蛇_(dá)指的是這塊內(nèi)存從根集出發(fā)，可以找到一個(gè)指向它的指針，不可達(dá)就是找不到指向它的指針。垃圾回收器首先從根集出發(fā)，沿著指針指向和傳遞的方向進(jìn)行掃描，當(dāng)找到了地址可用的內(nèi)存時(shí)給它做一個(gè)標(biāo)記。然后掃描整個(gè)鏈表內(nèi)存，并給其作標(biāo)記。當(dāng)掃描結(jié)束后，對(duì)現(xiàn)有內(nèi)存塊進(jìn)行檢查，如果存在沒(méi)有被標(biāo)記的內(nèi)存塊，則說(shuō)明其不在被引用鏈表中，則將其回收。

3 C語(yǔ)言中垃圾回收的常用算法及實(shí)現(xiàn)

目前，內(nèi)存垃圾回收機(jī)制有多種處理機(jī)制，如引用計(jì)數(shù)、標(biāo)記清除算法、復(fù)制算法、標(biāo)記整理算法、增量收集算法、分代收集算法等。無(wú)論何種機(jī)制，垃圾回收技術(shù)所解決的只有2個(gè)重要問(wèn)題：第一，如何識(shí)別當(dāng)前內(nèi)存中未被引用的內(nèi)存；第二，如何將失去管理的內(nèi)存進(jìn)行回收。下面本文將從引用計(jì)數(shù)和標(biāo)記清除算法2種機(jī)制出發(fā)闡述C語(yǔ)言如何實(shí)現(xiàn)垃圾回收。

3.1 引用計(jì)數(shù)

引用計(jì)數(shù)的原理非常簡(jiǎn)單：對(duì)于一個(gè)內(nèi)存塊，除內(nèi)存塊本身外增加一個(gè)引用計(jì)數(shù)，每當(dāng)這個(gè)內(nèi)存塊被外部的指針或內(nèi)存塊所引用的時(shí)候，引用計(jì)數(shù)加1；當(dāng)引用它的指針釋放了對(duì)它的引用的時(shí)候，則引用計(jì)數(shù)減1，同時(shí)檢查引用計(jì)數(shù)的值，當(dāng)引用計(jì)數(shù)為0時(shí)，就銷(xiāo)毀該內(nèi)存塊并釋放其所占用的內(nèi)存。引用計(jì)數(shù)機(jī)制需要2個(gè)函數(shù)，一個(gè)是增加引用計(jì)數(shù)，一個(gè)是減少引用計(jì)數(shù)并當(dāng)計(jì)數(shù)減少到0時(shí)釋放內(nèi)存。實(shí)現(xiàn)代碼如下：

引用計(jì)數(shù)算法有兩大優(yōu)點(diǎn)：第一是其垃圾回收過(guò)程無(wú)需打斷進(jìn)程運(yùn)行，內(nèi)存管理的開(kāi)銷(xiāo)分布于整個(gè)應(yīng)用程序運(yùn)行期間，應(yīng)用程序在正常運(yùn)行狀態(tài)下即可完成內(nèi)存垃圾回收；第二是在于空間上的引用局部性比較好，當(dāng)某個(gè)內(nèi)存塊的引用計(jì)數(shù)值變?yōu)?時(shí)，系統(tǒng)就可以立刻回，收內(nèi)存塊而無(wú)需二次遍歷，相比其他的算法，引用計(jì)數(shù)簡(jiǎn)單快捷。引用計(jì)數(shù)機(jī)制很簡(jiǎn)單，而且是很有效的資源管理方法，在資源充足的條件下，可以在很多場(chǎng)景中都得到有效的應(yīng)用。

但是，引用計(jì)數(shù)也存在一些缺點(diǎn)：首先是環(huán)形引用。比如現(xiàn)在內(nèi)存塊X引用內(nèi)存塊Y，Y內(nèi)存塊的計(jì)數(shù)器加1，然后Y內(nèi)存塊引用Z內(nèi)存塊，Z的計(jì)數(shù)加1，后來(lái)z又引用Y，Y的計(jì)數(shù)加1得到2。假如現(xiàn)在X不再引用Y了，Y的計(jì)數(shù)器成為1。而由于Y，Z互相引用，形成一個(gè)環(huán)回導(dǎo)致內(nèi)存塊Y，Z永遠(yuǎn)無(wú)法被回收。即無(wú)法釋放作為循環(huán)數(shù)據(jù)結(jié)構(gòu)的一部分的結(jié)構(gòu)。其次，每次在內(nèi)存塊創(chuàng)建或者釋放時(shí)，都要計(jì)算引用計(jì)數(shù)值，增加系統(tǒng)運(yùn)行時(shí)間。由于每個(gè)內(nèi)存塊要保持自己被引用的數(shù)量，必須分配一定的變量空間來(lái)存放計(jì)數(shù)器，增加額外的內(nèi)存。第三，引用計(jì)數(shù)占用了結(jié)構(gòu)中的第1個(gè)位置，而大部分機(jī)器中最快可以訪(fǎng)問(wèn)到的就是這個(gè)位置。

3.2 標(biāo)記一清除算法

標(biāo)記清除（Mark Sweep）算法是Lisp的語(yǔ)言設(shè)計(jì)者提出并應(yīng)用于Lisp語(yǔ)言的算法。該算法分成2個(gè)階段：標(biāo)記階段和清除階段。在標(biāo)記階段，垃圾回收器掃描每個(gè)內(nèi)存塊，對(duì)被引用的內(nèi)存塊進(jìn)行標(biāo)記。在標(biāo)記完成后，統(tǒng)一檢測(cè)內(nèi)存集中所有內(nèi)存，將未被標(biāo)記的內(nèi)存塊進(jìn)行回收。

標(biāo)記清除算法的核心問(wèn)題是如何標(biāo)記所有已經(jīng)被引用的內(nèi)存塊。當(dāng)內(nèi)存分配時(shí)，可能超過(guò)某個(gè)閥值，然后觸發(fā)垃圾回收。首先垃圾回收器建立一些根集合在靜態(tài)數(shù)據(jù)段、寄存器和棧中。然后垃圾回收器會(huì)從根集出發(fā)查找所有的內(nèi)存塊引用，然后在被引用的內(nèi)存塊上作標(biāo)記（mark），當(dāng)垃圾回收器遇上一個(gè)已經(jīng)被標(biāo)記的對(duì)象后就不再掃描了，以防止造成環(huán)回。這個(gè)階段就是所謂的標(biāo)記階段（Mark Phase）。當(dāng)標(biāo)記階段結(jié)束后，所有被標(biāo)記的內(nèi)存塊就稱(chēng)為可達(dá)對(duì)象（Reachable Object）或活對(duì)象（Live Object），而所有沒(méi)有被標(biāo)記的內(nèi)存塊則被認(rèn)為是垃圾，可以被回收。這個(gè)階段進(jìn)行完就進(jìn)入了清除階段（Sweep Phase）。垃圾回收器檢測(cè)內(nèi)存集，逐一釋放未被標(biāo)記的內(nèi)存。整個(gè)過(guò)程分為2個(gè)階段：找到所有存活內(nèi)存塊的標(biāo)記階段；清除所有未標(biāo)記的內(nèi)存塊的清除階段。

標(biāo)記階段實(shí)現(xiàn)代碼如下所示：

相比較引用計(jì)數(shù)算法，標(biāo)記清除算法可以避免環(huán)回引用問(wèn)題，同時(shí)也減少了在操作引用計(jì)數(shù)上帶來(lái)的時(shí)間開(kāi)銷(xiāo)。但是標(biāo)記清除算法是一種“停止啟動(dòng)”算法，在垃圾回收器運(yùn)行過(guò)程中，應(yīng)用程序必須暫時(shí)停止。此外，標(biāo)記清除算法在標(biāo)記階段需要遍歷所有的存活內(nèi)存塊，會(huì)造成一定的時(shí)間開(kāi)銷(xiāo)。在清除階段，清除垃圾對(duì)象后會(huì)造成大量的內(nèi)存碎片。因此標(biāo)記清除算法的主要研究問(wèn)題在于如何減少程序停頓時(shí)間和對(duì)內(nèi)存碎片的整理。

4 結(jié)語(yǔ)

本文詳細(xì)闡述了C語(yǔ)言垃圾產(chǎn)生的原理，分析了垃圾回收的基本原理，在此原理上詳細(xì)闡述實(shí)現(xiàn)垃圾回收的2種算法的優(yōu)缺點(diǎn)以及實(shí)現(xiàn)的代碼。希望通過(guò)詳細(xì)分析2種算法的機(jī)制，幫助開(kāi)發(fā)人員應(yīng)對(duì)實(shí)際問(wèn)題，開(kāi)發(fā)出高效的C程序。