Z—Stack內(nèi)存管理算法的改進(jìn)研究

鄧慧　郭改枝

摘要 研究了ZigBee協(xié)議棧中的內(nèi)存管理算法，并結(jié)合典型內(nèi)存管理算法TLSF（Two-level Segregated Fit）兩位標(biāo)志位管理內(nèi)存思想，對(duì)Z-Stack內(nèi)存管理算法進(jìn)行了改進(jìn)，該改進(jìn)算法同時(shí)又對(duì)內(nèi)存分配和釋放時(shí)的指針進(jìn)行動(dòng)態(tài)修改。IAR調(diào)試驗(yàn)證分析表明，該改進(jìn)算法提高了內(nèi)存分配速度和內(nèi)存利用率。

關(guān)鍵詞 ZigBee；內(nèi)存管理；內(nèi)存利用率；內(nèi)存分配速度

DOI DOI： 10.11907/rjdk.162529

中圖分類(lèi)號(hào)： TP311

文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào) 文章編號(hào)： 16727800（2017）002005103

0 引言

國(guó)內(nèi)外對(duì)Z-Stack內(nèi)存管理算法研究較少，現(xiàn)有的文獻(xiàn)[12]只是原理闡述，并沒(méi)有作出改進(jìn)。然而，Z-Stack內(nèi)存管理算法又存在內(nèi)存資源有限、內(nèi)存分配速度慢等問(wèn)題。本文針對(duì)上述問(wèn)題對(duì)Z-Stack內(nèi)存管理算法進(jìn)行了改進(jìn)。通過(guò)動(dòng)態(tài)修改指針和使用多位標(biāo)志位，優(yōu)化Z-Stack內(nèi)存管理算法，部分解決了低成本、內(nèi)存資源有限的ZigBee嵌入式系統(tǒng)內(nèi)存利用率和分配速度問(wèn)題。

1 Z-Stack內(nèi)存管理算法分析

1.1 內(nèi)存初始化

實(shí)際應(yīng)用中，通常根據(jù)ZigBee設(shè)備功能不同而分配不同大小的內(nèi)存空間，本文以協(xié)調(diào)器（MAXMEMHEAP =3072B）為例進(jìn)行算法分析。

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

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

1.2 動(dòng)態(tài)內(nèi)存分配和釋放

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

動(dòng)態(tài)內(nèi)存分配步驟如下： ①檢查申請(qǐng)內(nèi)存的大?。╯ize）：如果size小于等于16，則從小塊內(nèi)存開(kāi)始查找；否則，從大塊內(nèi)存開(kāi)始查找；②如果查找到的內(nèi)存塊正在使用，則累加標(biāo)志位coal置0（不累加），繼續(xù)查找下一塊；否則判斷當(dāng)前內(nèi)存是否大于等于size。如果大于等于size，則跳出循環(huán)；否則，記錄當(dāng)前指針，繼續(xù)尋找下一塊空閑內(nèi)存并進(jìn)行合并，直到當(dāng)前內(nèi)存大于等于size或查找到避免內(nèi)存溢出塊才跳出循環(huán)；③如果該塊空閑內(nèi)存比size大4B或更多，則進(jìn)行內(nèi)存分割；④如果申請(qǐng)內(nèi)存成功，則將新申請(qǐng)到的內(nèi)存標(biāo)志位置1，返回可用內(nèi)存空間指針；否則，指針?lè)祷豊ULL。

動(dòng)態(tài)內(nèi)存釋放步驟如下：①內(nèi)存指針向上移動(dòng)一個(gè)單位；②將標(biāo)志位置0；③判斷指向小塊內(nèi)存的指針是否大于當(dāng)前指針：如果大于當(dāng)前小塊指針，則將該指針調(diào)整到當(dāng)前指針位置。

2 Z-Stack內(nèi)存管理算法改進(jìn)與實(shí)現(xiàn)

2.1 動(dòng)態(tài)修改指針

在Z-Stack內(nèi)存管理算法中，每一次內(nèi)存分配都是從小塊或大塊內(nèi)存的開(kāi)始處查找，而不是從第一個(gè)可分配內(nèi)存空間開(kāi)始查找，嚴(yán)重影響了查找速度。本文基于此，在內(nèi)存分配和釋放時(shí)，將起始查找指針進(jìn)行動(dòng)態(tài)修改，避免申請(qǐng)小塊或大塊靠下部分內(nèi)存時(shí)，多次查找小塊或大塊靠上部分已使用內(nèi)存塊而浪費(fèi)時(shí)間。

內(nèi)存申請(qǐng)時(shí)，如果size≤16，則從小塊內(nèi)存開(kāi)始查找；否則，從大塊內(nèi)存開(kāi)始查找。當(dāng)查找到合適的內(nèi)存塊時(shí)，判斷該內(nèi)存塊是否大于等于size。當(dāng)該塊內(nèi)存比size大4B或更多時(shí)，進(jìn)行內(nèi)存分割。內(nèi)存分割后，如果size≤16，則小塊指針修改為分割后未使用內(nèi)存起始處；否則，則修改大塊指針為分割后未使用內(nèi)存起始處。

當(dāng)內(nèi)存釋放時(shí)，如果是分界區(qū)和避免內(nèi)存溢出塊，則指針不修改。否則，如果小塊指針大于當(dāng)前指針，則將小塊指針修改到當(dāng)前指針處；否則，大塊指針大于當(dāng)前指針，則將大塊指針修改到當(dāng)前指針處。

申請(qǐng)內(nèi)存時(shí)，向下修改指針；釋放內(nèi)存時(shí)，向上修改指針。這樣對(duì)大塊和小塊內(nèi)存指針進(jìn)行動(dòng)態(tài)修改，可以使得下次申請(qǐng)內(nèi)存時(shí)從第一塊未使用的內(nèi)存開(kāi)始查找，避免了原算法從大塊或小塊開(kāi)始處查找。動(dòng)態(tài)修改指針?lè)譃閮?nèi)存分配和釋放兩部分，如圖2和圖3所示。

按照上述內(nèi)存分配程序流程執(zhí)行，在IAR調(diào)試程序時(shí)得到圖4和圖5結(jié)果。綠色代碼行表示下步執(zhí)行到該行。圖4表明內(nèi)存分割后，向下修改小塊指針。圖5表明內(nèi)存分割后，向下修改大塊指針。結(jié)果表明指針向下修改成功。

按照上述內(nèi)存釋放的程序流程執(zhí)行，在IAR調(diào)試程序時(shí)得到圖6和圖7結(jié)果。圖6和圖7下一步都會(huì)執(zhí)行綠色代碼行。圖6表明小塊指針大于當(dāng)前指針，將小塊指針修改到當(dāng)前指針處；圖7表明大塊指針大于當(dāng)前指針，將大塊指針修改到當(dāng)前指針處。

2.2 多位標(biāo)志位

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

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

改進(jìn)算法的內(nèi)存初始化完成后，控制頭后13位表示內(nèi)存大小的具體數(shù)值如圖8條形框中所示，3位標(biāo)志位為圖8箭頭右邊所示。

先判斷分界區(qū)和避免內(nèi)存溢出塊是否使用，如果使用，則按照原算法基本思想執(zhí)行。如果第一位標(biāo)志位為0并且第三位標(biāo)志位為1，則返回空，說(shuō)明沒(méi)有查找到合適空間用來(lái)分配；如果查找到分界區(qū)，按照原算法思想跳過(guò)該內(nèi)存區(qū)，在大塊內(nèi)存繼續(xù)查找。多位標(biāo)志位程序流程如圖9所示。

3 結(jié)語(yǔ)

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

參考文獻(xiàn)：

[1] 吳瑛.ZigBee通信協(xié)議棧中的內(nèi)存和時(shí)間管理技術(shù)研究[J].計(jì)算機(jī)時(shí)代，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] 王冬慧，韓建民，莊嘉琪.基于線段樹(shù)的高效內(nèi)存管理算法及其空間優(yōu)化[J].計(jì)算機(jī)應(yīng)用，2015，35（12）：33683373.

[4] 吳文峰.嵌入式實(shí)時(shí)系統(tǒng)動(dòng)態(tài)內(nèi)存分配管理器的設(shè)計(jì)與實(shí)現(xiàn)[D].重慶： 重慶大學(xué)，2013.

[5] 陳君，樊皓，吳京洪.基于TLSF算法改進(jìn)的動(dòng)態(tài)內(nèi)存管理算法研究[J].網(wǎng)絡(luò)新媒體技術(shù)，2016（3）：4649.

（責(zé)任編輯：杜能鋼）