- 論壇徽章:
- 3
|
內(nèi)存管理內(nèi)幕
動態(tài)分配的選擇、折衷和實現(xiàn)
文檔選項
打印本頁
將此頁作為電子郵件發(fā)送
級別： 初級
Jonathan Bartlett (johnnyb@eskimo.com), 技術(shù)總監(jiān), New Media Worx
2004 年 11 月 29 日
本文將對 Linux™ 程序員可以使用的內(nèi)存管理技術(shù)進行概述，雖然關(guān)注的重點是 C 語言，但同樣也適用于其他語言。文中將為您提供如何管理內(nèi)存的細節(jié)，然后將進一步展示如何手工管理內(nèi)存，如何使用引用計數(shù)或者內(nèi)存池來半手工地管理內(nèi)存，以及如何使用垃圾收集自動管理內(nèi)存。
為什么必須管理內(nèi)存
內(nèi)存管理是計算機編程最為基本的領(lǐng)域之一。在很多腳本語言中，您不必擔(dān)心內(nèi)存是如何管理的，這并不能使得內(nèi)存管理的重要性有一點點降低。對實際編程來說，理解您的內(nèi)存管理器的能力與局限性至關(guān)重要。在大部分系統(tǒng)語言中，比如 C 和 C++，您必須進行內(nèi)存管理。本文將介紹手工的、半手工的以及自動的內(nèi)存管理實踐的基本概念。
追溯到在 Apple II 上進行匯編語言編程的時代，那時內(nèi)存管理還不是個大問題。您實際上在運行整個系統(tǒng)。系統(tǒng)有多少內(nèi)存，您就有多少內(nèi)存。您甚至不必費心思去弄明白它有多少內(nèi)存，因為每一臺機器的內(nèi)存數(shù)量都相同。所以，如果內(nèi)存需要非常固定，那么您只需要選擇一個內(nèi)存范圍并使用它即可。
不過，即使是在這樣一個簡單的計算機中，您也會有問題，尤其是當(dāng)您不知道程序的每個部分將需要多少內(nèi)存時。如果您的空間有限，而內(nèi)存需求是變化的，那么您需要一些方法來滿足這些需求：
確定您是否有足夠的內(nèi)存來處理數(shù)據(jù)。
從可用的內(nèi)存中獲取一部分內(nèi)存。
向可用內(nèi)存池（pool）中返回部分內(nèi)存，以使其可以由程序的其他部分或者其他程序使用。
實現(xiàn)這些需求的程序庫稱為 分配程序（allocators），因為它們負責(zé)分配和回收內(nèi)存。程序的動態(tài)性越強，內(nèi)存管理就越重要，您的內(nèi)存分配程序的選擇也就更重要。讓我們來了解可用于內(nèi)存管理的不同方法，它們的好處與不足，以及它們最適用的情形。
回頁首
C 風(fēng)格的內(nèi)存分配程序
C 編程語言提供了兩個函數(shù)來滿足我們的三個需求：
malloc：該函數(shù)分配給定的字節(jié)數(shù)，并返回一個指向它們的指針。如果沒有足夠的可用內(nèi)存，那么它返回一個空指針。
free：該函數(shù)獲得指向由 malloc 分配的內(nèi)存片段的指針，并將其釋放，以便以后的程序或操作系統(tǒng)使用（實際上，一些 malloc 實現(xiàn)只能將內(nèi)存歸還給程序，而無法將內(nèi)存歸還給操作系統(tǒng)）。
物理內(nèi)存和虛擬內(nèi)存
要理解內(nèi)存在程序中是如何分配的，首先需要理解如何將內(nèi)存從操作系統(tǒng)分配給程序。計算機上的每一個進程都認為自己可以訪問所有的物理內(nèi)存。顯然，由于同時在運行多個程序，所以每個進程不可能擁有全部內(nèi)存。實際上，這些進程使用的是 虛擬內(nèi)存。
只是作為一個例子，讓我們假定您的程序正在訪問地址為 629 的內(nèi)存。不過，虛擬內(nèi)存系統(tǒng)不需要將其存儲在位置為 629 的 RAM 中。實際上，它甚至可以不在 RAM 中 —— 如果物理 RAM 已經(jīng)滿了，它甚至可能已經(jīng)被轉(zhuǎn)移到硬盤上！由于這類地址不必反映內(nèi)存所在的物理位置，所以它們被稱為虛擬內(nèi)存。操作系統(tǒng)維持著一個虛擬地址到物理地址的轉(zhuǎn)換的表，以便計算機硬件可以正確地響應(yīng)地址請求。并且，如果地址在硬盤上而不是在 RAM 中，那么操作系統(tǒng)將暫時停止您的進程，將其他內(nèi)存轉(zhuǎn)存到硬盤中，從硬盤上加載被請求的內(nèi)存，然后再重新啟動您的進程。這樣，每個進程都獲得了自己可以使用的地址空間，可以訪問比您物理上安裝的內(nèi)存更多的內(nèi)存。
在 32-位 x86 系統(tǒng)上，每一個進程可以訪問 4 GB 內(nèi)存�，F(xiàn)在，大部分人的系統(tǒng)上并沒有 4 GB 內(nèi)存，即使您將 swap 也算上， 每個進程所使用的內(nèi)存也肯定少于 4 GB。因此，當(dāng)加載一個進程時，它會得到一個取決于某個稱為 系統(tǒng)中斷點（system break）的特定地址的初始內(nèi)存分配。該地址之后是未被映射的內(nèi)存 —— 用于在 RAM 或者硬盤中沒有分配相應(yīng)物理位置的內(nèi)存。因此，如果一個進程運行超出了它初始分配的內(nèi)存，那么它必須請求操作系統(tǒng)“映射進來（map in）”更多的內(nèi)存。（映射是一個表示一一對應(yīng)關(guān)系的數(shù)學(xué)術(shù)語 —— 當(dāng)內(nèi)存的虛擬地址有一個對應(yīng)的物理地址來存儲內(nèi)存內(nèi)容時，該內(nèi)存將被映射。）
基于 UNIX 的系統(tǒng)有兩個可映射到附加內(nèi)存中的基本系統(tǒng)調(diào)用：
brk： brk() 是一個非常簡單的系統(tǒng)調(diào)用。還記得系統(tǒng)中斷點嗎？該位置是進程映射的內(nèi)存邊界。 brk() 只是簡單地將這個位置向前或者向后移動，就可以向進程添加內(nèi)存或者從進程取走內(nèi)存。
mmap： mmap()，或者說是“內(nèi)存映像”，類似于 brk()，但是更為靈活。首先，它可以映射任何位置的內(nèi)存，而不單單只局限于進程。其次，它不僅可以將虛擬地址映射到物理的 RAM 或者 swap，它還可以將它們映射到文件和文件位置，這樣，讀寫內(nèi)存將對文件中的數(shù)據(jù)進行讀寫。不過，在這里，我們只關(guān)心 mmap 向進程添加被映射的內(nèi)存的能力。 munmap() 所做的事情與 mmap() 相反。
如您所見， brk() 或者 mmap() 都可以用來向我們的進程添加額外的虛擬內(nèi)存。在我們的例子中將使用 brk()，因為它更簡單，更通用。
實現(xiàn)一個簡單的分配程序
如果您曾經(jīng)編寫過很多 C 程序，那么您可能曾多次使用過 malloc() 和 free()。不過，您可能沒有用一些時間去思考它們在您的操作系統(tǒng)中是如何實現(xiàn)的。本節(jié)將向您展示 malloc 和 free 的一個最簡化實現(xiàn)的代碼，來幫助說明管理內(nèi)存時都涉及到了哪些事情。
要試著運行這些示例，需要先 復(fù)制本代碼清單，并將其粘貼到一個名為 malloc.c 的文件中。接下來，我將一次一個部分地對該清單進行解釋。
在大部分操作系統(tǒng)中，內(nèi)存分配由以下兩個簡單的函數(shù)來處理：
void *malloc(long numbytes)：該函數(shù)負責(zé)分配 numbytes 大小的內(nèi)存，并返回指向第一個字節(jié)的指針。
void free(void *firstbyte)：如果給定一個由先前的 malloc 返回的指針，那么該函數(shù)會將分配的空間歸還給進程的“空閑空間”。
malloc_init 將是初始化內(nèi)存分配程序的函數(shù)。它要完成以下三件事：將分配程序標(biāo)識為已經(jīng)初始化，找到系統(tǒng)中最后一個有效內(nèi)存地址，然后建立起指向我們管理的內(nèi)存的指針。這三個變量都是全局變量：
清單 1. 我們的簡單分配程序的全局變量
int has_initialized = 0;
void *managed_memory_start;
void *last_valid_address;
如前所述，被映射的內(nèi)存的邊界（最后一個有效地址）常被稱為系統(tǒng)中斷點或者 當(dāng)前中斷點。在很多 UNIX® 系統(tǒng)中，為了指出當(dāng)前系統(tǒng)中斷點，必須使用 sbrk(0) 函數(shù)。 sbrk 根據(jù)參數(shù)中給出的字節(jié)數(shù)移動當(dāng)前系統(tǒng)中斷點，然后返回新的系統(tǒng)中斷點。使用參數(shù) 0 只是返回當(dāng)前中斷點。這里是我們的 malloc 初始化代碼，它將找到當(dāng)前中斷點并初始化我們的變量：
清單 2. 分配程序初始化函數(shù)
/* 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;
}
現(xiàn)在，為了完全地管理內(nèi)存，我們需要能夠追蹤要分配和回收哪些內(nèi)存。在對內(nèi)存塊進行了 free 調(diào)用之后，我們需要做的是諸如將它們標(biāo)記為未被使用的等事情，并且，在調(diào)用 malloc 時，我們要能夠定位未被使用的內(nèi)存塊。因此， malloc 返回的每塊內(nèi)存的起始處首先要有這個結(jié)構(gòu)：
清單 3. 內(nèi)存控制塊結(jié)構(gòu)定義
struct mem_control_block {
int is_available;
int size;
};
現(xiàn)在，您可能會認為當(dāng)程序調(diào)用 malloc 時這會引發(fā)問題 —— 它們?nèi)绾沃肋@個結(jié)構(gòu)？答案是它們不必知道；在返回指針之前，我們會將其移動到這個結(jié)構(gòu)之后，把它隱藏起來。這使得返回的指針指向沒有用于任何其他用途的內(nèi)存。那樣，從調(diào)用程序的角度來看，它們所得到的全部是空閑的、開放的內(nèi)存。然后，當(dāng)通過 free() 將該指針傳遞回來時，我們只需要倒退幾個內(nèi)存字節(jié)就可以再次找到這個結(jié)構(gòu)。
在討論分配內(nèi)存之前，我們將先討論釋放，因為它更簡單。為了釋放內(nèi)存，我們必須要做的惟一一件事情就是，獲得我們給出的指針，回退 sizeof(struct mem_control_block) 個字節(jié)，并將其標(biāo)記為可用的。這里是對應(yīng)的代碼：
清單 4. 解除分配函數(shù)
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;
}
如您所見，在這個分配程序中，內(nèi)存的釋放使用了一個非常簡單的機制，在固定時間內(nèi)完成內(nèi)存釋放。分配內(nèi)存稍微困難一些。以下是該算法的略述：
清單 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
我們主要使用連接的指針遍歷內(nèi)存來尋找開放的內(nè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;
}
這就是我們的內(nèi)存管理器�，F(xiàn)在，我們只需要構(gòu)建它，并在程序中使用它即可。
運行下面的命令來構(gòu)建 malloc 兼容的分配程序（實際上，我們忽略了 realloc() 等一些函數(shù)，不過， malloc() 和 free() 才是最主要的函數(shù)）：
清單 7. 編譯分配程序
gcc -shared -fpic malloc.c -o malloc.so
該程序?qū)⑸梢粋�名為 malloc.so 的文件，它是一個包含有我們的代碼的共享庫。
在 UNIX 系統(tǒng)中，現(xiàn)在您可以用您的分配程序來取代系統(tǒng)的 malloc()，做法如下：
清單 8. 替換您的標(biāo)準(zhǔn)的 malloc
LD_PRELOAD=/path/to/malloc.so
export LD_PRELOAD
LD_PRELOAD 環(huán)境變量使動態(tài)鏈接器在加載任何可執(zhí)行程序之前，先加載給定的共享庫的符號。它還為特定庫中的符號賦予優(yōu)先權(quán)。因此，從現(xiàn)在起，該會話中的任何應(yīng)用程序都將使用我們的 malloc()，而不是只有系統(tǒng)的應(yīng)用程序能夠使用。有一些應(yīng)用程序不使用 malloc()，不過它們是例外。其他使用 realloc() 等其他內(nèi)存管理函數(shù)的應(yīng)用程序，或者錯誤地假定 malloc() 內(nèi)部行為的那些應(yīng)用程序，很可能會崩潰。ash shell 似乎可以使用我們的新 malloc() 很好地工作。
如果您想確保 malloc() 正在被使用，那么您應(yīng)該通過向函數(shù)的入口點添加 write() 調(diào)用來進行測試。
我們的內(nèi)存管理器在很多方面都還存在欠缺，但它可以有效地展示內(nèi)存管理需要做什么事情。它的某些缺點包括：
由于它對系統(tǒng)中斷點（一個全局變量）進行操作，所以它不能與其他分配程序或者 mmap 一起使用。
當(dāng)分配內(nèi)存時，在最壞的情形下，它將不得不遍歷 全部進程內(nèi)存；其中可能包括位于硬盤上的很多內(nèi)存，這意味著操作系統(tǒng)將不得不花時間去向硬盤移入數(shù)據(jù)和從硬盤中移出數(shù)據(jù)。
沒有很好的內(nèi)存不足處理方案（ malloc 只假定內(nèi)存分配是成功的）。
它沒有實現(xiàn)很多其他的內(nèi)存函數(shù)，比如 realloc()。
由于 sbrk() 可能會交回比我們請求的更多的內(nèi)存，所以在堆（heap）的末端會遺漏一些內(nèi)存。
雖然 is_available 標(biāo)記只包含一位信息，但它要使用完整的 4-字節(jié) 的字。
分配程序不是線程安全的。
分配程序不能將空閑空間拼合為更大的內(nèi)存塊。
分配程序的過于簡單的匹配算法會導(dǎo)致產(chǎn)生很多潛在的內(nèi)存碎片。
我確信還有很多其他問題。這就是為什么它只是一個例子!
其他 malloc 實現(xiàn)
malloc() 的實現(xiàn)有很多，這些實現(xiàn)各有優(yōu)點與缺點。在設(shè)計一個分配程序時，要面臨許多需要折衷的選擇，其中包括：
分配的速度。
回收的速度。
有線程的環(huán)境的行為。
內(nèi)存將要被用光時的行為。
局部緩存。
簿記（Bookkeeping）內(nèi)存開銷。
虛擬內(nèi)存環(huán)境中的行為。
小的或者大的對象。
實時保證。
每一個實現(xiàn)都有其自身的優(yōu)缺點集合。在我們的簡單的分配程序中，分配非常慢，而回收非�？�。另外，由于它在使用虛擬內(nèi)存系統(tǒng)方面較差，所以它最適于處理大的對象。
還有其他許多分配程序可以使用。其中包括：
Doug Lea Malloc：Doug Lea Malloc 實際上是完整的一組分配程序，其中包括 Doug Lea 的原始分配程序，GNU libc 分配程序和 ptmalloc。 Doug Lea 的分配程序有著與我們的版本非常類似的基本結(jié)構(gòu)，但是它加入了索引，這使得搜索速度更快，并且可以將多個沒有被使用的塊組合為一個大的塊。它還支持緩存，以便更快地再次使用最近釋放的內(nèi)存。 ptmalloc 是 Doug Lea Malloc 的一個擴展版本，支持多線程。在本文后面的 參考資料部分中，有一篇描述 Doug Lea 的 Malloc 實現(xiàn)的文章。
BSD Malloc：BSD Malloc 是隨 4.2 BSD 發(fā)行的實現(xiàn)，包含在 FreeBSD 之中，這個分配程序可以從預(yù)先確實大小的對象構(gòu)成的池中分配對象。它有一些用于對象大小的 size 類，這些對象的大小為 2 的若干次冪減去某一常數(shù)。所以，如果您請求給定大小的一個對象，它就簡單地分配一個與之匹配的 size 類。這樣就提供了一個快速的實現(xiàn)，但是可能會浪費內(nèi)存。在 參考資料部分中，有一篇描述該實現(xiàn)的文章。
Hoard：編寫 Hoard 的目標(biāo)是使內(nèi)存分配在多線程環(huán)境中進行得非�？�。因此，它的構(gòu)造以鎖的使用為中心，從而使所有進程不必等待分配內(nèi)存。它可以顯著地加快那些進行很多分配和回收的多線程進程的速度。在 參考資料部分中，有一篇描述該實現(xiàn)的文章。
眾多可用的分配程序中最有名的就是上述這些分配程序。如果您的程序有特別的分配需求，那么您可能更愿意編寫一個定制的能匹配您的程序內(nèi)存分配方式的分配程序。不過，如果不熟悉分配程序的設(shè)計，那么定制分配程序通常會帶來比它們解決的問題更多的問題。要獲得關(guān)于該主題的適當(dāng)?shù)慕榻B，請參閱 Donald Knuth 撰寫的 The Art of Computer Programming Volume 1: Fundamental Algorithms 中的第 2.5 節(jié)“Dynamic Storage Allocation”（請參閱 參考資料中的鏈接）。它有點過時，因為它沒有考慮虛擬內(nèi)存環(huán)境，不過大部分算法都是基于前面給出的函數(shù)。
在 C++ 中，通過重載 operator new()，您可以以每個類或者每個模板為單位實現(xiàn)自己的分配程序。在 Andrei Alexandrescu 撰寫的 Modern C++ Design 的第 4 章（“Small Object Allocation”）中，描述了一個小對象分配程序（請參閱 參考資料中的鏈接）。
基于 malloc() 的內(nèi)存管理的缺點
不只是我們的內(nèi)存管理器有缺點，基于 malloc() 的內(nèi)存管理器仍然也有很多缺點，不管您使用的是哪個分配程序。對于那些需要保持長期存儲的程序使用 malloc() 來管理內(nèi)存可能會非常令人失望。如果您有大量的不固定的內(nèi)存引用，經(jīng)常難以知道它們何時被釋放。生存期局限于當(dāng)前函數(shù)的內(nèi)存非常容易管理，但是對于生存期超出該范圍的內(nèi)存來說，管理內(nèi)存則困難得多。而且，關(guān)于內(nèi)存管理是由進行調(diào)用的程序還是由被調(diào)用的函數(shù)來負責(zé)這一問題，很多 API 都不是很明確。
因為管理內(nèi)存的問題，很多程序傾向于使用它們自己的內(nèi)存管理規(guī)則。C++ 的異常處理使得這項任務(wù)更成問題。有時好像致力于管理內(nèi)存分配和清理的代碼比實際完成計算任務(wù)的代碼還要多！因此，我們將研究內(nèi)存管理的其他選擇。
回頁首
半自動內(nèi)存管理策略
引用計數(shù)
引用計數(shù)是一種 半自動（semi-automated）的內(nèi)存管理技術(shù)，這表示它需要一些編程支持，但是它不需要您確切知道某一對象何時不再被使用。引用計數(shù)機制為您完成內(nèi)存管理任務(wù)。
在引用計數(shù)中，所有共享的數(shù)據(jù)結(jié)構(gòu)都有一個域來包含當(dāng)前活動“引用”結(jié)構(gòu)的次數(shù)。當(dāng)向一個程序傳遞一個指向某個數(shù)據(jù)結(jié)構(gòu)指針時，該程序會將引用計數(shù)增加 1。實質(zhì)上，您是在告訴數(shù)據(jù)結(jié)構(gòu)，它正在被存儲在多少個位置上。然后，當(dāng)您的進程完成對它的使用后，該程序就會將引用計數(shù)減少 1。結(jié)束這個動作之后，它還會檢查計數(shù)是否已經(jīng)減到零。如果是，那么它將釋放內(nèi)存。
這樣做的好處是，您不必追蹤程序中某個給定的數(shù)據(jù)結(jié)構(gòu)可能會遵循的每一條路徑。每次對其局部的引用，都將導(dǎo)致計數(shù)的適當(dāng)增加或減少。這樣可以防止在使用數(shù)據(jù)結(jié)構(gòu)時釋放該結(jié)構(gòu)。不過，當(dāng)您使用某個采用引用計數(shù)的數(shù)據(jù)結(jié)構(gòu)時，您必須記得運行引用計數(shù)函數(shù)。另外，內(nèi)置函數(shù)和第三方的庫不會知道或者可以使用您的引用計數(shù)機制。引用計數(shù)也難以處理發(fā)生循環(huán)引用的數(shù)據(jù)結(jié)構(gòu)。
要實現(xiàn)引用計數(shù)，您只需要兩個函數(shù) —— 一個增加引用計數(shù)，一個減少引用計數(shù)并當(dāng)計數(shù)減少到零時釋放內(nèi)存。
一個示例引用計數(shù)函數(shù)集可能看起來如下所示：
清單 9. 基本的引用計數(shù)函數(shù)
/* 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 可能會更復(fù)雜，這取決于您想要做的事情。例如，您可能想要為多線程程序增加鎖，那么您可能想擴展 refcountedstruct，使它同樣包含一個指向某個在釋放內(nèi)存之前要調(diào)用的函數(shù)的指針（類似于面向?qū)ο笳Z言中的析構(gòu)函數(shù) —— 如果您的結(jié)構(gòu)中包含這些指針，那么這是 必需的）。
當(dāng)使用 REF 和 UNREF 時，您需要遵守這些指針的分配規(guī)則：
UNREF 分配前左端指針（left-hand-side pointer）指向的值。
REF 分配后左端指針（left-hand-side pointer）指向的值。
在傳遞使用引用計數(shù)的結(jié)構(gòu)的函數(shù)中，函數(shù)需要遵循以下這些規(guī)則：
在函數(shù)的起始處 REF 每一個指針。
在函數(shù)的結(jié)束處 UNREF 第一個指針。
以下是一個使用引用計數(shù)的生動的代碼示例：
清單 10. 使用引用計數(shù)的示例
/* 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 */
}
由于引用計數(shù)是如此簡單，大部分程序員都自已去實現(xiàn)它，而不是使用庫。不過，它們依賴于 malloc 和 free 等低層的分配程序來實際地分配和釋放它們的內(nèi)存。
在 Perl 等高級語言中，進行內(nèi)存管理時使用引用計數(shù)非常廣泛。在這些語言中，引用計數(shù)由語言自動地處理，所以您根本不必擔(dān)心它，除非要編寫擴展模塊。由于所有內(nèi)容都必須進行引用計數(shù)，所以這會對速度產(chǎn)生一些影響，但它極大地提高了編程的安全性和方便性。以下是引用計數(shù)的益處：
實現(xiàn)簡單。
易于使用。
由于引用是數(shù)據(jù)結(jié)構(gòu)的一部分，所以它有一個好的緩存位置。
不過，它也有其不足之處：
要求您永遠不要忘記調(diào)用引用計數(shù)函數(shù)。
無法釋放作為循環(huán)數(shù)據(jù)結(jié)構(gòu)的一部分的結(jié)構(gòu)。
減緩幾乎每一個指針的分配。
盡管所使用的對象采用了引用計數(shù)，但是當(dāng)使用異常處理（比如 try 或 setjmp()/ longjmp()）時，您必須采取其他方法。
需要額外的內(nèi)存來處理引用。
引用計數(shù)占用了結(jié)構(gòu)中的第一個位置，在大部分機器中最快可以訪問到的就是這個位置。
在多線程環(huán)境中更慢也更難以使用。
C++ 可以通過使用 智能指針（smart pointers）來容忍程序員所犯的一些錯誤，智能指針可以為您處理引用計數(shù)等指針處理細節(jié)。不過，如果不得不使用任何先前的不能處理智能指針的代碼（比如對 C 庫的聯(lián)接），實際上，使用它們的后果通實比不使用它們更為困難和復(fù)雜。因此，它通常只是有益于純 C++ 項目。如果您想使用智能指針，那么您實在應(yīng)該去閱讀 Alexandrescu 撰寫的 Modern C++ Design 一書中的“Smart Pointers”那一章。
內(nèi)存池
內(nèi)存池是另一種半自動內(nèi)存管理方法。內(nèi)存池幫助某些程序進行自動內(nèi)存管理，這些程序會經(jīng)歷一些特定的階段，而且每個階段中都有分配給進程的特定階段的內(nèi)存。例如，很多網(wǎng)絡(luò)服務(wù)器進程都會分配很多針對每個連接的內(nèi)存 —— 內(nèi)存的最大生存期限為當(dāng)前連接的存在期。Apache 使用了池式內(nèi)存（pooled memory），將其連接拆分為各個階段，每個階段都有自己的內(nèi)存池。在結(jié)束每個階段時，會一次釋放所有內(nèi)存。
在池式內(nèi)存管理中，每次內(nèi)存分配都會指定內(nèi)存池，從中分配內(nèi)存。每個內(nèi)存池都有不同的生存期限。在 Apache 中，有一個持續(xù)時間為服務(wù)器存在期的內(nèi)存池，還有一個持續(xù)時間為連接的存在期的內(nèi)存池，以及一個持續(xù)時間為請求的存在期的池，另外還有其他一些內(nèi)存池。因此，如果我的一系列函數(shù)不會生成比連接持續(xù)時間更長的數(shù)據(jù)，那么我就可以完全從連接池中分配內(nèi)存，并知道在連接結(jié)束時，這些內(nèi)存會被自動釋放。另外，有一些實現(xiàn)允許注冊 清除函數(shù)（cleanup functions），在清除內(nèi)存池之前，恰好可以調(diào)用它，來完成在內(nèi)存被清理前需要完成的其他所有任務(wù)（類似于面向?qū)ο笾械奈鰳?gòu)函數(shù)）。
要在自己的程序中使用池，您既可以使用 GNU libc 的 obstack 實現(xiàn)，也可以使用 Apache 的 Apache Portable Runtime。GNU obstack 的好處在于，基于 GNU 的 Linux 發(fā)行版本中默認會包括它們。Apache Portable Runtime 的好處在于它有很多其他工具，可以處理編寫多平臺服務(wù)器軟件所有方面的事情。要深入了解 GNU obstack 和 Apache 的池式內(nèi)存實現(xiàn)，請參閱 參考資料部分中指向這些實現(xiàn)的文檔的鏈接。
下面的假想代碼列表展示了如何使用 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;
}
基本上，在操作的每一個主要階段結(jié)束之后，這個階段的 obstack 會被釋放。不過，要注意的是，如果一個過程需要分配持續(xù)時間比當(dāng)前階段更長的內(nèi)存，那么它也可以使用更長期限的 obstack，比如連接或者全局內(nèi)存。傳遞給 obstack_free() 的 NULL 指出它應(yīng)該釋放 obstack 的全部內(nèi)容�？梢杂闷渌闹�，但是它們通常不怎么實用。
使用池式內(nèi)存分配的益處如下所示：
應(yīng)用程序可以簡單地管理內(nèi)存。
內(nèi)存分配和回收更快，因為每次都是在一個池中完成的。分配可以在 O(1) 時間內(nèi)完成，釋放內(nèi)存池所需時間也差不多（實際上是 O(n) 時間，不過在大部分情況下會除以一個大的因數(shù)，使其變成 O(1)）。
可以預(yù)先分配錯誤處理池（Error-handling pools），以便程序在常規(guī)內(nèi)存被耗盡時仍可以恢復(fù)。
有非常易于使用的標(biāo)準(zhǔn)實現(xiàn)。
池式內(nèi)存的缺點是：
內(nèi)存池只適用于操作可以分階段的程序。
內(nèi)存池通常不能與第三方庫很好地合作。
如果程序的結(jié)構(gòu)發(fā)生變化，則不得不修改內(nèi)存池，這可能會導(dǎo)致內(nèi)存管理系統(tǒng)的重新設(shè)計。
您必須記住需要從哪個池進行分配。另外，如果在這里出錯，就很難捕獲該內(nèi)存池。
回頁首
垃圾收集
垃圾收集（Garbage collection）是全自動地檢測并移除不再使用的數(shù)據(jù)對象。垃圾收集器通常會在當(dāng)可用內(nèi)存減少到少于一個具體的閾值時運行。通常，它們以程序所知的可用的一組“基本”數(shù)據(jù) —— 棧數(shù)據(jù)、全局變量、寄存器 —— 作為出發(fā)點。然后它們嘗試去追蹤通過這些數(shù)據(jù)連接到每一塊數(shù)據(jù)。收集器找到的都是有用的數(shù)據(jù)；它沒有找到的就是垃圾，可以被銷毀并重新使用這些無用的數(shù)據(jù)。為了有效地管理內(nèi)存，很多類型的垃圾收集器都需要知道數(shù)據(jù)結(jié)構(gòu)內(nèi)部指針的規(guī)劃，所以，為了正確運行垃圾收集器，它們必須是語言本身的一部分。
收集器的類型
復(fù)制（copying）： 這些收集器將內(nèi)存存儲器分為兩部分，只允許數(shù)據(jù)駐留在其中一部分上。它們定時地從“基本”的元素開始將數(shù)據(jù)從一部分復(fù)制到另一部分。內(nèi)存新近被占用的部分現(xiàn)在成為活動的，另一部分上的所有內(nèi)容都認為是垃圾。另外，當(dāng)進行這項復(fù)制操作時，所有指針都必須被更新為指向每個內(nèi)存條目的新位置。因此，為使用這種垃圾收集方法，垃圾收集器必須與編程語言集成在一起。
標(biāo)記并清理（Mark and sweep）：每一塊數(shù)據(jù)都被加上一個標(biāo)簽。不定期的，所有標(biāo)簽都被設(shè)置為 0，收集器從“基本”的元素開始遍歷數(shù)據(jù)。當(dāng)它遇到內(nèi)存時，就將標(biāo)簽標(biāo)記為 1。最后沒有被標(biāo)記為 1 的所有內(nèi)容都認為是垃圾，以后分配內(nèi)存時會重新使用它們。
增量的（Incremental）：增量垃圾收集器不需要遍歷全部數(shù)據(jù)對象。因為在收集期間的突然等待，也因為與訪問所有當(dāng)前數(shù)據(jù)相關(guān)的緩存問題（所有內(nèi)容都不得不被頁入（page-in）），遍歷所有內(nèi)存會引發(fā)問題。增量收集器避免了這些問題。
保守的（Conservative）：保守的垃圾收集器在管理內(nèi)存時不需要知道與數(shù)據(jù)結(jié)構(gòu)相關(guān)的任何信息。它們只查看所有數(shù)據(jù)類型，并假定它們 可以全部都是指針。所以，如果一個字節(jié)序列可以是一個指向一塊被分配的內(nèi)存的指針，那么收集器就將其標(biāo)記為正在被引用。有時沒有被引用的內(nèi)存會被收集，這樣會引發(fā)問題，例如，如果一個整數(shù)域中包含一個值，該值是已分配內(nèi)存的地址。不過，這種情況極少發(fā)生，而且它只會浪費少量內(nèi)存。保守的收集器的優(yōu)勢是，它們可以與任何編程語言相集成。
Hans Boehm 的保守垃圾收集器是可用的最流行的垃圾收集器之一，因為它是免費的，而且既是保守的又是增量的，可以使用 --enable-redirect-malloc 選項來構(gòu)建它，并且可以將它用作系統(tǒng)分配程序的簡易替代者（drop-in replacement）（用 malloc/ free 代替它自己的 API）。實際上，如果這樣做，您就可以使用與我們在示例分配程序中所使用的相同的 LD_PRELOAD 技巧，在系統(tǒng)上的幾乎任何程序中啟用垃圾收集。如果您懷疑某個程序正在泄漏內(nèi)存，那么您可以使用這個垃圾收集器來控制進程。在早期，當(dāng) Mozilla 嚴重地泄漏內(nèi)存時，很多人在其中使用了這項技術(shù)。這種垃圾收集器既可以在 Windows® 下運行，也可以在 UNIX 下運行。
垃圾收集的一些優(yōu)點：
您永遠不必擔(dān)心內(nèi)存的雙重釋放或者對象的生命周期。
使用某些收集器，您可以使用與常規(guī)分配相同的 API。
其缺點包括：
使用大部分收集器時，您都無法干涉何時釋放內(nèi)存。
在多數(shù)情況下，垃圾收集比其他形式的內(nèi)存管理更慢。
垃圾收集錯誤引發(fā)的缺陷難于調(diào)試。
如果您忘記將不再使用的指針設(shè)置為 null，那么仍然會有內(nèi)存泄漏。
回頁首
結(jié)束語
一切都需要折衷：性能、易用、易于實現(xiàn)、支持線程的能力等，這里只列出了其中的一些。為了滿足項目的要求，有很多內(nèi)存管理模式可以供您使用。每種模式都有大量的實現(xiàn)，各有其優(yōu)缺點。對很多項目來說，使用編程環(huán)境默認的技術(shù)就足夠了，不過，當(dāng)您的項目有特殊的需要時，了解可用的選擇將會有幫助。下表對比了本文中涉及的內(nèi)存管理策略。
表 1. 內(nèi)存分配策略的對比
策略 分配速度 回收速度 局部緩存 易用性 通用性 實時可用 SMP 線程友好
定制分配程序 取決于實現(xiàn) 取決于實現(xiàn) 取決于實現(xiàn) 很難 無 取決于實現(xiàn) 取決于實現(xiàn)
簡單分配程序 內(nèi)存使用少時較快 很快 差 容易 高 否 否
GNU malloc 中 快 中 容易 高 否 中
Hoard 中 中 中 容易 高 否 是
引用計數(shù) N/A N/A 非常好 中 中 是（取決于 malloc 實現(xiàn)） 取決于實現(xiàn)
池 中 非�？� 極好 中 中 是（取決于 malloc 實現(xiàn)） 取決于實現(xiàn)
垃圾收集 中（進行收集時慢） 中 差 中 中 否 幾乎不
增量垃圾收集 中 中 中 中 中 否 幾乎不
增量保守垃圾收集 中 中 中 容易 高 否 幾乎不
參考資料
您可以參閱本文在 developerWorks 全球站點上的 英文原文。
Web 上的文檔
GNU C Library 手冊的 obstacks 部分 提供了 obstacks 編程接口。
Apache Portable Runtime 文檔 描述了它們的池式分配程序的接口。
基本的分配程序
Doug Lea 的 Malloc 是最流行的內(nèi)存分配程序之一。
BSD Malloc 用于大部分基于 BSD 的系統(tǒng)中。
ptmalloc 起源于 Doug Lea 的 malloc，用于 GLIBC 之中。
Hoard 是一個為多線程應(yīng)用程序優(yōu)化的 malloc 實現(xiàn)。
GNU Memory-Mapped Malloc（GDB 的組成部分） 是一個基于 mmap() 的 malloc 實現(xiàn)。
池式分配程序
GNU Obstacks（GNU Libc 的組成部分）是安裝最多的池式分配程序，因為在每一個基于 glibc 的系統(tǒng)中都有它。
Apache 的池式分配程序（Apache Portable Runtime 中） 是應(yīng)用最為廣泛的池式分配程序。
Squid 有其自己的池式分配程序。
NetBSD 也有其自己的池式分配程序。
talloc 是一個池式分配程序，是 Samba 的組成部分。
智能指針和定制分配程序
Loki C++ Library 有很多為 C++ 實現(xiàn)的通用模式，包括智能指針和一個定制的小對象分配程序。
垃圾收集器
Hahns Boehm Conservative Garbage Collector 是最流行的開源垃圾收集器，它可以用于常規(guī)的 C/C++ 程序。
關(guān)于現(xiàn)代操作系統(tǒng)中的虛擬內(nèi)存的文章
Marshall Kirk McKusick 和 Michael J. Karels 合著的 A New Virtual Memory Implementation for Berkeley UNIX 討論了 BSD 的 VM 系統(tǒng)。
Mel Gorman's Linux VM Documentation 討論了 Linux VM 系統(tǒng)。
關(guān)于 malloc 的文章
Poul-Henning Kamp 撰寫的 Malloc in Modern Virtual Memory Environments 討論的是 malloc 以及它如何與 BSD 虛擬內(nèi)存交互。
Berger、McKinley、Blumofe 和 Wilson 合著的 Hoard -- a Scalable Memory Allocator for Multithreaded Environments 討論了 Hoard 分配程序的實現(xiàn)。
Marshall Kirk McKusick 和 Michael J. Karels 合著的 Design of a General Purpose Memory Allocator for the 4.3BSD UNIX Kernel 討論了內(nèi)核級的分配程序。
Doug Lea 撰寫的 A Memory Allocator 給出了一個關(guān)于設(shè)計和實現(xiàn)分配程序的概述，其中包括設(shè)計選擇與折衷。
Emery D. Berger 撰寫的 Memory Management for High-Performance Applications 討論的是定制內(nèi)存管理以及它如何影響高性能應(yīng)用程序。
關(guān)于定制分配程序的文章
Doug Lea 撰寫的 Some Storage Management Techniques for Container Classes 描述的是為 C++ 類編寫定制分配程序。
Berger、Zorn 和 McKinley 合著的 Composing High-Performance Memory Allocators 討論了如何編寫定制分配程序來加快具體工作的速度。
Berger、Zorn 和 McKinley 合著的 Reconsidering Custom Memory Allocation 再次提及了定制分配的主題，看是否真正值得為其費心。
關(guān)于垃圾收集的文章
Paul R. Wilson 撰寫的 Uniprocessor Garbage Collection Techniques 給出了垃圾收集的一個基本概述。
Benjamin Zorn 撰寫的 The Measured Cost of Garbage Collection 給出了關(guān)于垃圾收集和性能的硬數(shù)據(jù)（hard data）。
Hans-Juergen Boehm 撰寫的 Memory Allocation Myths and Half-Truths 給出了關(guān)于垃圾收集的神話（myths）。
Hans-Juergen Boehm 撰寫的 Space Efficient Conservative Garbage Collection 是一篇描述他的用于 C/C++ 的垃圾收集器的文章。
Web 上的通用參考資料
內(nèi)存管理參考 中有很多關(guān)于內(nèi)存管理參考資料和技術(shù)文章的鏈接。
關(guān)于內(nèi)存管理和內(nèi)存層級的 OOPS Group Papers 是非常好的一組關(guān)于此主題的技術(shù)文章。
C++ 中的內(nèi)存管理討論的是為 C++ 編寫定制的分配程序。
Programming Alternatives: Memory Management 討論了程序員進行內(nèi)存管理時的一些選擇。
垃圾收集 FAQ 討論了關(guān)于垃圾收集您需要了解的所有內(nèi)容。
Richard Jones 的 Garbage Collection Bibliography 有指向任何您想要的關(guān)于垃圾收集的文章的鏈接。
書籍
Michael Daconta 撰寫的 C++ Pointers and Dynamic Memory Management 介紹了關(guān)于內(nèi)存管理的很多技術(shù)。
Frantisek Franek 撰寫的 Memory as a Programming Concept in C and C++ 討論了有效使用內(nèi)存的技術(shù)與工具，并給出了在計算機編程中應(yīng)當(dāng)引起注意的內(nèi)存相關(guān)錯誤的角色。
Richard Jones 和 Rafael Lins 合著的 Garbage Collection: Algorithms for Automatic Dynamic Memory Management 描述了當(dāng)前使用的最常見的垃圾收集算法。
在 Donald Knuth 撰寫的 The Art of Computer Programming 第 1 卷 Fundamental Algorithms 的第 2.5 節(jié)“Dynamic Storage Allocation”中，描述了實現(xiàn)基本的分配程序的一些技術(shù)。
在 Donald Knuth 撰寫的 The Art of Computer Programming 第 1 卷 Fundamental Algorithms 的第 2.3.5 節(jié)“Lists and Garbage Collection”中，討論了用于列表的垃圾收集算法。
Andrei Alexandrescu 撰寫的 Modern C++ Design 第 4 章“Small Object Allocation”描述了一個比 C++ 標(biāo)準(zhǔn)分配程序效率高得多的一個高速小對象分配程序。
Andrei Alexandrescu 撰寫的 Modern C++ Design 第 7 章“Smart Pointers”描述了在 C++ 中智能指針的實現(xiàn)。
Jonathan 撰寫的 Programming from the Ground Up 第 8 章“Intermediate Memory Topics”中有本文使用的簡單分配程序的一個匯編語言版本。
來自 developerWorks
自我管理數(shù)據(jù)緩沖區(qū)內(nèi)存 （developerWorks，2004 年 1 月）略述了一個用于管理內(nèi)存的自管理的抽象數(shù)據(jù)緩存器的偽 C （pseudo-C）實現(xiàn)。
A framework for the user defined malloc replacement feature （developerWorks，2002 年 2 月）展示了如何利用 AIX 中的一個工具，使用自己設(shè)計的內(nèi)存子系統(tǒng)取代原有的內(nèi)存子系統(tǒng)。
掌握 Linux 調(diào)試技術(shù) （developerWorks，2002 年 8 月）描述了可以使用調(diào)試方法的 4 種不同情形：段錯誤、內(nèi)存溢出、內(nèi)存泄漏和掛起。
在 處理 Java 程序中的內(nèi)存漏洞 （developerWorks，2001 年 2 月）中，了解導(dǎo)致 Java 內(nèi)存泄漏的原因，以及何時需要考慮它們。
在 developerWorks Linux 專區(qū)中，可以找到更多為 Linux 開發(fā)人員準(zhǔn)備的參考資料。
從 developerWorks 的 Speed-start your Linux app 專區(qū)中，可以下載運行于 Linux 之上的 IBM 中間件產(chǎn)品的免費測試版本，其中包括 WebSphere® Studio Application Developer、WebSphere Application Server、DB2® Universal Database、Tivoli® Access Manager 和 Tivoli Directory Server，查找 how-to 文章和技術(shù)支持。
通過參與 developerWorks blogs 加入到 developerWorks 社區(qū)。
可以在 Developer Bookstore Linux 專欄中定購 打折出售的 Linux 書籍。
關(guān)于作者
Jonathan Bartlett 是 Programming from the Ground Up 一書的作者，這本書介紹的是 Linux 匯編語言編程。Jonathan Bartlett 是 New Media Worx 的總開發(fā)師，負責(zé)為客戶開發(fā) Web、視頻、kiosk 和桌面應(yīng)用程序。您可以通過 johnnyb@eskimo.com 與 Jonathan 聯(lián)系。 |
|
免費注冊
發(fā)表于 2008-12-07 20:22
