R TOS動態(tài)分區(qū)內(nèi)存管理機制的優(yōu)化設(shè)計

引 言
    在嵌入式領(lǐng)域中，嵌入式實時操作系統(tǒng)(RTOS)正得到越來越廣泛的應(yīng)用。采用嵌入式實時操作系統(tǒng)可以更合理、更有效地利用CPU的資源，簡化應(yīng)用軟件的設(shè)計，縮短系統(tǒng)開發(fā)時間，更好地保證系統(tǒng)的實時性和可靠性。內(nèi)存資源作為嵌入式系統(tǒng)中極為重要的資源之一，其管理機制歷來是嵌入式系統(tǒng)設(shè)計的重點和難點。內(nèi)存管理機制的優(yōu)劣程度極大地影響著嵌入式系統(tǒng)的整體性能，因此在嵌入式RTOS的內(nèi)存管理機制中必須滿足以下3個要求：
    ①實時性。在嵌入式RTOS中不僅要求調(diào)度機制的實時性，資源的分配和回收的實時性也十分重要。
    ②可靠性。嵌入式系統(tǒng)的應(yīng)用領(lǐng)域決定了嵌入式RTOS必須具有高可靠性，而內(nèi)存管理的可靠程度直接影響RTOS的可靠性，因此內(nèi)存管理的可靠性也必不可少。
    ③高效性。由于嵌入式系統(tǒng)資源的稀缺性，因而高效的資源管理機制也同等重要。

1 動態(tài)分區(qū)內(nèi)存管理機制
1．1 動態(tài)分區(qū)內(nèi)存管理概述
    在許多小型嵌入式系統(tǒng)中并未實現(xiàn)虛擬內(nèi)存機制，動態(tài)分區(qū)內(nèi)存管理機制仍然是首選。分區(qū)存儲管理是滿足多道程序設(shè)計的最簡單的存儲管理方法，它允許多個用戶程序同時存在系統(tǒng)內(nèi)存中，即共享內(nèi)存空間。早期的分區(qū)存儲管理采用固定分區(qū)的方法，把內(nèi)存空間分成若干個大小不等的區(qū)域，稱為分區(qū)。每個用戶程序(作業(yè)、進(jìn)程)調(diào)入內(nèi)存后，占用其中1個分區(qū)，程序運行完成后釋放該分區(qū)。這種存儲管理方法的主要問題是內(nèi)存使用效率極低，很快就被淘汰了。取而代之的是動態(tài)分區(qū)存儲管理技術(shù)。圖1顯示的是動態(tài)內(nèi)存管理的數(shù)據(jù)結(jié)構(gòu)。

1．2 動態(tài)分區(qū)內(nèi)存分收算法及其性能分析
    在動態(tài)內(nèi)存分配機制中一般采用兩種設(shè)計方案：最佳適應(yīng)算法和首次適應(yīng)算法。最佳適應(yīng)算法要求所有的空閑內(nèi)存塊按照內(nèi)存塊的大小，由小到大鏈接在一起。首次適應(yīng)算法中所有的空閑內(nèi)存塊都是按地址由小到大鏈接的。圖2顯示了這2種算法的流程(假設(shè)系統(tǒng)申請的內(nèi)存塊大小為n)。

    最佳適應(yīng)算法和首次適應(yīng)算法在分配內(nèi)存的流程上是一致的，然而由于空閑內(nèi)存塊的組織形式不同，其分配的性能也不盡相同。最佳適應(yīng)算法由于每次分配都是首先分配與所要求的內(nèi)存塊大小最接近的空閑內(nèi)存塊，因而其內(nèi)存利用率相對較高。然而由于在內(nèi)存回收過程中需要合并那些地址相鄰的空閑塊，最佳適應(yīng)算法往往需要遍歷整個空閑區(qū)鏈表以尋找符合條件的內(nèi)存塊。而首次適應(yīng)算法由于是按照地址的順序相連，因而在內(nèi)存回收方面有著最佳適應(yīng)算法無法比擬的性能。
    圖3顯示了在幾種不同情況下，動態(tài)分區(qū)內(nèi)存回收機制所采取的策略。

    在A中，釋放區(qū)回收后合并成新內(nèi)存塊f，其首地址為f1內(nèi)存塊的首地址，大小為f1和R內(nèi)存塊的大小之和。在B中，釋放區(qū)回收后合并成新內(nèi)存塊f，其首地址為R內(nèi)存塊的首地址，大小為f1和R內(nèi)存塊的大小之和。在C中，釋放區(qū)回收后合并成新內(nèi)存塊f，其首地址為f1內(nèi)存塊的首地址，大小為f1和R以及f2內(nèi)存塊的大小之和。在D中，釋放區(qū)回收后不進(jìn)行合并，直接插入空閑區(qū)鏈表并返回。
    動態(tài)分區(qū)內(nèi)存的分配機制有效地避免了內(nèi)存內(nèi)部碎片的存在，同時在內(nèi)存回收策略中使用合并算法也極大地減少了內(nèi)存外部碎片存在的可能性。然而，當(dāng)系統(tǒng)需要分配大量的小塊內(nèi)存時，動態(tài)分區(qū)內(nèi)存管理機制的性能卻并不令人滿意。其不足之處主要存在以下2個方面：
    ①當(dāng)系統(tǒng)分配大量的小塊內(nèi)存后，其空閑區(qū)表或空閑區(qū)隊列將會變得異常龐大。無論是首次適配算法還是最佳適應(yīng)算法都需要遍歷空閑區(qū)搜索合適的內(nèi)存塊，因此過于龐大的空閑區(qū)結(jié)構(gòu)使搜索算法變得低效。
    ②系統(tǒng)在某些特定的時刻往往會對大量的小塊內(nèi)存進(jìn)行頻繁分配和回收。頻繁地對小塊內(nèi)存進(jìn)行分割分配和合并回收，其實時性表現(xiàn)得并不令人滿意。
    基于以上2點，如何在動態(tài)分區(qū)內(nèi)存管理機制的基礎(chǔ)上優(yōu)化小塊內(nèi)存的管理機制，成為提高動態(tài)分區(qū)內(nèi)存管理性能的關(guān)鍵因素之一。

2 小塊內(nèi)存動態(tài)緩存分配機制
    大部分實時操作系統(tǒng)內(nèi)存分配機制并未對大塊內(nèi)存和小塊內(nèi)存的分配做出不同的算法設(shè)計，然而在實際分配過程中，很難用一種分配算法兼顧大小內(nèi)存的高效分配。針對動態(tài)分區(qū)內(nèi)存管理機制中對小塊內(nèi)存分配的局限性，提出了小塊內(nèi)存動態(tài)緩存機制。該機制在繼承了動態(tài)分區(qū)管理機制優(yōu)良性能的同時，優(yōu)化了小塊內(nèi)存的管理，對內(nèi)存管理的實時性和高效性都有一定提高。系統(tǒng)中同時存在2種內(nèi)存數(shù)據(jù)結(jié)構(gòu)，分別為小塊內(nèi)存和大塊內(nèi)存設(shè)計。大塊內(nèi)存依舊采取動態(tài)分區(qū)內(nèi)存管理機制，而小塊內(nèi)存采取動態(tài)緩存分配。小塊內(nèi)存數(shù)據(jù)結(jié)構(gòu)如圖4所示。

    假設(shè)小塊內(nèi)存最小為1字節(jié)，并以2的指數(shù)遞增，最大為512字節(jié)。這也就意味著當(dāng)系統(tǒng)需要分配或釋放小于或等于512字節(jié)的內(nèi)存時，會執(zhí)行小塊內(nèi)存操作。圖5和圖6分別是小塊內(nèi)存的分配和回收流程(圖中j代表需操作的小塊內(nèi)存對應(yīng)的緩存號，若申請120字節(jié)則j對應(yīng)為8；min代表小塊內(nèi)存最大的緩存號，如圖中min＝9)。

    圖7是對小塊內(nèi)存操作算法的簡單模擬。小塊內(nèi)存緩存區(qū)從上到下依次緩存512～64字節(jié)的內(nèi)存塊。有4個操作過程：分配64字節(jié)→分配128字節(jié)→回收64字節(jié)→回收128字節(jié)。

    ①分配64字節(jié)。初始狀態(tài)小塊內(nèi)存緩存區(qū)為空，此時將會執(zhí)行大塊內(nèi)存分配操作并將1 KB內(nèi)存分割緩存到小塊內(nèi)存緩存區(qū)。在分配64字節(jié)內(nèi)存時，系統(tǒng)自動探測到了128字節(jié)、256字節(jié)和512字節(jié)處的緩存區(qū)已經(jīng)處于饑餓狀態(tài)，因此也將會分配其緩存區(qū)1塊內(nèi)存。
    ②分配128字節(jié)。由于系統(tǒng)存在該大小的緩存，因此直接獲取并返回。
    ③回收64字節(jié)。由于釋放后，系統(tǒng)中64字節(jié)大小的內(nèi)存塊可以合并，因此合并后鏈入上一級緩存區(qū)。
    ④回收128字節(jié)。內(nèi)存塊再次進(jìn)行合并操作，最終調(diào)用大塊內(nèi)存釋放操作，從而回到原始態(tài)。
    圖7所示的內(nèi)存操作只是一個非常簡單的模擬，實際系統(tǒng)內(nèi)存的分配和回收是非常復(fù)雜和不確定的，而小塊內(nèi)存動態(tài)緩存分配機制的性能在這種情況下表現(xiàn)得尤為突出?？傮w而言其具有以下幾點優(yōu)勢：
    ①快速性。因為使用了緩存機制，所以在大部分情況下，小塊內(nèi)存釋放后依舊在緩存區(qū)中，當(dāng)系統(tǒng)再次分配該大小的內(nèi)存塊時就極為快速。
    ②自適應(yīng)性。在分配小塊內(nèi)存的過程中，算法能檢測出處于饑餓狀態(tài)的內(nèi)存塊大小，并依次為它們所在的緩存區(qū)分配1塊相應(yīng)大小的內(nèi)存塊。
    ③動態(tài)性。在小塊內(nèi)存的回收過程中，該算法將對內(nèi)存塊進(jìn)行合并重組。假若某時刻先前從大塊內(nèi)存中分配的1 KB內(nèi)存塊全部被小內(nèi)存塊釋放，其經(jīng)過重組后必定能重新添加到大內(nèi)存塊存儲區(qū)。

3 優(yōu)化后的系統(tǒng)內(nèi)存管理機制
    圖8和圖9分別是優(yōu)化后系統(tǒng)分配和回收內(nèi)存的算法，圖中的max代表的是小塊內(nèi)存的最大值。當(dāng)不能得到所需的小塊內(nèi)存，或者釋放小塊內(nèi)存最終合并成大塊內(nèi)存時，分別調(diào)用大塊內(nèi)存分配和釋放操作，從而保證小塊內(nèi)存和大塊內(nèi)存操作能很好地協(xié)作，增強了系統(tǒng)的穩(wěn)定性。

結(jié) 語
    盡管在引入小塊內(nèi)存動態(tài)緩存分配機制后，系統(tǒng)在分配小塊內(nèi)存時會存在一定的內(nèi)存內(nèi)部碎片，但由于小塊內(nèi)存本身很小以及大塊內(nèi)存的動態(tài)分區(qū)管理機制，很好地降低了系統(tǒng)中由于存在內(nèi)存碎片而帶來的風(fēng)險。在實際模擬測驗1中，經(jīng)優(yōu)化過的動態(tài)分區(qū)內(nèi)存管理機制能在一定程度上提高系統(tǒng)的實時性及可靠性，在嵌入式RTOS的設(shè)計中具有實際的意義。