VxWorks實時操作系統內存分配算法優化

中國科學院軟件研究所 李彥峰 李麗穎山東農村信用社聯合社 韓廣志金陵科技學院 徐尚喻

?

VxWorks實時操作系統內存分配算法優化

中國科學院軟件研究所 李彥峰 李麗穎
山東農村信用社聯合社 韓廣志
金陵科技學院 徐尚喻

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

【關鍵詞】內存分配；位圖管理；內存碎片；分配效率

0　引言

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

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

1　固定大小內存分配

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

2　優化內存分配算法

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

3　具體實現

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

當內存分配請求大于sizeof（MEMORY_SLICE）時，直接調用malloc函數實現內存的分配而無需經過我們的內存分配；反之，則首先將內存分配請求大小調整到大小為sizeof（MEMORY_SLICE），然后遍歷memlist鏈表，直到找到可用的BLOCK_HDR或者達到memlist鏈表表尾。

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

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

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

如果遍歷memlist并沒有找到freeptr所在的內存塊，則表明freeptr所保存的內存是利用全局的malloc函數直接進行分配的。則直接利用系統的內存回收函數free進行回收即可。

4　總結

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

參考文獻

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

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

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

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

作者簡介：