本文將對 Linux? 程序員可以使用的內存管理技術進行概述,雖然關注的重點是 C 語言,但同樣也適用于其他語言。文中將為您提供如何管理內存的細節,然后將進一步展示如何手工管理內存,如何使用引用計數或者內存池來半手工地管理內存,以及如何使用垃圾收集自動管理內存。
為什么必須管理內存
內存管理是計算機編程最為基本的領域之一。在很多腳本語言中,您不必擔心內存是如何管理的,這并不能使得內存管理的重要性有一點點降低。對實際編程來說,理解您的內存管理器的能力與局限性至關重要。在大部分系統語言中,比如 C 和 C++,您必須進行內存管理。本文將介紹手工的、半手工的以及自動的內存管理實踐的基本概念。
追溯到在 Apple II 上進行匯編語言編程的時代,那時內存管理還不是個大問題。您實際上在運行整個系統。系統有多少內存,您就有多少內存。您甚至不必費心思去弄明白它有多少內存,因為每一臺機器的內存數量都相同。所以,如果內存需要非常固定,那么您只需要選擇一個內存范圍并使用它即可。
不過,即使是在這樣一個簡單的計算機中,您也會有問題,尤其是當您不知道程序的每個部分將需要多少內存時。如果您的空間有限,而內存需求是變化的,那么您需要一些方法來滿足這些需求:
- 確定您是否有足夠的內存來處理數據。
- 從可用的內存中獲取一部分內存。
- 向可用內存池(pool)中返回部分內存,以使其可以由程序的其他部分或者其他程序使用。
實現這些需求的程序庫稱為 分配程序(allocators),因為它們負責分配和回收內存。程序的動態性越強,內存管理就越重要,您的內存分配程序的選擇也就更重要。讓我們來了解可用于內存管理的不同方法,它們的好處與不足,以及它們最適用的情形。
C 風格的內存分配程序
C 編程語言提供了兩個函數來滿足我們的三個需求:
-
malloc:該函數分配給定的字節數,并返回一個指向它們的指針。如果沒有足夠的可用內存,那么它返回一個空指針。
-
free:該函數獲得指向由
malloc
分配的內存片段的指針,并將其釋放,以便以后的程序或操作系統使用(實際上,一些 malloc
實現只能將內存歸還給程序,而無法將內存歸還給操作系統)。
物理內存和虛擬內存
要理解內存在程序中是如何分配的,首先需要理解如何將內存從操作系統分配給程序。計算機上的每一個進程都認為自己可以訪問所有的物理內存。顯然,由于同時在運行多個程序,所以每個進程不可能擁有全部內存。實際上,這些進程使用的是 虛擬內存。
只是作為一個例子,讓我們假定您的程序正在訪問地址為 629 的內存。不過,虛擬內存系統不需要將其存儲在位置為 629 的 RAM 中。實際上,它甚至可以不在 RAM 中 —— 如果物理 RAM 已經滿了,它甚至可能已經被轉移到硬盤上!由于這類地址不必反映內存所在的物理位置,所以它們被稱為虛擬內存。操作系統維持著一個虛擬地址到物理地址的轉換的表,以便計算機硬件可以正確地響應地址請求。并且,如果地址在硬盤上而不是在 RAM 中,那么操作系統將暫時停止您的進程,將其他內存轉存到硬盤中,從硬盤上加載被請求的內存,然后再重新啟動您的進程。這樣,每個進程都獲得了自己可以使用的地址空間,可以訪問比您物理上安裝的內存更多的內存。
在 32-位 x86 系統上,每一個進程可以訪問 4 GB 內存。現在,大部分人的系統上并沒有 4 GB 內存,即使您將 swap 也算上, 每個進程所使用的內存也肯定少于 4 GB。因此,當加載一個進程時,它會得到一個取決于某個稱為 系統中斷點(system break)的特定地址的初始內存分配。該地址之后是未被映射的內存 —— 用于在 RAM 或者硬盤中沒有分配相應物理位置的內存。因此,如果一個進程運行超出了它初始分配的內存,那么它必須請求操作系統“映射進來(map in)”更多的內存。(映射是一個表示一一對應關系的數學術語 —— 當內存的虛擬地址有一個對應的物理地址來存儲內存內容時,該內存將被映射。)
基于 UNIX 的系統有兩個可映射到附加內存中的基本系統調用:
-
brk:
brk()
是一個非常簡單的系統調用。還記得系統中斷點嗎?該位置是進程映射的內存邊界。 brk()
只是簡單地將這個位置向前或者向后移動,就可以向進程添加內存或者從進程取走內存。
-
mmap:
mmap()
,或者說是“內存映像”,類似于 brk()
,但是更為靈活。首先,它可以映射任何位置的內存,而不單單只局限于進程。其次,它不僅可以將虛擬地址映射到物理的 RAM 或者 swap,它還可以將它們映射到文件和文件位置,這樣,讀寫內存將對文件中的數據進行讀寫。不過,在這里,我們只關心 mmap
向進程添加被映射的內存的能力。 munmap()
所做的事情與 mmap()
相反。
如您所見, brk()
或者 mmap()
都可以用來向我們的進程添加額外的虛擬內存。在我們的例子中將使用 brk()
,因為它更簡單,更通用。
實現一個簡單的分配程序
如果您曾經編寫過很多 C 程序,那么您可能曾多次使用過 malloc()
和 free()
。不過,您可能沒有用一些時間去思考它們在您的操作系統中是如何實現的。本節將向您展示 malloc
和 free
的一個最簡化實現的代碼,來幫助說明管理內存時都涉及到了哪些事情。
要試著運行這些示例,需要先 復制本代碼清單,并將其粘貼到一個名為 malloc.c 的文件中。接下來,我將一次一個部分地對該清單進行解釋。
在大部分操作系統中,內存分配由以下兩個簡單的函數來處理:
-
void *malloc(long numbytes)
:該函數負責分配 numbytes
大小的內存,并返回指向第一個字節的指針。
-
void free(void *firstbyte)
:如果給定一個由先前的 malloc
返回的指針,那么該函數會將分配的空間歸還給進程的“空閑空間”。
malloc_init
將是初始化內存分配程序的函數。它要完成以下三件事:將分配程序標識為已經初始化,找到系統中最后一個有效內存地址,然后建立起指向我們管理的內存的指針。這三個變量都是全局變量:
清單 1. 我們的簡單分配程序的全局變量
int has_initialized = 0;
void *managed_memory_start;
void *last_valid_address;
|
如前所述,被映射的內存的邊界(最后一個有效地址)常被稱為系統中斷點或者 當前中斷點。在很多 UNIX? 系統中,為了指出當前系統中斷點,必須使用 sbrk(0)
函數。 sbrk
根據參數中給出的字節數移動當前系統中斷點,然后返回新的系統中斷點。使用參數 0
只是返回當前中斷點。這里是我們的 malloc
初始化代碼,它將找到當前中斷點并初始化我們的變量:
清單 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;
}
|
現在,為了完全地管理內存,我們需要能夠追蹤要分配和回收哪些內存。在對內存塊進行了 free
調用之后,我們需要做的是諸如將它們標記為未被使用的等事情,并且,在調用 malloc
時,我們要能夠定位未被使用的內存塊。因此, malloc
返回的每塊內存的起始處首先要有這個結構:
清單 3. 內存控制塊結構定義
struct mem_control_block {
int is_available;
int size;
};
|
現在,您可能會認為當程序調用 malloc
時這會引發問題 —— 它們如何知道這個結構?答案是它們不必知道;在返回指針之前,我們會將其移動到這個結構之后,把它隱藏起來。這使得返回的指針指向沒有用于任何其他用途的內存。那樣,從調用程序的角度來看,它們所得到的全部是空閑的、開放的內存。然后,當通過 free()
將該指針傳遞回來時,我們只需要倒退幾個內存字節就可以再次找到這個結構。
在討論分配內存之前,我們將先討論釋放,因為它更簡單。為了釋放內存,我們必須要做的惟一一件事情就是,獲得我們給出的指針,回退 sizeof(struct mem_control_block)
個字節,并將其標記為可用的。這里是對應的代碼:
清單 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;
}
|
如您所見,在這個分配程序中,內存的釋放使用了一個非常簡單的機制,在固定時間內完成內存釋放。分配內存稍微困難一些。以下是該算法的略述:
清單 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
|
我們主要使用連接的指針遍歷內存來尋找開放的內存塊。這里是代碼:
清單 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;
}
|
這就是我們的內存管理器。現在,我們只需要構建它,并在程序中使用它即可。
運行下面的命令來構建 malloc
兼容的分配程序(實際上,我們忽略了 realloc()
等一些函數,不過, malloc()
和 free()
才是最主要的函數):
清單 7. 編譯分配程序
gcc -shared -fpic malloc.c -o malloc.so
|
該程序將生成一個名為 malloc.so 的文件,它是一個包含有我們的代碼的共享庫。
在 UNIX 系統中,現在您可以用您的分配程序來取代系統的 malloc()
,做法如下:
清單 8. 替換您的標準的 malloc
LD_PRELOAD=/path/to/malloc.so
export LD_PRELOAD
|
LD_PRELOAD
環境變量使動態鏈接器在加載任何可執行程序之前,先加載給定的共享庫的符號。它還為特定庫中的符號賦予優先權。因此,從現在起,該會話中的任何應用程序都將使用我們的 malloc()
,而不是只有系統的應用程序能夠使用。有一些應用程序不使用 malloc()
,不過它們是例外。其他使用 realloc()
等其他內存管理函數的應用程序,或者錯誤地假定 malloc()
內部行為的那些應用程序,很可能會崩潰。ash shell 似乎可以使用我們的新 malloc()
很好地工作。
如果您想確保 malloc()
正在被使用,那么您應該通過向函數的入口點添加 write()
調用來進行測試。
我們的內存管理器在很多方面都還存在欠缺,但它可以有效地展示內存管理需要做什么事情。它的某些缺點包括:
- 由于它對系統中斷點(一個全局變量)進行操作,所以它不能與其他分配程序或者
mmap
一起使用。
- 當分配內存時,在最壞的情形下,它將不得不遍歷 全部進程內存;其中可能包括位于硬盤上的很多內存,這意味著操作系統將不得不花時間去向硬盤移入數據和從硬盤中移出數據。
- 沒有很好的內存不足處理方案(
malloc
只假定內存分配是成功的)。
- 它沒有實現很多其他的內存函數,比如
realloc()
。
- 由于
sbrk()
可能會交回比我們請求的更多的內存,所以在堆(heap)的末端會遺漏一些內存。
- 雖然
is_available
標記只包含一位信息,但它要使用完整的 4-字節 的字。
- 分配程序不是線程安全的。
- 分配程序不能將空閑空間拼合為更大的內存塊。
- 分配程序的過于簡單的匹配算法會導致產生很多潛在的內存碎片。
- 我確信還有很多其他問題。這就是為什么它只是一個例子!
其他 malloc 實現
malloc()
的實現有很多,這些實現各有優點與缺點。在設計一個分配程序時,要面臨許多需要折衷的選擇,其中包括:
- 分配的速度。
- 回收的速度。
- 有線程的環境的行為。
- 內存將要被用光時的行為。
- 局部緩存。
- 簿記(Bookkeeping)內存開銷。
- 虛擬內存環境中的行為。
- 小的或者大的對象。
- 實時保證。
每一個實現都有其自身的優缺點集合。在我們的簡單的分配程序中,分配非常慢,而回收非常快。另外,由于它在使用虛擬內存系統方面較差,所以它最適于處理大的對象。
還有其他許多分配程序可以使用。其中包括:
-
Doug Lea Malloc:Doug Lea Malloc 實際上是完整的一組分配程序,其中包括 Doug Lea 的原始分配程序,GNU libc 分配程序和
ptmalloc
。 Doug Lea 的分配程序有著與我們的版本非常類似的基本結構,但是它加入了索引,這使得搜索速度更快,并且可以將多個沒有被使用的塊組合為一個大的塊。它還支持緩存,以便更快地再次使用最近釋放的內存。 ptmalloc
是 Doug Lea Malloc 的一個擴展版本,支持多線程。在本文后面的 參考資料部分中,有一篇描述 Doug Lea 的 Malloc 實現的文章。
-
BSD Malloc:BSD Malloc 是隨 4.2 BSD 發行的實現,包含在 FreeBSD 之中,這個分配程序可以從預先確實大小的對象構成的池中分配對象。它有一些用于對象大小的 size 類,這些對象的大小為 2 的若干次冪減去某一常數。所以,如果您請求給定大小的一個對象,它就簡單地分配一個與之匹配的 size 類。這樣就提供了一個快速的實現,但是可能會浪費內存。在 參考資料部分中,有一篇描述該實現的文章。
-
Hoard:編寫 Hoard 的目標是使內存分配在多線程環境中進行得非常快。因此,它的構造以鎖的使用為中心,從而使所有進程不必等待分配內存。它可以顯著地加快那些進行很多分配和回收的多線程進程的速度。在 參考資料部分中,有一篇描述該實現的文章。
眾多可用的分配程序中最有名的就是上述這些分配程序。如果您的程序有特別的分配需求,那么您可能更愿意編寫一個定制的能匹配您的程序內存分配方式的分配程序。不過,如果不熟悉分配程序的設計,那么定制分配程序通常會帶來比它們解決的問題更多的問題。要獲得關于該主題的適當的介紹,請參閱 Donald Knuth 撰寫的 The Art of Computer Programming Volume 1: Fundamental Algorithms 中的第 2.5 節“Dynamic Storage Allocation”(請參閱 參考資料中的鏈接)。它有點過時,因為它沒有考慮虛擬內存環境,不過大部分算法都是基于前面給出的函數。
在 C++ 中,通過重載 operator new()
,您可以以每個類或者每個模板為單位實現自己的分配程序。在 Andrei Alexandrescu 撰寫的 Modern C++ Design 的第 4 章(“Small Object Allocation”)中,描述了一個小對象分配程序(請參閱 參考資料中的鏈接)。
基于 malloc() 的內存管理的缺點
不只是我們的內存管理器有缺點,基于 malloc()
的內存管理器仍然也有很多缺點,不管您使用的是哪個分配程序。對于那些需要保持長期存儲的程序使用 malloc()
來管理內存可能會非常令人失望。如果您有大量的不固定的內存引用,經常難以知道它們何時被釋放。生存期局限于當前函數的內存非常容易管理,但是對于生存期超出該范圍的內存來說,管理內存則困難得多。而且,關于內存管理是由進行調用的程序還是由被調用的函數來負責這一問題,很多 API 都不是很明確。
因為管理內存的問題,很多程序傾向于使用它們自己的內存管理規則。C++ 的異常處理使得這項任務更成問題。有時好像致力于管理內存分配和清理的代碼比實際完成計算任務的代碼還要多!因此,我們將研究內存管理的其他選擇。
半自動內存管理策略
引用計數
引用計數是一種 半自動(semi-automated)的內存管理技術,這表示它需要一些編程支持,但是它不需要您確切知道某一對象何時不再被使用。引用計數機制為您完成內存管理任務。
在引用計數中,所有共享的數據結構都有一個域來包含當前活動“引用”結構的次數。當向一個程序傳遞一個指向某個數據結構指針時,該程序會將引用計數增加 1。實質上,您是在告訴數據結構,它正在被存儲在多少個位置上。然后,當您的進程完成對它的使用后,該程序就會將引用計數減少 1。結束這個動作之后,它還會檢查計數是否已經減到零。如果是,那么它將釋放內存。
這樣做的好處是,您不必追蹤程序中某個給定的數據結構可能會遵循的每一條路徑。每次對其局部的引用,都將導致計數的適當增加或減少。這樣可以防止在使用數據結構時釋放該結構。不過,當您使用某個采用引用計數的數據結構時,您必須記得運行引用計數函數。另外,內置函數和第三方的庫不會知道或者可以使用您的引用計數機制。引用計數也難以處理發生循環引用的數據結構。
要實現引用計數,您只需要兩個函數 —— 一個增加引用計數,一個減少引用計數并當計數減少到零時釋放內存。
一個示例引用計數函數集可能看起來如下所示:
清單 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
可能會更復雜,這取決于您想要做的事情。例如,您可能想要為多線程程序增加鎖,那么您可能想擴展 refcountedstruct
,使它同樣包含一個指向某個在釋放內存之前要調用的函數的指針(類似于面向對象語言中的析構函數 —— 如果您的結構中包含這些指針,那么這是 必需的)。
當使用 REF
和 UNREF
時,您需要遵守這些指針的分配規則:
-
UNREF
分配前左端指針(left-hand-side pointer)指向的值。
-
REF
分配后左端指針(left-hand-side pointer)指向的值。
在傳遞使用引用計數的結構的函數中,函數需要遵循以下這些規則:
- 在函數的起始處 REF 每一個指針。
- 在函數的結束處 UNREF 第一個指針。
以下是一個使用引用計數的生動的代碼示例:
清單 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 */
}
|
由于引用計數是如此簡單,大部分程序員都自已去實現它,而不是使用庫。不過,它們依賴于 malloc
和 free
等低層的分配程序來實際地分配和釋放它們的內存。
在 Perl 等高級語言中,進行內存管理時使用引用計數非常廣泛。在這些語言中,引用計數由語言自動地處理,所以您根本不必擔心它,除非要編寫擴展模塊。由于所有內容都必須進行引用計數,所以這會對速度產生一些影響,但它極大地提高了編程的安全性和方便性。以下是引用計數的益處:
- 實現簡單。
- 易于使用。
- 由于引用是數據結構的一部分,所以它有一個好的緩存位置。
不過,它也有其不足之處:
- 要求您永遠不要忘記調用引用計數函數。
- 無法釋放作為循環數據結構的一部分的結構。
- 減緩幾乎每一個指針的分配。
- 盡管所使用的對象采用了引用計數,但是當使用異常處理(比如
try
或 setjmp()
/ longjmp()
)時,您必須采取其他方法。
- 需要額外的內存來處理引用。
- 引用計數占用了結構中的第一個位置,在大部分機器中最快可以訪問到的就是這個位置。
- 在多線程環境中更慢也更難以使用。
C++ 可以通過使用 智能指針(smart pointers)來容忍程序員所犯的一些錯誤,智能指針可以為您處理引用計數等指針處理細節。不過,如果不得不使用任何先前的不能處理智能指針的代碼(比如對 C 庫的聯接),實際上,使用它們的后果通實比不使用它們更為困難和復雜。因此,它通常只是有益于純 C++ 項目。如果您想使用智能指針,那么您實在應該去閱讀 Alexandrescu 撰寫的 Modern C++ Design 一書中的“Smart Pointers”那一章。
內存池
內存池是另一種半自動內存管理方法。內存池幫助某些程序進行自動內存管理,這些程序會經歷一些特定的階段,而且每個階段中都有分配給進程的特定階段的內存。例如,很多網絡服務器進程都會分配很多針對每個連接的內存 —— 內存的最大生存期限為當前連接的存在期。Apache 使用了池式內存(pooled memory),將其連接拆分為各個階段,每個階段都有自己的內存池。在結束每個階段時,會一次釋放所有內存。
在池式內存管理中,每次內存分配都會指定內存池,從中分配內存。每個內存池都有不同的生存期限。在 Apache 中,有一個持續時間為服務器存在期的內存池,還有一個持續時間為連接的存在期的內存池,以及一個持續時間為請求的存在期的池,另外還有其他一些內存池。因此,如果我的一系列函數不會生成比連接持續時間更長的數據,那么我就可以完全從連接池中分配內存,并知道在連接結束時,這些內存會被自動釋放。另外,有一些實現允許注冊 清除函數(cleanup functions),在清除內存池之前,恰好可以調用它,來完成在內存被清理前需要完成的其他所有任務(類似于面向對象中的析構函數)。
要在自己的程序中使用池,您既可以使用 GNU libc 的 obstack 實現,也可以使用 Apache 的 Apache Portable Runtime。GNU obstack 的好處在于,基于 GNU 的 Linux 發行版本中默認會包括它們。Apache Portable Runtime 的好處在于它有很多其他工具,可以處理編寫多平臺服務器軟件所有方面的事情。要深入了解 GNU obstack 和 Apache 的池式內存實現,請參閱 參考資料部分中指向這些實現的文檔的鏈接。
下面的假想代碼列表展示了如何使用 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;
}
|
基本上,在操作的每一個主要階段結束之后,這個階段的 obstack 會被釋放。不過,要注意的是,如果一個過程需要分配持續時間比當前階段更長的內存,那么它也可以使用更長期限的 obstack,比如連接或者全局內存。傳遞給 obstack_free()
的 NULL
指出它應該釋放 obstack 的全部內容。可以用其他的值,但是它們通常不怎么實用。
使用池式內存分配的益處如下所示:
- 應用程序可以簡單地管理內存。
- 內存分配和回收更快,因為每次都是在一個池中完成的。分配可以在 O(1) 時間內完成,釋放內存池所需時間也差不多(實際上是 O(n) 時間,不過在大部分情況下會除以一個大的因數,使其變成 O(1))。
- 可以預先分配錯誤處理池(Error-handling pools),以便程序在常規內存被耗盡時仍可以恢復。
- 有非常易于使用的標準實現。
池式內存的缺點是:
- 內存池只適用于操作可以分階段的程序。
- 內存池通常不能與第三方庫很好地合作。
- 如果程序的結構發生變化,則不得不修改內存池,這可能會導致內存管理系統的重新設計。
- 您必須記住需要從哪個池進行分配。另外,如果在這里出錯,就很難捕獲該內存池。
垃圾收集
垃圾收集(Garbage collection)是全自動地檢測并移除不再使用的數據對象。垃圾收集器通常會在當可用內存減少到少于一個具體的閾值時運行。通常,它們以程序所知的可用的一組“基本”數據 —— 棧數據、全局變量、寄存器 —— 作為出發點。然后它們嘗試去追蹤通過這些數據連接到每一塊數據。收集器找到的都是有用的數據;它沒有找到的就是垃圾,可以被銷毀并重新使用這些無用的數據。為了有效地管理內存,很多類型的垃圾收集器都需要知道數據結構內部指針的規劃,所以,為了正確運行垃圾收集器,它們必須是語言本身的一部分。
收集器的類型
-
復制(copying): 這些收集器將內存存儲器分為兩部分,只允許數據駐留在其中一部分上。它們定時地從“基本”的元素開始將數據從一部分復制到另一部分。內存新近被占用的部分現在成為活動的,另一部分上的所有內容都認為是垃圾。另外,當進行這項復制操作時,所有指針都必須被更新為指向每個內存條目的新位置。因此,為使用這種垃圾收集方法,垃圾收集器必須與編程語言集成在一起。
-
標記并清理(Mark and sweep):每一塊數據都被加上一個標簽。不定期的,所有標簽都被設置為 0,收集器從“基本”的元素開始遍歷數據。當它遇到內存時,就將標簽標記為 1。最后沒有被標記為 1 的所有內容都認為是垃圾,以后分配內存時會重新使用它們。
-
增量的(Incremental):增量垃圾收集器不需要遍歷全部數據對象。因為在收集期間的突然等待,也因為與訪問所有當前數據相關的緩存問題(所有內容都不得不被頁入(page-in)),遍歷所有內存會引發問題。增量收集器避免了這些問題。
-
保守的(Conservative):保守的垃圾收集器在管理內存時不需要知道與數據結構相關的任何信息。它們只查看所有數據類型,并假定它們 可以全部都是指針。所以,如果一個字節序列可以是一個指向一塊被分配的內存的指針,那么收集器就將其標記為正在被引用。有時沒有被引用的內存會被收集,這樣會引發問題,例如,如果一個整數域中包含一個值,該值是已分配內存的地址。不過,這種情況極少發生,而且它只會浪費少量內存。保守的收集器的優勢是,它們可以與任何編程語言相集成。
Hans Boehm 的保守垃圾收集器是可用的最流行的垃圾收集器之一,因為它是免費的,而且既是保守的又是增量的,可以使用 --enable-redirect-malloc
選項來構建它,并且可以將它用作系統分配程序的簡易替代者(drop-in replacement)(用 malloc
/ free
代替它自己的 API)。實際上,如果這樣做,您就可以使用與我們在示例分配程序中所使用的相同的 LD_PRELOAD
技巧,在系統上的幾乎任何程序中啟用垃圾收集。如果您懷疑某個程序正在泄漏內存,那么您可以使用這個垃圾收集器來控制進程。在早期,當 Mozilla 嚴重地泄漏內存時,很多人在其中使用了這項技術。這種垃圾收集器既可以在 Windows? 下運行,也可以在 UNIX 下運行。
垃圾收集的一些優點:
- 您永遠不必擔心內存的雙重釋放或者對象的生命周期。
- 使用某些收集器,您可以使用與常規分配相同的 API。
其缺點包括:
- 使用大部分收集器時,您都無法干涉何時釋放內存。
- 在多數情況下,垃圾收集比其他形式的內存管理更慢。
- 垃圾收集錯誤引發的缺陷難于調試。
- 如果您忘記將不再使用的指針設置為 null,那么仍然會有內存泄漏。
結束語
一切都需要折衷:性能、易用、易于實現、支持線程的能力等,這里只列出了其中的一些。為了滿足項目的要求,有很多內存管理模式可以供您使用。每種模式都有大量的實現,各有其優缺點。對很多項目來說,使用編程環境默認的技術就足夠了,不過,當您的項目有特殊的需要時,了解可用的選擇將會有幫助。下表對比了本文中涉及的內存管理策略。
表 1. 內存分配策略的對比
策略
|
分配速度
|
回收速度
|
局部緩存
|
易用性
|
通用性
|
實時可用
|
SMP 線程友好
|
定制分配程序 |
取決于實現 |
取決于實現 |
取決于實現 |
很難 |
無 |
取決于實現 |
取決于實現 |
簡單分配程序 |
內存使用少時較快 |
很快 |
差 |
容易 |
高 |
否 |
否 |
GNU malloc |
中 |
快 |
中 |
容易 |
高 |
否 |
中 |
Hoard |
中 |
中 |
中 |
容易 |
高 |
否 |
是 |
引用計數 |
N/A |
N/A |
非常好 |
中 |
中 |
是(取決于 malloc 實現) |
取決于實現 |
池 |
中 |
非常快 |
極好 |
中 |
中 |
是(取決于 malloc 實現) |
取決于實現 |
垃圾收集 |
中(進行收集時慢) |
中 |
差 |
中 |
中 |
否 |
幾乎不 |
增量垃圾收集 |
中 |
中 |
中 |
中 |
中 |
否 |
幾乎不 |
增量保守垃圾收集 |
中 |
中 |
中 |
容易 |
高 |
否 |
幾乎不 |