Z―Stack内存管理算法的改进研究

开篇：润墨网以专业的文秘视角，为您筛选了一篇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]；②修改内存控制头信息。

动态内存分配步骤如下： ①检查申请内存的大小（size）：如果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：///s？wd=paperuri：（2f7ac6f1d337f00f9c1ac3389b808d15）&filter，2010.

[3] 王冬慧，韩建民，庄嘉琪.基于线段树的高效内存管理算法及其空间优化[J].计算机应用，2015，35（12）：33683373.

[4] 吴文峰.嵌入式实时系统动态内存分配管理器的设计与实现[D].重庆： 重庆大学，2013.

[5] 陈君，樊皓，吴京洪.基于TLSF算法改进的动态内存管理算法研究[J].网络新媒体技术，2016（3）：4649.