Z—Stack內存管理算法的改進研究

鄧慧　郭改枝

摘要 研究了ZigBee協議棧中的內存管理算法，并結合典型內存管理算法TLSF（Two-level Segregated Fit）兩位標志位管理內存思想，對Z-Stack內存管理算法進行了改進，該改進算法同時又對內存分配和釋放時的指針進行動態修改。IAR調試驗證分析表明，該改進算法提高了內存分配速度和內存利用率。

關鍵詞 ZigBee；內存管理；內存利用率；內存分配速度

DOI DOI： 10.11907/rjdk.162529

中圖分類號： TP311

文獻標識碼： A 文章編號 文章編號： 16727800（2017）002005103

0 引言

國內外對Z-Stack內存管理算法研究較少，現有的文獻[12]只是原理闡述，并沒有作出改進。然而，Z-Stack內存管理算法又存在內存資源有限、內存分配速度慢等問題。本文針對上述問題對Z-Stack內存管理算法進行了改進。通過動態修改指針和使用多位標志位，優化Z-Stack內存管理算法，部分解決了低成本、內存資源有限的ZigBee嵌入式系統內存利用率和分配速度問題。

1 Z-Stack內存管理算法分析

1.1 內存初始化

實際應用中，通常根據ZigBee設備功能不同而分配不同大小的內存空間，本文以協調器（MAXMEMHEAP =3072B）為例進行算法分析。

在算法中，每次申請內存將第一個2字節（2B）設置為內存控制頭。其中最高位為標志位，標識以此內存分配控制頭開始的內存區域是否被使用。根據Z-Stack的配置，小塊內存大小設置為232B，大塊和小塊之間的分界區為2B，還有避免內存泄漏2B，剩余字節數為大塊內存2836字節。Z-Stack內存初始化具體步驟如下：①將指針移動到內存塊的最后2B位置，數值設置為0以避免內存溢出；②將頭指針移動到內存塊的起始位置，設置小塊內存大小為232；③將指針移動到小塊內存結束處，設置大塊內存大小為2838；④在大塊內存起始處，申請只有控制頭的2B空間，為了避免小塊內存與大塊內存合并分界區，將大塊內存大小修改為2836。

內存初始化完成之后如圖1所示。用箭頭標出內存塊的標志位為1，其它部分內存塊標志位都為0，內存具體大小為條形框中的數值。

1.2 動態內存分配和釋放

內存分配主要分為兩個階段：①空閑內存區間查找階段[3]；②修改內存控制頭信息。

動態內存分配步驟如下： ①檢查申請內存的大?。╯ize）：如果size小于等于16，則從小塊內存開始查找；否則，從大塊內存開始查找；②如果查找到的內存塊正在使用，則累加標志位coal置0（不累加），繼續查找下一塊；否則判斷當前內存是否大于等于size。如果大于等于size，則跳出循環；否則，記錄當前指針，繼續尋找下一塊空閑內存并進行合并，直到當前內存大于等于size或查找到避免內存溢出塊才跳出循環；③如果該塊空閑內存比size大4B或更多，則進行內存分割；④如果申請內存成功，則將新申請到的內存標志位置1，返回可用內存空間指針；否則，指針返回NULL。

動態內存釋放步驟如下：①內存指針向上移動一個單位；②將標志位置0；③判斷指向小塊內存的指針是否大于當前指針：如果大于當前小塊指針，則將該指針調整到當前指針位置。

2 Z-Stack內存管理算法改進與實現

2.1 動態修改指針

在Z-Stack內存管理算法中，每一次內存分配都是從小塊或大塊內存的開始處查找，而不是從第一個可分配內存空間開始查找，嚴重影響了查找速度。本文基于此，在內存分配和釋放時，將起始查找指針進行動態修改，避免申請小塊或大塊靠下部分內存時，多次查找小塊或大塊靠上部分已使用內存塊而浪費時間。

內存申請時，如果size≤16，則從小塊內存開始查找；否則，從大塊內存開始查找。當查找到合適的內存塊時，判斷該內存塊是否大于等于size。當該塊內存比size大4B或更多時，進行內存分割。內存分割后，如果size≤16，則小塊指針修改為分割后未使用內存起始處；否則，則修改大塊指針為分割后未使用內存起始處。

當內存釋放時，如果是分界區和避免內存溢出塊，則指針不修改。否則，如果小塊指針大于當前指針，則將小塊指針修改到當前指針處；否則，大塊指針大于當前指針，則將大塊指針修改到當前指針處。

申請內存時，向下修改指針；釋放內存時，向上修改指針。這樣對大塊和小塊內存指針進行動態修改，可以使得下次申請內存時從第一塊未使用的內存開始查找，避免了原算法從大塊或小塊開始處查找。動態修改指針分為內存分配和釋放兩部分，如圖2和圖3所示。

按照上述內存分配程序流程執行，在IAR調試程序時得到圖4和圖5結果。綠色代碼行表示下步執行到該行。圖4表明內存分割后，向下修改小塊指針。圖5表明內存分割后，向下修改大塊指針。結果表明指針向下修改成功。

按照上述內存釋放的程序流程執行，在IAR調試程序時得到圖6和圖7結果。圖6和圖7下一步都會執行綠色代碼行。圖6表明小塊指針大于當前指針，將小塊指針修改到當前指針處；圖7表明大塊指針大于當前指針，將大塊指針修改到當前指針處。

2.2 多位標志位

內存分配時，如果申請1B大小，先查看分界區和避免內存溢出塊中后一個字節是否使用。如果沒有使用，則返回分界區或避免內存溢出的指針；否則，按照原算法查找。按照改進算法，可以節省4B節空間，提高內存利用率0.13%。本文以3072B為例，如果內存空間更小，則內存利用率會更高。

在內存管理中，原算法只用到了一位標志位，不能很好利用有限的內存空間。借鑒TLSF算法[45]的兩位標志位思想，使用多位標志位實現對內存空間的管理，以提高內存空間利用率，減少內存碎片。改進后的算法用控制頭2B中最高3位表示標志位，具體方法如下：①普通塊（除了分界區和避免內存泄露的兩塊內存）：未使用的用000表示，使用的用100表示；②分界區：未使用的用101表示，使用的用111表示；③避免內存泄露塊：未使用的用001表示，使用的用011表示。

改進算法的內存初始化完成后，控制頭后13位表示內存大小的具體數值如圖8條形框中所示，3位標志位為圖8箭頭右邊所示。

先判斷分界區和避免內存溢出塊是否使用，如果使用，則按照原算法基本思想執行。如果第一位標志位為0并且第三位標志位為1，則返回空，說明沒有查找到合適空間用來分配；如果查找到分界區，按照原算法思想跳過該內存區，在大塊內存繼續查找。多位標志位程序流程如圖9所示。

3 結語

本文對Z-Stack內存管理算法進行了改進，在調試（debugger）模式下選擇Auto查看變量的變化值。分析了變量值的正確性，證明改進算法在保證原算法正常使用的基礎上，Z-Stack能夠穩定工作，沒有出現內存溢出現象，減少了內存空間的浪費，提高了協議棧的處理速度，有效解決了Z-Stack內存利用率和內存分配速度兩大重要問題。

參考文獻：

[1] 吳瑛.ZigBee通信協議棧中的內存和時間管理技術研究[J].計算機時代，2008（9）：6062.

[2] FORTINO G，GALZARANO S，GIANNANTONIO R，et al.Spinebased application development on heterogeneous wireless body sensor networks[EB/OL].http：//xueshu.baidu.com/s？wd=paperuri：（2f7ac6f1d337f00f9c1ac3389b808d15）&filter，2010.

[3] 王冬慧，韓建民，莊嘉琪.基于線段樹的高效內存管理算法及其空間優化[J].計算機應用，2015，35（12）：33683373.

[4] 吳文峰.嵌入式實時系統動態內存分配管理器的設計與實現[D].重慶： 重慶大學，2013.

[5] 陳君，樊皓，吳京洪.基于TLSF算法改進的動態內存管理算法研究[J].網絡新媒體技術，2016（3）：4649.

（責任編輯：杜能鋼）