一種提高Linux內存管理實時性的設計方案

王兆文,蔣澤軍,陳進朝

(西北工業大學計算機學院,西安710129)

一種提高Linux內存管理實時性的設計方案

王兆文,蔣澤軍,陳進朝

(西北工業大學計算機學院,西安710129)

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

Linux系統;實時性;內存映射;內存鎖定;內存管理算法;分區管理

1 概述

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

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

2 影響內存管理實時性的因素分析

Linux在內存管理方面影響系統實時性的因素主要有以下3個方面:

(1)用戶態和內核態之間的模式轉換

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

(2)頁面交換機制

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

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

應用程序在調用 malloc/free函數進行內存申請/釋放時,系統采用動態內存分配,即從堆上分配內存[3],由于申請大小和申請釋放時機不同,當頻繁進行這些操作時會產生大量的內存碎片,導致系統性能降低,花費時間不確定。

3 內存管理實時性改進方案設計

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

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

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

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

圖1 內存管理實時性的改進方案

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

3.1 內存映射

進程用戶空間的一部分可以和磁盤文件的某一部分或者設備文件相關聯,因此,內核把對線性區中頁內某個字節的訪問轉換成文件中相應字節的操作。這種技術稱為內存映射[5]。進程發出一個mmap()系統調用來創建一個新的內存映射。一旦創建了這種映射,進程就可以從這個新線性區的內存單元讀取數據,也就等價于讀取了文件中存放的數據,如圖2所示。

圖2 內存映射的原理

mmap()系統調用的原型:

void*mmap(void*addr,size_t length,int prot,int flags,int fd,off_t offsize);

返回值:成功則返回映射區起始地址。失敗則返回MAP_FAILED(-1)。

參數:

addr:指定映射的起始地址;

length:將文件的多大長度映射到內存;

prot:映射區的保護方式;

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

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

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

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

映射的實現過程:首先,驅動程序先分配好一段內存;接著,用戶進程通過系統調用mmap()告訴內核需要將多大的內存映射到內核空間,內核經過一系列處理后調用對應的驅動程序的file_operation結構中的(*mmap)()方法,在該方法中調用remap_ pfn_range()方法建立映射關系,即建立映射區的頁表。簡單點說就是驅動程序在(*mmap)()中利用remap_pfn_range()函數將內核空間的一段內存與用戶空間的一段內存建立映射關系,如圖3所示。

圖3 內存映射的實現過程

在不使用內存映射的情況下,應用程序使用read()/write()等函數與設備傳輸數據,需要先切換到內核模式,使用copy_to_user/copy_from_user等內存復制函數將數據復制到內核空間,然后輸出到設備。使用內存映射以后,在應用程序的進程地址空間上映射了設備驅動程序提供的物理地址,用戶程序就可以不用切換到內核空間拷貝數據而直接訪問物理地址,這樣就大大提高了用戶程序訪問磁盤文件或者硬件設備的效率。

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

3.2 內存鎖定

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

3.3 對內存管理算法的改進

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

系統使用m_partition結構來表示每個分區,這樣整個區域就可以用一個m_partition結構數組來維護,m_partition結構中的空閑鏈表和已使用鏈表用來標記各個分區中的內存單元使用情況,其結構示意圖如圖4所示。

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

圖4 分區的數據結構示意圖

算法的運行過程如下:

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

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

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

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

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

4 性能測試與結果分析

分別對實時方案改進前和改進后申請相同大小內存的性能進行對比測試:改進前,使用系統原有的malloc函數申請一塊內存,并對其讀寫數據,然后由free函數釋放這塊內存,測試整個過程所花費的時間;改進后,使用RTmalloc函數申請同樣大小的內存并且讀寫數據,然后由RTfree函數釋放,測試所花費的時間。

測試環境:處理器為Intel(R)Core(TM)2 Duo,頻率為2.70 GHz,物理內存為2 GB,頁面交換空間為2 GB,操作系統為CentOS6.0(Linux3.6.0內核)平臺。當物理內存使用率較高并且內存碎片較多時,系統原有的方法效率低下且花費時間不確定。而改造方案中的內存鎖定與內存管理算法主要是解決這個問題的,因此,測試時制造了內存緊張的環境,使內存使用率達到90%,頁面交換率達到50%。

4.1 對不同大小內存的測試

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

表1 方案改進前后內存性能測試結果

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

4.2 對不同內存環境的測試

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

圖6 內存緊張環境下耗費時間對比

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

圖7 內存不緊張環境下耗費時間對比

表2 不同環境下內存性能測試時間平均值 μs

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

綜合起來看,改進后的內存方案較好地提高了Linux系統在內存管理方面的實時性,可以應用在對實時性要求較高的任務中。

5 結束語

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

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

[2] Mauerer W.深入Linux內核架構[M].郭 旭,譯.北京:人民郵電出版社,2010.

[3] 楊 峰.基于Linux內核的動態內存管理機制的實現[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內核[M].陳莉君,張瓊聲,張宏偉,譯.3版.北京:中國電力出版社,2007.

[6] 任橋偉.Linux內核修煉之道[M].北京:人民郵電出版社,2010.

[7] 康 華.Linux內核空間與用戶空間信息交互方法[EB/OL].(2011-11-23).http://www.kerneltravel. net/jiaoliu/005.htm.

[8] 劉 斌,朱程榮.Linux內核與用戶空間通信機制研究[J].電腦知識與技術,2012,8(16):70-71,103.

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

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

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

[12] 李滿麗.復雜嵌入式系統內存管理方案的研究與實現[D].廈門:廈門大學,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

航空科學基金資助項目(2012ZC53040);國家部委基金資助項目;西北工業大學研究生創業種子基金資助項目。

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

2013-07-10

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