動(dòng)態(tài)內(nèi)存管理非常耗時(shí),，對(duì)效率影響很大，然而在實(shí)際的編程應(yīng)用中,，卻不可避免地經(jīng)常要用到堆中的內(nèi)存,。但是通過Malloc函數(shù)或New等進(jìn)行的內(nèi)存分配存在先天缺陷： (1)利用默認(rèn)的內(nèi)存管理函數(shù)在堆上分配和釋放內(nèi)存需要花費(fèi)很多時(shí)間；(2)隨著時(shí)間的推移,，堆上會(huì)形成許多內(nèi)存碎片,，在應(yīng)用程序進(jìn)行內(nèi)存申請(qǐng)操作將受到更大的影響，導(dǎo)致應(yīng)用程序的運(yùn)行越來越慢[1-3],。

    當(dāng)應(yīng)用程序需要對(duì)固定大小的對(duì)象經(jīng)常性地申請(qǐng)內(nèi)存時(shí),，常會(huì)采用內(nèi)存池（Memory Pool）技術(shù)來提高內(nèi)存管理效率。經(jīng)典的內(nèi)存池做法是一次性分配大量大小相同的小塊內(nèi)存,，通過該技術(shù)可以極大地加快內(nèi)存分配/釋放過程,。內(nèi)存池技術(shù)通過批量申請(qǐng)內(nèi)存，降低了內(nèi)存申請(qǐng)次數(shù),，從而使操作節(jié)省了時(shí)間,。在減少了內(nèi)存碎片產(chǎn)生的同時(shí)，對(duì)性能的提升有顯著的幫助,。
    綜上,，內(nèi)存池有其巨大的優(yōu)勢(shì)，但是原有的內(nèi)存池也存在一定的缺陷,。在多線程場(chǎng)合下應(yīng)用時(shí),，每個(gè)新產(chǎn)生的線程如何在O(1)時(shí)間內(nèi)獲取內(nèi)存塊，如何保證其安全有效性,，以及如何管理內(nèi)存塊的數(shù)量方面存在一定的不足的,，本文對(duì)此進(jìn)行研究，并給出一種新的解決方案。
1 內(nèi)存池制作原理以及工作流程
    本內(nèi)存池基于多線程環(huán)境,，需要考慮到多線程下數(shù)據(jù)的安全,，以及快速獲取內(nèi)存塊等條件。在獲取內(nèi)存塊索引號(hào)時(shí),，采用加鎖的方式,，雖然會(huì)耗費(fèi)一定的時(shí)間,但是運(yùn)行安全得到了保障。在程序運(yùn)行之前需創(chuàng)建好內(nèi)存池,，并用一個(gè)結(jié)構(gòu)體struct mem_pool進(jìn)行封裝,里面包含內(nèi)存池的一些私有數(shù)據(jù),。當(dāng)有新線程產(chǎn)生時(shí)，直接像內(nèi)存池申請(qǐng)一塊已經(jīng)分配好了的內(nèi)存,，線程的具體內(nèi)存操作都在該內(nèi)存塊中進(jìn)行,。同時(shí)，內(nèi)存池結(jié)構(gòu)體中隱藏一個(gè)管理線程,，該線程的工作是定時(shí)檢查內(nèi)存池中空閑內(nèi)存塊的數(shù)量是否過多或者過少,。當(dāng)過多時(shí)，申請(qǐng)釋放,，直到達(dá)到門檻值,；當(dāng)過少時(shí)，申請(qǐng)?jiān)黾尤舾?，以備不時(shí)之需,。內(nèi)存池結(jié)構(gòu)如圖1所示。

    對(duì)于內(nèi)存池中的內(nèi)存塊,采用結(jié)構(gòu)struct mem_block維護(hù)其數(shù)據(jù),，該結(jié)構(gòu)以一個(gè)鏈表的形式維護(hù)實(shí)際內(nèi)存區(qū)域,，結(jié)構(gòu)體中有兩個(gè)管理內(nèi)存的區(qū)域：(1)常規(guī)大小鏈表區(qū)域。當(dāng)需要的內(nèi)存小于常規(guī)大小時(shí),，則線程的內(nèi)存請(qǐng)求都將從該區(qū)域獲得,；當(dāng)該區(qū)域內(nèi)存將滿時(shí)，則線程可以繼續(xù)申請(qǐng)同樣大小的內(nèi)存塊,，鏈接到該常規(guī)大小鏈表上,。(2)大塊內(nèi)存鏈表區(qū)域。當(dāng)線程申請(qǐng)的內(nèi)存超過該內(nèi)存塊的大小時(shí),，將在系統(tǒng)中申請(qǐng)一塊大的內(nèi)存鏈接到該大塊內(nèi)存鏈表上,，這樣可以對(duì)內(nèi)存塊進(jìn)行統(tǒng)一管理；當(dāng)線程壽命結(jié)束時(shí),，調(diào)用reset函數(shù)將大塊內(nèi)存釋放,，同時(shí)重設(shè)常規(guī)內(nèi)存鏈表區(qū)域，只保留最開始的一塊,，其余后面申請(qǐng)的塊全部釋放,并標(biāo)記內(nèi)存塊的使用狀態(tài)為空閑,，同時(shí)重設(shè)一些內(nèi)部指針,，指向內(nèi)存塊可用的起始位置[4]。
    創(chuàng)建內(nèi)存池結(jié)構(gòu),，并初始化,，此時(shí)在內(nèi)存中存儲(chǔ)著一份內(nèi)存池的動(dòng)態(tài)管理單元,。當(dāng)創(chuàng)建新線程時(shí),，該線程通過內(nèi)存塊查找函數(shù)，并查詢內(nèi)存池結(jié)構(gòu),。如有空閑內(nèi)存塊則直接將該內(nèi)存塊的索引號(hào)index送給線程,，同時(shí)將該內(nèi)存塊的空閑標(biāo)志flag設(shè)為繁忙；如果內(nèi)存池中沒有可用的空閑內(nèi)存塊,，且內(nèi)存塊數(shù)量未達(dá)到設(shè)置的頂峰,，則可以申請(qǐng)add_memblock；若正在使用的內(nèi)存塊超過了最大設(shè)置的內(nèi)存塊數(shù)量,，則線程將調(diào)用Malloc函數(shù),，并自行調(diào)用Free釋放該內(nèi)存塊。管理線程周期性地調(diào)用get_mp_status來查看內(nèi)存池狀態(tài),若空閑線程低于門檻值(最小空閑內(nèi)存塊數(shù)),則調(diào)度add_memblock函數(shù)創(chuàng)建新的內(nèi)存塊到池中,；若空閑內(nèi)存塊高于門檻值(最大空閑內(nèi)存數(shù)),，則調(diào)度del_memblock銷毀多余的內(nèi)存塊。線程生命周期結(jié)束后,，將內(nèi)存塊的繁忙標(biāo)記設(shè)置為空閑狀態(tài),，并且重新初始化該內(nèi)存塊，將內(nèi)存塊重新投入到內(nèi)存池中,，等待其他線程重復(fù)利用,。內(nèi)存池的工作流程如圖2所示。

2 內(nèi)存池主要技術(shù)
2.1 內(nèi)存池中空閑內(nèi)存塊的查找方式
   當(dāng)進(jìn)程服務(wù)繁忙時(shí),，一些內(nèi)存塊長(zhǎng)期被某些線程占用的情況下,，也可能延長(zhǎng)內(nèi)存池響應(yīng)時(shí)間，影響響應(yīng)速度,。內(nèi)存池調(diào)度算法的一項(xiàng)重要任務(wù)就是盡可能提高查找空閑內(nèi)存塊的速度,。而簡(jiǎn)單地遍歷內(nèi)存池鏈表顯然不能滿足請(qǐng)求線程的需要，這種方式不僅延長(zhǎng)了調(diào)用者的返回時(shí)間,，而且極大增加了內(nèi)存池對(duì)請(qǐng)求線程的響應(yīng)時(shí)間,。特別是在服務(wù)器繁忙時(shí)，當(dāng)處于請(qǐng)求內(nèi)存塊的線程越多,，查找空閑內(nèi)存塊所花費(fèi)的時(shí)間就越長(zhǎng),。因此，本文提出以下兩種查找方法：
    (1) 位圖查找方式
    用位圖方式維護(hù)內(nèi)存池中的內(nèi)存塊單元,，查找空閑內(nèi)存塊將只需遍歷位圖,，位圖按單個(gè)字節(jié)進(jìn)行查找效率較高,。另外，在線程結(jié)束時(shí)的前一刻,，維護(hù)當(dāng)前空閑內(nèi)存塊的索引index,可在下次查找空閑內(nèi)存塊時(shí)直接獲取這個(gè)值,，而時(shí)間耗費(fèi)是O(1)級(jí)的，這將大大提高響應(yīng)時(shí)間,。
    (2) 基于數(shù)組的方式
    基于鏈表實(shí)現(xiàn)的內(nèi)存池,，在創(chuàng)建內(nèi)存池時(shí)或者每次增加池中內(nèi)存塊數(shù)時(shí)都必須分配新的管理結(jié)構(gòu)，再進(jìn)行鏈接,；并且在查找空閑內(nèi)存塊時(shí),，需要遍歷內(nèi)存池，其直接后果是造成線程請(qǐng)求內(nèi)存塊的時(shí)間大大增加,。而數(shù)組的方式有其天然的優(yōu)勢(shì),，當(dāng)用位圖查找到了空閑內(nèi)存塊的索引后，也即知道了內(nèi)存塊在數(shù)組中的位置,，由此可以迅速地定位空閑內(nèi)存塊,，大大提高了響應(yīng)速度。
2.2 內(nèi)存池中內(nèi)存塊的數(shù)量動(dòng)態(tài)調(diào)整
    固定的內(nèi)存池在有些情況下并不能滿足實(shí)際情況的需要,，動(dòng)態(tài)內(nèi)存池常見的調(diào)整方法有基于閾值觸發(fā)和基于預(yù)測(cè)公式兩種形式,。基于預(yù)測(cè)公式方法通過統(tǒng)計(jì)學(xué)的經(jīng)驗(yàn)公式來預(yù)測(cè),，優(yōu)點(diǎn)是能夠反應(yīng)內(nèi)存池消耗內(nèi)存的真實(shí)傾向,，迅速查找和釋放內(nèi)存塊；缺點(diǎn)是按照統(tǒng)計(jì)公式計(jì)算的結(jié)果,，通常局限于某些特定場(chǎng)合和應(yīng)用,，并且在內(nèi)存池中造成系統(tǒng)資源消耗較大?；陂撝涤|發(fā)方法通常按照參數(shù)配置來控制內(nèi)存池的某些參數(shù),，優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單、通用性強(qiáng),、可控性好,；缺點(diǎn)是需要精確計(jì)算配置參數(shù)，否則性能會(huì)急劇下降,。為保證內(nèi)存池的通用性,，這里使用參數(shù)可調(diào)整的閾值觸發(fā)方式動(dòng)態(tài)調(diào)整內(nèi)存池。
    (1) 相關(guān)參數(shù)合理性設(shè)置
    設(shè)內(nèi)存池中最大內(nèi)存塊數(shù)為MAX_NUM,，內(nèi)存池中最小內(nèi)存塊數(shù)為MIN_NUM,，內(nèi)存池中最小空閑內(nèi)存塊數(shù)為MIN_IDLE，內(nèi)存池最大空閑內(nèi)存塊數(shù)為MAX_IDLE,，方法是：
    ①初始化創(chuàng)建MIN_NUM個(gè)空閑內(nèi)存塊,；
    ②池中空閑內(nèi)存塊數(shù)量低于MIN_IDLE時(shí),，觸發(fā)內(nèi)存池調(diào)整，添加MIN_IDLE個(gè)內(nèi)存塊,；
　 ③池中空閑內(nèi)存塊數(shù)量高于MAX_IDLE時(shí),，觸發(fā)內(nèi)存發(fā)池調(diào)整，刪除MIN_IDLE個(gè)內(nèi)存塊
    ④調(diào)整過程確保內(nèi)存池中內(nèi)存塊數(shù)不多于MAX_NUM個(gè),也不少于MIN_NUM個(gè),。
    對(duì)以上參數(shù)的合理設(shè)置可以保證內(nèi)存池能動(dòng)態(tài)地處理內(nèi)存塊過多或過少時(shí)的情況,，同時(shí)在處理大量請(qǐng)求時(shí)，避免請(qǐng)求線程等待太久,。
    (2) 設(shè)置內(nèi)存池模式
    內(nèi)存池的工作模式能夠影響的調(diào)整行為：
    ①可增可減模式：內(nèi)存池處于動(dòng)態(tài)管理狀態(tài),，實(shí)時(shí)調(diào)整內(nèi)存塊的數(shù)量,在條件允許的情況下增加或刪除空閑內(nèi)存塊,。
    ②只增不減模式：內(nèi)存池處于動(dòng)態(tài)管理狀態(tài),，內(nèi)存池只會(huì)做出添加內(nèi)存塊的調(diào)整行為，不會(huì)做出刪減內(nèi)存塊的調(diào)整,。
    ③不增不減模式：內(nèi)存池處于動(dòng)態(tài)管理狀態(tài),，既不增加內(nèi)存塊，也不刪除內(nèi)存塊,。
    對(duì)內(nèi)存池模式的設(shè)置應(yīng)盡可能多地滿足不同的應(yīng)用場(chǎng)合,，使內(nèi)存池具有更好的適應(yīng)性和通用性。相對(duì)于其他兩種模式來說,，可增可減模式適應(yīng)性較強(qiáng),，既不浪費(fèi)系統(tǒng)資源，又可提供良好的服務(wù),。
2.3 內(nèi)存池中內(nèi)存塊組織結(jié)構(gòu)的調(diào)整
   將內(nèi)存塊大小固定的內(nèi)存池在使用時(shí)將遇到諸多不便,。不同的任務(wù)線程對(duì)于內(nèi)存大小的需求不一樣，對(duì)于一般的服務(wù),，可能線程所需要的內(nèi)存塊只在幾十~幾百字節(jié)之間,，但對(duì)于另外一些服務(wù)，線程將需要幾千甚至幾兆的內(nèi)存來處理數(shù)據(jù),。因此,，合適的內(nèi)存塊的大小將影響請(qǐng)求線程的效率。內(nèi)存塊組織結(jié)構(gòu)如圖3所示,。

3 代碼組織
   借鑒C++語(yǔ)言中的面向?qū)ο蟮乃枷?，在C語(yǔ)言中利用結(jié)構(gòu)體模擬C++語(yǔ)言中的類，用函數(shù)指針模擬類方法,，通過指針強(qiáng)制轉(zhuǎn)換實(shí)現(xiàn)數(shù)據(jù)隱藏,。頭文件.h中包含數(shù)據(jù)結(jié)構(gòu)，而.c文件中包含實(shí)際的內(nèi)存池結(jié)構(gòu),，這樣可避免用戶操作結(jié)構(gòu)體中的數(shù)據(jù)成員雖然不能真正地像C++中隱藏?cái)?shù)據(jù),，但是也達(dá)到了一定的隱藏效果[5-6],。
3.1 內(nèi)存池使用方法
    mp_mem_pool *pool = create_mem_pool();
    pool->init(pool, NULL,“log.txt”);
    pool->find_min_idle_index(pool);
    pool->palloc(pool, index, size);
    destroy_mem_pool( pool);
3.2 函數(shù)與接口的功能
       struct mp_mem_pool_s{
       MPBOOL    (*init)(mp_mem_pool *pool, mp_mem_conf *conf, const char *log_file);
       void    (*reset)(mp_mem_pool *pool);
       void(*reset_memblock)(mp_mem_pool *pool, const int index);
     void( *get_mp_status )( mp_mem_pool *pool);
     void(*print_mp_status)(mp_mem_pool *pool);
       int(*find_min_idle_index)(mp_mem_pool *pool)；
       void    *(*palloc)(mp_mem_pool *pool, const int index,  size_t size);
       void    (*pnalloc)(mp_mem_pool *pool, const int index, size_t size);
       void    (*pcalloc)(mp_mem_pool *pool, const int index,  size_t size);
       void    (*pmemalign)(mp_mem_pool *pool, const int index, size_t size, size_t alignment);
       mp_mem_pool *create_mem_pool();
       void destroy_mem_pool( mp_mem_pool* pool );
    函數(shù)用戶接口較為簡(jiǎn)單,，主要為創(chuàng)建和銷毀內(nèi)存池的接口,，以及查找池中空閑內(nèi)存塊索引。內(nèi)存池本身也有自己的接口struct mp_mem_pool_s,只有類似C++中的成員函數(shù)沒有數(shù)據(jù),，所有數(shù)據(jù)都在實(shí)現(xiàn)文件中進(jìn)行處理,，這樣隱藏?cái)?shù)據(jù)的好處是避免用戶隨意操作內(nèi)存池管理單元中的數(shù)據(jù)。
    create_mem_pool:    創(chuàng)建內(nèi)存池;
    destroy_mem_pool:    銷毀內(nèi)存池;
    init: 初始化內(nèi)存池(沒有初始化是無法使用的,，可以根據(jù)配置文件調(diào)節(jié)內(nèi)存池行為);
     reset:關(guān)閉內(nèi)存池,，將其退回到創(chuàng)建時(shí)的狀態(tài);
       reset_memblock:重置具體的內(nèi)存塊，將其退回到初始化時(shí)的狀態(tài);
       get_mp_status:獲取內(nèi)存池狀態(tài)(當(dāng)前的內(nèi)存塊數(shù)量,，最大內(nèi)存塊數(shù),，以及空閑內(nèi)存塊數(shù)量等);
       print_mp_status:打印內(nèi)存池的工作狀態(tài)到終端上顯示;
       find_min_idle_index:返回內(nèi)存池中空閑內(nèi)存塊的索引;
       palloc:請(qǐng)求線程申請(qǐng)到內(nèi)存塊之后,調(diào)用該函數(shù)進(jìn)行內(nèi)存分配操作，分配時(shí)進(jìn)行對(duì)齊處理;
       pnalloc:請(qǐng)求線程申請(qǐng)到內(nèi)存塊之后,調(diào)用該函數(shù)進(jìn)行內(nèi)存分配操作,，分配時(shí)不進(jìn)行對(duì)齊處理;
       pcalloc:請(qǐng)求線程申請(qǐng)到內(nèi)存塊之后,，調(diào)用該函數(shù)進(jìn)行內(nèi)存分配操作，分配時(shí)進(jìn)行對(duì)齊處理,，同時(shí)將內(nèi)存清零;
       pmemalign:分配大塊內(nèi)存的操作函數(shù),。
　    實(shí)際的應(yīng)用中內(nèi)存池通常都是與線程池、以及任務(wù)池結(jié)合在一起使用,，但各個(gè)模塊之間耦合越緊,，模塊的重用就會(huì)越困難，移植性越低,。因此內(nèi)存池的接口應(yīng)盡可能地保持其獨(dú)立性,，不依賴外部條件。而內(nèi)存池的使用者只需要做初期初始化工作,，將描述內(nèi)存池的結(jié)構(gòu)體作為全局變量,，然后在線程的工作函數(shù)中調(diào)用find_min_idle_index尋找到可用內(nèi)存塊索引即可，操作簡(jiǎn)單方便[6-8],。
4 比較與測(cè)試
    (1) 測(cè)試環(huán)境
    Intel(R) Core(TM) i3-2100 CPU @ 2.80 GHz,，2 GB內(nèi)存;Fedora 14(內(nèi)核2.6.35.14-106.fc14.i686，GCC 4.5.1,，GLIBC 2.12.90)
    (2) 測(cè)試設(shè)計(jì)
    內(nèi)存池的使用相比線程中直接調(diào)用Malloc,、Free函數(shù)分配和銷毀內(nèi)存的優(yōu)勢(shì)，主要體現(xiàn)在一次性申請(qǐng)連續(xù)N塊內(nèi)存,，并且在程序結(jié)束后統(tǒng)一釋放,。而多線程環(huán)境中每個(gè)線程單獨(dú)調(diào)用Malloc、Free則需要大量的系統(tǒng)調(diào)用開銷,，同時(shí),，將可能產(chǎn)生許多內(nèi)存碎片,。而內(nèi)存池的使用能夠節(jié)省Malloc、Free不斷地調(diào)用時(shí)間,，避免了可能出現(xiàn)的內(nèi)存碎片,，從而保證內(nèi)存池的使用有利于復(fù)用和管理。
    針對(duì)本測(cè)試所設(shè)計(jì)的測(cè)試程序?yàn)?，在使用?nèi)存池環(huán)境下,，主線程先創(chuàng)建并初始化內(nèi)存池，內(nèi)存池中每個(gè)Memblock的大小設(shè)為1 KB,，內(nèi)存池的配置文件中設(shè)置最大內(nèi)存塊數(shù)量為201,，最小內(nèi)存塊數(shù)量為30，最大空閑內(nèi)存塊數(shù)量為60,，最小空閑內(nèi)存塊數(shù)量為10,。之后主線程產(chǎn)生200個(gè)線程，所有線程的工作就是向內(nèi)存池申請(qǐng)內(nèi)存塊,之后再在申請(qǐng)到的Memblock中分別分配128 B,、1 KB,、 2 KB,，以及同時(shí)申請(qǐng)128 B和1 KB,，然后用time命令來計(jì)算user time和sys time。
    在不使用內(nèi)存池情況下,，每個(gè)線程將單獨(dú)調(diào)用malloc和free函數(shù)來分配和釋放內(nèi)存,，同樣分別分配128 B,1 KB,2 KB以及同時(shí)申請(qǐng)128 B和1 KB內(nèi)存。需要注意的是,，為了避免客觀因素影響,，兩個(gè)測(cè)試程序中的其余部分應(yīng)盡量一致。每種情況進(jìn)行100次測(cè)試,，平均得到的測(cè)試結(jié)果如表1所示,。
    (3) 結(jié)果分析
    由表1可見，在不使用內(nèi)存池的測(cè)試中,，當(dāng)一個(gè)線程中多次分配以及釋放時(shí),，將消耗更多的時(shí)間。而使用內(nèi)存池的結(jié)果還是比較理想的,。每個(gè)線程分配內(nèi)存的大小對(duì)于用戶時(shí)間和系統(tǒng)時(shí)間幾乎毫無影響,，它不需要Malloc和Free不斷地操作，節(jié)約了大量庫(kù)函數(shù)調(diào)用,、系統(tǒng)調(diào)用的開銷,，減少了內(nèi)存碎片，特別對(duì)于服務(wù)器程序的運(yùn)行,，是非?？捎^的,。

    本文設(shè)計(jì)一種在多線程環(huán)境下的內(nèi)存池算法，優(yōu)化了池中內(nèi)存塊的維護(hù)和查找算法,，并保證了接口的簡(jiǎn)單易用性,，使其更易于與項(xiàng)目集成。
參考文獻(xiàn)
[1] 翁小東. 電信級(jí)用系統(tǒng)中多進(jìn)程共享內(nèi)存池的實(shí)現(xiàn)[J].電腦知識(shí)技術(shù),2009,4(5-12):3300-3306
[2] 劉小華. 基于C++的內(nèi)存池的實(shí)現(xiàn)[J].福建電腦, 2008(1):82-83.
[3] 張海闊,，趙沖沖,，王玉，等. 鏈表快速查找的內(nèi)存池管理優(yōu)化技術(shù)研究[C]. 2007年全國(guó)高性能計(jì)算學(xué)術(shù)年會(huì), 2007.
[4] 胡萌,趙衛(wèi)東,王志成,等. 線程池設(shè)計(jì)與動(dòng)態(tài)優(yōu)化[J]. 電腦知識(shí)與技術(shù),，2008,4(9):2753-2755.
[5] STEVENS W R. UNIX網(wǎng)路編程(第2卷)[M]. 北京：人民郵電出版社,2010.
[6] 趙海,李志蜀,韓學(xué)為,等. 一種鏈?zhǔn)浇Y(jié)構(gòu)在內(nèi)存管理中的應(yīng)用[J].高等函授學(xué)報(bào):自然科學(xué)版,2002,15(4)：46-48.
[7] 翁小東.基于UNIX C語(yǔ)言的一種線程池實(shí)現(xiàn)[J]. 電腦知識(shí)與技術(shù),2009,5(16):4222-4223.
[8] LOWELL R M. A C++ pooled, shared memory allocator for simulator development[C]. IEEE,2004,Proceedings of the 37th Annual Simulation Symposium,，2004.