王兆文,蔣澤軍,陳進朝

(西北工業(yè)大學(xué)計算機學(xué)院,西安710129)

一種提高Linux內(nèi)存管理實時性的設(shè)計方案

王兆文,蔣澤軍,陳進朝

(西北工業(yè)大學(xué)計算機學(xué)院,西安710129)

針對Linux系統(tǒng)在內(nèi)存管理方面實時性支持不夠的問題,設(shè)計一種提高Linux內(nèi)存管理實時性的方案。從3個方面改進Linux系統(tǒng)內(nèi)存管理的實時性,包括建立內(nèi)存映射來減少用戶態(tài)和內(nèi)核態(tài)之間的模式轉(zhuǎn)換,將內(nèi)存鎖定避免換頁操作,改進系統(tǒng)原有的內(nèi)存管理算法來消除內(nèi)存操作的不確定性。改進后的內(nèi)存管理算法基于分區(qū)管理和最佳適配的原理,時間復(fù)雜度為O(1)。實驗結(jié)果表明,該方案可以提高Linux內(nèi)存管理的時間性能,特別是在內(nèi)存使用緊張的環(huán)境下效果更加明顯,性能提高率可達49.5%,能夠滿足實時性的要求。

Linux系統(tǒng);實時性;內(nèi)存映射;內(nèi)存鎖定;內(nèi)存管理算法;分區(qū)管理

1 概述

隨著信息技術(shù)的飛速發(fā)展,實時系統(tǒng)得到了越來越廣泛和深入的應(yīng)用。實時性的含義并不意味著“快”,它是指系統(tǒng)的時間響應(yīng)特性。具體主要有以下3個要求:(1)時間約束,任務(wù)響應(yīng)時間在要求的期限內(nèi)。(2)可預(yù)測性,任務(wù)的執(zhí)行時間可以預(yù)先判斷,是有界的,沒有不確定因素影響。(3)可靠性。

Linux2.6系統(tǒng)在實時性方面做了許多改進,但是在內(nèi)核可搶占性、中斷機制、虛擬內(nèi)存技術(shù)等方面還是不能滿足越來越高的實時要求[1],特別是在內(nèi)存管理方面,Linux更注重于空間效率與時間效率的平衡,對實時性的支持還不夠完善。需要深入分析影響內(nèi)存管理實時性的原因并對其加以改進。因此,本文設(shè)計一種提高 Linux內(nèi)存管理實時性的方案。

2 影響內(nèi)存管理實時性的因素分析

Linux在內(nèi)存管理方面影響系統(tǒng)實時性的因素主要有以下3個方面:

(1)用戶態(tài)和內(nèi)核態(tài)之間的模式轉(zhuǎn)換

在Linux中,實時任務(wù)運行在用戶態(tài),而出于系統(tǒng)安全的目的,用戶態(tài)和內(nèi)核態(tài)之間的程序不能直接通信。當有數(shù)據(jù)需要傳輸和處理時,系統(tǒng)需要不斷地在用戶態(tài)和內(nèi)核態(tài)之間切換,不斷復(fù)制數(shù)據(jù),這樣就增加了任務(wù)完成時間,有可能造成超時。

(2)頁面交換機制

Linux采用了虛擬內(nèi)存技術(shù),當系統(tǒng)需要更多內(nèi)存時,它將暫時不使用的頁面從內(nèi)存換出到磁盤,增大可用內(nèi)存空間,然后再將需要使用的頁面換入到內(nèi)存中,這就是頁面交換機制[2]。對于實時任務(wù)而言,缺頁換頁操作會帶來延時,更重要的是,它會帶來操作時間的不確定,而這些對實時任務(wù)來說都是不能容忍的。

(3)內(nèi)存操作的不確定因素

應(yīng)用程序在調(diào)用 malloc/free函數(shù)進行內(nèi)存申請/釋放時,系統(tǒng)采用動態(tài)內(nèi)存分配,即從堆上分配內(nèi)存[3],由于申請大小和申請釋放時機不同,當頻繁進行這些操作時會產(chǎn)生大量的內(nèi)存碎片,導(dǎo)致系統(tǒng)性能降低,花費時間不確定。

3 內(nèi)存管理實時性改進方案設(shè)計

針對以上非實時性因素,從3個方面改進系統(tǒng)實時性:

(1)建立虛擬地址和物理地址之間的映射,使得用戶層和內(nèi)核層之間的通信無需經(jīng)過模式轉(zhuǎn)換,避免模式轉(zhuǎn)換帶來的時間消耗。

(2)將內(nèi)存頁面鎖定在物理內(nèi)存中,使得實時任務(wù)不會產(chǎn)生缺頁換頁。

(3)改進操作系統(tǒng)原有的內(nèi)存管理方法,設(shè)計新的內(nèi)存管理算法代替系統(tǒng)原有的方法,避免原內(nèi)存操作帶來的不確定性[4]。改進方案如圖1所示。

圖1 內(nèi)存管理實時性的改進方案

系統(tǒng)首先用kmalloc()函數(shù)在驅(qū)動程序中申請足夠大的一塊內(nèi)存,之后每個用戶程序需要使用內(nèi)存時,先對這塊區(qū)域進行映射,然后用SetPageReserved ()函數(shù)將這塊內(nèi)存區(qū)域設(shè)置為保留(即內(nèi)存鎖定),用戶通過內(nèi)存管理模塊導(dǎo)出的用戶接口(分配(RTmalloc)、釋放(RTfree))來使用內(nèi)存。具體的內(nèi)存分配釋放算法由內(nèi)存管理模塊實現(xiàn),這部分功能對用戶是透明的,用戶程序通過用戶接口直接使用內(nèi)存。

3.1 內(nèi)存映射

進程用戶空間的一部分可以和磁盤文件的某一部分或者設(shè)備文件相關(guān)聯(lián),因此,內(nèi)核把對線性區(qū)中頁內(nèi)某個字節(jié)的訪問轉(zhuǎn)換成文件中相應(yīng)字節(jié)的操作。這種技術(shù)稱為內(nèi)存映射[5]。進程發(fā)出一個mmap()系統(tǒng)調(diào)用來創(chuàng)建一個新的內(nèi)存映射。一旦創(chuàng)建了這種映射,進程就可以從這個新線性區(qū)的內(nèi)存單元讀取數(shù)據(jù),也就等價于讀取了文件中存放的數(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ū)的保護方式;

flags:映射對象的共享標志;

fd:文件描述符,代表要映射的文件;

offset:以文件開始處的偏移量;

根據(jù)fd參數(shù)指向文件類型的不同,內(nèi)存映射可以分為不同的方式。當fd指向類型為設(shè)備文件時,為內(nèi)存映射設(shè)備方式[6];當指向類型為普通磁盤文件時,為內(nèi)存映射文件方式,2種方式的原理基本相同,但是實現(xiàn)方式有所不同,本文主要介紹內(nèi)存映射設(shè)備方式。

映射的實現(xiàn)過程:首先,驅(qū)動程序先分配好一段內(nèi)存;接著,用戶進程通過系統(tǒng)調(diào)用mmap()告訴內(nèi)核需要將多大的內(nèi)存映射到內(nèi)核空間,內(nèi)核經(jīng)過一系列處理后調(diào)用對應(yīng)的驅(qū)動程序的file_operation結(jié)構(gòu)中的(*mmap)()方法,在該方法中調(diào)用remap_ pfn_range()方法建立映射關(guān)系,即建立映射區(qū)的頁表。簡單點說就是驅(qū)動程序在(*mmap)()中利用remap_pfn_range()函數(shù)將內(nèi)核空間的一段內(nèi)存與用戶空間的一段內(nèi)存建立映射關(guān)系,如圖3所示。

圖3 內(nèi)存映射的實現(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)用程序的進程地址空間上映射了設(shè)備驅(qū)動程序提供的物理地址,用戶程序就可以不用切換到內(nèi)核空間拷貝數(shù)據(jù)而直接訪問物理地址,這樣就大大提高了用戶程序訪問磁盤文件或者硬件設(shè)備的效率。

內(nèi)存映射通常應(yīng)用在那些內(nèi)核和用戶空間需要快速大量交互數(shù)據(jù)的情況下,特別是那些對實時性要求較強的應(yīng)用。實際上,它是把內(nèi)核中特定部分的內(nèi)存空間映射到用戶級程序的內(nèi)存空間去[7]。服務(wù)器需要對視頻內(nèi)存進行大量數(shù)據(jù)交換,可以被看作是內(nèi)存映射用法的一個典型例子,它將視頻內(nèi)存直接映射到了用戶空間,而視頻內(nèi)存在內(nèi)核空間是有特定位置的。也就是說,內(nèi)存映射是為某個進程映射特定的內(nèi)核空間區(qū)域,把這塊區(qū)域留作專用[8],因此,它對整個系統(tǒng)安全性的影響是很小的。

3.2 內(nèi)存鎖定

針對換頁操作帶來的延遲和不確定,采用內(nèi)存鎖定的方法加以解決。內(nèi)存鎖定是一種將進程保留在內(nèi)存而不產(chǎn)生頁面交換的方法,它允許程序在物理內(nèi)存上鎖住它的部分或全部地址空間。內(nèi)存鎖定以頁為基本單位,被指定區(qū)間所包含的每個內(nèi)存頁都會被鎖定。Linux提供了內(nèi)存鎖定和解鎖的API,用戶程序中可使用mlock()/munlock()函數(shù),驅(qū)動程序中可使用 SetPageReserved()/ClearPageReserved()函數(shù)[9]。內(nèi)存鎖定可以有效解決換頁操作帶來的延遲和不確定,但是要避免同時鎖定大量的內(nèi)存頁面,否則將會因為內(nèi)存緊張而造成系統(tǒng)的整體性能降低。

3.3 對內(nèi)存管理算法的改進

改進后的內(nèi)存管理算法采用二級分區(qū)的思想,將之前鎖定的內(nèi)存區(qū)域分成若干個分區(qū),每個分區(qū)又分成若干大小相同的內(nèi)存單元,不同分區(qū)的內(nèi)存單元大小各不相同,系統(tǒng)以分區(qū)為單位來管理內(nèi)存,而用戶程序以單個內(nèi)存單元為單位來獲得和釋放內(nèi)存[10],每次收到用戶申請時系統(tǒng)找出大小最合適的一個空閑單元來滿足申請,釋放時將其放回原來所屬的分區(qū)中。

系統(tǒng)使用m_partition結(jié)構(gòu)來表示每個分區(qū),這樣整個區(qū)域就可以用一個m_partition結(jié)構(gòu)數(shù)組來維護,m_partition結(jié)構(gòu)中的空閑鏈表和已使用鏈表用來標記各個分區(qū)中的內(nèi)存單元使用情況,其結(jié)構(gòu)示意圖如圖4所示。

系統(tǒng)還預(yù)留一部分空間作為備用空間,當某個分區(qū)的內(nèi)存單元需求量很大不夠用時,從備用空間補充分配一些空間給這個分區(qū);當有個別用戶申請超過最大塊限制時,直接從備用空間分配[11]。

圖4 分區(qū)的數(shù)據(jù)結(jié)構(gòu)示意圖

算法的運行過程如下:

(1)初始化過程。系統(tǒng)先映射16 MB大小的內(nèi)存區(qū)域,將這塊區(qū)域分別以1 KB,4 KB,8 KB, 16 KB,32 KB,64 KB為單元分成6個不同的分區(qū),每個分區(qū)分成大小相同的若干單元并建立一個空閑鏈表和一個已使用鏈表。

(2)分配過程。用戶申請一塊內(nèi)存,系統(tǒng)根據(jù)用戶申請的大小確定從哪個分區(qū)中分配內(nèi)存單元,例如此時有一個用戶程序申請25 KB的內(nèi)存,因為16＜25＜32,所以選擇從32 KB的分區(qū)中分配,將這個分區(qū)的空閑鏈表的第一個節(jié)點對應(yīng)的內(nèi)存單元首地址返回給用戶,將此節(jié)點從空閑鏈表刪除并插入到已使用鏈表尾部。

(3)使用過程。用戶程序使用內(nèi)存。

(4)釋放過程。使用完畢,將此節(jié)點單元從已使用鏈表刪除并插入空閑鏈表頭部。

采用這種管理方法的優(yōu)點是:(1)算法的原理與實現(xiàn)簡單。(2)響應(yīng)時間快,分配時分區(qū)查找時間是常數(shù)N(分區(qū)的數(shù)量,此時為6),其時間復(fù)雜度為O(1),單個鏈表節(jié)點的刪除和插入基本都在鏈表頭部或者尾部,不需要花費過多的時間去查找定位。(3)時間性能穩(wěn)定可靠,分區(qū)查找時間和單個鏈表節(jié)點操作時間相對固定,整個過程沒有不確定因素影響。(4)因為每次最多只分配一個單元,不存在外部碎片;同時每次查找大小最合適的內(nèi)存單元,所以內(nèi)部碎片也相對較少[12]。

4 性能測試與結(jié)果分析

分別對實時方案改進前和改進后申請相同大小內(nèi)存的性能進行對比測試:改進前,使用系統(tǒng)原有的malloc函數(shù)申請一塊內(nèi)存,并對其讀寫數(shù)據(jù),然后由free函數(shù)釋放這塊內(nèi)存,測試整個過程所花費的時間;改進后,使用RTmalloc函數(shù)申請同樣大小的內(nèi)存并且讀寫數(shù)據(jù),然后由RTfree函數(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)核)平臺。當物理內(nèi)存使用率較高并且內(nèi)存碎片較多時,系統(tǒng)原有的方法效率低下且花費時間不確定。而改造方案中的內(nèi)存鎖定與內(nèi)存管理算法主要是解決這個問題的,因此,測試時制造了內(nèi)存緊張的環(huán)境,使內(nèi)存使用率達到90%,頁面交換率達到50%。

4.1 對不同大小內(nèi)存的測試

多次申請不同大小的內(nèi)存,測試結(jié)果如表1所示。對測試結(jié)果進行對比,如圖5所示。

表1 方案改進前后內(nèi)存性能測試結(jié)果

圖5 方案改進前后耗費時間平均值對比

4.2 對不同內(nèi)存環(huán)境的測試

在內(nèi)存緊張的環(huán)境下(內(nèi)存使用率90%,頁面交換率50%),申請16 KB大小內(nèi)存,測試方案改進前后所花費的時間結(jié)果如圖6所示。

圖6 內(nèi)存緊張環(huán)境下耗費時間對比

在內(nèi)存不緊張的環(huán)境下(內(nèi)存使用率15%,頁面交換率0),申請16 KB大小內(nèi)存,測試方案改進前后所花費的時間結(jié)果如圖7所示。將不同環(huán)境的性能測試結(jié)果進行對比,如表2所示。

圖7 內(nèi)存不緊張環(huán)境下耗費時間對比

表2 不同環(huán)境下內(nèi)存性能測試時間平均值 μs

從實驗結(jié)果可以看出,在對相同大小的內(nèi)存進行多次分配、讀寫、釋放操作時,當內(nèi)存環(huán)境緊張時,改進后的方案所花費的平均時間比改進前所花費的平均時間少,時間性能提高率最高可達49.5%,時間差的絕對值大,而且改進后的時間穩(wěn)定性好;當內(nèi)存環(huán)境不緊張時,雖然改進后的方案所花費時間也比改進前少,但是絕對值小,時間穩(wěn)定性對比效果也不明顯(因為改進前后都沒有頁面交換)。也就是說,內(nèi)存環(huán)境緊張時,改進方案的效果要比內(nèi)存環(huán)境不緊張時的效果更加明顯。

綜合起來看,改進后的內(nèi)存方案較好地提高了Linux系統(tǒng)在內(nèi)存管理方面的實時性,可以應(yīng)用在對實時性要求較高的任務(wù)中。

5 結(jié)束語

本文提出了一種Linux系統(tǒng)內(nèi)存管理實時化改進方案,主要通過內(nèi)存映射、內(nèi)存鎖定及新的內(nèi)存管理算法改進內(nèi)存管理中的非實時性因素。實驗測試結(jié)果表明,該方案能夠滿足Linux系統(tǒng)中實時任務(wù)對內(nèi)存操作的實時性要求,適用于系統(tǒng)內(nèi)存使用率高且又對實時性要求較高的場合。由于在內(nèi)存管理算法中初始化時限制了可分配內(nèi)存大小,使得該方案不夠靈活,下一步需要解決分配過程中可能出現(xiàn)的一些特殊情況,擴大算法的適用范圍。

[1] 周保余,孔德剛,趙宏偉,等.嵌入式Linux實時性研究[J].吉林大學(xué)學(xué)報:信息科學(xué)版,2011,29(4):339-340.

[2] Mauerer W.深入Linux內(nèi)核架構(gòu)[M].郭 旭,譯.北京:人民郵電出版社,2010.

[3] 楊 峰.基于Linux內(nèi)核的動態(tài)內(nèi)存管理機制的實現(xiàn)[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].電腦知識與技術(shù),2012,8(16):70-71,103.

[9] Gorman M.深入理解Linux虛擬內(nèi)存管理[M].北京:北京航空航天大學(xué)出版社,2006.

[10] 俞勤豐,孫 涌.μC/OS-Ⅱ中內(nèi)存管理方法的分析及改進[J].計算機工程,2009,35(11):280-281.

[11] 王小銀,陳莉君.Linux內(nèi)核中內(nèi)存池的實現(xiàn)及應(yīng)用[J].西安郵電學(xué)院學(xué)報,2011,16(4):40-43.

[12] 李滿麗.復(fù)雜嵌入式系統(tǒng)內(nèi)存管理方案的研究與實現(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é)基金資助項目(2012ZC53040);國家部委基金資助項目;西北工業(yè)大學(xué)研究生創(chuàng)業(yè)種子基金資助項目。

王兆文(1978-),男,工程師、碩士,主研方向:分布式實時嵌入式系統(tǒng);蔣澤軍,教授;陳進朝,博士研究生。

2013-07-10

2013-09-17E-mail:xxkhw@tom.com