Buddy算法在μC/OSII動態(tài)內存管理改進方案中的應用
加入技術交流群
圖3 改進方案中的內存管理組織結構
② 首先初始化一個內存控制塊結構數(shù)組struct OS_MEM []，其下標是內存塊規(guī)模的對數(shù)，引入結構數(shù)組的目的是在申請內存塊時能夠快速定位，起到索引的作用。而內存塊的實際大小為內存塊規(guī)模與內存塊粒度的乘積。然后將內存塊按內存塊規(guī)模從小到大掛到不同結構數(shù)組指向的鏈表上，并且保證初始化后同一鏈表上的內存塊地址不連續(xù)。在申請內存塊通過內存控制結構數(shù)組的下標快速定位到內存塊鏈表，查看內存塊控制結構字段中OSMemFreeList成員指針是否為空。若不為空，則從表頭取一個內存塊，并返回該內存塊的地址；否則向后搜索數(shù)組，看是否有空閑內存塊。若有則將該內存塊一分為二，低地址的那塊分配給申請者，高地址的那塊則掛到前一個結構數(shù)組的表頭，以備其他申請者申請。同樣，釋放內存塊時也是通過結構數(shù)組快速定位到具體結構數(shù)組，然后檢查該結構數(shù)組內存塊鏈表中是否有和要釋放的內存塊地址連續(xù)的內存塊。若有，則合并兩內存塊并掛到后一個結構數(shù)組，并檢查地址是否連續(xù)，直至沒有為止；若無，則將該內存塊掛到該內存塊鏈表的表尾。改進后的內存管理組織結構如圖3所示。
4.2 具體改進措施
① 改進函數(shù)OS_MemInit（void）。此函數(shù)原來是初始化空閑內存控制塊鏈表，改進后此函數(shù)用于初始化OS_MEM結構數(shù)組即可，根據OS_CFG.H文件中宏OS_MAX_MEM_PART來決定數(shù)組元素個數(shù)。
② 改進函數(shù)OSMemCreate（void *addr, INT32U nblks, INT32U granularity , INT8U *err）。根據Buddy的規(guī)則橫向創(chuàng)建內存塊，每創(chuàng)建一個內存塊就鏈到相應的結構體數(shù)組上，如圖3的Create Direction所示，這樣能保證每個結構數(shù)組上的相同大小的內存塊地址不連續(xù)，從而避免了所有內存塊合并的現(xiàn)象。創(chuàng)建出來的內存塊組織結構如圖3所示。
③ 改進函數(shù)OSMemGet（INT32U size, INT32U granularity, INT8U *err）。因為結構體數(shù)組名是在OS_CFG.H文件中宏定義的，所以本函數(shù)的參數(shù)只包括需求的內存塊大小及內存塊粒度即可。用內存塊大小除以內存塊粒度，首先判斷所得值是否為2的冪次，若是直接取對數(shù)即得結構數(shù)組的下標；若不是則取對數(shù)后向上取整。得到指定數(shù)組元素后若有內存塊，取下一內存塊然后指針下移，若無內存塊則繼續(xù)搜索下一個結構數(shù)組。若該數(shù)組有空閑內存塊則取將其平分為兩塊，一塊分配出去，一塊掛到前面結構數(shù)組鏈表。這樣一直搜索到最后一個結構數(shù)組，若一直無內存塊，則報錯返回。
④ 改進函數(shù)OSMemPut（INT32U size, INT32U granularity）。如何取得結構數(shù)組下標值同OSMemGet（）函數(shù)。在找到所要回收的結構數(shù)組后，判斷該數(shù)組內存塊鏈表上是否有與要回收的內存塊連續(xù)的地址。若有合并且掛到下一內存塊結構數(shù)組內存塊鏈表，這樣一直到最后一個結構數(shù)組，目的是為了保證有更大的內存塊可滿足應用程序的申請，提高了內存管理的可靠性。
在改進以上函數(shù)的基礎上，還可以在申請內存塊之前有選擇地使用OSMemQuery（）查詢內存中是否有滿足需要的內存塊。如果沒有則作好相應的規(guī)避措施，進一步提高內存管理的可靠性，使系統(tǒng)更穩(wěn)定。
5 實驗結果及性能分析
針對改進前后μC/OSII內存管理策略的特點，設計一組具有代表性的測試用例來分析μC/OSII系統(tǒng)在改進前后內存管理的可靠性和靈活性。實驗環(huán)境為ARM Develop Suit V1. 2及三星公司S3C2440微控制器，由于S3C2440片內包含MMU模塊，所以需要將協(xié)處理器CP15的C1寄存器0位置0,以禁用MMU功能。
假設兩種方案內存初始化都創(chuàng)建了5個分區(qū)，每個分區(qū)中所含內存塊為10個，且這5個內存分區(qū)中的內存塊大小依次為16 B、32 B、64 B、128 B、256 B。原方案創(chuàng)建分區(qū)時要調用5次OSMemCreate（）函數(shù)，而改進方案只需調用一次。表1是申請內存塊大小與兩種方案可以滿足的次數(shù)之間的關系。
表1 申請內存塊大小與兩種方案可以滿足的次數(shù)比較
由表1的數(shù)據及圖4的對比曲線可看出，改進方案與原方案在可用內存完全相同的情況下，使內存的利用率大大提高。因為可靠性與可滿足次數(shù)正相關，而可滿足次數(shù)與曲線與坐標軸圍成的面積成正比，所以該面積與可靠性正相關。新方案曲線所圍圖形面積為12960，而原方案曲線所圍成的圖形面積為2400。所以新方案的可靠性將比原來方案提高大約4倍，而且申請內存塊越小，可滿足次數(shù)越多，提高了內存分配的靈活性。
圖4 兩種方案可滿足次數(shù)對比曲線
6 結語
本文的創(chuàng)新之處在于針對μC/OSII在內存管理可靠性不高、內存塊分配不夠靈活的特點，借鑒Buddy算法思想，對其進行改進，形成了一種基于Buddy算法思想、高可靠性的內存管理策略。實驗表明，新方案一次創(chuàng)建內存區(qū)，即可滿足內存塊大小需求不均勻的場合，既提高內存分配的靈活性，避免了大量內碎片的產生，又增強了內存分配的可靠性。因此，新方案在可靠性要求高的嵌入式系統(tǒng)中可以得到更好的應用。
評論