淺析malloc（）的幾種實現(xiàn)方式

malloc（）是C語言中動態(tài)存儲管理的一組標(biāo)準(zhǔn)庫函數(shù)之一。其作用是在內(nèi)存的動態(tài)存儲區(qū)中分配一個長度為size的連續(xù)空間。其參數(shù)是一個無符號整形數(shù)，返回值是一個指向所分配的連續(xù)存儲域的起始地址的指針。

　　動態(tài)內(nèi)存分配就是指在程序執(zhí)行的過程中動態(tài)地分配或者回收存儲空間的分配內(nèi)存的方法。動態(tài)內(nèi)存分配不像數(shù)組等靜態(tài)內(nèi)存分配方法那樣需要預(yù)先分配存儲空間，而是由系統(tǒng)根據(jù)程序的需要即時分配，且分配的大小就是程序要求的大小。本文簡單介紹動態(tài)內(nèi)存分配函數(shù)malloc（）及幾種實現(xiàn)方法。

　　1． 簡介

　　malloc（）是C語言中動態(tài)存儲管理的一組標(biāo)準(zhǔn)庫函數(shù)之一。其作用是在內(nèi)存的動態(tài)存儲區(qū)中分配一個長度為size的連續(xù)空間。其參數(shù)是一個無符號整形數(shù)，返回值是一個指向所分配的連續(xù)存儲域的起始地址的指針。還有一點必須注意的是，當(dāng)函數(shù)未能成功分配存儲空間（如內(nèi)存不足）就會返回一個NULL指針。所以在調(diào)用該函數(shù)時應(yīng)該檢測返回值是否為NULL并執(zhí)行相應(yīng)的操作。

　　2． 函數(shù)說明

　　C語言的動態(tài)存儲管理由一組標(biāo)準(zhǔn)庫函數(shù)實現(xiàn)，其原型在標(biāo)準(zhǔn)文件<stdlib.h>里描述，需要用這些功
能時應(yīng)包含這個文件。與動態(tài)存儲分配有關(guān)的函數(shù)共有四個，其中就包括存儲分配函數(shù)malloc（）。函數(shù)原型是：void *malloc (size_t n);這里的size_t是標(biāo)準(zhǔn)庫里定義的一個類型，它是一個無符號整型。這個整型能夠滿足所有對存儲塊大小描述的需要，具體相當(dāng)于哪個整型由具體的C系統(tǒng)確定。malloc的返回值為(void *)類型（這是通用指針的一個重要用途），它分配一片能存放大小為n的數(shù)據(jù)的存儲塊，返回對應(yīng)的指針值；如果不能滿足申請（找不到能滿足要求的存儲塊）就返回NULL。在使用時，應(yīng)該把malloc的返回值轉(zhuǎn)換到特定指針類型，賦給一個指針。

　　注意，雖然這里的存儲塊是通過動態(tài)分配得到的，但是它的大小也是確定的，同樣不允許越界使用。例如上面程序段分配的塊里能存n個雙精度數(shù)據(jù)，隨后的使用就必須在這個范圍內(nèi)進(jìn)行。越界使用動態(tài)分配的存儲塊，尤其是越界賦值，可能引起非常嚴(yán)重的后果，通常會破壞程序的運行系統(tǒng)，可能造成本程序或者整個計算機(jī)系統(tǒng)垮臺。

　　下例是一個動態(tài)分配的例子：
　　#include <stdlib.h>

　　main()
　　{
　　int count,*array; /*count是一個計數(shù)器，array是一個整型指針，也可以理解為指向一個整型數(shù)組的首地址*/
　　if((array(int *) malloc (10*sizeof(int)))==NULL)
　　{
　　printf("不能成功分配存儲空間。");
　　exit(1);
　　}
　　for (count=0;count〈10;count++) /*給數(shù)組賦值*/
　　array[count]=count;
　　for(count=0;count〈10;count++) /*打印數(shù)組元素*/
　　printf("%2d",array[count]);
　　}

　　上例中動態(tài)分配了10個整型存儲區(qū)域，然后進(jìn)行賦值并打印。例中if((array(int *) malloc (10*sizeof(int)))==NULL)語句可以分為以下幾步：
　　1）分配10個整型的連續(xù)存儲空間，并返回一個指向其起始地址的整型指針
　　2）把此整型指針地址賦給array
　　3）檢測返回值是否為NULL

　　3． malloc（）工作機(jī)制

　　malloc函數(shù)的實質(zhì)體現(xiàn)在，它有一個將可用的內(nèi)存塊連接為一個長長的列表的所謂空閑鏈表。調(diào)用malloc函數(shù)時，它沿連接表尋找一個大到足以滿足用戶請求所需要的內(nèi)存塊。然后，將該內(nèi)存塊一分為二（一塊的大小與用戶請求的大小相等，另一塊的大小就是剩下的字節(jié)）。接下來，將分配給用戶的那塊內(nèi)存?zhèn)鹘o用戶，并將剩下的那塊（如果有的話）返回到連接表上。調(diào)用free函數(shù)時，它將用戶釋放的內(nèi)存塊連接到空閑鏈上。到最后，空閑鏈會被切成很多的小內(nèi)存片段，如果這時用戶申請一個大的內(nèi)存片段，那么空閑鏈上可能沒有可以滿足用戶要求的片段了。于是，malloc函數(shù)請求延時，并開始在空閑鏈上翻箱倒柜地檢查各內(nèi)存片段，對它們進(jìn)行整理，將相鄰的小空閑塊合并成較大的內(nèi)存塊。

　　4． malloc（）在操作系統(tǒng)中的實現(xiàn)

　　在 C 程序中，多次使用malloc () 和 free()。不過，您可能沒有用一些時間去思考它們在您的操作系統(tǒng)中是如何實現(xiàn)的。本節(jié)將向您展示 malloc 和 free 的一個最簡化實現(xiàn)的代碼，來幫助說明管理內(nèi)存時都涉及到了哪些事情。

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

　　void *malloc (long numbytes)：該函數(shù)負(fù)責(zé)分配 numbytes 大小的內(nèi)存，并返回指向第一個字節(jié)的指針。

　　void free(void *firstbyte)：如果給定一個由先前的 malloc 返回的指針，那么該函數(shù)會將分配的空間歸還給進(jìn)程的“空閑空間”。

　　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
　　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)存塊進(jìn)行了 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)在，您可能會認(rè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)存的釋放使用了一個非常簡單的機(jī)制，在固定時間內(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&nbs