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

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

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

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

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

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

DOI:10.11863/j.suse.2015.04.07

收稿日期:2015-06-01

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

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

中圖分類號(hào)：TP316.2

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

引言

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

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

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

嵌入式Linux的進(jìn)程運(yùn)行過程中，若其所要訪問的頁面不在內(nèi)存中時(shí)，需把它們調(diào)入內(nèi)存，若內(nèi)存已無空閑空間時(shí)，為了保證該進(jìn)程能正常運(yùn)行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁程序或數(shù)據(jù)，送外存儲(chǔ)器的對(duì)換區(qū)中。但應(yīng)將哪個(gè)頁面調(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)存不足時(shí)，若有進(jìn)程引起新的內(nèi)存空間的分配需求，系統(tǒng)內(nèi)核采用雙向鏈表對(duì)系統(tǒng)內(nèi)存空間進(jìn)行掃描，以釋放最久未使用過的內(nèi)存頁面滿足系統(tǒng)需求。在這個(gè)過程中系統(tǒng)需要產(chǎn)生多個(gè)中斷，以響應(yīng)內(nèi)外存儲(chǔ)間的頁面置換。中斷是嵌入式Linux系統(tǒng)諸多操作事務(wù)中最耗時(shí)的操作之一，而且時(shí)間很難預(yù)測(cè)，因此，它對(duì)系統(tǒng)實(shí)時(shí)性的影響也是非常大的，如果系統(tǒng)中某些實(shí)時(shí)性要求較高的任務(wù)在執(zhí)行過程中頻繁的產(chǎn)生頁面置換中斷的話，將非常不利于系統(tǒng)的實(shí)時(shí)性能，甚至給系統(tǒng)造成災(zāi)難性的后果。

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

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

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

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

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

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

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

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

{

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

{

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

}

else

{

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

}

}

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

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

{

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

{

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

}

else

{

等待下一個(gè)時(shí)間間隔或者缺頁中斷

}

}

3實(shí)驗(yàn)分析

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

表2　實(shí)驗(yàn)數(shù)據(jù)表

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

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

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

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

4結(jié)束語

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

參 考 文 獻(xiàn)：

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

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

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

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

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

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

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

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

[9]陳何杰,鄭靈翔.ARM Linux中斷系統(tǒng)移植研究.廈門大學(xué)學(xué)報(bào),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ì)算機(jī)系統(tǒng)Bootloader 的設(shè)計(jì)與實(shí)現(xiàn).天津理工大學(xué)學(xué)報(bào),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)存儲(chǔ)器測(cè)試算法及應(yīng)用.桂林電子科技大學(xué)學(xué)報(bào),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