1 內存管理概述

內存管理是操作系統的中心任務之一，其主要任務是組織內存以容納內核和待執行程序，跟蹤當前內存的使用情況，在需要時為進程分配內存，使用完畢后釋放并回收內存。目前嵌入式系統中常用的內存管理策略主要有兩種--靜態內存分配和動態內存分配。

靜態內存分配： 編譯或鏈接時將所需內存分配好，程序運行起來后所分配的內存不釋放。對于實時性和可靠性要求極高的系統，不允許延遲或者分配失效，必須采用靜態內存分配的方式。

動態內存分配： 根據程序執行過程中所需內存的大小而動態分配內存的策略。此方案按需分配內存，避免了靜態分配中的內存浪費，靈活性比較強，給程序的實現帶來了很大方便。缺點是容易造成內存碎片，且容易造成程序響應不及時等問題。

綜上所述，靜態內存分配和動態內存分配各有優點，出于嵌入式系統可靠性、實時性及成本、功耗的考慮，如何在兩種方案中作出平衡的選擇是令嵌入式操作系統設計者頭疼的事。一般的嵌入式操作系統都是兩種方案的高效結合，μC/OSII也不例外。除此之外，嵌入式操作系統對內存的分配還有以下幾點要求：

① 可靠性。內存分配的請求必須得到滿足，如果分配失敗可能會帶來災難性的后果。比如，航天飛機的嵌入式操作系統若發生內存分配失效，損失是不可估量的。

② 快速性。嵌入式系統對實時性的保證，要求簡單、快速地分配內存。

③ 高效性。嵌入式系統中內存是一種有限、昂貴的資源，內存分配要盡可能地減少浪費。

μC/OSII作為一種典型的嵌入式操作系統，其內存管理同樣要滿足以上3點要求，下面簡單介紹μC/OSII的內存管理策略，并分析其不足之處。

2 μC/OSII動態內存管理方案及不足

2.1 μC/OSII內存管理方案簡介

μC/OSII內存管理模塊主要由一個數據結構體和5個函數組成：

◆ 內存控制塊數據結構OS_MEM；

◆ 內存分區創建函數OSMemCreate（void *addr, INT32U nblks, INT32U blksize, INT8U *err）；

◆ 內存塊分配函數OSMemGet（OS_MEM *pmem , INT8U *err）；

◆ 內存塊釋放函數OSMemPut（OS_MEM *pmem , void *pblk）；

◆ 內存分區狀態查詢函數OSMemQuery（OS_MEM *pmem, OS_MEM_DATA *p_mem_data）；

◆ 內存控制塊鏈表初始化函數OSMemInit（void）。

μC/OSII用一個內存控制塊（OS_MEM）來管理內存分區，主要通過以下4步來管理：

① 內存控制塊鏈表初始化函數OSMemInit（）負責創建空內存控制塊結構的鏈表，鏈表長度由內核OS_CFG.H文件中定義的OS_MAX_MEM_PART宏確定。

② 內存塊創建函數OSMemCreate（）先從空內存控制塊結構鏈表上獲取一個空的內存控制根塊結構，根據用戶需要內存塊的大小來創建分區。一個分區中含有相同大小的內存塊，各內存塊也是通過鏈表鏈接起來，而不同分區中的內存塊大小一般不同，如圖1所示的Partition # 1和Partition # 2中內存塊的大小是不同的。

圖1 μC/OSII通過內存控制塊管理內存

③ 內存塊分配函數OSMemGet（）通過從內存控制塊鏈表中找到能夠滿足自己內存塊需要的內存控制塊，然后從這個內存控制塊指向的分區鏈表首部得到自己需要的內存塊。

④ 內存塊釋放函數OSMemPut（）負責回收內存塊。當應用程序不再使用某一個內存塊時，必須及時把它釋放，并放回到相應的內存分區中。

2.2 μC/OSII內存管理方案的不足之處

如前所述，μC/OSII的內存管理方案簡短精煉，僅百余行代碼，5個函數就能勝任。然而考慮到第1節提到的嵌入式系統對內存管理策略的3個要求，μC/OSII的內存管理策略存在以下不足之處：

① 原μC/OSII內存管理方案可靠性不高。因為原方案中各內存分區之間是孤立的，沒有聯系。一個內存分區上的內存塊用完時，不能利用其他分區上的內存塊，而只是簡單地報錯，從而使系統可靠性大大降低。在內存塊大小及需求量不確定的場合，如果經常發生內存申請得不到滿足的情況，是嵌入式系統所不能容忍的。

② 原μC/OSII內存管理方案中內存分配不夠靈活。舉個例子來說，一個應用程序需要大小為1 KB、512 B、256 B三種內存塊，原方案有兩種解決方案，一是創建一個內存塊大小為1 KB的內存分區，內存塊數目至少為3個；二是創建3個內存分區，內存塊大小分別為1 KB、512 B、256 B。方案一創建了較少分區，性能有保證，但造成內存資源的浪費；方案二雖然沒有浪費內存，但卻調用3次OS_MemCreate（）函數，效率較低。

3 Buddy算法簡介

Buddy算法是內存管理的經典算法，目的是為了解決內存的外碎片問題，以及提高內存管理的可靠性。Buddy算法在Linux內核內存管理模塊得到成功的應用。

如圖2 所示，Buddy算法將所有空閑頁框分組為10個塊鏈表，每個塊鏈表的每個塊元素分別包含1、2、4、8、16、32、64、128、256、512個連續的頁框，每個塊的第一個頁框的物理地址是該塊大小的整數倍。例如，大小為4個頁框的塊，其起始地址是4×212（一個頁框的大小為4K,4個頁框的大小為4×4K,1K=1024=210，4K=212）的倍數。

圖2 Buddy算法簡介

假設要請求一個128個頁框的塊，算法先檢查128個頁框的鏈表是否有空閑塊，如果沒有則查256個頁框的鏈表，有則將256個頁框的塊分裂為兩份，一份使用，一份插入128個頁框的鏈表。如果還沒有，就查512個頁框的鏈表，有的話就分裂為128、128、256，一個128使用，剩余兩個插入對應鏈表。如果在512還沒查到，則返回出錯信號。用這種方法來分配頁框，由Linux內核的穩定性可知其可靠性。

回收過程相反，內核試圖把大小為b的空閑伙伴合并為一個大小為2b的單獨塊，滿足以下條件的兩個塊稱為伙伴： 兩個塊具有相同的大小，記做b；它們的物理地址是連續的；第一個塊的第一個頁框的物理地址是2b×212的倍數。該算法迭代，如果成功合并所釋放的塊，會試圖合并2b的塊來形成更大的塊。在本方案中，只要滿足前兩個條件就足夠了。

4 μC/OSII內存管理改進方案

4.1 改進方案思路

① 修改內存控制塊的結構OS_MEM，去掉OS_MemAddr、OS_MemNFree成員，添加一個內存塊鏈表尾指針OSMemBlkTail，所以OS_MEM結構還含有4個成員：OSMemFreeList、OSMemBlkSize、OSMemNBlks、OSMemBlkTail。改進后的內存控制塊結構如圖3所示。

圖3 改進方案中的內存管理組織結構

② 首先初始化一個內存控制塊結構數組struct OS_MEM []，其下標是內存塊規模的對數，引入結構數組的目的是在申請內存塊時能夠快速定位，起到索引的作用。而內存塊的實際大小為內存塊規模與內存塊粒度的乘積。然后將內存塊按內存塊規模從小到大掛到不同結構數組指向的鏈表上，并且保證初始化后同一鏈表上的內存塊地址不連續。在申請內存塊通過內存控制結構數組的下標快速定位到內存塊鏈表，查看內存塊控制結構字段中OSMemFreeList成員指針是否為空。若不為空，則從表頭取一個內存塊，并返回該內存塊的地址；否則向后搜索數組，看是否有空閑內存塊。若有則將該內存塊一分為二，低地址的那塊分配給申請者，高地址的那塊則掛到前一個結構數組的表頭，以備其他申請者申請。同樣，釋放內存塊時也是通過結構數組快速定位到具體結構數組，然后檢查該結構數組內存塊鏈表中是否有和要釋放的內存塊地址連續的內存塊。若有，則合并兩內存塊并掛到后一個結構數組，并檢查地址是否連續，直至沒有為止；若無，則將該內存塊掛到該內存塊鏈表的表尾。改進后的內存管理組織結構如圖3所示。

4.2 具體改進措施

① 改進函數OS_MemInit（void）。此函數原來是初始化空閑內存控制塊鏈表，改進后此函數用于初始化OS_MEM結構數組即可，根據OS_CFG.H文件中宏OS_MAX_MEM_PART來決定數組元素個數。

② 改進函數OSMemCreate（void *addr, INT32U nblks, INT32U granularity , INT8U *err）。根據Buddy的規則橫向創建內存塊，每創建一個內存塊就鏈到相應的結構體數組上，如圖3的Create Direction所示，這樣能保證每個結構數組上的相同大小的內存塊地址不連續，從而避免了所有內存塊合并的現象。創建出來的內存塊組織結構如圖3所示。

③ 改進函數OSMemGet（INT32U size, INT32U granularity, INT8U *err）。因為結構體數組名是在OS_CFG.H文件中宏定義的，所以本函數的參數只包括需求的內存塊大小及內存塊粒度即可。用內存塊大小除以內存塊粒度，首先判斷所得值是否為2的冪次，若是直接取對數即得結構數組的下標；若不是則取對數后向上取整。得到指定數組元素后若有內存塊，取下一內存塊然后指針下移，若無內存塊則繼續搜索下一個結構數組。若該數組有空閑內存塊則取將其平分為兩塊，一塊分配出去，一塊掛到前面結構數組鏈表。這樣一直搜索到最后一個結構數組，若一直無內存塊，則報錯返回。

④ 改進函數OSMemPut（INT32U size, INT32U granularity）。如何取得結構數組下標值同OSMemGet（）函數。在找到所要回收的結構數組后，判斷該數組內存塊鏈表上是否有與要回收的內存塊連續的地址。若有合并且掛到下一內存塊結構數組內存塊鏈表，這樣一直到最后一個結構數組，目的是為了保證有更大的內存塊可滿足應用程序的申請，提高了內存管理的可靠性。

在改進以上函數的基礎上，還可以在申請內存塊之前有選擇地使用OSMemQuery（）查詢內存中是否有滿足需要的內存塊。如果沒有則作好相應的規避措施，進一步提高內存管理的可靠性，使系統更穩定。

5 實驗結果及性能分析

針對改進前后μC/OSII內存管理策略的特點，設計一組具有代表性的測試用例來分析μC/OSII系統在改進前后內存管理的可靠性和靈活性。實驗環境為ARM Develop Suit V1. 2及三星公司S3C2440微控制器，由于S3C2440片內包含MMU模塊，所以需要將協處理器CP15的C1寄存器0位置0,以禁用MMU功能。

假設兩種方案內存初始化都創建了5個分區，每個分區中所含內存塊為10個，且這5個內存分區中的內存塊大小依次為16 B、32 B、64 B、128 B、256 B。原方案創建分區時要調用5次OSMemCreate（）函數，而改進方案只需調用一次。表1是申請內存塊大小與兩種方案可以滿足的次數之間的關系。

表1 申請內存塊大小與兩種方案可以滿足的次數比較

由表1的數據及圖4的對比曲線可看出，改進方案與原方案在可用內存完全相同的情況下，使內存的利用率大大提高。因為可靠性與可滿足次數正相關，而可滿足次數與曲線與坐標軸圍成的面積成正比，所以該面積與可靠性正相關。新方案曲線所圍圖形面積為12960， 而原方案曲線所圍成的圖形面積為2400。所以新方案的可靠性將比原來方案提高大約4倍，而且申請內存塊越小，可滿足次數越多，提高了內存分配的靈活性。

圖4 兩種方案可滿足次數對比曲線

6 結語

本文的創新之處在于針對μC/OSII在內存管理可靠性不高、內存塊分配不夠靈活的特點，借鑒Buddy算法思想，對其進行改進，形成了一種基于Buddy算法思想、高可靠性的內存管理策略。實驗表明，新方案一次創建內存區，即可滿足內存塊大小需求不均勻的場合，既提高內存分配的靈活性，避免了大量內碎片的產生，又增強了內存分配的可靠性。因此，新方案在可靠性要求高的嵌入式系統中可以得到更好的應用。