本文將對 Linux? 程序員可以使用的內存管理技術(shù)進(jìn)行概述，雖然關(guān)注的重點(diǎn)是 C 語(yǔ)言，但同樣也適用于其他語(yǔ)言。文中將為您提供如何管理內存的細節，然后將進(jìn)一步展示如何手工管理內存，如何使用引用計數或者內存池來(lái)半手工地管理內存，以及如何使用垃圾收集自動(dòng)管理內存。 為什么必須管理內存 內存管理是計算機編程最為基本的領(lǐng)域之一。在很多腳本語(yǔ)言中，您不必擔心內存是如何管理的，這并不能使得內存管理的重要性有一點(diǎn)點(diǎn)降低。對實(shí)際編程來(lái)說(shuō)，理解您的內存管理器的能力與局限性至關(guān)重要。在大部分系統語(yǔ)言中，比如 C 和 C++，您必須進(jìn)行內存管理。本文將介紹手工的、半手工的以及自動(dòng)的內存管理實(shí)踐的基本概念。 追溯到在 Apple II 上進(jìn)行匯編語(yǔ)言編程的時(shí)代，那時(shí)內存管理還不是個(gè)大問(wèn)題。您實(shí)際上在運行整個(gè)系統。系統有多少內存，您就有多少內存。您甚至不必費心思去弄明白它有多少內存，因為每一臺機器的內存數量都相同。所以，如果內存需要非常固定，那么您只需要選擇一個(gè)內存范圍并使用它即可。 不過(guò)，即使是在這樣一個(gè)簡(jiǎn)單的計算機中，您也會(huì )有問(wèn)題，尤其是當您不知道程序的每個(gè)部分將需要多少內存時(shí)。如果您的空間有限，而內存需求是變化的，那么您需要一些方法來(lái)滿(mǎn)足這些需求： - 確定您是否有足夠的內存來(lái)處理數據。
- 從可用的內存中獲取一部分內存。
- 向可用內存池（pool）中返回部分內存，以使其可以由程序的其他部分或者其他程序使用。
實(shí)現這些需求的程序庫稱(chēng)為 分配程序（allocators），因為它們負責分配和回收內存。程序的動(dòng)態(tài)性越強，內存管理就越重要，您的內存分配程序的選擇也就更重要。讓我們來(lái)了解可用于內存管理的不同方法，它們的好處與不足，以及它們最適用的情形。
C 風(fēng)格的內存分配程序 C 編程語(yǔ)言提供了兩個(gè)函數來(lái)滿(mǎn)足我們的三個(gè)需求： - malloc：該函數分配給定的字節數，并返回一個(gè)指向它們的指針。如果沒(méi)有足夠的可用內存，那么它返回一個(gè)空指針。
- free：該函數獲得指向由
malloc 分配的內存片段的指針，并將其釋放，以便以后的程序或操作系統使用（實(shí)際上，一些 malloc 實(shí)現只能將內存歸還給程序，而無(wú)法將內存歸還給操作系統）。 物理內存和虛擬內存 要理解內存在程序中是如何分配的，首先需要理解如何將內存從操作系統分配給程序。計算機上的每一個(gè)進(jìn)程都認為自己可以訪(fǎng)問(wèn)所有的物理內存。顯然，由于同時(shí)在運行多個(gè)程序，所以每個(gè)進(jìn)程不可能擁有全部?jì)却?。?shí)際上，這些進(jìn)程使用的是 虛擬內存。 只是作為一個(gè)例子，讓我們假定您的程序正在訪(fǎng)問(wèn)地址為 629 的內存。不過(guò)，虛擬內存系統不需要將其存儲在位置為 629 的 RAM 中。實(shí)際上，它甚至可以不在 RAM 中 —— 如果物理 RAM 已經(jīng)滿(mǎn)了，它甚至可能已經(jīng)被轉移到硬盤(pán)上！由于這類(lèi)地址不必反映內存所在的物理位置，所以它們被稱(chēng)為虛擬內存。操作系統維持著(zhù)一個(gè)虛擬地址到物理地址的轉換的表，以便計算機硬件可以正確地響應地址請求。并且，如果地址在硬盤(pán)上而不是在 RAM 中，那么操作系統將暫時(shí)停止您的進(jìn)程，將其他內存轉存到硬盤(pán)中，從硬盤(pán)上加載被請求的內存，然后再重新啟動(dòng)您的進(jìn)程。這樣，每個(gè)進(jìn)程都獲得了自己可以使用的地址空間，可以訪(fǎng)問(wèn)比您物理上安裝的內存更多的內存。 在 32-位 x86 系統上，每一個(gè)進(jìn)程可以訪(fǎng)問(wèn) 4 GB 內存?，F在，大部分人的系統上并沒(méi)有 4 GB 內存，即使您將 swap 也算上， 每個(gè)進(jìn)程所使用的內存也肯定少于 4 GB。因此，當加載一個(gè)進(jìn)程時(shí)，它會(huì )得到一個(gè)取決于某個(gè)稱(chēng)為 系統中斷點(diǎn)（system break）的特定地址的初始內存分配。該地址之后是未被映射的內存 —— 用于在 RAM 或者硬盤(pán)中沒(méi)有分配相應物理位置的內存。因此，如果一個(gè)進(jìn)程運行超出了它初始分配的內存，那么它必須請求操作系統“映射進(jìn)來(lái)（map in）”更多的內存。（映射是一個(gè)表示一一對應關(guān)系的數學(xué)術(shù)語(yǔ) —— 當內存的虛擬地址有一個(gè)對應的物理地址來(lái)存儲內存內容時(shí)，該內存將被映射。） 基于 UNIX 的系統有兩個(gè)可映射到附加內存中的基本系統調用： - brk：
brk() 是一個(gè)非常簡(jiǎn)單的系統調用。還記得系統中斷點(diǎn)嗎？該位置是進(jìn)程映射的內存邊界。 brk() 只是簡(jiǎn)單地將這個(gè)位置向前或者向后移動(dòng)，就可以向進(jìn)程添加內存或者從進(jìn)程取走內存。 - mmap：
mmap()，或者說(shuō)是“內存映像”，類(lèi)似于 brk()，但是更為靈活。首先，它可以映射任何位置的內存，而不單單只局限于進(jìn)程。其次，它不僅可以將虛擬地址映射到物理的 RAM 或者 swap，它還可以將它們映射到文件和文件位置，這樣，讀寫(xiě)內存將對文件中的數據進(jìn)行讀寫(xiě)。不過(guò)，在這里，我們只關(guān)心 mmap 向進(jìn)程添加被映射的內存的能力。 munmap() 所做的事情與 mmap() 相反。 如您所見(jiàn)， brk() 或者 mmap() 都可以用來(lái)向我們的進(jìn)程添加額外的虛擬內存。在我們的例子中將使用 brk()，因為它更簡(jiǎn)單，更通用。 實(shí)現一個(gè)簡(jiǎn)單的分配程序 如果您曾經(jīng)編寫(xiě)過(guò)很多 C 程序，那么您可能曾多次使用過(guò) malloc() 和 free()。不過(guò)，您可能沒(méi)有用一些時(shí)間去思考它們在您的操作系統中是如何實(shí)現的。本節將向您展示 malloc 和 free 的一個(gè)最簡(jiǎn)化實(shí)現的代碼，來(lái)幫助說(shuō)明管理內存時(shí)都涉及到了哪些事情。 要試著(zhù)運行這些示例，需要先 復制本代碼清單，并將其粘貼到一個(gè)名為 malloc.c 的文件中。接下來(lái)，我將一次一個(gè)部分地對該清單進(jìn)行解釋。 在大部分操作系統中，內存分配由以下兩個(gè)簡(jiǎn)單的函數來(lái)處理： void *malloc(long numbytes)：該函數負責分配 numbytes 大小的內存，并返回指向第一個(gè)字節的指針。 void free(void *firstbyte)：如果給定一個(gè)由先前的 malloc 返回的指針，那么該函數會(huì )將分配的空間歸還給進(jìn)程的“空閑空間”。 malloc_init 將是初始化內存分配程序的函數。它要完成以下三件事：將分配程序標識為已經(jīng)初始化，找到系統中最后一個(gè)有效內存地址，然后建立起指向我們管理的內存的指針。這三個(gè)變量都是全局變量：
清單 1. 我們的簡(jiǎn)單分配程序的全局變量
int has_initialized = 0; void *managed_memory_start; void *last_valid_address;
|
如前所述，被映射的內存的邊界（最后一個(gè)有效地址）常被稱(chēng)為系統中斷點(diǎn)或者 當前中斷點(diǎn)。在很多 UNIX? 系統中，為了指出當前系統中斷點(diǎn)，必須使用 sbrk(0) 函數。 sbrk 根據參數中給出的字節數移動(dòng)當前系統中斷點(diǎn)，然后返回新的系統中斷點(diǎn)。使用參數 0 只是返回當前中斷點(diǎn)。這里是我們的 malloc 初始化代碼，它將找到當前中斷點(diǎn)并初始化我們的變量：
清單 2. 分配程序初始化函數
/* Include the sbrk function */ #include <unistd.h> void malloc_init() { /* grab the last valid address from the OS */ last_valid_address = sbrk(0); /* we don‘t have any memory to manage yet, so *just set the beginning to be last_valid_address */ managed_memory_start = last_valid_address; /* Okay, we‘re initialized and ready to go */ has_initialized = 1; }
|
現在，為了完全地管理內存，我們需要能夠追蹤要分配和回收哪些內存。在對內存塊進(jìn)行了 free 調用之后，我們需要做的是諸如將它們標記為未被使用的等事情，并且，在調用 malloc 時(shí)，我們要能夠定位未被使用的內存塊。因此， malloc 返回的每塊內存的起始處首先要有這個(gè)結構：
清單 3. 內存控制塊結構定義
struct mem_control_block { int is_available; int size; };
|
現在，您可能會(huì )認為當程序調用 malloc 時(shí)這會(huì )引發(fā)問(wèn)題 —— 它們如何知道這個(gè)結構？答案是它們不必知道；在返回指針之前，我們會(huì )將其移動(dòng)到這個(gè)結構之后，把它隱藏起來(lái)。這使得返回的指針指向沒(méi)有用于任何其他用途的內存。那樣，從調用程序的角度來(lái)看，它們所得到的全部是空閑的、開(kāi)放的內存。然后，當通過(guò) free() 將該指針傳遞回來(lái)時(shí)，我們只需要倒退幾個(gè)內存字節就可以再次找到這個(gè)結構。 在討論分配內存之前，我們將先討論釋放，因為它更簡(jiǎn)單。為了釋放內存，我們必須要做的惟一一件事情就是，獲得我們給出的指針，回退 sizeof(struct mem_control_block) 個(gè)字節，并將其標記為可用的。這里是對應的代碼：
清單 4. 解除分配函數
void free(void *firstbyte) { struct mem_control_block *mcb; /* Backup from the given pointer to find the * mem_control_block */ mcb = firstbyte - sizeof(struct mem_control_block); /* Mark the block as being available */ mcb->is_available = 1; /* That‘s It! We‘re done. */ return; }
|
如您所見(jiàn)，在這個(gè)分配程序中，內存的釋放使用了一個(gè)非常簡(jiǎn)單的機制，在固定時(shí)間內完成內存釋放。分配內存稍微困難一些。以下是該算法的略述：
清單 5. 主分配程序的偽代碼
1. If our allocator has not been initialized, initialize it. 2. Add sizeof(struct mem_control_block) to the size requested. 3. start at managed_memory_start. 4. Are we at last_valid address? 5. If we are: A. We didn‘t find any existing space that was large enough -- ask the operating system for more and return that. 6. Otherwise: A. Is the current space available (check is_available from the mem_control_block)? B. If it is: i) Is it large enough (check "size" from the mem_control_block)? ii) If so: a. Mark it as unavailable b. Move past mem_control_block and return the pointer iii) Otherwise: a. Move forward "size" bytes b. Go back go step 4 C. Otherwise: i) Move forward "size" bytes ii) Go back to step 4
|
我們主要使用連接的指針遍歷內存來(lái)尋找開(kāi)放的內存塊。這里是代碼：
清單 6. 主分配程序
void *malloc(long numbytes) { /* Holds where we are looking in memory */ void *current_location; /* This is the same as current_location, but cast to a * memory_control_block */ struct mem_control_block *current_location_mcb; /* This is the memory location we will return. It will * be set to 0 until we find something suitable */ void *memory_location; /* Initialize if we haven‘t already done so */ if(! has_initialized) { malloc_init(); } /* The memory we search for has to include the memory * control block, but the users of malloc don‘t need * to know this, so we‘ll just add it in for them. */ numbytes = numbytes + sizeof(struct mem_control_block); /* Set memory_location to 0 until we find a suitable * location */ memory_location = 0; /* Begin searching at the start of managed memory */ current_location = managed_memory_start; /* Keep going until we have searched all allocated space */ while(current_location != last_valid_address) { /* current_location and current_location_mcb point * to the same address. However, current_location_mcb * is of the correct type, so we can use it as a struct. * current_location is a void pointer so we can use it * to calculate addresses. */ current_location_mcb = (struct mem_control_block *)current_location; if(current_location_mcb->is_available) { if(current_location_mcb->size >= numbytes) { /* Woohoo! We‘ve found an open, * appropriately-size location. */ /* It is no longer available */ current_location_mcb->is_available = 0; /* We own it */ memory_location = current_location; /* Leave the loop */ break; } } /* If we made it here, it‘s because the Current memory * block not suitable; move to the next one */ current_location = current_location + current_location_mcb->size; } /* If we still don‘t have a valid location, we‘ll * have to ask the operating system for more memory */ if(! memory_location) { /* Move the program break numbytes further */ sbrk(numbytes); /* The new memory will be where the last valid * address left off */ memory_location = last_valid_address; /* We‘ll move the last valid address forward * numbytes */ last_valid_address = last_valid_address + numbytes; /* We need to initialize the mem_control_block */ current_location_mcb = memory_location; current_location_mcb->is_available = 0; current_location_mcb->size = numbytes; } /* Now, no matter what (well, except for error conditions), * memory_location has the address of the memory, including * the mem_control_block */ /* Move the pointer past the mem_control_block */ memory_location = memory_location + sizeof(struct mem_control_block); /* Return the pointer */ return memory_location; }
|
這就是我們的內存管理器?，F在，我們只需要構建它，并在程序中使用它即可。 運行下面的命令來(lái)構建 malloc 兼容的分配程序（實(shí)際上，我們忽略了 realloc() 等一些函數，不過(guò)， malloc() 和 free() 才是最主要的函數）：
清單 7. 編譯分配程序
gcc -shared -fpic malloc.c -o malloc.so
|
該程序將生成一個(gè)名為 malloc.so 的文件，它是一個(gè)包含有我們的代碼的共享庫。 在 UNIX 系統中，現在您可以用您的分配程序來(lái)取代系統的 malloc()，做法如下：
清單 8. 替換您的標準的 malloc
LD_PRELOAD=/path/to/malloc.so export LD_PRELOAD
|
LD_PRELOAD 環(huán)境變量使動(dòng)態(tài)鏈接器在加載任何可執行程序之前，先加載給定的共享庫的符號。它還為特定庫中的符號賦予優(yōu)先權。因此，從現在起，該會(huì )話(huà)中的任何應用程序都將使用我們的 malloc()，而不是只有系統的應用程序能夠使用。有一些應用程序不使用 malloc()，不過(guò)它們是例外。其他使用 realloc() 等其他內存管理函數的應用程序，或者錯誤地假定 malloc() 內部行為的那些應用程序，很可能會(huì )崩潰。ash shell 似乎可以使用我們的新 malloc() 很好地工作。
如果您想確保 malloc() 正在被使用，那么您應該通過(guò)向函數的入口點(diǎn)添加 write() 調用來(lái)進(jìn)行測試。 我們的內存管理器在很多方面都還存在欠缺，但它可以有效地展示內存管理需要做什么事情。它的某些缺點(diǎn)包括： - 由于它對系統中斷點(diǎn)（一個(gè)全局變量）進(jìn)行操作，所以它不能與其他分配程序或者
mmap 一起使用。 - 當分配內存時(shí)，在最壞的情形下，它將不得不遍歷 全部進(jìn)程內存；其中可能包括位于硬盤(pán)上的很多內存，這意味著(zhù)操作系統將不得不花時(shí)間去向硬盤(pán)移入數據和從硬盤(pán)中移出數據。
- 沒(méi)有很好的內存不足處理方案（
malloc 只假定內存分配是成功的）。 - 它沒(méi)有實(shí)現很多其他的內存函數，比如
realloc()。 - 由于
sbrk() 可能會(huì )交回比我們請求的更多的內存，所以在堆（heap）的末端會(huì )遺漏一些內存。 - 雖然
is_available 標記只包含一位信息，但它要使用完整的 4-字節 的字。 - 分配程序不是線(xiàn)程安全的。
- 分配程序不能將空閑空間拼合為更大的內存塊。
- 分配程序的過(guò)于簡(jiǎn)單的匹配算法會(huì )導致產(chǎn)生很多潛在的內存碎片。
- 我確信還有很多其他問(wèn)題。這就是為什么它只是一個(gè)例子!
其他 malloc 實(shí)現 malloc() 的實(shí)現有很多，這些實(shí)現各有優(yōu)點(diǎn)與缺點(diǎn)。在設計一個(gè)分配程序時(shí)，要面臨許多需要折衷的選擇，其中包括：
- 分配的速度。
- 回收的速度。
- 有線(xiàn)程的環(huán)境的行為。
- 內存將要被用光時(shí)的行為。
- 局部緩存。
- 簿記（Bookkeeping）內存開(kāi)銷(xiāo)。
- 虛擬內存環(huán)境中的行為。
- 小的或者大的對象。
- 實(shí)時(shí)保證。
每一個(gè)實(shí)現都有其自身的優(yōu)缺點(diǎn)集合。在我們的簡(jiǎn)單的分配程序中，分配非常慢，而回收非?？?。另外，由于它在使用虛擬內存系統方面較差，所以它最適于處理大的對象。 還有其他許多分配程序可以使用。其中包括： - Doug Lea Malloc：Doug Lea Malloc 實(shí)際上是完整的一組分配程序，其中包括 Doug Lea 的原始分配程序，GNU libc 分配程序和
ptmalloc。 Doug Lea 的分配程序有著(zhù)與我們的版本非常類(lèi)似的基本結構，但是它加入了索引，這使得搜索速度更快，并且可以將多個(gè)沒(méi)有被使用的塊組合為一個(gè)大的塊。它還支持緩存，以便更快地再次使用最近釋放的內存。 ptmalloc 是 Doug Lea Malloc 的一個(gè)擴展版本，支持多線(xiàn)程。在本文后面的 參考資料部分中，有一篇描述 Doug Lea 的 Malloc 實(shí)現的文章。 - BSD Malloc：BSD Malloc 是隨 4.2 BSD 發(fā)行的實(shí)現，包含在 FreeBSD 之中，這個(gè)分配程序可以從預先確實(shí)大小的對象構成的池中分配對象。它有一些用于對象大小的 size 類(lèi)，這些對象的大小為 2 的若干次冪減去某一常數。所以，如果您請求給定大小的一個(gè)對象，它就簡(jiǎn)單地分配一個(gè)與之匹配的 size 類(lèi)。這樣就提供了一個(gè)快速的實(shí)現，但是可能會(huì )浪費內存。在 參考資料部分中，有一篇描述該實(shí)現的文章。
- Hoard：編寫(xiě) Hoard 的目標是使內存分配在多線(xiàn)程環(huán)境中進(jìn)行得非?？?。因此，它的構造以鎖的使用為中心，從而使所有進(jìn)程不必等待分配內存。它可以顯著(zhù)地加快那些進(jìn)行很多分配和回收的多線(xiàn)程進(jìn)程的速度。在 參考資料部分中，有一篇描述該實(shí)現的文章。
眾多可用的分配程序中最有名的就是上述這些分配程序。如果您的程序有特別的分配需求，那么您可能更愿意編寫(xiě)一個(gè)定制的能匹配您的程序內存分配方式的分配程序。不過(guò)，如果不熟悉分配程序的設計，那么定制分配程序通常會(huì )帶來(lái)比它們解決的問(wèn)題更多的問(wèn)題。要獲得關(guān)于該主題的適當的介紹，請參閱 Donald Knuth 撰寫(xiě)的 The Art of Computer Programming Volume 1: Fundamental Algorithms 中的第 2.5 節“Dynamic Storage Allocation”（請參閱 參考資料中的鏈接）。它有點(diǎn)過(guò)時(shí)，因為它沒(méi)有考慮虛擬內存環(huán)境，不過(guò)大部分算法都是基于前面給出的函數。 在 C++ 中，通過(guò)重載 operator new()，您可以以每個(gè)類(lèi)或者每個(gè)模板為單位實(shí)現自己的分配程序。在 Andrei Alexandrescu 撰寫(xiě)的 Modern C++ Design 的第 4 章（“Small Object Allocation”）中，描述了一個(gè)小對象分配程序（請參閱 參考資料中的鏈接）。 基于 malloc() 的內存管理的缺點(diǎn) 不只是我們的內存管理器有缺點(diǎn)，基于 malloc() 的內存管理器仍然也有很多缺點(diǎn)，不管您使用的是哪個(gè)分配程序。對于那些需要保持長(cháng)期存儲的程序使用 malloc() 來(lái)管理內存可能會(huì )非常令人失望。如果您有大量的不固定的內存引用，經(jīng)常難以知道它們何時(shí)被釋放。生存期局限于當前函數的內存非常容易管理，但是對于生存期超出該范圍的內存來(lái)說(shuō)，管理內存則困難得多。而且，關(guān)于內存管理是由進(jìn)行調用的程序還是由被調用的函數來(lái)負責這一問(wèn)題，很多 API 都不是很明確。 因為管理內存的問(wèn)題，很多程序傾向于使用它們自己的內存管理規則。C++ 的異常處理使得這項任務(wù)更成問(wèn)題。有時(shí)好像致力于管理內存分配和清理的代碼比實(shí)際完成計算任務(wù)的代碼還要多！因此，我們將研究?jì)却婀芾淼钠渌x擇。
半自動(dòng)內存管理策略 引用計數 引用計數是一種 半自動(dòng)（semi-automated）的內存管理技術(shù)，這表示它需要一些編程支持，但是它不需要您確切知道某一對象何時(shí)不再被使用。引用計數機制為您完成內存管理任務(wù)。 在引用計數中，所有共享的數據結構都有一個(gè)域來(lái)包含當前活動(dòng)“引用”結構的次數。當向一個(gè)程序傳遞一個(gè)指向某個(gè)數據結構指針時(shí)，該程序會(huì )將引用計數增加 1。實(shí)質(zhì)上，您是在告訴數據結構，它正在被存儲在多少個(gè)位置上。然后，當您的進(jìn)程完成對它的使用后，該程序就會(huì )將引用計數減少 1。結束這個(gè)動(dòng)作之后，它還會(huì )檢查計數是否已經(jīng)減到零。如果是，那么它將釋放內存。 這樣做的好處是，您不必追蹤程序中某個(gè)給定的數據結構可能會(huì )遵循的每一條路徑。每次對其局部的引用，都將導致計數的適當增加或減少。這樣可以防止在使用數據結構時(shí)釋放該結構。不過(guò)，當您使用某個(gè)采用引用計數的數據結構時(shí)，您必須記得運行引用計數函數。另外，內置函數和第三方的庫不會(huì )知道或者可以使用您的引用計數機制。引用計數也難以處理發(fā)生循環(huán)引用的數據結構。 要實(shí)現引用計數，您只需要兩個(gè)函數 —— 一個(gè)增加引用計數，一個(gè)減少引用計數并當計數減少到零時(shí)釋放內存。 一個(gè)示例引用計數函數集可能看起來(lái)如下所示：
清單 9. 基本的引用計數函數
/* Structure Definitions*/ /* Base structure that holds a refcount */ struct refcountedstruct { int refcount; } /* All refcounted structures must mirror struct * refcountedstruct for their first variables */ /* Refcount maintenance functions */ /* Increase reference count */ void REF(void *data) { struct refcountedstruct *rstruct; rstruct = (struct refcountedstruct *) data; rstruct->refcount++; } /* Decrease reference count */ void UNREF(void *data) { struct refcountedstruct *rstruct; rstruct = (struct refcountedstruct *) data; rstruct->refcount--; /* Free the structure if there are no more users */ if(rstruct->refcount == 0) { free(rstruct); } }
|
REF 和 UNREF 可能會(huì )更復雜，這取決于您想要做的事情。例如，您可能想要為多線(xiàn)程程序增加鎖，那么您可能想擴展 refcountedstruct，使它同樣包含一個(gè)指向某個(gè)在釋放內存之前要調用的函數的指針（類(lèi)似于面向對象語(yǔ)言中的析構函數 —— 如果您的結構中包含這些指針，那么這是 必需的）。
當使用 REF 和 UNREF 時(shí)，您需要遵守這些指針的分配規則： UNREF 分配前左端指針（left-hand-side pointer）指向的值。 REF 分配后左端指針（left-hand-side pointer）指向的值。 在傳遞使用引用計數的結構的函數中，函數需要遵循以下這些規則： - 在函數的起始處 REF 每一個(gè)指針。
- 在函數的結束處 UNREF 第一個(gè)指針。
以下是一個(gè)使用引用計數的生動(dòng)的代碼示例：
清單 10. 使用引用計數的示例
/* EXAMPLES OF USAGE */ /* Data type to be refcounted */ struct mydata { int refcount; /* same as refcountedstruct */ int datafield1; /* Fields specific to this struct */ int datafield2; /* other declarations would go here as appropriate */ }; /* Use the functions in code */ void dosomething(struct mydata *data) { REF(data); /* Process data */ /* when we are through */ UNREF(data); } struct mydata *globalvar1; /* Note that in this one, we don‘t decrease the * refcount since we are maintaining the reference * past the end of the function call through the * global variable */ void storesomething(struct mydata *data) { REF(data); /* passed as a parameter */ globalvar1 = data; REF(data); /* ref because of Assignment */ UNREF(data); /* Function finished */ }
|
由于引用計數是如此簡(jiǎn)單，大部分程序員都自已去實(shí)現它，而不是使用庫。不過(guò)，它們依賴(lài)于 malloc 和 free 等低層的分配程序來(lái)實(shí)際地分配和釋放它們的內存。 在 Perl 等高級語(yǔ)言中，進(jìn)行內存管理時(shí)使用引用計數非常廣泛。在這些語(yǔ)言中，引用計數由語(yǔ)言自動(dòng)地處理，所以您根本不必擔心它，除非要編寫(xiě)擴展模塊。由于所有內容都必須進(jìn)行引用計數，所以這會(huì )對速度產(chǎn)生一些影響，但它極大地提高了編程的安全性和方便性。以下是引用計數的益處： - 實(shí)現簡(jiǎn)單。
- 易于使用。
- 由于引用是數據結構的一部分，所以它有一個(gè)好的緩存位置。
不過(guò)，它也有其不足之處： - 要求您永遠不要忘記調用引用計數函數。
- 無(wú)法釋放作為循環(huán)數據結構的一部分的結構。
- 減緩幾乎每一個(gè)指針的分配。
- 盡管所使用的對象采用了引用計數，但是當使用異常處理（比如
try 或 setjmp()/ longjmp()）時(shí)，您必須采取其他方法。 - 需要額外的內存來(lái)處理引用。
- 引用計數占用了結構中的第一個(gè)位置，在大部分機器中最快可以訪(fǎng)問(wèn)到的就是這個(gè)位置。
- 在多線(xiàn)程環(huán)境中更慢也更難以使用。
C++ 可以通過(guò)使用 智能指針（smart pointers）來(lái)容忍程序員所犯的一些錯誤，智能指針可以為您處理引用計數等指針處理細節。不過(guò)，如果不得不使用任何先前的不能處理智能指針的代碼（比如對 C 庫的聯(lián)接），實(shí)際上，使用它們的后果通實(shí)比不使用它們更為困難和復雜。因此，它通常只是有益于純 C++ 項目。如果您想使用智能指針，那么您實(shí)在應該去閱讀 Alexandrescu 撰寫(xiě)的 Modern C++ Design 一書(shū)中的“Smart Pointers”那一章。 內存池 內存池是另一種半自動(dòng)內存管理方法。內存池幫助某些程序進(jìn)行自動(dòng)內存管理，這些程序會(huì )經(jīng)歷一些特定的階段，而且每個(gè)階段中都有分配給進(jìn)程的特定階段的內存。例如，很多網(wǎng)絡(luò )服務(wù)器進(jìn)程都會(huì )分配很多針對每個(gè)連接的內存 —— 內存的最大生存期限為當前連接的存在期。Apache 使用了池式內存（pooled memory），將其連接拆分為各個(gè)階段，每個(gè)階段都有自己的內存池。在結束每個(gè)階段時(shí)，會(huì )一次釋放所有內存。 在池式內存管理中，每次內存分配都會(huì )指定內存池，從中分配內存。每個(gè)內存池都有不同的生存期限。在 Apache 中，有一個(gè)持續時(shí)間為服務(wù)器存在期的內存池，還有一個(gè)持續時(shí)間為連接的存在期的內存池，以及一個(gè)持續時(shí)間為請求的存在期的池，另外還有其他一些內存池。因此，如果我的一系列函數不會(huì )生成比連接持續時(shí)間更長(cháng)的數據，那么我就可以完全從連接池中分配內存，并知道在連接結束時(shí)，這些內存會(huì )被自動(dòng)釋放。另外，有一些實(shí)現允許注冊 清除函數（cleanup functions），在清除內存池之前，恰好可以調用它，來(lái)完成在內存被清理前需要完成的其他所有任務(wù)（類(lèi)似于面向對象中的析構函數）。 要在自己的程序中使用池，您既可以使用 GNU libc 的 obstack 實(shí)現，也可以使用 Apache 的 Apache Portable Runtime。GNU obstack 的好處在于，基于 GNU 的 Linux 發(fā)行版本中默認會(huì )包括它們。Apache Portable Runtime 的好處在于它有很多其他工具，可以處理編寫(xiě)多平臺服務(wù)器軟件所有方面的事情。要深入了解 GNU obstack 和 Apache 的池式內存實(shí)現，請參閱 參考資料部分中指向這些實(shí)現的文檔的鏈接。 下面的假想代碼列表展示了如何使用 obstack：
清單 11. obstack 的示例代碼
#include <obstack.h> #include <stdlib.h> /* Example code listing for using obstacks */ /* Used for obstack macros (xmalloc is a malloc function that exits if memory is exhausted */ #define obstack_chunk_alloc xmalloc #define obstack_chunk_free free /* Pools */ /* Only permanent allocations should go in this pool */ struct obstack *global_pool; /* This pool is for per-connection data */ struct obstack *connection_pool; /* This pool is for per-request data */ struct obstack *request_pool; void allocation_failed() { exit(1); } int main() { /* Initialize Pools */ global_pool = (struct obstack *) xmalloc (sizeof (struct obstack)); obstack_init(global_pool); connection_pool = (struct obstack *) xmalloc (sizeof (struct obstack)); obstack_init(connection_pool); request_pool = (struct obstack *) xmalloc (sizeof (struct obstack)); obstack_init(request_pool); /* Set the error handling function */ obstack_alloc_failed_handler = &allocation_failed; /* Server main loop */ while(1) { wait_for_connection(); /* We are in a connection */ while(more_requests_available()) { /* Handle request */ handle_request(); /* Free all of the memory allocated * in the request pool */ obstack_free(request_pool, NULL); } /* We‘re finished with the connection, time * to free that pool */ obstack_free(connection_pool, NULL); } } int handle_request() { /* Be sure that all object allocations are allocated * from the request pool */ int bytes_i_need = 400; void *data1 = obstack_alloc(request_pool, bytes_i_need); /* Do stuff to process the request */ /* return */ return 0; }
|
基本上，在操作的每一個(gè)主要階段結束之后，這個(gè)階段的 obstack 會(huì )被釋放。不過(guò)，要注意的是，如果一個(gè)過(guò)程需要分配持續時(shí)間比當前階段更長(cháng)的內存，那么它也可以使用更長(cháng)期限的 obstack，比如連接或者全局內存。傳遞給 obstack_free() 的 NULL 指出它應該釋放 obstack 的全部?jì)热??？梢杂闷渌闹?，但是它們通常不怎么?shí)用。 使用池式內存分配的益處如下所示： - 應用程序可以簡(jiǎn)單地管理內存。
- 內存分配和回收更快，因為每次都是在一個(gè)池中完成的。分配可以在 O(1) 時(shí)間內完成，釋放內存池所需時(shí)間也差不多（實(shí)際上是 O(n) 時(shí)間，不過(guò)在大部分情況下會(huì )除以一個(gè)大的因數，使其變成 O(1)）。
- 可以預先分配錯誤處理池（Error-handling pools），以便程序在常規內存被耗盡時(shí)仍可以恢復。
- 有非常易于使用的標準實(shí)現。
池式內存的缺點(diǎn)是： - 內存池只適用于操作可以分階段的程序。
- 內存池通常不能與第三方庫很好地合作。
- 如果程序的結構發(fā)生變化，則不得不修改內存池，這可能會(huì )導致內存管理系統的重新設計。
- 您必須記住需要從哪個(gè)池進(jìn)行分配。另外，如果在這里出錯，就很難捕獲該內存池。
垃圾收集 垃圾收集（Garbage collection）是全自動(dòng)地檢測并移除不再使用的數據對象。垃圾收集器通常會(huì )在當可用內存減少到少于一個(gè)具體的閾值時(shí)運行。通常，它們以程序所知的可用的一組“基本”數據 —— 棧數據、全局變量、寄存器 —— 作為出發(fā)點(diǎn)。然后它們嘗試去追蹤通過(guò)這些數據連接到每一塊數據。收集器找到的都是有用的數據；它沒(méi)有找到的就是垃圾，可以被銷(xiāo)毀并重新使用這些無(wú)用的數據。為了有效地管理內存，很多類(lèi)型的垃圾收集器都需要知道數據結構內部指針的規劃，所以，為了正確運行垃圾收集器，它們必須是語(yǔ)言本身的一部分。 收集器的類(lèi)型 - 復制（copying）： 這些收集器將內存存儲器分為兩部分，只允許數據駐留在其中一部分上。它們定時(shí)地從“基本”的元素開(kāi)始將數據從一部分復制到另一部分。內存新近被占用的部分現在成為活動(dòng)的，另一部分上的所有內容都認為是垃圾。另外，當進(jìn)行這項復制操作時(shí)，所有指針都必須被更新為指向每個(gè)內存條目的新位置。因此，為使用這種垃圾收集方法，垃圾收集器必須與編程語(yǔ)言集成在一起。
- 標記并清理（Mark and sweep）：每一塊數據都被加上一個(gè)標簽。不定期的，所有標簽都被設置為 0，收集器從“基本”的元素開(kāi)始遍歷數據。當它遇到內存時(shí)，就將標簽標記為 1。最后沒(méi)有被標記為 1 的所有內容都認為是垃圾，以后分配內存時(shí)會(huì )重新使用它們。
- 增量的（Incremental）：增量垃圾收集器不需要遍歷全部數據對象。因為在收集期間的突然等待，也因為與訪(fǎng)問(wèn)所有當前數據相關(guān)的緩存問(wèn)題（所有內容都不得不被頁(yè)入（page-in）），遍歷所有內存會(huì )引發(fā)問(wèn)題。增量收集器避免了這些問(wèn)題。
- 保守的（Conservative）：保守的垃圾收集器在管理內存時(shí)不需要知道與數據結構相關(guān)的任何信息。它們只查看所有數據類(lèi)型，并假定它們 可以全部都是指針。所以，如果一個(gè)字節序列可以是一個(gè)指向一塊被分配的內存的指針，那么收集器就將其標記為正在被引用。有時(shí)沒(méi)有被引用的內存會(huì )被收集，這樣會(huì )引發(fā)問(wèn)題，例如，如果一個(gè)整數域中包含一個(gè)值，該值是已分配內存的地址。不過(guò)，這種情況極少發(fā)生，而且它只會(huì )浪費少量?jì)却?。保守的收集器的?yōu)勢是，它們可以與任何編程語(yǔ)言相集成。
Hans Boehm 的保守垃圾收集器是可用的最流行的垃圾收集器之一，因為它是免費的，而且既是保守的又是增量的，可以使用 --enable-redirect-malloc 選項來(lái)構建它，并且可以將它用作系統分配程序的簡(jiǎn)易替代者（drop-in replacement）（用 malloc/ free 代替它自己的 API）。實(shí)際上，如果這樣做，您就可以使用與我們在示例分配程序中所使用的相同的 LD_PRELOAD 技巧，在系統上的幾乎任何程序中啟用垃圾收集。如果您懷疑某個(gè)程序正在泄漏內存，那么您可以使用這個(gè)垃圾收集器來(lái)控制進(jìn)程。在早期，當 Mozilla 嚴重地泄漏內存時(shí)，很多人在其中使用了這項技術(shù)。這種垃圾收集器既可以在 Windows? 下運行，也可以在 UNIX 下運行。 垃圾收集的一些優(yōu)點(diǎn)： - 您永遠不必擔心內存的雙重釋放或者對象的生命周期。
- 使用某些收集器，您可以使用與常規分配相同的 API。
其缺點(diǎn)包括： - 使用大部分收集器時(shí)，您都無(wú)法干涉何時(shí)釋放內存。
- 在多數情況下，垃圾收集比其他形式的內存管理更慢。
- 垃圾收集錯誤引發(fā)的缺陷難于調試。
- 如果您忘記將不再使用的指針設置為 null，那么仍然會(huì )有內存泄漏。
結束語(yǔ) 一切都需要折衷：性能、易用、易于實(shí)現、支持線(xiàn)程的能力等，這里只列出了其中的一些。為了滿(mǎn)足項目的要求，有很多內存管理模式可以供您使用。每種模式都有大量的實(shí)現，各有其優(yōu)缺點(diǎn)。對很多項目來(lái)說(shuō)，使用編程環(huán)境默認的技術(shù)就足夠了，不過(guò)，當您的項目有特殊的需要時(shí)，了解可用的選擇將會(huì )有幫助。下表對比了本文中涉及的內存管理策略。 表 1. 內存分配策略的對比 | 策略 | 分配速度 | 回收速度 | 局部緩存 | 易用性 | 通用性 | 實(shí)時(shí)可用 | SMP 線(xiàn)程友好 | | 定制分配程序 | 取決于實(shí)現 | 取決于實(shí)現 | 取決于實(shí)現 | 很難 | 無(wú) | 取決于實(shí)現 | 取決于實(shí)現 | | 簡(jiǎn)單分配程序 | 內存使用少時(shí)較快 | 很快 | 差 | 容易 | 高 | 否 | 否 | GNU malloc | 中 | 快 | 中 | 容易 | 高 | 否 | 中 | | Hoard | 中 | 中 | 中 | 容易 | 高 | 否 | 是 | | 引用計數 | N/A | N/A | 非常好 | 中 | 中 | 是（取決于 malloc 實(shí)現） | 取決于實(shí)現 | | 池 | 中 | 非?？? | 極好 | 中 | 中 | 是（取決于 malloc 實(shí)現） | 取決于實(shí)現 | | 垃圾收集 | 中（進(jìn)行收集時(shí)慢） | 中 | 差 | 中 | 中 | 否 | 幾乎不 | | 增量垃圾收集 | 中 | 中 | 中 | 中 | 中 | 否 | 幾乎不 | | 增量保守垃圾收集 | 中 | 中 | 中 | 容易 | 高 | 否 | 幾乎不 |
參考資料 - 您可以參閱本文在 developerWorks 全球站點(diǎn)上的 英文原文。
Web 上的文檔 基本的分配程序 池式分配程序 智能指針和定制分配程序 垃圾收集器 關(guān)于現代操作系統中的虛擬內存的文章 關(guān)于 malloc 的文章 關(guān)于定制分配程序的文章 關(guān)于垃圾收集的文章 Web 上的通用參考資料 書(shū)籍 來(lái)自 developerWorks
| 
