VxWorks實時操作系統(tǒng)內(nèi)存分配算法優(yōu)化

中國科學(xué)院軟件研究所 李彥峰 李麗穎山東農(nóng)村信用社聯(lián)合社 韓廣志金陵科技學(xué)院 徐尚喻

?

VxWorks實時操作系統(tǒng)內(nèi)存分配算法優(yōu)化

中國科學(xué)院軟件研究所 李彥峰 李麗穎
山東農(nóng)村信用社聯(lián)合社 韓廣志
金陵科技學(xué)院 徐尚喻

【摘要】通過研究VxWorks實時系統(tǒng)內(nèi)存分配算法，發(fā)現(xiàn)VxWorks的內(nèi)存管理算法的局限性。本文提出通過在VxWorks實時操作系統(tǒng)原有的內(nèi)存管理功能上添加功能，用于實現(xiàn)固定大小內(nèi)存分配。新增加的功能利用位圖管理內(nèi)存，通過降低內(nèi)存管理信息占整個內(nèi)存塊的比率提高內(nèi)存使用效率，通過將固定大小的內(nèi)存片合并為一組進(jìn)行整體的內(nèi)存分配來降低內(nèi)存碎片；同時由于減少了內(nèi)存碎片，從而間接提高內(nèi)存的分配速度。

【關(guān)鍵詞】內(nèi)存分配；位圖管理；內(nèi)存碎片；分配效率

0　引言

VxWorks內(nèi)存管理是基于Flat模式實現(xiàn)的，管理框架分為分區(qū)（Partition）、Pool（池）、Block（塊）。系統(tǒng)中的具體實現(xiàn)為分區(qū)結(jié)構(gòu)體memSysPartition，內(nèi)存中的空閑內(nèi)存通過這個結(jié)構(gòu)體的成員變量freelist鏈接起來。VxWorks原有的內(nèi)存分配實現(xiàn)相對而言比較簡單——所有任務(wù)的內(nèi)存分配請求調(diào)用malloc函數(shù)從系統(tǒng)內(nèi)存分區(qū)memSysPartition中獲得。內(nèi)存請求分配時利用最先適應(yīng)算法從系統(tǒng)分區(qū)結(jié)構(gòu)中來滿足內(nèi)存分配請求，而內(nèi)存回收時則會將相鄰地址的空閑內(nèi)存給聚合成一個更大的空閑內(nèi)存。

VxWorks的以上內(nèi)存分配設(shè)計沒有考慮小內(nèi)存分配請求的優(yōu)化，很容易導(dǎo)致下列問題：第一，當(dāng)系統(tǒng)中存在大量的小內(nèi)存分配請求時，就可能使得內(nèi)存中出現(xiàn)較多的內(nèi)存碎片；導(dǎo)致系統(tǒng)中存在可用的內(nèi)存卻因為大小不能滿足而出現(xiàn)內(nèi)存分配失敗的結(jié)果，從而影響系統(tǒng)的穩(wěn)定性。第二，freelist鏈表中的小內(nèi)存過多時，整個鏈表長度會很長，從而使得鏈表的搜索時間效率降低。第三，整個系統(tǒng)中，一個內(nèi)存塊（BLOCK）就有一個管理信息，小內(nèi)存分配會出現(xiàn)管理信息站用大量內(nèi)存空閑的情況。第四，由于所有的內(nèi)存分配都要競爭系統(tǒng)內(nèi)存分區(qū)memSysPartition的保護(hù)鎖，導(dǎo)致系統(tǒng)的運行變慢，降低系統(tǒng)的效率。

1　固定大小內(nèi)存分配

基于上面的考慮，我們的改進(jìn)通過在現(xiàn)有的VxWorks操作系統(tǒng)的內(nèi)存分配上面加上一層：將現(xiàn)有的內(nèi)存管理層次從分區(qū)（PARTITION）、池（POOL）、塊（BLOCK）擴展到分區(qū)（PARTITION）、池（POOL）、塊（BLOCK）、內(nèi)存片(MEMORY_SLICE)。也就是將小內(nèi)存的內(nèi)存請求都轉(zhuǎn)化為大小為一個內(nèi)存片（MEMORY_SLICE）的請求，同時將這些固定大小的內(nèi)存片組合成一個內(nèi)存序列。內(nèi)存序列增加一些額外的內(nèi)存管理信息頭部就組成一個內(nèi)存塊（BLOCK_HDR）原來每個小的內(nèi)存片都需要一個BLOCK_HDR的管理信息，現(xiàn)在多個內(nèi)存片共享一個BLOCK_HDR的管理信息；而BLOCK_HDR內(nèi)部的內(nèi)存片序列中的內(nèi)存片MEMORY_SLICE則通過較小的內(nèi)部管理信息進(jìn)行管理，從而達(dá)到固定大小的內(nèi)存塊管理信息共享的目的；同時由于固定大小的內(nèi)存以一組內(nèi)存片為單位進(jìn)行分配和回收降低了系統(tǒng)的內(nèi)存碎片，提高了系統(tǒng)內(nèi)存使用的效率，同時增強了系統(tǒng)的穩(wěn)定性。

2　優(yōu)化內(nèi)存分配算法

算法的主要實現(xiàn)思想是，給小內(nèi)存塊定義一個下界N——所有小于等于N的內(nèi)存分配請求都會調(diào)整到大小為N的內(nèi)存分配，而多個這樣的大小為N的內(nèi)存片MEMORY_SLICE組成一個內(nèi)存片序列MEMORY_ARRAY。為了減少額外的內(nèi)存管理信息，利用位圖管理思想來管理固定大小的內(nèi)存，即每一個內(nèi)存片MEMORY_SLICE和一個內(nèi)存管理位圖的位對應(yīng)；當(dāng)位圖的中的某一位為1的時候表明內(nèi)存被占用，反之則未被占用。同時，為了方便位圖的運算，每一個位圖包含32個位。這樣位圖的操作可以轉(zhuǎn)換為C語言中的整形數(shù)的位操作，同時32個位對應(yīng)內(nèi)存中的4個字節(jié)，而VxWorks以4字節(jié)為單位進(jìn)行對齊，這樣的設(shè)定可以減少內(nèi)存中不必要的對齊操作。另外，由于BLOCK_HDR不是最底層的內(nèi)存管理單位，所以還需要額外的鏈表對這些BLOCK_HDR進(jìn)行管理，以方便內(nèi)存分配時找到包含內(nèi)存片序列的BLOCK_HDR。因此，擴展的內(nèi)存管理還需要一個額外的鏈表節(jié)點DL_NODE用于將所有的包含內(nèi)存片序列MEMORY_ARRAY的BLOCK_HDR鏈接到系統(tǒng)全局鏈表中。經(jīng)過調(diào)整之后，每一個包含32個內(nèi)存片的內(nèi)存片序列MEMORY_ARRAY和一個DL_NODE以及一個32位的位圖BITMAP組成VxWorks的一個基本的內(nèi)存塊BLOCK_HDR。這些包含內(nèi)存片序列的內(nèi)存塊BLOCK_HDR通過DL_NODE鏈接到鏈表memlist中。

3　具體實現(xiàn)

根據(jù)上面的實現(xiàn)思想，在VxWorks操作系統(tǒng)中實現(xiàn)小內(nèi)存轉(zhuǎn)化為固定大小的小內(nèi)存的管理，需要增加一個全局的DL_LIST變量memlist，通過memlist變量將包含內(nèi)存片序列的BLOCK_HDR鏈接起來；同時為了實現(xiàn)VxWorks系統(tǒng)下面的多任務(wù)訪問還需要額外的SEMPHORE信號量來輔助實現(xiàn)memlist的互斥訪問，在代碼當(dāng)中的定義：SEMAPHORE memsm； DL_LIST memlist;

當(dāng)內(nèi)存分配請求大于sizeof（MEMORY_SLICE）時，直接調(diào)用malloc函數(shù)實現(xiàn)內(nèi)存的分配而無需經(jīng)過我們的內(nèi)存分配；反之，則首先將內(nèi)存分配請求大小調(diào)整到大小為sizeof（MEMORY_SLICE），然后遍歷memlist鏈表，直到找到可用的BLOCK_HDR或者達(dá)到memlist鏈表表尾。

增加上訴定義來簡化理解，其中CusMan用于管理內(nèi)存片序列MEMORY_ARRAY，bitmap用于內(nèi)存的位圖管理，node用于連接到全局的鏈表memlist中。遍歷的過程中，通過memlist得到鏈表節(jié)點node，將node指針強制轉(zhuǎn)化為CusMan類型的指針cusmanptr。通過CusMan指針cusmanptr可以得到管理內(nèi)存片序列的內(nèi)存管理位圖bitmap，將32位的bitmap看作一個整形數(shù)。利用這個整形數(shù)與0xFFFFFFFF進(jìn)行比較，如果小于0xFFFFFFFF則表明在當(dāng)前的內(nèi)存塊節(jié)點包含可用的空閑內(nèi)存，則中止遍歷。否則，直到到達(dá)鏈表表尾并終止遍歷過程。如果遍歷到達(dá)鏈表尾終止，則需要重新調(diào)用malloc函數(shù)分配一個大小為sizeof（MEM_ARRAY）+sizeof（CusMan）的內(nèi)存塊BLOCK_HDR。將這個內(nèi)存塊中的與內(nèi)存序列對應(yīng)的內(nèi)存管理信息CusMan中的bitmap的第一個bit設(shè)置為1，同時返回內(nèi)存序列中的第一個MEM_SLICE，并利用CusMan中的鏈表節(jié)點DL_NODE將新分配的內(nèi)存塊BLOCK_HDR掛載到memlist鏈表中。

當(dāng)出現(xiàn)有鏈表節(jié)點node得到的CusMan的成員變量bitmap不全為1而中止遍歷時，則表明memlist中該鏈表節(jié)點可以滿足內(nèi)存分配請求。則轉(zhuǎn)入到對包含該節(jié)點的內(nèi)存塊BLOCK_HDR的處理過程，首先通過節(jié)點node找到CusMan指針，然后通過CusMan指針找到成員變量bitmap。通過位測試操作，找到bitmap中第一個為0的bit位，將該bit位設(shè)置為1，并且返回與這個bit對應(yīng)的MEM_SLICE。

由于分配的時候出現(xiàn)的調(diào)整，所以在釋放的時候也需要相應(yīng)的改變。在內(nèi)存釋放時，取下memlist鏈表當(dāng)中的內(nèi)存塊節(jié)點DL_NODE，通過DL_NODE可以得到內(nèi)存序列MEMORY_ARRAY。根據(jù)比較需要回收的內(nèi)存地址freeptr和內(nèi)存序列所包含的地址范圍來判斷freeptr是否落在包含該節(jié)點的內(nèi)存塊BLOCK_HDR當(dāng)中。如果找到freeptr所在的內(nèi)存塊BLOCK_HDR，則通過BLOCK_HDR可以找到內(nèi)存片序列MEMORY_ARRAY。由于MEMORY_ARRAY中的內(nèi)存片是固定大小的，所以可以利用freeptr減去內(nèi)存片序列MEMORY_ARRAY的首地址再除以每一個內(nèi)存片的大小N得到freeptr在內(nèi)存片序列MEMORY_ARRAY中的索引，通過這個索引找到內(nèi)存管理信息CusMan中的bitmap成員變量，將與索引對應(yīng)的bit設(shè)置為0即可。然后測試該CusMan中的bitmap中的bit位是否全部為0。如果全部為0，則表明節(jié)點node所在的整個內(nèi)存塊BLOCK_HDR都是空閑的，因此調(diào)用系統(tǒng)的內(nèi)存回收函數(shù)free將整個內(nèi)存塊回收。

如果遍歷memlist并沒有找到freeptr所在的內(nèi)存塊，則表明freeptr所保存的內(nèi)存是利用全局的malloc函數(shù)直接進(jìn)行分配的。則直接利用系統(tǒng)的內(nèi)存回收函數(shù)free進(jìn)行回收即可。

4　總結(jié)

通過在系統(tǒng)內(nèi)存管理上面增加新的內(nèi)存管理層來管理固定大小的內(nèi)存分配，可以顯著降低系統(tǒng)的內(nèi)存碎片。同時，系統(tǒng)中的全局內(nèi)存鏈表長度變短，使得內(nèi)存分配過程中搜索時間復(fù)雜度降低。改進(jìn)之后的內(nèi)存管理系統(tǒng)利用了CPU擅長處理的數(shù)字和邏輯計算，所以在新增加的內(nèi)存分配和回收的過程當(dāng)中的內(nèi)存管理位圖的測試處理不會消耗太多時間。同時，由于整個系統(tǒng)當(dāng)中小內(nèi)存塊的數(shù)目降低，使得memSysPartition的成員變量freelist的長度降低了一個數(shù)量級，從而系統(tǒng)分配的遍歷的效率會大大升高。而內(nèi)存管理信息由原來的32個BLOCK_HDR降低為一個BLOCK_HDR加1個32位的內(nèi)存管理位圖和一個DL_NODE，顯著的增加有效內(nèi)存的比例。同時內(nèi)存碎片的減少會提高系統(tǒng)的穩(wěn)定性。

參考文獻(xiàn)

[1]陳京,王曉冬,黃標(biāo),丁家昕.一種誤差可控的地圖邊界線的等距線計算方法[J].計算機工程與應(yīng)用.

[2]王鵬,邱天爽,李景春,譚海峰.基于四階累積量的近場源多參數(shù)聯(lián)合估計[J].大連理工大學(xué)學(xué)報,2015(06).

[3]方箭,魯俊,朱穎,李芃芃.全球數(shù)字紅利頻譜釋放現(xiàn)狀及展望[J].電訊技術(shù),2015(12).

李彥峰（1982-），山東德州人，碩士研究生，中級職稱，研究方向：軟件工程嵌入式系統(tǒng)。

作者簡介：