嵌入式Linux內(nèi)存管理的優(yōu)化

嵌入式Linux內(nèi)存管理的優(yōu)化

于國龍a,b, 崔忠偉a,b, 左羽a,b

(貴州師范學(xué)院a.數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院;b.貴州省高校工業(yè)物聯(lián)網(wǎng)工程技術(shù)研究中心, 貴陽550018)

摘要：內(nèi)存管理是影響嵌入式Linux實時性的一個關(guān)鍵因素，為了提高嵌入式Linux的實時性，對其內(nèi)存管理進(jìn)行了優(yōu)化。首先為系統(tǒng)中的重要任務(wù)分配了專用的內(nèi)存區(qū)域，使重要任務(wù)在內(nèi)存不足時不被置換出去，以保障重要任務(wù)優(yōu)先執(zhí)行；然后通過利用系統(tǒng)空閑時間來掃描系統(tǒng)內(nèi)存的方法，使得任務(wù)在執(zhí)行時盡量減少缺頁中斷的發(fā)生，從而提高系統(tǒng)的實時性；最后通過實驗對比OPT最優(yōu)算法、LRU算法、優(yōu)化后的LUR算法的缺頁中斷數(shù)和任務(wù)截止期錯失率，發(fā)現(xiàn)優(yōu)化后的LUR算法的缺頁中斷數(shù)和任務(wù)截止期錯失率在三者中最低，說明通過以上的內(nèi)存優(yōu)化方法使得嵌入式Linux的實時性得到了提高。

關(guān)鍵詞：嵌入式Linux;實時性;重要任務(wù);頁面置換;缺頁中斷

文章編號：1673-1549(2015)04-0033-04

DOI:10.11863/j.suse.2015.04.07

收稿日期:2015-06-01

基金項目:貴陽市科技計劃項目( 筑科合同［2013101］10-6) ; 貴州師范學(xué)院校級項目( 14ZC009)

作者簡介:于國龍(1981-)，男，遼寧丹東人，講師，碩士，主要從事嵌入式系統(tǒng)方面的研究，(E-mail)896999517@ qq．com

中圖分類號：TP316.2

文獻(xiàn)標(biāo)志碼：A

引言

近年來，隨著電子計算機(jī)硬件和軟件系統(tǒng)的發(fā)展，越來越多的嵌入式產(chǎn)品走進(jìn)人們的日常生活，如音樂播放器、手機(jī)、數(shù)字電視等。嵌入式系統(tǒng)主要是面向?qū)Ｓ妙I(lǐng)域的系統(tǒng)，對實時性能有著較高的要求，并且大多數(shù)的嵌人式系統(tǒng)都搭載了嵌入式操作系統(tǒng)。嵌入式 Linux 操作系統(tǒng)以其特有的開放性、與生俱來的網(wǎng)絡(luò)特性，在嵌入式領(lǐng)域得到了廣泛應(yīng)用，目前已經(jīng)被成功地應(yīng)用到了PDA、移動電話、音樂播放器等各種嵌入式設(shè)備上。但在國防、航空、工業(yè)控制等對實時性要求非常嚴(yán)格的場合中，嵌入式Linux的實時性還有待改進(jìn)，因此，提高嵌入式Linux的實時性成為嵌入式操作系統(tǒng)的一個重要研究方向[1-2]。

目前嵌入式Linux實時性的解決方案非常多，但總的來說，在構(gòu)造嵌入式Linux系統(tǒng)時，主要從細(xì)粒度微定時器、內(nèi)核搶占機(jī)制、實時調(diào)度策略、中斷機(jī)制、內(nèi)存管理優(yōu)化等幾個方面來改善系統(tǒng)的實時性。內(nèi)存管理是系統(tǒng)實時性的重要部分，快速有效的存儲能提高系統(tǒng)的實時性[1,3-5]。內(nèi)存管理中，內(nèi)存不足時頁面置換的效率是影響系統(tǒng)實時性的關(guān)鍵，目前嵌入式Linux中，主要采用LRU(最近最少使用)算法、FIFO(先進(jìn)先出)算法、NFU(最不經(jīng)常使用)算法等作為內(nèi)存不足時的頁面置換算法[6-8]。其中LRU算法用的最多，也最高效，但是LRU算法在嵌入式系統(tǒng)中的應(yīng)用也存在一定不足，如頁面置換中斷多，重要的任務(wù)不能得到優(yōu)先內(nèi)存保障等，針對這些不足，文章采用重要任務(wù)專用內(nèi)存，并對內(nèi)存定時間隔掃描以減少缺頁中斷的發(fā)生，因為中斷的執(zhí)行時間不確定，且往往耗時較多，嚴(yán)重影響系統(tǒng)的實時性，下面就是對嵌入式Linux內(nèi)存管理的優(yōu)化。

1嵌入式Linux內(nèi)存頁面置換算法

嵌入式Linux的進(jìn)程運(yùn)行過程中，若其所要訪問的頁面不在內(nèi)存中時，需把它們調(diào)入內(nèi)存，若內(nèi)存已無空閑空間時，為了保證該進(jìn)程能正常運(yùn)行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁程序或數(shù)據(jù)，送外存儲器的對換區(qū)中。但應(yīng)將哪個頁面調(diào)出，就需要根據(jù)一定的內(nèi)存頁面置換算法來確定，常用的內(nèi)存頁面置換算法見表1，其中，最為常用的算法有OPT算法、LRU算法、NFU算法等[9-11]。

表1　常用的頁面置換算法

2LRU算法的優(yōu)化

2.1　LRU算法在嵌入式系統(tǒng)中應(yīng)用的不足

在嵌入式Linux中大多采用LRU頁面置換算法，當(dāng)系統(tǒng)內(nèi)存不足時，若有進(jìn)程引起新的內(nèi)存空間的分配需求，系統(tǒng)內(nèi)核采用雙向鏈表對系統(tǒng)內(nèi)存空間進(jìn)行掃描，以釋放最久未使用過的內(nèi)存頁面滿足系統(tǒng)需求。在這個過程中系統(tǒng)需要產(chǎn)生多個中斷，以響應(yīng)內(nèi)外存儲間的頁面置換。中斷是嵌入式Linux系統(tǒng)諸多操作事務(wù)中最耗時的操作之一，而且時間很難預(yù)測，因此，它對系統(tǒng)實時性的影響也是非常大的，如果系統(tǒng)中某些實時性要求較高的任務(wù)在執(zhí)行過程中頻繁的產(chǎn)生頁面置換中斷的話，將非常不利于系統(tǒng)的實時性能，甚至給系統(tǒng)造成災(zāi)難性的后果。

針對以上LRU頁面置換算法在嵌入式Linux中應(yīng)用存在的不足，可以采用以下的優(yōu)化方法[12-14]：首先，在LRU頁面置換算法中，要盡可能地保證系統(tǒng)中實時性要求高的那些重要任務(wù)能優(yōu)先順利地執(zhí)行完成；其次，在此基礎(chǔ)之上，還要盡可能地減少任務(wù)在執(zhí)行過程中頁面置換中斷的發(fā)生，從而提高系統(tǒng)的實時性。基于以上的思想，提出了基于重要任務(wù)間隔掃描的LRU算法。

2.2　基于重要任務(wù)間隔掃描的LRU算法

基于上文提到的LRU算法的優(yōu)化思想，需要著重解決兩個問題：(1) 重要任務(wù)常駐內(nèi)存；(2) 運(yùn)行過程中頁面置換中斷。

首先要解決重要任務(wù)常駐內(nèi)存的問題，可以在內(nèi)存空間中，按實際需要劃分出一塊空間來，讓系統(tǒng)中比較重要的任務(wù)常駐內(nèi)存，不被其它任務(wù)置換出來。這樣重要的實時任務(wù)就不會因為內(nèi)存不足，來回的在內(nèi)外存之間置換，從而提高重要任務(wù)的實時性。在嵌入式Linux系統(tǒng)中，可以通過kswapd進(jìn)程來實現(xiàn)重要實時任務(wù)的內(nèi)存常駐。在kswapd進(jìn)程中增加一個內(nèi)存頁面區(qū)域，當(dāng)系統(tǒng)初始化時，將系統(tǒng)中重要的實時任務(wù)所需的內(nèi)存頁面空間載入該區(qū)域，這樣kswapd的掃描進(jìn)程就不再掃描該區(qū)域，這樣不僅保證了重要程序的內(nèi)存空間的供給，另一方面也減少了kswapd進(jìn)程的掃描時間，提高掃描效率，從而增強(qiáng)系統(tǒng)的實時性。

其次，通過優(yōu)化對內(nèi)存的掃描來減少任務(wù)運(yùn)行過程中頁面置換中斷的發(fā)生。由于中斷的執(zhí)行時間較長，且比較難預(yù)測，這對實時任務(wù)的執(zhí)行是非常不利的，也會影響到整個系統(tǒng)的實時性。針對以上的考慮，在系統(tǒng)處于空閑時間時，啟動內(nèi)存掃描，并進(jìn)行頁面置換，來減少任務(wù)執(zhí)行過程中內(nèi)存頁面置換中斷的發(fā)生。在系統(tǒng)中設(shè)定一個時間間隔，每個時間間隔到達(dá)之后，當(dāng)?shù)谝淮纬霈F(xiàn)系統(tǒng)空閑時，開始掃描內(nèi)存，查找那些在內(nèi)存區(qū)域最近最少使用的頁面，將這些內(nèi)存頁面置換出去，不必等到內(nèi)存不足時再置換，這樣會減少任務(wù)執(zhí)行過程中的內(nèi)存置換的次數(shù)，從而提高系統(tǒng)的實時性。

2.3　優(yōu)化后的LRU算法實現(xiàn)

首先要實現(xiàn)優(yōu)化后的kswapd進(jìn)程。kswapd進(jìn)程的實現(xiàn)相當(dāng)復(fù)雜，這不僅僅涉及復(fù)雜的頁面交換技術(shù)，還涉及與磁盤相關(guān)的具體文件操作，需要調(diào)用很多函數(shù)，其中由Swap_out()和shrink_cache()一起完成到底哪些頁面會被作為候選頁以備換出。shrink_cache()要做很多換出的準(zhǔn)備工作[1,6]，它關(guān)注兩個隊列：“活躍的”LRU隊列和“非活躍的”FIFO 隊列，每個隊列都是struct page形成的鏈表。kswapd進(jìn)程實現(xiàn)的偽代碼如下：

while(系統(tǒng)內(nèi)存不足時)

{

if(不是重要任務(wù)內(nèi)存區(qū)域)

{

對“非活躍的”FIFO 隊列進(jìn)行掃描，然后進(jìn)行頁面置換。

}

else

{

跳過該區(qū)域，對其它區(qū)域進(jìn)行掃描

}

}

接下來要實現(xiàn)系統(tǒng)對內(nèi)存的間隔掃描。需要在Linux 內(nèi)核中添加一個系統(tǒng)調(diào)用，并指明系統(tǒng)主動掃描內(nèi)存頁面的時間間隔的參數(shù)。具體實現(xiàn)的偽代碼描述如下：

While(系統(tǒng)到達(dá)時間間隔)

{

if(空閑內(nèi)存頁面<=設(shè)定值)

{

將非活躍隊列中的最近最少使用的頁面置換。

}

else

{

等待下一個時間間隔或者缺頁中斷

}

}

3實驗分析

為了驗證上面的LRU算法優(yōu)化效果，在博創(chuàng)嵌入式試驗箱上做了相應(yīng)的實驗，硬件環(huán)境是Samsung公司基于ARM公司ARM920T處理器核的S3C2410處理器，它擁有64 M內(nèi)存的內(nèi)存，并在開發(fā)板上面移植了Linux Kernel 2.6內(nèi)核。在此實驗平臺上，通過對OPT最優(yōu)算法、LRU算法、優(yōu)化后的LUR算法三者進(jìn)行頁面中斷次數(shù)和截止期錯失率的對比實驗，來分析優(yōu)化后的LRU算法的性能。實驗任務(wù)參數(shù)參見文獻(xiàn)[6-8,15-16]，實驗中任務(wù)的周期(ms)、運(yùn)行時間(ms)、任務(wù)運(yùn)行所需的內(nèi)存頁數(shù)見表2。

表2　實驗數(shù)據(jù)表

首先通過實驗分析優(yōu)化后的LUR算法在內(nèi)存不足時的缺頁率。對OPT最優(yōu)算法、LRU算法、優(yōu)化后的LUR算法，在隨著任務(wù)s1，s2…，s9依次載入系統(tǒng)時，所產(chǎn)生的缺頁率進(jìn)行比較，結(jié)果如圖1所示。從圖1可知，隨著任務(wù)不斷的載入系統(tǒng)，三種算法的系統(tǒng)中的內(nèi)存缺頁率都在不斷地增加，相對OPT最優(yōu)算法與LRU算法而言，優(yōu)化后的LRU算法的內(nèi)存缺頁率低于LRU算法，接近OTP算法，顯然，當(dāng)內(nèi)存不足時，在保證重要任務(wù)的前提下，缺頁率得到了降低。

圖1　任務(wù)內(nèi)存缺頁中斷數(shù)

其次再通過實驗來分析優(yōu)化后的LRU算法對系統(tǒng)的實時性的影響。對OPT最優(yōu)算法、LRU算法、優(yōu)化后的LUR算法，在隨著任務(wù)s1，s2…，s9依次載入系統(tǒng)時，任務(wù)的截止期錯失率進(jìn)行實驗分析，結(jié)果如圖2所示。通過實驗結(jié)果可以看出，三個算法隨著任務(wù)數(shù)的增加，截止期錯失率都在增加，但優(yōu)化后的LRU算法的截止期錯失率要低于LRU算法，這說明優(yōu)化后的LRU算法，使得系統(tǒng)的實時性有所提高，能使更多的任務(wù)實時完成。

圖2　任務(wù)截止期錯失率

4結(jié)束語

通過為系統(tǒng)中的重要任務(wù)分配固定的內(nèi)存區(qū)域，以減少重要任務(wù)因內(nèi)存不足而發(fā)生的頁面置換，重要任務(wù)就會常駐內(nèi)存，在內(nèi)存不足時不會頻繁的發(fā)生頁面置換中斷，可以在一定程度上有效地提高重要任務(wù)的實時性，這對嵌入式系統(tǒng)尤為重要。同時利用系統(tǒng)的空閑時間，來對內(nèi)存進(jìn)行掃描。正常情況下，對內(nèi)存掃描只發(fā)生在缺頁時，要對系統(tǒng)掃描找出最近最少使用的頁面進(jìn)行掃描并進(jìn)行置換，任務(wù)就需要等待內(nèi)存掃描置換這個過程，降低了系統(tǒng)的實時性；如果在系統(tǒng)空閑時間對內(nèi)存進(jìn)行掃描，并將最近最少使用的內(nèi)存置換出去，不必等到內(nèi)存不足時再掃描置換，可以提高處理器的利用率，從而提高系統(tǒng)的實時性。針對以上思想優(yōu)化后的LRU算法的實驗結(jié)果表明，優(yōu)化后的LRU算法頁面置換中斷數(shù)量要低于優(yōu)化前，并且任務(wù)的截止期錯失率也低于優(yōu)化前，說明優(yōu)化后的LRU算法的實時性得到了提高。

參 考 文 獻(xiàn)：

[1]吳志君,段富海.嵌入式Linux系統(tǒng)內(nèi)存優(yōu)化使用方法研究.甘肅科學(xué)學(xué)報,2012,24(1):139-142.

[2]武建平,方攀,凌明,等.面向Linux內(nèi)核的片上存儲優(yōu)化.微電子學(xué),2012,36(2):82-84.

[3]呂廣鋒,陳蜀宇.一種新的適用于Nandflash的Linux內(nèi)存交換模型.計算機(jī)應(yīng)用研究,2010,27(10): 97-100.

[4]楊峰.基于Linux內(nèi)核的動態(tài)內(nèi)存管理機(jī)制的實現(xiàn).計算機(jī)工程,2010,36(9):85-88.

[5]高超,韓銳,倪宏.嵌入式Linux平臺內(nèi)存管理方案.小型微型計算機(jī)系統(tǒng),2011,32(4):29-31.

[6]張昌昌,林滿山,宋威,等.基于缺頁的Linux任務(wù)管理器設(shè)計與實現(xiàn).計算機(jī)工程與設(shè)計,2011,32(9):3059-3062.

[7]黃仁,李建章,程平.基于RM與EDF的實時混合調(diào)度算法研究.電子技術(shù)應(yīng)用,2010,36(12):29-31.

[8]張建,劉青昆,王異奇.Linux實時化方法的研究與實現(xiàn).計算機(jī)工程,2011,37(11):253-256.

[9]陳何杰,鄭靈翔.ARM Linux中斷系統(tǒng)移植研究.廈門大學(xué)學(xué)報,2010,49(3):341-344.

[10]Song Kai,Yan Liping.Improvement of real-time performance of Linux 2.6 Kernel for embedded application//Proceedings of 2009 International Forum on Computer Science-Technology and Applications,Chongqing,China,December25-27,2009:71-74.

[11]趙連玉,靳飛.嵌入式計算機(jī)系統(tǒng)Bootloader 的設(shè)計與實現(xiàn).天津理工大學(xué)學(xué)報,2011,27(1):22-26.

[12]Lee C,Lim S H.Caching and deferred write of metadata for Yaffs2 flash file system//Proceedings of International Conference on Embedded and Ubiquitous Computing,Melbourne,Australia,October 24-26,2011:41-46.

[13]Purdila O,Grijincu L A,Tapus N.The Linux Kerne Library//Proceedings of Roedunet International Conference (RoEduNet),Sibiu,Romania,June 24-26,2010:316-319.

[14]Liu Yinli,Yu Hongli,Zhang Pengpeng.The implementation of embedded acquisition based on v4l2//Proceedings of 2011 International Conference on Electronics,Communications and Control,Ningbo,China,September 9-11,2010:549-552.

[15]周上群.一種新的嵌入式系統(tǒng)存儲器測試算法及應(yīng)用.桂林電子科技大學(xué)學(xué)報,2013,33(3):29-32.

[16]Liu Yijun,Chen Wenbin,He Xiaoman.Research and implementation of embedded graphic user interface based on Linux//Proceedings of 2010 3rd IEEE International Conference on Computer Science and Information Technology(ICCSIT),Chengdu,China,July 9-11,2010: 693-696.

The Optimization of Embedded Linux Memory Management

YUGuolonga,b,CUIZhongweia,b,ZUOYua,b

(a.School of Mathematics and Computer Science; b.Guizhou Province University Industrial Networking

Engineering Technology Research Center, Guizhou Normal College, Guiyang 550018, China)

Abstract:Memory management is a key factor to impact the instantaneity of embedded Linux. In order to improve the instantaneity of embedded Linux, its memory management is optimized. At first, the important task in the system is assigned a dedicated memory area, so that important task will not be swapped out when the memory is lacking, which can protect the important task precedence; Then through the method that use the system idle time to scan the system RAM, to reduce the frequency of missing page interrupt in the task execution, thereby the system instantaneity is improved. Last, the missing page interrupts numbers and the task deadline miss ratios of OPT optimization algorithm, LRU algorithm and optimized LUR algorithm are compared through experiment, and it is found that the missing page interrupts number and the task deadline miss ratio of optimized LUR algorithm is the least among the three algorithms, which indicates that the instantaneity of embedded Linux is improved through the above described memory optimization method.

Key words: embedded Linux; instantaneity; important task; page replacement; missing page interrupt