linux內(nèi)存管理內(nèi)幕

原文地址：http://blog.csdn.net/wangyuling1234567890/article/details/39609863

忽然想起前幾天在公司看到一篇關(guān)于內(nèi)存管理的文章，但當(dāng)時(shí)由于別的事情給打斷了。今天想起來(lái)，就又在網(wǎng)上找了一下，與大家分享一下。

雖然自己現(xiàn)在從事內(nèi)核模塊開(kāi)發(fā)，對(duì)內(nèi)存池和引用計(jì)數(shù)也有所了解，但由于理解深度及文筆，不能自己娓娓道來(lái)，所以就和大家一起來(lái)瞻仰一下大師給我們的講解。

以下內(nèi)容來(lái)自于http://www.ibm.com/developerworks/cn/linux/l-memory/

內(nèi)存管理內(nèi)幕

動(dòng)態(tài)分配的選擇、折衷和實(shí)現(xiàn)

*****************************************************************************************************************************************************************************************************

為什么必須管理內(nèi)存

內(nèi)存管理是計(jì)算機(jī)編程最為基本的領(lǐng)域之一。在很多腳本語(yǔ)言中，您不必?fù)?dān)心內(nèi)存是如何管理的，這并不能使得內(nèi)存管理的重要性有一點(diǎn)點(diǎn)降低。對(duì)實(shí)際編程來(lái)說(shuō)，理解您的內(nèi)存管理器的能力與局限性至關(guān)重要。在大部分系統(tǒng)語(yǔ)言中，比如 C 和 C++，您必須進(jìn)行內(nèi)存管理。本文將介紹手工的、半手工的以及自動(dòng)的內(nèi)存管理實(shí)踐的基本概念。

追溯到在 Apple II 上進(jìn)行匯編語(yǔ)言編程的時(shí)代，那時(shí)內(nèi)存管理還不是個(gè)大問(wèn)題。您實(shí)際上在運(yùn)行整個(gè)系統(tǒng)。系統(tǒng)有多少內(nèi)存，您就有多少內(nèi)存。您甚至不必費(fèi)心思去弄明白它有多少內(nèi)存，因?yàn)槊恳慌_(tái)機(jī)器的內(nèi)存數(shù)量都相同。所以，如果內(nèi)存需要非常固定，那么您只需要選擇一個(gè)內(nèi)存范圍并使用它即可。

不過(guò)，即使是在這樣一個(gè)簡(jiǎn)單的計(jì)算機(jī)中，您也會(huì)有問(wèn)題，尤其是當(dāng)您不知道程序的每個(gè)部分將需要多少內(nèi)存時(shí)。如果您的空間有限，而內(nèi)存需求是變化的，那么您需要一些方法來(lái)滿(mǎn)足這些需求：

• 確定您是否有足夠的內(nèi)存來(lái)處理數(shù)據(jù)。
• 從可用的內(nèi)存中獲取一部分內(nèi)存。
• 向可用內(nèi)存池（pool）中返回部分內(nèi)存，以使其可以由程序的其他部分或者其他程序使用。

實(shí)現(xiàn)這些需求的程序庫(kù)稱(chēng)為 分配程序（allocators），因?yàn)樗鼈冐?fù)責(zé)分配和回收內(nèi)存。程序的動(dòng)態(tài)性越強(qiáng)，內(nèi)存管理就越重要，您的內(nèi)存分配程序的選擇也就更重要。讓我們來(lái)了解可用于內(nèi)存管理的不同方法，它們的好處與不足，以及它們最適用的情形。

*****************************************************************************************************************************************************************************************************

C 風(fēng)格的內(nèi)存分配程序

C 編程語(yǔ)言提供了兩個(gè)函數(shù)來(lái)滿(mǎn)足我們的三個(gè)需求：

• malloc：該函數(shù)分配給定的字節(jié)數(shù)，并返回一個(gè)指向它們的指針。如果沒(méi)有足夠的可用內(nèi)存，那么它返回一個(gè)空指針。
• free：該函數(shù)獲得指向由 malloc 分配的內(nèi)存片段的指針，并將其釋放，以便以后的程序或操作系統(tǒng)使用（實(shí)際上，一些malloc 實(shí)現(xiàn)只能將內(nèi)存歸還給程序，而無(wú)法將內(nèi)存歸還給操作系統(tǒng)）。

物理內(nèi)存和虛擬內(nèi)存

要理解內(nèi)存在程序中是如何分配的，首先需要理解如何將內(nèi)存從操作系統(tǒng)分配給程序。計(jì)算機(jī)上的每一個(gè)進(jìn)程都認(rèn)為自己可以訪問(wèn)所有的物理內(nèi)存。顯然，由于同時(shí)在運(yùn)行多個(gè)程序，所以每個(gè)進(jìn)程不可能擁有全部?jī)?nèi)存。實(shí)際上，這些進(jìn)程使用的是虛擬內(nèi)存。

只是作為一個(gè)例子，讓我們假定您的程序正在訪問(wèn)地址為 629 的內(nèi)存。不過(guò)，虛擬內(nèi)存系統(tǒng)不需要將其存儲(chǔ)在位置為 629 的 RAM 中。實(shí)際上，它甚至可以不在 RAM 中 ―― 如果物理 RAM 已經(jīng)滿(mǎn)了，它甚至可能已經(jīng)被轉(zhuǎn)移到硬盤(pán)上！由于這類(lèi)地址不必反映內(nèi)存所在的物理位置，所以它們被稱(chēng)為虛擬內(nèi)存。操作系統(tǒng)維持著一個(gè)虛擬地址到物理地址的轉(zhuǎn)換的表，以便計(jì)算機(jī)硬件可以正確地響應(yīng)地址請(qǐng)求。并且，如果地址在硬盤(pán)上而不是在 RAM 中，那么操作系統(tǒng)將暫時(shí)停止您的進(jìn)程，將其他內(nèi)存轉(zhuǎn)存到硬盤(pán)中，從硬盤(pán)上加載被請(qǐng)求的內(nèi)存，然后再重新啟動(dòng)您的進(jìn)程。這樣，每個(gè)進(jìn)程都獲得了自己可以使用的地址空間，可以訪問(wèn)比您物理上安裝的內(nèi)存更多的內(nèi)存。

在 32-位 x86 系統(tǒng)上，每一個(gè)進(jìn)程可以訪問(wèn) 4 GB 內(nèi)存?，F(xiàn)在，大部分人的系統(tǒng)上并沒(méi)有 4 GB 內(nèi)存，即使您將 swap 也算上， 每個(gè)進(jìn)程所使用的內(nèi)存也肯定少于 4 GB。因此，當(dāng)加載一個(gè)進(jìn)程時(shí)，它會(huì)得到一個(gè)取決于某個(gè)稱(chēng)為系統(tǒng)中斷點(diǎn)（system break）的特定地址的初始內(nèi)存分配。該地址之后是未被映射的內(nèi)存 ―― 用于在 RAM 或者硬盤(pán)中沒(méi)有分配相應(yīng)物理位置的內(nèi)存。因此，如果一個(gè)進(jìn)程運(yùn)行超出了它初始分配的內(nèi)存，那么它必須請(qǐng)求操作系統(tǒng)“映射進(jìn)來(lái)（map in）”更多的內(nèi)存。（映射是一個(gè)表示一一對(duì)應(yīng)關(guān)系的數(shù)學(xué)術(shù)語(yǔ) ―― 當(dāng)內(nèi)存的虛擬地址有一個(gè)對(duì)應(yīng)的物理地址來(lái)存儲(chǔ)內(nèi)存內(nèi)容時(shí)，該內(nèi)存將被映射。）

基于 UNIX 的系統(tǒng)有兩個(gè)可映射到附加內(nèi)存中的基本系統(tǒng)調(diào)用：

• brk：brk() 是一個(gè)非常簡(jiǎn)單的系統(tǒng)調(diào)用。還記得系統(tǒng)中斷點(diǎn)嗎？該位置是進(jìn)程映射的內(nèi)存邊界。brk() 只是簡(jiǎn)單地將這個(gè)位置向前或者向后移動(dòng)，就可以向進(jìn)程添加內(nèi)存或者從進(jìn)程取走內(nèi)存。
• mmap：mmap()，或者說(shuō)是“內(nèi)存映像”，類(lèi)似于 brk()，但是更為靈活。首先，它可以映射任何位置的內(nèi)存，而不單單只局限于進(jìn)程。其次，它不僅可以將虛擬地址映射到物理的 RAM 或者 swap，它還可以將它們映射到文件和文件位置，這樣，讀寫(xiě)內(nèi)存將對(duì)文件中的數(shù)據(jù)進(jìn)行讀寫(xiě)。不過(guò)，在這里，我們只關(guān)心mmap 向進(jìn)程添加被映射的內(nèi)存的能力。munmap() 所做的事情與mmap() 相反。

如您所見(jiàn)， brk() 或者 mmap() 都可以用來(lái)向我們的進(jìn)程添加額外的虛擬內(nèi)存。在我們的例子中將使用brk()，因?yàn)樗?jiǎn)單，更通用。

實(shí)現(xiàn)一個(gè)簡(jiǎn)單的分配程序

如果您曾經(jīng)編寫(xiě)過(guò)很多 C 程序，那么您可能曾多次使用過(guò) malloc() 和 free()。不過(guò)，您可能沒(méi)有用一些時(shí)間去思考它們?cè)谀牟僮飨到y(tǒng)中是如何實(shí)現(xiàn)的。本節(jié)將向您展示malloc 和free 的一個(gè)最簡(jiǎn)化實(shí)現(xiàn)的代碼，來(lái)幫助說(shuō)明管理內(nèi)存時(shí)都涉及到了哪些事情。

要試著運(yùn)行這些示例，需要先 復(fù)制本代碼清單，并將其粘貼到一個(gè)名為 malloc.c 的文件中。接下來(lái)，我將一次一個(gè)部分地對(duì)該清單進(jìn)行解釋。

在大部分操作系統(tǒng)中，內(nèi)存分配由以下兩個(gè)簡(jiǎn)單的函數(shù)來(lái)處理：

• void *malloc(long numbytes)：該函數(shù)負(fù)責(zé)分配 numbytes 大小的內(nèi)存，并返回指向第一個(gè)字節(jié)的指針。
• void free(void *firstbyte)：如果給定一個(gè)由先前的 malloc 返回的指針，那么該函數(shù)會(huì)將分配的空間歸還給進(jìn)程的“空閑空間”。

malloc_init 將是初始化內(nèi)存分配程序的函數(shù)。它要完成以下三件事：將分配程序標(biāo)識(shí)為已經(jīng)初始化，找到系統(tǒng)中最后一個(gè)有效內(nèi)存地址，然后建立起指向我們管理的內(nèi)存的指針。這三個(gè)變量都是全局變量：

清單 1. 我們的簡(jiǎn)單分配程序的全局變量

如前所述，被映射的內(nèi)存的邊界（最后一個(gè)有效地址）常被稱(chēng)為系統(tǒng)中斷點(diǎn)或者 當(dāng)前中斷點(diǎn)。在很多 UNIX? 系統(tǒng)中，為了指出當(dāng)前系統(tǒng)中斷點(diǎn)，必須使用sbrk(0) 函數(shù)。sbrk 根據(jù)參數(shù)中給出的字節(jié)數(shù)移動(dòng)當(dāng)前系統(tǒng)中斷點(diǎn)，然后返回新的系統(tǒng)中斷點(diǎn)。使用參數(shù)0 只是返回當(dāng)前中斷點(diǎn)。這里是我們的malloc 初始化代碼，它將找到當(dāng)前中斷點(diǎn)并初始化我們的變量：

清單 2. 分配程序初始化函數(shù)

現(xiàn)在，為了完全地管理內(nèi)存，我們需要能夠追蹤要分配和回收哪些內(nèi)存。在對(duì)內(nèi)存塊進(jìn)行了 free 調(diào)用之后，我們需要做的是諸如將它們標(biāo)記為未被使用的等事情，并且，在調(diào)用malloc 時(shí)，我們要能夠定位未被使用的內(nèi)存塊。因此，malloc 返回的每塊內(nèi)存的起始處首先要有這個(gè)結(jié)構(gòu)：

清單 3. 內(nèi)存控制塊結(jié)構(gòu)定義

現(xiàn)在，您可能會(huì)認(rèn)為當(dāng)程序調(diào)用 malloc 時(shí)這會(huì)引發(fā)問(wèn)題 ―― 它們?nèi)绾沃肋@個(gè)結(jié)構(gòu)？答案是它們不必知道；在返回指針之前，我們會(huì)將其移動(dòng)到這個(gè)結(jié)構(gòu)之后，把它隱藏起來(lái)。這使得返回的指針指向沒(méi)有用于任何其他用途的內(nèi)存。那樣，從調(diào)用程序的角度來(lái)看，它們所得到的全部是空閑的、開(kāi)放的內(nèi)存。然后，當(dāng)通過(guò)free() 將該指針傳遞回來(lái)時(shí)，我們只需要倒退幾個(gè)內(nèi)存字節(jié)就可以再次找到這個(gè)結(jié)構(gòu)。

在討論分配內(nèi)存之前，我們將先討論釋放，因?yàn)樗?jiǎn)單。為了釋放內(nèi)存，我們必須要做的惟一一件事情就是，獲得我們給出的指針，回退 sizeof(struct mem_control_block) 個(gè)字節(jié)，并將其標(biāo)記為可用的。這里是對(duì)應(yīng)的代碼：

清單 4. 解除分配函數(shù)

如您所見(jiàn)，在這個(gè)分配程序中，內(nèi)存的釋放使用了一個(gè)非常簡(jiǎn)單的機(jī)制，在固定時(shí)間內(nèi)完成內(nèi)存釋放。分配內(nèi)存稍微困難一些。以下是該算法的略述：

清單 5. 主分配程序的偽代碼

我們主要使用連接的指針遍歷內(nèi)存來(lái)尋找開(kāi)放的內(nèi)存塊。這里是代碼：

清單 6. 主分配程序

這就是我們的內(nèi)存管理器?，F(xiàn)在，我們只需要構(gòu)建它，并在程序中使用它即可。

運(yùn)行下面的命令來(lái)構(gòu)建 malloc 兼容的分配程序（實(shí)際上，我們忽略了 realloc() 等一些函數(shù)，不過(guò)，malloc() 和free() 才是最主要的函數(shù)）：

清單 7. 編譯分配程序

該程序?qū)⑸梢粋€(gè)名為 malloc.so 的文件，它是一個(gè)包含有我們的代碼的共享庫(kù)。

在 UNIX 系統(tǒng)中，現(xiàn)在您可以用您的分配程序來(lái)取代系統(tǒng)的 malloc()，做法如下：

清單 8. 替換您的標(biāo)準(zhǔn)的 malloc

LD_PRELOAD 環(huán)境變量使動(dòng)態(tài)鏈接器在加載任何可執(zhí)行程序之前，先加載給定的共享庫(kù)的符號(hào)。它還為特定庫(kù)中的符號(hào)賦予優(yōu)先權(quán)。因此，從現(xiàn)在起，該會(huì)話(huà)中的任何應(yīng)用程序都將使用我們的malloc()，而不是只有系統(tǒng)的應(yīng)用程序能夠使用。有一些應(yīng)用程序不使用malloc()，不過(guò)它們是例外。其他使用realloc() 等其他內(nèi)存管理函數(shù)的應(yīng)用程序，或者錯(cuò)誤地假定malloc() 內(nèi)部行為的那些應(yīng)用程序，很可能會(huì)崩潰。ash shell 似乎可以使用我們的新malloc() 很好地工作。

如果您想確保 malloc() 正在被使用，那么您應(yīng)該通過(guò)向函數(shù)的入口點(diǎn)添加 write() 調(diào)用來(lái)進(jìn)行測(cè)試。

我們的內(nèi)存管理器在很多方面都還存在欠缺，但它可以有效地展示內(nèi)存管理需要做什么事情。它的某些缺點(diǎn)包括：

• 由于它對(duì)系統(tǒng)中斷點(diǎn)（一個(gè)全局變量）進(jìn)行操作，所以它不能與其他分配程序或者 mmap 一起使用。
• 當(dāng)分配內(nèi)存時(shí)，在最壞的情形下，它將不得不遍歷 全部進(jìn)程內(nèi)存；其中可能包括位于硬盤(pán)上的很多內(nèi)存，這意味著操作系統(tǒng)將不得不花時(shí)間去向硬盤(pán)移入數(shù)據(jù)和從硬盤(pán)中移出數(shù)據(jù)。
• 沒(méi)有很好的內(nèi)存不足處理方案（ malloc 只假定內(nèi)存分配是成功的）。
• 它沒(méi)有實(shí)現(xiàn)很多其他的內(nèi)存函數(shù)，比如 realloc()。
• 由于 sbrk() 可能會(huì)交回比我們請(qǐng)求的更多的內(nèi)存，所以在堆（heap）的末端會(huì)遺漏一些內(nèi)存。
• 雖然 is_available 標(biāo)記只包含一位信息，但它要使用完整的 4-字節(jié) 的字。
• 分配程序不是線程安全的。
• 分配程序不能將空閑空間拼合為更大的內(nèi)存塊。
• 分配程序的過(guò)于簡(jiǎn)單的匹配算法會(huì)導(dǎo)致產(chǎn)生很多潛在的內(nèi)存碎片。
• 我確信還有很多其他問(wèn)題。這就是為什么它只是一個(gè)例子!

其他 malloc 實(shí)現(xiàn)

malloc() 的實(shí)現(xiàn)有很多，這些實(shí)現(xiàn)各有優(yōu)點(diǎn)與缺點(diǎn)。在設(shè)計(jì)一個(gè)分配程序時(shí)，要面臨許多需要折衷的選擇，其中包括：

• 分配的速度。
• 回收的速度。
• 有線程的環(huán)境的行為。
• 內(nèi)存將要被用光時(shí)的行為。
• 局部緩存。
• 簿記（Bookkeeping）內(nèi)存開(kāi)銷(xiāo)。
• 虛擬內(nèi)存環(huán)境中的行為。
• 小的或者大的對(duì)象。
• 實(shí)時(shí)保證。

每一個(gè)實(shí)現(xiàn)都有其自身的優(yōu)缺點(diǎn)集合。在我們的簡(jiǎn)單的分配程序中，分配非常慢，而回收非?？?。另外，由于它在使用虛擬內(nèi)存系統(tǒng)方面較差，所以它最適于處理大的對(duì)象。

還有其他許多分配程序可以使用。其中包括：

• Doug Lea Malloc：Doug Lea Malloc 實(shí)際上是完整的一組分配程序，其中包括 Doug Lea 的原始分配程序，GNU libc 分配程序和ptmalloc。Doug Lea 的分配程序有著與我們的版本非常類(lèi)似的基本結(jié)構(gòu)，但是它加入了索引，這使得搜索速度更快，并且可以將多個(gè)沒(méi)有被使用的塊組合為一個(gè)大的塊。它還支持緩存，以便更快地再次使用最近釋放的內(nèi)存。ptmalloc 是 Doug Lea Malloc 的一個(gè)擴(kuò)展版本，支持多線程。在本文后面的 參考資料部分中，有一篇描述 Doug Lea 的 Malloc 實(shí)現(xiàn)的文章。
• BSD Malloc：BSD Malloc 是隨 4.2 BSD 發(fā)行的實(shí)現(xiàn)，包含在 FreeBSD 之中，這個(gè)分配程序可以從預(yù)先確實(shí)大小的對(duì)象構(gòu)成的池中分配對(duì)象。它有一些用于對(duì)象大小的 size 類(lèi)，這些對(duì)象的大小為 2 的若干次冪減去某一常數(shù)。所以，如果您請(qǐng)求給定大小的一個(gè)對(duì)象，它就簡(jiǎn)單地分配一個(gè)與之匹配的 size 類(lèi)。這樣就提供了一個(gè)快速的實(shí)現(xiàn)，但是可能會(huì)浪費(fèi)內(nèi)存。在參考資料部分中，有一篇描述該實(shí)現(xiàn)的文章。
• Hoard：編寫(xiě) Hoard 的目標(biāo)是使內(nèi)存分配在多線程環(huán)境中進(jìn)行得非?？臁Ｒ虼?，它的構(gòu)造以鎖的使用為中心，從而使所有進(jìn)程不必等待分配內(nèi)存。它可以顯著地加快那些進(jìn)行很多分配和回收的多線程進(jìn)程的速度。在參考資料部分中，有一篇描述該實(shí)現(xiàn)的文章。

眾多可用的分配程序中最有名的就是上述這些分配程序。如果您的程序有特別的分配需求，那么您可能更愿意編寫(xiě)一個(gè)定制的能匹配您的程序內(nèi)存分配方式的分配程序。不過(guò)，如果不熟悉分配程序的設(shè)計(jì)，那么定制分配程序通常會(huì)帶來(lái)比它們解決的問(wèn)題更多的問(wèn)題。要獲得關(guān)于該主題的適當(dāng)?shù)慕榻B，請(qǐng)參閱 Donald Knuth 撰寫(xiě)的The Art of Computer Programming Volume 1: Fundamental Algorithms 中的第 2.5 節(jié)“Dynamic Storage Allocation”（請(qǐng)參閱參考資料中的鏈接）。它有點(diǎn)過(guò)時(shí)，因?yàn)樗鼪](méi)有考慮虛擬內(nèi)存環(huán)境，不過(guò)大部分算法都是基于前面給出的函數(shù)。

在 C++ 中，通過(guò)重載 operator new()，您可以以每個(gè)類(lèi)或者每個(gè)模板為單位實(shí)現(xiàn)自己的分配程序。在 Andrei Alexandrescu 撰寫(xiě)的Modern C++ Design 的第 4 章（“Small Object Allocation”）中，描述了一個(gè)小對(duì)象分配程序（請(qǐng)參閱參考資料中的鏈接）。

基于 malloc() 的內(nèi)存管理的缺點(diǎn)

不只是我們的內(nèi)存管理器有缺點(diǎn)，基于 malloc() 的內(nèi)存管理器仍然也有很多缺點(diǎn)，不管您使用的是哪個(gè)分配程序。對(duì)于那些需要保持長(zhǎng)期存儲(chǔ)的程序使用malloc() 來(lái)管理內(nèi)存可能會(huì)非常令人失望。如果您有大量的不固定的內(nèi)存引用，經(jīng)常難以知道它們何時(shí)被釋放。生存期局限于當(dāng)前函數(shù)的內(nèi)存非常容易管理，但是對(duì)于生存期超出該范圍的內(nèi)存來(lái)說(shuō)，管理內(nèi)存則困難得多。而且，關(guān)于內(nèi)存管理是由進(jìn)行調(diào)用的程序還是由被調(diào)用的函數(shù)來(lái)負(fù)責(zé)這一問(wèn)題，很多 API 都不是很明確。

因?yàn)楣芾韮?nèi)存的問(wèn)題，很多程序傾向于使用它們自己的內(nèi)存管理規(guī)則。C++ 的異常處理使得這項(xiàng)任務(wù)更成問(wèn)題。有時(shí)好像致力于管理內(nèi)存分配和清理的代碼比實(shí)際完成計(jì)算任務(wù)的代碼還要多！因此，我們將研究?jī)?nèi)存管理的其他選擇。

*****************************************************************************************************************************************************************************************************

半自動(dòng)內(nèi)存管理策略

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

引用計(jì)數(shù)是一種 半自動(dòng)（semi-automated）的內(nèi)存管理技術(shù)，這表示它需要一些編程支持，但是它不需要您確切知道某一對(duì)象何時(shí)不再被使用。引用計(jì)數(shù)機(jī)制為您完成內(nèi)存管理任務(wù)。

在引用計(jì)數(shù)中，所有共享的數(shù)據(jù)結(jié)構(gòu)都有一個(gè)域來(lái)包含當(dāng)前活動(dòng)“引用”結(jié)構(gòu)的次數(shù)。當(dāng)向一個(gè)程序傳遞一個(gè)指向某個(gè)數(shù)據(jù)結(jié)構(gòu)指針時(shí)，該程序會(huì)將引用計(jì)數(shù)增加 1。實(shí)質(zhì)上，您是在告訴數(shù)據(jù)結(jié)構(gòu)，它正在被存儲(chǔ)在多少個(gè)位置上。然后，當(dāng)您的進(jìn)程完成對(duì)它的使用后，該程序就會(huì)將引用計(jì)數(shù)減少 1。結(jié)束這個(gè)動(dòng)作之后，它還會(huì)檢查計(jì)數(shù)是否已經(jīng)減到零。如果是，那么它將釋放內(nèi)存。

這樣做的好處是，您不必追蹤程序中某個(gè)給定的數(shù)據(jù)結(jié)構(gòu)可能會(huì)遵循的每一條路徑。每次對(duì)其局部的引用，都將導(dǎo)致計(jì)數(shù)的適當(dāng)增加或減少。這樣可以防止在使用數(shù)據(jù)結(jié)構(gòu)時(shí)釋放該結(jié)構(gòu)。不過(guò)，當(dāng)您使用某個(gè)采用引用計(jì)數(shù)的數(shù)據(jù)結(jié)構(gòu)時(shí)，您必須記得運(yùn)行引用計(jì)數(shù)函數(shù)。另外，內(nèi)置函數(shù)和第三方的庫(kù)不會(huì)知道或者可以使用您的引用計(jì)數(shù)機(jī)制。引用計(jì)數(shù)也難以處理發(fā)生循環(huán)引用的數(shù)據(jù)結(jié)構(gòu)。

要實(shí)現(xiàn)引用計(jì)數(shù)，您只需要兩個(gè)函數(shù) ―― 一個(gè)增加引用計(jì)數(shù)，一個(gè)減少引用計(jì)數(shù)并當(dāng)計(jì)數(shù)減少到零時(shí)釋放內(nèi)存。

一個(gè)示例引用計(jì)數(shù)函數(shù)集可能看起來(lái)如下所示：

清單 9. 基本的引用計(jì)數(shù)函數(shù)

REF 和 UNREF 可能會(huì)更復(fù)雜，這取決于您想要做的事情。例如，您可能想要為多線程程序增加鎖，那么您可能想擴(kuò)展refcountedstruct，使它同樣包含一個(gè)指向某個(gè)在釋放內(nèi)存之前要調(diào)用的函數(shù)的指針（類(lèi)似于面向?qū)ο笳Z(yǔ)言中的析構(gòu)函數(shù) ―― 如果您的結(jié)構(gòu)中包含這些指針，那么這是必需的）。

當(dāng)使用 REF 和 UNREF 時(shí)，您需要遵守這些指針的分配規(guī)則：

• UNREF 分配前左端指針（left-hand-side pointer）指向的值。
• REF 分配后左端指針（left-hand-side pointer）指向的值。

在傳遞使用引用計(jì)數(shù)的結(jié)構(gòu)的函數(shù)中，函數(shù)需要遵循以下這些規(guī)則：

• 在函數(shù)的起始處 REF 每一個(gè)指針。
• 在函數(shù)的結(jié)束處 UNREF 第一個(gè)指針。

以下是一個(gè)使用引用計(jì)數(shù)的生動(dòng)的代碼示例：

清單 10. 使用引用計(jì)數(shù)的示例

由于引用計(jì)數(shù)是如此簡(jiǎn)單，大部分程序員都自已去實(shí)現(xiàn)它，而不是使用庫(kù)。不過(guò)，它們依賴(lài)于 malloc 和 free 等低層的分配程序來(lái)實(shí)際地分配和釋放它們的內(nèi)存。

在 Perl 等高級(jí)語(yǔ)言中，進(jìn)行內(nèi)存管理時(shí)使用引用計(jì)數(shù)非常廣泛。在這些語(yǔ)言中，引用計(jì)數(shù)由語(yǔ)言自動(dòng)地處理，所以您根本不必?fù)?dān)心它，除非要編寫(xiě)擴(kuò)展模塊。由于所有內(nèi)容都必須進(jìn)行引用計(jì)數(shù)，所以這會(huì)對(duì)速度產(chǎn)生一些影響，但它極大地提高了編程的安全性和方便性。以下是引用計(jì)數(shù)的益處：

• 實(shí)現(xiàn)簡(jiǎn)單。
• 易于使用。
• 由于引用是數(shù)據(jù)結(jié)構(gòu)的一部分，所以它有一個(gè)好的緩存位置。

不過(guò)，它也有其不足之處：

• 要求您永遠(yuǎn)不要忘記調(diào)用引用計(jì)數(shù)函數(shù)。
• 無(wú)法釋放作為循環(huán)數(shù)據(jù)結(jié)構(gòu)的一部分的結(jié)構(gòu)。
• 減緩幾乎每一個(gè)指針的分配。
• 盡管所使用的對(duì)象采用了引用計(jì)數(shù)，但是當(dāng)使用異常處理（比如 try 或 setjmp()/ longjmp()）時(shí)，您必須采取其他方法。
• 需要額外的內(nèi)存來(lái)處理引用。
• 引用計(jì)數(shù)占用了結(jié)構(gòu)中的第一個(gè)位置，在大部分機(jī)器中最快可以訪問(wèn)到的就是這個(gè)位置。
• 在多線程環(huán)境中更慢也更難以使用。

C++ 可以通過(guò)使用 智能指針（smart pointers）來(lái)容忍程序員所犯的一些錯(cuò)誤，智能指針可以為您處理引用計(jì)數(shù)等指針處理細(xì)節(jié)。不過(guò)，如果不得不使用任何先前的不能處理智能指針的代碼（比如對(duì) C 庫(kù)的聯(lián)接），實(shí)際上，使用它們的后果通實(shí)比不使用它們更為困難和復(fù)雜。因此，它通常只是有益于純 C++ 項(xiàng)目。如果您想使用智能指針，那么您實(shí)在應(yīng)該去閱讀 Alexandrescu 撰寫(xiě)的Modern C++ Design 一書(shū)中的“Smart Pointers”那一章。

內(nèi)存池

內(nèi)存池是另一種半自動(dòng)內(nèi)存管理方法。內(nèi)存池幫助某些程序進(jìn)行自動(dòng)內(nèi)存管理，這些程序會(huì)經(jīng)歷一些特定的階段，而且每個(gè)階段中都有分配給進(jìn)程的特定階段的內(nèi)存。例如，很多網(wǎng)絡(luò)服務(wù)器進(jìn)程都會(huì)分配很多針對(duì)每個(gè)連接的內(nèi)存 ―― 內(nèi)存的最大生存期限為當(dāng)前連接的存在期。Apache 使用了池式內(nèi)存（pooled memory），將其連接拆分為各個(gè)階段，每個(gè)階段都有自己的內(nèi)存池。在結(jié)束每個(gè)階段時(shí)，會(huì)一次釋放所有內(nèi)存。

在池式內(nèi)存管理中，每次內(nèi)存分配都會(huì)指定內(nèi)存池，從中分配內(nèi)存。每個(gè)內(nèi)存池都有不同的生存期限。在 Apache 中，有一個(gè)持續(xù)時(shí)間為服務(wù)器存在期的內(nèi)存池，還有一個(gè)持續(xù)時(shí)間為連接的存在期的內(nèi)存池，以及一個(gè)持續(xù)時(shí)間為請(qǐng)求的存在期的池，另外還有其他一些內(nèi)存池。因此，如果我的一系列函數(shù)不會(huì)生成比連接持續(xù)時(shí)間更長(zhǎng)的數(shù)據(jù)，那么我就可以完全從連接池中分配內(nèi)存，并知道在連接結(jié)束時(shí)，這些內(nèi)存會(huì)被自動(dòng)釋放。另外，有一些實(shí)現(xiàn)允許注冊(cè)清除函數(shù)（cleanup functions），在清除內(nèi)存池之前，恰好可以調(diào)用它，來(lái)完成在內(nèi)存被清理前需要完成的其他所有任務(wù)（類(lèi)似于面向?qū)ο笾械奈鰳?gòu)函數(shù)）。

要在自己的程序中使用池，您既可以使用 GNU libc 的 obstack 實(shí)現(xiàn)，也可以使用 Apache 的 Apache Portable Runtime。GNU obstack 的好處在于，基于 GNU 的 Linux 發(fā)行版本中默認(rèn)會(huì)包括它們。Apache Portable Runtime 的好處在于它有很多其他工具，可以處理編寫(xiě)多平臺(tái)服務(wù)器軟件所有方面的事情。要深入了解 GNU obstack 和 Apache 的池式內(nèi)存實(shí)現(xiàn)，請(qǐng)參閱參考資料部分中指向這些實(shí)現(xiàn)的文檔的鏈接。

下面的假想代碼列表展示了如何使用 obstack：

清單 11. obstack 的示例代碼

基本上，在操作的每一個(gè)主要階段結(jié)束之后，這個(gè)階段的 obstack 會(huì)被釋放。不過(guò)，要注意的是，如果一個(gè)過(guò)程需要分配持續(xù)時(shí)間比當(dāng)前階段更長(zhǎng)的內(nèi)存，那么它也可以使用更長(zhǎng)期限的 obstack，比如連接或者全局內(nèi)存。傳遞給obstack_free() 的NULL 指出它應(yīng)該釋放 obstack 的全部?jī)?nèi)容。可以用其他的值，但是它們通常不怎么實(shí)用。

使用池式內(nèi)存分配的益處如下所示：

• 應(yīng)用程序可以簡(jiǎn)單地管理內(nèi)存。
• 內(nèi)存分配和回收更快，因?yàn)槊看味际窃谝粋€(gè)池中完成的。分配可以在 O(1) 時(shí)間內(nèi)完成，釋放內(nèi)存池所需時(shí)間也差不多（實(shí)際上是 O(n) 時(shí)間，不過(guò)在大部分情況下會(huì)除以一個(gè)大的因數(shù)，使其變成 O(1)）。
• 可以預(yù)先分配錯(cuò)誤處理池（Error-handling pools），以便程序在常規(guī)內(nèi)存被耗盡時(shí)仍可以恢復(fù)。
• 有非常易于使用的標(biāo)準(zhǔn)實(shí)現(xiàn)。

池式內(nèi)存的缺點(diǎn)是：

• 內(nèi)存池只適用于操作可以分階段的程序。
• 內(nèi)存池通常不能與第三方庫(kù)很好地合作。
• 如果程序的結(jié)構(gòu)發(fā)生變化，則不得不修改內(nèi)存池，這可能會(huì)導(dǎo)致內(nèi)存管理系統(tǒng)的重新設(shè)計(jì)。
• 您必須記住需要從哪個(gè)池進(jìn)行分配。另外，如果在這里出錯(cuò)，就很難捕獲該內(nèi)存池。

*****************************************************************************************************************************************************************************************************

垃圾收集

垃圾收集（Garbage collection）是全自動(dòng)地檢測(cè)并移除不再使用的數(shù)據(jù)對(duì)象。垃圾收集器通常會(huì)在當(dāng)可用內(nèi)存減少到少于一個(gè)具體的閾值時(shí)運(yùn)行。通常，它們以程序所知的可用的一組“基本”數(shù)據(jù) ―― 棧數(shù)據(jù)、全局變量、寄存器 ―― 作為出發(fā)點(diǎn)。然后它們嘗試去追蹤通過(guò)這些數(shù)據(jù)連接到每一塊數(shù)據(jù)。收集器找到的都是有用的數(shù)據(jù)；它沒(méi)有找到的就是垃圾，可以被銷(xiāo)毀并重新使用這些無(wú)用的數(shù)據(jù)。為了有效地管理內(nèi)存，很多類(lèi)型的垃圾收集器都需要知道數(shù)據(jù)結(jié)構(gòu)內(nèi)部指針的規(guī)劃，所以，為了正確運(yùn)行垃圾收集器，它們必須是語(yǔ)言本身的一部分。

收集器的類(lèi)型

• 復(fù)制（copying）： 這些收集器將內(nèi)存存儲(chǔ)器分為兩部分，只允許數(shù)據(jù)駐留在其中一部分上。它們定時(shí)地從“基本”的元素開(kāi)始將數(shù)據(jù)從一部分復(fù)制到另一部分。內(nèi)存新近被占用的部分現(xiàn)在成為活動(dòng)的，另一部分上的所有內(nèi)容都認(rèn)為是垃圾。另外，當(dāng)進(jìn)行這項(xiàng)復(fù)制操作時(shí)，所有指針都必須被更新為指向每個(gè)內(nèi)存條目的新位置。因此，為使用這種垃圾收集方法，垃圾收集器必須與編程語(yǔ)言集成在一起。
• 標(biāo)記并清理（Mark and sweep）：每一塊數(shù)據(jù)都被加上一個(gè)標(biāo)簽。不定期的，所有標(biāo)簽都被設(shè)置為 0，收集器從“基本”的元素開(kāi)始遍歷數(shù)據(jù)。當(dāng)它遇到內(nèi)存時(shí)，就將標(biāo)簽標(biāo)記為 1。最后沒(méi)有被標(biāo)記為 1 的所有內(nèi)容都認(rèn)為是垃圾，以后分配內(nèi)存時(shí)會(huì)重新使用它們。
• 增量的（Incremental）：增量垃圾收集器不需要遍歷全部數(shù)據(jù)對(duì)象。因?yàn)樵谑占陂g的突然等待，也因?yàn)榕c訪問(wèn)所有當(dāng)前數(shù)據(jù)相關(guān)的緩存問(wèn)題（所有內(nèi)容都不得不被頁(yè)入（page-in）），遍歷所有內(nèi)存會(huì)引發(fā)問(wèn)題。增量收集器避免了這些問(wèn)題。
• 保守的（Conservative）：保守的垃圾收集器在管理內(nèi)存時(shí)不需要知道與數(shù)據(jù)結(jié)構(gòu)相關(guān)的任何信息。它們只查看所有數(shù)據(jù)類(lèi)型，并假定它們可以全部都是指針。所以，如果一個(gè)字節(jié)序列可以是一個(gè)指向一塊被分配的內(nèi)存的指針，那么收集器就將其標(biāo)記為正在被引用。有時(shí)沒(méi)有被引用的內(nèi)存會(huì)被收集，這樣會(huì)引發(fā)問(wèn)題，例如，如果一個(gè)整數(shù)域中包含一個(gè)值，該值是已分配內(nèi)存的地址。不過(guò)，這種情況極少發(fā)生，而且它只會(huì)浪費(fèi)少量?jī)?nèi)存。保守的收集器的優(yōu)勢(shì)是，它們可以與任何編程語(yǔ)言相集成。

Hans Boehm 的保守垃圾收集器是可用的最流行的垃圾收集器之一，因?yàn)樗敲赓M(fèi)的，而且既是保守的又是增量的，可以使用 --enable-redirect-malloc 選項(xiàng)來(lái)構(gòu)建它，并且可以將它用作系統(tǒng)分配程序的簡(jiǎn)易替代者（drop-in replacement）（用malloc/free 代替它自己的 API）。實(shí)際上，如果這樣做，您就可以使用與我們?cè)谑纠峙涑绦蛑兴褂玫南嗤?code>LD_PRELOAD 技巧，在系統(tǒng)上的幾乎任何程序中啟用垃圾收集。如果您懷疑某個(gè)程序正在泄漏內(nèi)存，那么您可以使用這個(gè)垃圾收集器來(lái)控制進(jìn)程。在早期，當(dāng) Mozilla 嚴(yán)重地泄漏內(nèi)存時(shí)，很多人在其中使用了這項(xiàng)技術(shù)。這種垃圾收集器既可以在 Windows? 下運(yùn)行，也可以在 UNIX 下運(yùn)行。

垃圾收集的一些優(yōu)點(diǎn)：

• 您永遠(yuǎn)不必?fù)?dān)心內(nèi)存的雙重釋放或者對(duì)象的生命周期。
• 使用某些收集器，您可以使用與常規(guī)分配相同的 API。

其缺點(diǎn)包括：

• 使用大部分收集器時(shí)，您都無(wú)法干涉何時(shí)釋放內(nèi)存。
• 在多數(shù)情況下，垃圾收集比其他形式的內(nèi)存管理更慢。
• 垃圾收集錯(cuò)誤引發(fā)的缺陷難于調(diào)試。
• 如果您忘記將不再使用的指針設(shè)置為 null，那么仍然會(huì)有內(nèi)存泄漏。

*****************************************************************************************************************************************************************************************************

結(jié)束語(yǔ)

一切都需要折衷：性能、易用、易于實(shí)現(xiàn)、支持線程的能力等，這里只列出了其中的一些。為了滿(mǎn)足項(xiàng)目的要求，有很多內(nèi)存管理模式可以供您使用。每種模式都有大量的實(shí)現(xiàn)，各有其優(yōu)缺點(diǎn)。對(duì)很多項(xiàng)目來(lái)說(shuō)，使用編程環(huán)境默認(rèn)的技術(shù)就足夠了，不過(guò)，當(dāng)您的項(xiàng)目有特殊的需要時(shí)，了解可用的選擇將會(huì)有幫助。下表對(duì)比了本文中涉及的內(nèi)存管理策略。

表 1. 內(nèi)存分配策略的對(duì)比

――――――――  更多內(nèi)容，請(qǐng)查看原文：http://www.ibm.com/developerworks/cn/linux/l-memory/

生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)