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

?

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

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

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

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

0　引言

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

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

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

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

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

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

3　具體實(shí)現(xiàn)

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

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

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

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

由于分配的時(shí)候出現(xiàn)的調(diào)整，所以在釋放的時(shí)候也需要相應(yīng)的改變。在內(nèi)存釋放時(shí)，取下memlist鏈表當(dāng)中的內(nèi)存塊節(jié)點(diǎn)DL_NODE，通過DL_NODE可以得到內(nèi)存序列MEMORY_ARRAY。根據(jù)比較需要回收的內(nèi)存地址freeptr和內(nèi)存序列所包含的地址范圍來判斷freeptr是否落在包含該節(jié)點(diǎn)的內(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的首地址再除以每一個(gè)內(nèi)存片的大小N得到freeptr在內(nèi)存片序列MEMORY_ARRAY中的索引，通過這個(gè)索引找到內(nèi)存管理信息CusMan中的bitmap成員變量，將與索引對(duì)應(yīng)的bit設(shè)置為0即可。然后測(cè)試該CusMan中的bitmap中的bit位是否全部為0。如果全部為0，則表明節(jié)點(diǎn)node所在的整個(gè)內(nèi)存塊BLOCK_HDR都是空閑的，因此調(diào)用系統(tǒng)的內(nèi)存回收函數(shù)free將整個(gè)內(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)存碎片。同時(shí)，系統(tǒng)中的全局內(nèi)存鏈表長度變短，使得內(nèi)存分配過程中搜索時(shí)間復(fù)雜度降低。改進(jìn)之后的內(nèi)存管理系統(tǒng)利用了CPU擅長處理的數(shù)字和邏輯計(jì)算，所以在新增加的內(nèi)存分配和回收的過程當(dāng)中的內(nèi)存管理位圖的測(cè)試處理不會(huì)消耗太多時(shí)間。同時(shí)，由于整個(gè)系統(tǒng)當(dāng)中小內(nèi)存塊的數(shù)目降低，使得memSysPartition的成員變量freelist的長度降低了一個(gè)數(shù)量級(jí)，從而系統(tǒng)分配的遍歷的效率會(huì)大大升高。而內(nèi)存管理信息由原來的32個(gè)BLOCK_HDR降低為一個(gè)BLOCK_HDR加1個(gè)32位的內(nèi)存管理位圖和一個(gè)DL_NODE，顯著的增加有效內(nèi)存的比例。同時(shí)內(nèi)存碎片的減少會(huì)提高系統(tǒng)的穩(wěn)定性。

參考文獻(xiàn)

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

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

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

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

作者簡介：