中國(guó)科學(xué)院軟件研究所 李彥峰 李麗穎山東農(nóng)村信用社聯(lián)合社 韓廣志金陵科技學(xué)院 徐尚喻
?
VxWorks實(shí)時(shí)操作系統(tǒng)內(nèi)存分配算法優(yōu)化
中國(guó)科學(xué)院軟件研究所 李彥峰 李麗穎
山東農(nóng)村信用社聯(lián)合社 韓廣志
金陵科技學(xué)院 徐尚喻
【摘要】通過(guò)研究VxWorks實(shí)時(shí)系統(tǒng)內(nèi)存分配算法,發(fā)現(xiàn)VxWorks的內(nèi)存管理算法的局限性。本文提出通過(guò)在VxWorks實(shí)時(shí)操作系統(tǒng)原有的內(nèi)存管理功能上添加功能,用于實(shí)現(xiàn)固定大小內(nèi)存分配。新增加的功能利用位圖管理內(nèi)存,通過(guò)降低內(nèi)存管理信息占整個(gè)內(nèi)存塊的比率提高內(nèi)存使用效率,通過(guò)將固定大小的內(nèi)存片合并為一組進(jìn)行整體的內(nèi)存分配來(lái)降低內(nèi)存碎片;同時(shí)由于減少了內(nèi)存碎片,從而間接提高內(nèi)存的分配速度。
【關(guān)鍵詞】?jī)?nèi)存分配;位圖管理;內(nèi)存碎片;分配效率
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)存通過(guò)這個(gè)結(jié)構(gòu)體的成員變量freelist鏈接起來(lái)。VxWorks原有的內(nèi)存分配實(shí)現(xiàn)相對(duì)而言比較簡(jiǎn)單——所有任務(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)中來(lái)滿足內(nèi)存分配請(qǐng)求,而內(nèi)存回收時(shí)則會(huì)將相鄰地址的空閑內(nèi)存給聚合成一個(gè)更大的空閑內(nèi)存。
VxWorks的以上內(nèi)存分配設(shè)計(jì)沒(méi)有考慮小內(nèi)存分配請(qǐng)求的優(yōu)化,很容易導(dǎo)致下列問(wèn)題:第一,當(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)存過(guò)多時(shí),整個(gè)鏈表長(zhǎng)度會(huì)很長(zhǎng),從而使得鏈表的搜索時(shí)間效率降低。第三,整個(gè)系統(tǒng)中,一個(gè)內(nèi)存塊(BLOCK)就有一個(gè)管理信息,小內(nèi)存分配會(huì)出現(xiàn)管理信息站用大量?jī)?nèi)存空閑的情況。第四,由于所有的內(nèi)存分配都要競(jìng)爭(zhēng)系統(tǒng)內(nèi)存分區(qū)memSysPartition的保護(hù)鎖,導(dǎo)致系統(tǒng)的運(yùn)行變慢,降低系統(tǒng)的效率。
基于上面的考慮,我們的改進(jìn)通過(guò)在現(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)原來(lái)每個(gè)小的內(nèi)存片都需要一個(gè)BLOCK_HDR的管理信息,現(xiàn)在多個(gè)內(nèi)存片共享一個(gè)BLOCK_HDR的管理信息;而B(niǎo)LOCK_HDR內(nèi)部的內(nèi)存片序列中的內(nèi)存片MEMORY_SLICE則通過(guò)較小的內(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)定性。
算法的主要實(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)存管理信息,利用位圖管理思想來(lá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語(yǔ)言中的整形數(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)過(guò)調(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通過(guò)DL_NODE鏈接到鏈表memlist中。
根據(jù)上面的實(shí)現(xiàn)思想,在VxWorks操作系統(tǒng)中實(shí)現(xiàn)小內(nèi)存轉(zhuǎn)化為固定大小的小內(nèi)存的管理,需要增加一個(gè)全局的DL_LIST變量memlist,通過(guò)memlist變量將包含內(nèi)存片序列的BLOCK_HDR鏈接起來(lái);同時(shí)為了實(shí)現(xiàn)VxWorks系統(tǒng)下面的多任務(wù)訪問(wèn)還需要額外的SEMPHORE信號(hào)量來(lái)輔助實(shí)現(xiàn)memlist的互斥訪問(wèn),在代碼當(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)存的分配而無(wú)需經(jīng)過(guò)我們的內(nèi)存分配;反之,則首先將內(nèi)存分配請(qǐng)求大小調(diào)整到大小為sizeof(MEMORY_SLICE),然后遍歷memlist鏈表,直到找到可用的BLOCK_HDR或者達(dá)到memlist鏈表表尾。
增加上訴定義來(lái)簡(jiǎn)化理解,其中CusMan用于管理內(nèi)存片序列MEMORY_ARRAY,bitmap用于內(nèi)存的位圖管理,node用于連接到全局的鏈表memlist中。遍歷的過(guò)程中,通過(guò)memlist得到鏈表節(jié)點(diǎn)node,將node指針強(qiáng)制轉(zhuǎn)化為CusMan類型的指針cusmanptr。通過(guò)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á)鏈表表尾并終止遍歷過(guò)程。如果遍歷到達(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的處理過(guò)程,首先通過(guò)節(jié)點(diǎn)node找到CusMan指針,然后通過(guò)CusMan指針找到成員變量bitmap。通過(guò)位測(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,通過(guò)DL_NODE可以得到內(nèi)存序列MEMORY_ARRAY。根據(jù)比較需要回收的內(nèi)存地址freeptr和內(nèi)存序列所包含的地址范圍來(lái)判斷freeptr是否落在包含該節(jié)點(diǎn)的內(nèi)存塊BLOCK_HDR當(dāng)中。如果找到freeptr所在的內(nèi)存塊BLOCK_HDR,則通過(guò)BLOCK_HDR可以找到內(nèi)存片序列MEMORY_ARRAY。由于MEMORY_ARRAY中的內(nèi)存片是固定大小的,所以可以利用freeptr減去內(nèi)存片序列MEMORY_ARRAY的首地址再除以每一個(gè)內(nèi)存片的大小N得到freeptr在內(nèi)存片序列MEMORY_ARRAY中的索引,通過(guò)這個(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并沒(méi)有找到freeptr所在的內(nèi)存塊,則表明freeptr所保存的內(nèi)存是利用全局的malloc函數(shù)直接進(jìn)行分配的。則直接利用系統(tǒng)的內(nèi)存回收函數(shù)free進(jìn)行回收即可。
通過(guò)在系統(tǒng)內(nèi)存管理上面增加新的內(nèi)存管理層來(lái)管理固定大小的內(nèi)存分配,可以顯著降低系統(tǒng)的內(nèi)存碎片。同時(shí),系統(tǒng)中的全局內(nèi)存鏈表長(zhǎng)度變短,使得內(nèi)存分配過(guò)程中搜索時(shí)間復(fù)雜度降低。改進(jìn)之后的內(nèi)存管理系統(tǒng)利用了CPU擅長(zhǎng)處理的數(shù)字和邏輯計(jì)算,所以在新增加的內(nèi)存分配和回收的過(guò)程當(dāng)中的內(nèi)存管理位圖的測(cè)試處理不會(huì)消耗太多時(shí)間。同時(shí),由于整個(gè)系統(tǒng)當(dāng)中小內(nèi)存塊的數(shù)目降低,使得memSysPartition的成員變量freelist的長(zhǎng)度降低了一個(gè)數(shù)量級(jí),從而系統(tǒng)分配的遍歷的效率會(huì)大大升高。而內(nèi)存管理信息由原來(lá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]王鵬,邱天爽,李景春,譚海峰.基于四階累積量的近場(chǎng)源多參數(shù)聯(lián)合估計(jì)[J].大連理工大學(xué)學(xué)報(bào),2015(06).
[3]方箭,魯俊,朱穎,李芃芃.全球數(shù)字紅利頻譜釋放現(xiàn)狀及展望[J].電訊技術(shù),2015(12).
李彥峰(1982-),山東德州人,碩士研究生,中級(jí)職稱,研究方向:軟件工程嵌入式系統(tǒng)。
作者簡(jiǎn)介: