王兆文,蔣澤軍,陳進(jìn)朝
(西北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院,西安710129)
一種提高Linux內(nèi)存管理實(shí)時(shí)性的設(shè)計(jì)方案
王兆文,蔣澤軍,陳進(jìn)朝
(西北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院,西安710129)
針對(duì)Linux系統(tǒng)在內(nèi)存管理方面實(shí)時(shí)性支持不夠的問題,設(shè)計(jì)一種提高Linux內(nèi)存管理實(shí)時(shí)性的方案。從3個(gè)方面改進(jìn)Linux系統(tǒng)內(nèi)存管理的實(shí)時(shí)性,包括建立內(nèi)存映射來減少用戶態(tài)和內(nèi)核態(tài)之間的模式轉(zhuǎn)換,將內(nèi)存鎖定避免換頁操作,改進(jìn)系統(tǒng)原有的內(nèi)存管理算法來消除內(nèi)存操作的不確定性。改進(jìn)后的內(nèi)存管理算法基于分區(qū)管理和最佳適配的原理,時(shí)間復(fù)雜度為O(1)。實(shí)驗(yàn)結(jié)果表明,該方案可以提高Linux內(nèi)存管理的時(shí)間性能,特別是在內(nèi)存使用緊張的環(huán)境下效果更加明顯,性能提高率可達(dá)49.5%,能夠滿足實(shí)時(shí)性的要求。
Linux系統(tǒng);實(shí)時(shí)性;內(nèi)存映射;內(nèi)存鎖定;內(nèi)存管理算法;分區(qū)管理
隨著信息技術(shù)的飛速發(fā)展,實(shí)時(shí)系統(tǒng)得到了越來越廣泛和深入的應(yīng)用。實(shí)時(shí)性的含義并不意味著“快”,它是指系統(tǒng)的時(shí)間響應(yīng)特性。具體主要有以下3個(gè)要求:(1)時(shí)間約束,任務(wù)響應(yīng)時(shí)間在要求的期限內(nèi)。(2)可預(yù)測性,任務(wù)的執(zhí)行時(shí)間可以預(yù)先判斷,是有界的,沒有不確定因素影響。(3)可靠性。
Linux2.6系統(tǒng)在實(shí)時(shí)性方面做了許多改進(jìn),但是在內(nèi)核可搶占性、中斷機(jī)制、虛擬內(nèi)存技術(shù)等方面還是不能滿足越來越高的實(shí)時(shí)要求[1],特別是在內(nèi)存管理方面,Linux更注重于空間效率與時(shí)間效率的平衡,對(duì)實(shí)時(shí)性的支持還不夠完善。需要深入分析影響內(nèi)存管理實(shí)時(shí)性的原因并對(duì)其加以改進(jìn)。因此,本文設(shè)計(jì)一種提高 Linux內(nèi)存管理實(shí)時(shí)性的方案。
Linux在內(nèi)存管理方面影響系統(tǒng)實(shí)時(shí)性的因素主要有以下3個(gè)方面:
(1)用戶態(tài)和內(nèi)核態(tài)之間的模式轉(zhuǎn)換
在Linux中,實(shí)時(shí)任務(wù)運(yùn)行在用戶態(tài),而出于系統(tǒng)安全的目的,用戶態(tài)和內(nèi)核態(tài)之間的程序不能直接通信。當(dāng)有數(shù)據(jù)需要傳輸和處理時(shí),系統(tǒng)需要不斷地在用戶態(tài)和內(nèi)核態(tài)之間切換,不斷復(fù)制數(shù)據(jù),這樣就增加了任務(wù)完成時(shí)間,有可能造成超時(shí)。
(2)頁面交換機(jī)制
Linux采用了虛擬內(nèi)存技術(shù),當(dāng)系統(tǒng)需要更多內(nèi)存時(shí),它將暫時(shí)不使用的頁面從內(nèi)存換出到磁盤,增大可用內(nèi)存空間,然后再將需要使用的頁面換入到內(nèi)存中,這就是頁面交換機(jī)制[2]。對(duì)于實(shí)時(shí)任務(wù)而言,缺頁換頁操作會(huì)帶來延時(shí),更重要的是,它會(huì)帶來操作時(shí)間的不確定,而這些對(duì)實(shí)時(shí)任務(wù)來說都是不能容忍的。
(3)內(nèi)存操作的不確定因素
應(yīng)用程序在調(diào)用 malloc/free函數(shù)進(jìn)行內(nèi)存申請(qǐng)/釋放時(shí),系統(tǒng)采用動(dòng)態(tài)內(nèi)存分配,即從堆上分配內(nèi)存[3],由于申請(qǐng)大小和申請(qǐng)釋放時(shí)機(jī)不同,當(dāng)頻繁進(jìn)行這些操作時(shí)會(huì)產(chǎn)生大量的內(nèi)存碎片,導(dǎo)致系統(tǒng)性能降低,花費(fèi)時(shí)間不確定。
針對(duì)以上非實(shí)時(shí)性因素,從3個(gè)方面改進(jìn)系統(tǒng)實(shí)時(shí)性:
(1)建立虛擬地址和物理地址之間的映射,使得用戶層和內(nèi)核層之間的通信無需經(jīng)過模式轉(zhuǎn)換,避免模式轉(zhuǎn)換帶來的時(shí)間消耗。
(2)將內(nèi)存頁面鎖定在物理內(nèi)存中,使得實(shí)時(shí)任務(wù)不會(huì)產(chǎn)生缺頁換頁。
(3)改進(jìn)操作系統(tǒng)原有的內(nèi)存管理方法,設(shè)計(jì)新的內(nèi)存管理算法代替系統(tǒng)原有的方法,避免原內(nèi)存操作帶來的不確定性[4]。改進(jìn)方案如圖1所示。
圖1 內(nèi)存管理實(shí)時(shí)性的改進(jìn)方案
系統(tǒng)首先用kmalloc()函數(shù)在驅(qū)動(dòng)程序中申請(qǐng)足夠大的一塊內(nèi)存,之后每個(gè)用戶程序需要使用內(nèi)存時(shí),先對(duì)這塊區(qū)域進(jìn)行映射,然后用SetPageReserved ()函數(shù)將這塊內(nèi)存區(qū)域設(shè)置為保留(即內(nèi)存鎖定),用戶通過內(nèi)存管理模塊導(dǎo)出的用戶接口(分配(RTmalloc)、釋放(RTfree))來使用內(nèi)存。具體的內(nèi)存分配釋放算法由內(nèi)存管理模塊實(shí)現(xiàn),這部分功能對(duì)用戶是透明的,用戶程序通過用戶接口直接使用內(nèi)存。
3.1 內(nèi)存映射
進(jìn)程用戶空間的一部分可以和磁盤文件的某一部分或者設(shè)備文件相關(guān)聯(lián),因此,內(nèi)核把對(duì)線性區(qū)中頁內(nèi)某個(gè)字節(jié)的訪問轉(zhuǎn)換成文件中相應(yīng)字節(jié)的操作。這種技術(shù)稱為內(nèi)存映射[5]。進(jìn)程發(fā)出一個(gè)mmap()系統(tǒng)調(diào)用來創(chuàng)建一個(gè)新的內(nèi)存映射。一旦創(chuàng)建了這種映射,進(jìn)程就可以從這個(gè)新線性區(qū)的內(nèi)存單元讀取數(shù)據(jù),也就等價(jià)于讀取了文件中存放的數(shù)據(jù),如圖2所示。
圖2 內(nèi)存映射的原理
mmap()系統(tǒng)調(diào)用的原型:
void*mmap(void*addr,size_t length,int prot,int flags,int fd,off_t offsize);
返回值:成功則返回映射區(qū)起始地址。失敗則返回MAP_FAILED(-1)。
參數(shù):
addr:指定映射的起始地址;
length:將文件的多大長度映射到內(nèi)存;
prot:映射區(qū)的保護(hù)方式;
flags:映射對(duì)象的共享標(biāo)志;
fd:文件描述符,代表要映射的文件;
offset:以文件開始處的偏移量;
根據(jù)fd參數(shù)指向文件類型的不同,內(nèi)存映射可以分為不同的方式。當(dāng)fd指向類型為設(shè)備文件時(shí),為內(nèi)存映射設(shè)備方式[6];當(dāng)指向類型為普通磁盤文件時(shí),為內(nèi)存映射文件方式,2種方式的原理基本相同,但是實(shí)現(xiàn)方式有所不同,本文主要介紹內(nèi)存映射設(shè)備方式。
映射的實(shí)現(xiàn)過程:首先,驅(qū)動(dòng)程序先分配好一段內(nèi)存;接著,用戶進(jìn)程通過系統(tǒng)調(diào)用mmap()告訴內(nèi)核需要將多大的內(nèi)存映射到內(nèi)核空間,內(nèi)核經(jīng)過一系列處理后調(diào)用對(duì)應(yīng)的驅(qū)動(dòng)程序的file_operation結(jié)構(gòu)中的(*mmap)()方法,在該方法中調(diào)用remap_ pfn_range()方法建立映射關(guān)系,即建立映射區(qū)的頁表。簡單點(diǎn)說就是驅(qū)動(dòng)程序在(*mmap)()中利用remap_pfn_range()函數(shù)將內(nèi)核空間的一段內(nèi)存與用戶空間的一段內(nèi)存建立映射關(guān)系,如圖3所示。
圖3 內(nèi)存映射的實(shí)現(xiàn)過程
在不使用內(nèi)存映射的情況下,應(yīng)用程序使用read()/write()等函數(shù)與設(shè)備傳輸數(shù)據(jù),需要先切換到內(nèi)核模式,使用copy_to_user/copy_from_user等內(nèi)存復(fù)制函數(shù)將數(shù)據(jù)復(fù)制到內(nèi)核空間,然后輸出到設(shè)備。使用內(nèi)存映射以后,在應(yīng)用程序的進(jìn)程地址空間上映射了設(shè)備驅(qū)動(dòng)程序提供的物理地址,用戶程序就可以不用切換到內(nèi)核空間拷貝數(shù)據(jù)而直接訪問物理地址,這樣就大大提高了用戶程序訪問磁盤文件或者硬件設(shè)備的效率。
內(nèi)存映射通常應(yīng)用在那些內(nèi)核和用戶空間需要快速大量交互數(shù)據(jù)的情況下,特別是那些對(duì)實(shí)時(shí)性要求較強(qiáng)的應(yīng)用。實(shí)際上,它是把內(nèi)核中特定部分的內(nèi)存空間映射到用戶級(jí)程序的內(nèi)存空間去[7]。服務(wù)器需要對(duì)視頻內(nèi)存進(jìn)行大量數(shù)據(jù)交換,可以被看作是內(nèi)存映射用法的一個(gè)典型例子,它將視頻內(nèi)存直接映射到了用戶空間,而視頻內(nèi)存在內(nèi)核空間是有特定位置的。也就是說,內(nèi)存映射是為某個(gè)進(jìn)程映射特定的內(nèi)核空間區(qū)域,把這塊區(qū)域留作專用[8],因此,它對(duì)整個(gè)系統(tǒng)安全性的影響是很小的。
3.2 內(nèi)存鎖定
針對(duì)換頁操作帶來的延遲和不確定,采用內(nèi)存鎖定的方法加以解決。內(nèi)存鎖定是一種將進(jìn)程保留在內(nèi)存而不產(chǎn)生頁面交換的方法,它允許程序在物理內(nèi)存上鎖住它的部分或全部地址空間。內(nèi)存鎖定以頁為基本單位,被指定區(qū)間所包含的每個(gè)內(nèi)存頁都會(huì)被鎖定。Linux提供了內(nèi)存鎖定和解鎖的API,用戶程序中可使用mlock()/munlock()函數(shù),驅(qū)動(dòng)程序中可使用 SetPageReserved()/ClearPageReserved()函數(shù)[9]。內(nèi)存鎖定可以有效解決換頁操作帶來的延遲和不確定,但是要避免同時(shí)鎖定大量的內(nèi)存頁面,否則將會(huì)因?yàn)閮?nèi)存緊張而造成系統(tǒng)的整體性能降低。
3.3 對(duì)內(nèi)存管理算法的改進(jìn)
改進(jìn)后的內(nèi)存管理算法采用二級(jí)分區(qū)的思想,將之前鎖定的內(nèi)存區(qū)域分成若干個(gè)分區(qū),每個(gè)分區(qū)又分成若干大小相同的內(nèi)存單元,不同分區(qū)的內(nèi)存單元大小各不相同,系統(tǒng)以分區(qū)為單位來管理內(nèi)存,而用戶程序以單個(gè)內(nèi)存單元為單位來獲得和釋放內(nèi)存[10],每次收到用戶申請(qǐng)時(shí)系統(tǒng)找出大小最合適的一個(gè)空閑單元來滿足申請(qǐng),釋放時(shí)將其放回原來所屬的分區(qū)中。
系統(tǒng)使用m_partition結(jié)構(gòu)來表示每個(gè)分區(qū),這樣整個(gè)區(qū)域就可以用一個(gè)m_partition結(jié)構(gòu)數(shù)組來維護(hù),m_partition結(jié)構(gòu)中的空閑鏈表和已使用鏈表用來標(biāo)記各個(gè)分區(qū)中的內(nèi)存單元使用情況,其結(jié)構(gòu)示意圖如圖4所示。
系統(tǒng)還預(yù)留一部分空間作為備用空間,當(dāng)某個(gè)分區(qū)的內(nèi)存單元需求量很大不夠用時(shí),從備用空間補(bǔ)充分配一些空間給這個(gè)分區(qū);當(dāng)有個(gè)別用戶申請(qǐng)超過最大塊限制時(shí),直接從備用空間分配[11]。
圖4 分區(qū)的數(shù)據(jù)結(jié)構(gòu)示意圖
算法的運(yùn)行過程如下:
(1)初始化過程。系統(tǒng)先映射16 MB大小的內(nèi)存區(qū)域,將這塊區(qū)域分別以1 KB,4 KB,8 KB, 16 KB,32 KB,64 KB為單元分成6個(gè)不同的分區(qū),每個(gè)分區(qū)分成大小相同的若干單元并建立一個(gè)空閑鏈表和一個(gè)已使用鏈表。
(2)分配過程。用戶申請(qǐng)一塊內(nèi)存,系統(tǒng)根據(jù)用戶申請(qǐng)的大小確定從哪個(gè)分區(qū)中分配內(nèi)存單元,例如此時(shí)有一個(gè)用戶程序申請(qǐng)25 KB的內(nèi)存,因?yàn)?6<25<32,所以選擇從32 KB的分區(qū)中分配,將這個(gè)分區(qū)的空閑鏈表的第一個(gè)節(jié)點(diǎn)對(duì)應(yīng)的內(nèi)存單元首地址返回給用戶,將此節(jié)點(diǎn)從空閑鏈表刪除并插入到已使用鏈表尾部。
(3)使用過程。用戶程序使用內(nèi)存。
(4)釋放過程。使用完畢,將此節(jié)點(diǎn)單元從已使用鏈表刪除并插入空閑鏈表頭部。
采用這種管理方法的優(yōu)點(diǎn)是:(1)算法的原理與實(shí)現(xiàn)簡單。(2)響應(yīng)時(shí)間快,分配時(shí)分區(qū)查找時(shí)間是常數(shù)N(分區(qū)的數(shù)量,此時(shí)為6),其時(shí)間復(fù)雜度為O(1),單個(gè)鏈表節(jié)點(diǎn)的刪除和插入基本都在鏈表頭部或者尾部,不需要花費(fèi)過多的時(shí)間去查找定位。(3)時(shí)間性能穩(wěn)定可靠,分區(qū)查找時(shí)間和單個(gè)鏈表節(jié)點(diǎn)操作時(shí)間相對(duì)固定,整個(gè)過程沒有不確定因素影響。(4)因?yàn)槊看巫疃嘀环峙湟粋€(gè)單元,不存在外部碎片;同時(shí)每次查找大小最合適的內(nèi)存單元,所以內(nèi)部碎片也相對(duì)較少[12]。
分別對(duì)實(shí)時(shí)方案改進(jìn)前和改進(jìn)后申請(qǐng)相同大小內(nèi)存的性能進(jìn)行對(duì)比測試:改進(jìn)前,使用系統(tǒng)原有的malloc函數(shù)申請(qǐng)一塊內(nèi)存,并對(duì)其讀寫數(shù)據(jù),然后由free函數(shù)釋放這塊內(nèi)存,測試整個(gè)過程所花費(fèi)的時(shí)間;改進(jìn)后,使用RTmalloc函數(shù)申請(qǐng)同樣大小的內(nèi)存并且讀寫數(shù)據(jù),然后由RTfree函數(shù)釋放,測試所花費(fèi)的時(shí)間。
測試環(huán)境:處理器為Intel(R)Core(TM)2 Duo,頻率為2.70 GHz,物理內(nèi)存為2 GB,頁面交換空間為2 GB,操作系統(tǒng)為CentOS6.0(Linux3.6.0內(nèi)核)平臺(tái)。當(dāng)物理內(nèi)存使用率較高并且內(nèi)存碎片較多時(shí),系統(tǒng)原有的方法效率低下且花費(fèi)時(shí)間不確定。而改造方案中的內(nèi)存鎖定與內(nèi)存管理算法主要是解決這個(gè)問題的,因此,測試時(shí)制造了內(nèi)存緊張的環(huán)境,使內(nèi)存使用率達(dá)到90%,頁面交換率達(dá)到50%。
4.1 對(duì)不同大小內(nèi)存的測試
多次申請(qǐng)不同大小的內(nèi)存,測試結(jié)果如表1所示。對(duì)測試結(jié)果進(jìn)行對(duì)比,如圖5所示。
表1 方案改進(jìn)前后內(nèi)存性能測試結(jié)果
圖5 方案改進(jìn)前后耗費(fèi)時(shí)間平均值對(duì)比
4.2 對(duì)不同內(nèi)存環(huán)境的測試
在內(nèi)存緊張的環(huán)境下(內(nèi)存使用率90%,頁面交換率50%),申請(qǐng)16 KB大小內(nèi)存,測試方案改進(jìn)前后所花費(fèi)的時(shí)間結(jié)果如圖6所示。
圖6 內(nèi)存緊張環(huán)境下耗費(fèi)時(shí)間對(duì)比
在內(nèi)存不緊張的環(huán)境下(內(nèi)存使用率15%,頁面交換率0),申請(qǐng)16 KB大小內(nèi)存,測試方案改進(jìn)前后所花費(fèi)的時(shí)間結(jié)果如圖7所示。將不同環(huán)境的性能測試結(jié)果進(jìn)行對(duì)比,如表2所示。
圖7 內(nèi)存不緊張環(huán)境下耗費(fèi)時(shí)間對(duì)比
表2 不同環(huán)境下內(nèi)存性能測試時(shí)間平均值 μs
從實(shí)驗(yàn)結(jié)果可以看出,在對(duì)相同大小的內(nèi)存進(jìn)行多次分配、讀寫、釋放操作時(shí),當(dāng)內(nèi)存環(huán)境緊張時(shí),改進(jìn)后的方案所花費(fèi)的平均時(shí)間比改進(jìn)前所花費(fèi)的平均時(shí)間少,時(shí)間性能提高率最高可達(dá)49.5%,時(shí)間差的絕對(duì)值大,而且改進(jìn)后的時(shí)間穩(wěn)定性好;當(dāng)內(nèi)存環(huán)境不緊張時(shí),雖然改進(jìn)后的方案所花費(fèi)時(shí)間也比改進(jìn)前少,但是絕對(duì)值小,時(shí)間穩(wěn)定性對(duì)比效果也不明顯(因?yàn)楦倪M(jìn)前后都沒有頁面交換)。也就是說,內(nèi)存環(huán)境緊張時(shí),改進(jìn)方案的效果要比內(nèi)存環(huán)境不緊張時(shí)的效果更加明顯。
綜合起來看,改進(jìn)后的內(nèi)存方案較好地提高了Linux系統(tǒng)在內(nèi)存管理方面的實(shí)時(shí)性,可以應(yīng)用在對(duì)實(shí)時(shí)性要求較高的任務(wù)中。
本文提出了一種Linux系統(tǒng)內(nèi)存管理實(shí)時(shí)化改進(jìn)方案,主要通過內(nèi)存映射、內(nèi)存鎖定及新的內(nèi)存管理算法改進(jìn)內(nèi)存管理中的非實(shí)時(shí)性因素。實(shí)驗(yàn)測試結(jié)果表明,該方案能夠滿足Linux系統(tǒng)中實(shí)時(shí)任務(wù)對(duì)內(nèi)存操作的實(shí)時(shí)性要求,適用于系統(tǒng)內(nèi)存使用率高且又對(duì)實(shí)時(shí)性要求較高的場合。由于在內(nèi)存管理算法中初始化時(shí)限制了可分配內(nèi)存大小,使得該方案不夠靈活,下一步需要解決分配過程中可能出現(xiàn)的一些特殊情況,擴(kuò)大算法的適用范圍。
[1] 周保余,孔德剛,趙宏偉,等.嵌入式Linux實(shí)時(shí)性研究[J].吉林大學(xué)學(xué)報(bào):信息科學(xué)版,2011,29(4):339-340.
[2] Mauerer W.深入Linux內(nèi)核架構(gòu)[M].郭 旭,譯.北京:人民郵電出版社,2010.
[3] 楊 峰.基于Linux內(nèi)核的動(dòng)態(tài)內(nèi)存管理機(jī)制的實(shí)現(xiàn)[J].計(jì)算機(jī)工程,2010,36(9):85-86.
[4] Cwiklinski L,Kicinski W.Management of Memory in a Real-timeMeasurementSystem Based on a Signal Processor[J].Metrology and Measurement Systems,2010, (4):589-598.
[5] Bovet D P,Cesati M.深入理解 Linux內(nèi)核[M].陳莉君,張瓊聲,張宏偉,譯.3版.北京:中國電力出版社,2007.
[6] 任橋偉.Linux內(nèi)核修煉之道[M].北京:人民郵電出版社,2010.
[7] 康 華.Linux內(nèi)核空間與用戶空間信息交互方法[EB/OL].(2011-11-23).http://www.kerneltravel. net/jiaoliu/005.htm.
[8] 劉 斌,朱程榮.Linux內(nèi)核與用戶空間通信機(jī)制研究[J].電腦知識(shí)與技術(shù),2012,8(16):70-71,103.
[9] Gorman M.深入理解Linux虛擬內(nèi)存管理[M].北京:北京航空航天大學(xué)出版社,2006.
[10] 俞勤豐,孫 涌.μC/OS-Ⅱ中內(nèi)存管理方法的分析及改進(jìn)[J].計(jì)算機(jī)工程,2009,35(11):280-281.
[11] 王小銀,陳莉君.Linux內(nèi)核中內(nèi)存池的實(shí)現(xiàn)及應(yīng)用[J].西安郵電學(xué)院學(xué)報(bào),2011,16(4):40-43.
[12] 李滿麗.復(fù)雜嵌入式系統(tǒng)內(nèi)存管理方案的研究與實(shí)現(xiàn)[D].廈門:廈門大學(xué),2009.
編輯 顧逸斐
A Design Scheme for Improving Real-time Property of Memory Management in Linux
WANG Zhao-wen,JIANG Ze-jun,CHEN Jin-chao
(School of Computer Science,Northwestern Polytechnical University,Xi'an 710129,China)
To the problem of imperfection in real-time property of memory management under Linux system,this paper designs a solution to improve the timeliness.It works in three aspects:establishing a mapping relationship between virtual address and physical address to reduce the switch between the user mode and kernel mode,locking memory to avoid page exchanging,improving the original algorithm of memory management to remove the nondeterministic operations.The modified memory management algorithm is based on the principle of partitioned management and best fit,whose time complexity is O(1).Experimental results show that this solution is a good way to improve the performance of memory management,in the environment of memory tension,its effect is more obvious,and performance improvement rate can reach 49.5%.It meets the requirement of real-time.
Linux system;real-time property;memory mapping;memory locking;memory management algorithm; partitioned management
1000-3428(2014)09-0291-04
A
TP316.81
10.3969/j.issn.1000-3428.2014.09.058
航空科學(xué)基金資助項(xiàng)目(2012ZC53040);國家部委基金資助項(xiàng)目;西北工業(yè)大學(xué)研究生創(chuàng)業(yè)種子基金資助項(xiàng)目。
王兆文(1978-),男,工程師、碩士,主研方向:分布式實(shí)時(shí)嵌入式系統(tǒng);蔣澤軍,教授;陳進(jìn)朝,博士研究生。
2013-07-10
2013-09-17E-mail:xxkhw@tom.com