|
引 言 在嵌入式領域中，嵌入式實時操作系統(RTOS)正得到越來越廣泛的應用。采用嵌入式實時操作系統可以更合理、更有效地利用CPU的資源，簡化應用軟件的設計，縮短系統開發時間，更好地保證系統的實時性和可靠性。內存資源作為嵌入式系統中極為重要的資源之一，其管理機制歷來是嵌入式系統設計的重點和難點。內存管理機制的優劣程度極大地影響著嵌入式系統的整體性能，因此在嵌入式RTOS的內存管理機制中必須滿足以下3個要求： ①實時性。在嵌入式RTOS中不僅要求調度機制的實時性，資源的分配和回收的實時性也十分重要。 ②可靠性。嵌入式系統的應用領域決定了嵌入式RTOS必須具有高可靠性，而內存管理的可靠程度直接影響RTOS的可靠性，因此內存管理的可靠性也必不可少。 ③高效性。由于嵌入式系統資源的稀缺性，因而高效的資源管理機制也同等重要。 1 動態分區內存管理機制 1．1 動態分區內存管理概述 在許多小型嵌入式系統中并未實現虛擬內存機制，動態分區內存管理機制仍然是首選。分區存儲管理是滿足多道程序設計的最簡單的存儲管理方法，它允許多個用戶程序同時存在系統內存中，即共享內存空間。早期的分區存儲管理采用固定分區的方法，把內存空間分成若干個大小不等的區域，稱為分區。每個用戶程序 (作業、進程)調入內存后，占用其中1個分區，程序運行完成后釋放該分區。這種存儲管理方法的主要問題是內存使用效率極低，很快就被淘汰了。取而代之的是動態分區存儲管理技術。圖1顯示的是動態內存管理的數據結構。 
1．2 動態分區內存分收算法及其性能分析 在動態內存分配機制中一般采用兩種設計方案：最佳適應算法和首次適應算法。最佳適應算法要求所有的空閑內存塊按照內存塊的大小，由小到大鏈接在一起。首次適應算法中所有的空閑內存塊都是按地址由小到大鏈接的。圖2顯示了這2種算法的流程(假設系統申請的內存塊大小為n)。
最佳適應算法和首次適應算法在分配內存的流程上是一致的，然而由于空閑內存塊的組織形式不同，其分配的性能也不盡相同。最佳適應算法由于每次分配都是首先分配與所要求的內存塊大小最接近的空閑內存塊，因而其內存利用率相對較高。然而由于在內存回收過程中需要合并那些地址相鄰的空閑塊，最佳適應算法往往需要遍歷整個空閑區鏈表以尋找符合條件的內存塊。而首次適應算法由于是按照地址的順序相連，因而在內存回收方面有著最佳適應算法無法比擬的性能。 圖3顯示了在幾種不同情況下，動態分區內存回收機制所采取的策略。
在A中，釋放區回收后合并成新內存塊f，其首地址為f1內存塊的首地址，大小為f1和R內存塊的大小之和。在B中，釋放區回收后合并成新內存塊f，其首地址為R內存塊的首地址，大小為f1和R內存塊的大小之和。在C中，釋放區回收后合并成新內存塊f，其首地址為f1內存塊的首地址，大小為f1和R以及f2內存塊的大小之和。在D中，釋放區回收后不進行合并，直接插入空閑區鏈表并返回。 動態分區內存的分配機制有效地避免了內存內部碎片的存在，同時在內存回收策略中使用合并算法也極大地減少了內存外部碎片存在的可能性。然而，當系統需要分配大量的小塊內存時，動態分區內存管理機制的性能卻并不令人滿意。其不足之處主要存在以下2個方面： ①當系統分配大量的小塊內存后，其空閑區表或空閑區隊列將會變得異常龐大。無論是首次適配算法還是最佳適應算法都需要遍歷空閑區搜索合適的內存塊，因此過于龐大的空閑區結構使搜索算法變得低效。 ②系統在某些特定的時刻往往會對大量的小塊內存進行頻繁分配和回收。頻繁地對小塊內存進行分割分配和合并回收，其實時性表現得并不令人滿意。 基于以上2點，如何在動態分區內存管理機制的基礎上優化小塊內存的管理機制，成為提高動態分區內存管理性能的關鍵因素之一。 2 小塊內存動態緩存分配機制 大部分實時操作系統內存分配機制并未對大塊內存和小塊內存的分配做出不同的算法設計，然而在實際分配過程中，很難用一種分配算法兼顧大小內存的高效分配。針對動態分區內存管理機制中對小塊內存分配的局限性，提出了小塊內存動態緩存機制。該機制在繼承了動態分區管理機制優良性能的同時，優化了小塊內存的管理，對內存管理的實時性和高效性都有一定提高。系統中同時存在2種內存數據結構，分別為小塊內存和大塊內存設計。大塊內存依舊采取動態分區內存管理機制，而小塊內存采取動態緩存分配。小塊內存數據結構如圖4所示。
假設小塊內存最小為1字節，并以2的指數遞增，最大為512字節。這也就意味著當系統需要分配或釋放小于或等于512字節的內存時，會執行小塊內存操作。圖5和圖6分別是小塊內存的分配和回收流程(圖中j代表需操作的小塊內存對應的緩存號，若申請120字節則j對應為8；min代表小塊內存最大的緩存號，如圖中min＝9)。
圖7是對小塊內存操作算法的簡單模擬。小塊內存緩存區從上到下依次緩存512～64字節的內存塊。有4個操作過程：分配64字節→分配128字節→回收64字節→回收128字節。 ①分配64字節。初始狀態小塊內存緩存區為空，此時將會執行大塊內存分配操作并將1 KB內存分割緩存到小塊內存緩存區。在分配64字節內存時，系統自動探測到了128字節、256字節和512字節處的緩存區已經處于饑餓狀態，因此也將會分配其緩存區1塊內存。 ②分配128字節。由于系統存在該大小的緩存，因此直接獲取并返回。 ③回收64字節。由于釋放后，系統中64字節大小的內存塊可以合并，因此合并后鏈入上一級緩存區。 ④回收128字節。內存塊再次進行合并操作，最終調用大塊內存釋放操作，從而回到原始態。
圖7所示的內存操作只是一個非常簡單的模擬，實際系統內存的分配和回收是非常復雜和不確定的，而小塊內存動態緩存分配機制的性能在這種情況下表現得尤為突出。總體而言其具有以下幾點優勢： ①快速性。因為使用了緩存機制，所以在大部分情況下，小塊內存釋放后依舊在緩存區中，當系統再次分配該大小的內存塊時就極為快速。 ②自適應性。在分配小塊內存的過程中，算法能檢測出處于饑餓狀態的內存塊大小，并依次為它們所在的緩存區分配1塊相應大小的內存塊。 ③動態性。在小塊內存的回收過程中，該算法將對內存塊進行合并重組。假若某時刻先前從大塊內存中分配的1 KB內存塊全部被小內存塊釋放，其經過重組后必定能重新添加到大內存塊存儲區。 3 優化后的系統內存管理機制 圖8和圖9分別是優化后系統分配和回收內存的算法，圖中的max代表的是小塊內存的最大值。當不能得到所需的小塊內存，或者釋放小塊內存最終合并成大塊內存時，分別調用大塊內存分配和釋放操作，從而保證小塊內存和大塊內存操作能很好地協作，增強了系統的穩定性。
結 語 盡管在引入小塊內存動態緩存分配機制后，系統在分配小塊內存時會存在一定的內存內部碎片，但由于小塊內存本身很小以及大塊內存的動態分區管理機制，很好地降低了系統中由于存在內存碎片而帶來的風險。在實際模擬測驗1中，經優化過的動態分區內存管理機制能在一定程度上提高系統的實時性及可靠性，在嵌入式RTOS的設計中具有實際的意義。 參考文獻 1. 劉濱,王琦,等.嵌入式操作系統FreeRTOS的原理與實現[J].單片機與嵌入式系統應用,2005(7). 2. 張堯,史美林,等.計算機操作系統教程[M].3版.北京:清華大學出版社,2006:117-118. 3. Gorman Mel.Understanding the Linux Virtual Memory Manager[M].白洛,等譯.北京:北京航空航天大學出版社,2006:94-95. 作 者：復旦大學 葉新棟 唐志強 涂時亮 來源：《單片機與嵌入式系統應用》2009年第9期 |
