一种内存管理方法和装置

本发明涉及内存管理技术，具体涉及一种内存管理方法和装置。

因嵌入式系统应用广泛，如何对嵌入式系统内存进行高效管理成为了研究 热点。

目前，在嵌入系统中，主要采用两种内存管理方法：一种是静态内存管理 方法，另一种是动态内存管理方法；这里，对内存管理主要涉及到内存申请与 内存释放；其中，

静态内存管理方法，事先将内存划分为几个区，再将几个区划分为多个大 小相等的内存块；当有内存申请时，如果预申请的内存大小与内存块或区内存 大小相等或相近，内存利用率较高；但是，如果预申请的内存很小，则很小的 预申请内存却占用了很大的内存块，因灵活性较差，就会造成内存利用率低。

动态内存管理方法，通常通过链表或栈方法来实现；其中，链表方法利用 链表将空闲内存块排列，当进程需要申请内存时，从链表的头部开始搜索空闲 内存块，直到搜索到大小合适的内存块，将搜索到的内存块分配给申请内存的 进程使用；当有内存块释放时，链表方法将已经释放的内存块即空闲内存块放 在链表的尾部；栈方法与链表方法类似，将空闲内存块排列在栈顶，当有进程 申请内存时，从栈顶开始搜索，直到搜索出大小合适的内存块；当有内存块释 放时，将已经释放的内存块即空闲内存块排放在栈顶；在嵌入式系统中，动态 内存管理方法应用得很多，但是，因为嵌入式系统需要不断地对内存进行申请 和释放，即嵌入式系统需要不断地对内存进行动态分配，加重了系统本身资源 运行负担。

有鉴于此，本发明的主要目的在于提供一种内存管理方法和装置，可提高 内存申请和释放灵活性，减轻嵌入式系统资源运行负担。

为达到上述目的，本发明的技术方案是这样实现的：

本发明提供了一种内存管理方法，将内存划分为一阶以上内存池，每阶内 存池具有至少一个管理节点；该方法还包括：

申请内存时，根据申请内存大小确定出阶内存池，再根据内存池管理列表 中阶内存池的占用情况为内存申请分配内存；

释放内存时，根据需释放内存的标记信息，对内存进行释放。

上述方案中，所述内存池管理列表处于初始化初期阶段；

所述申请内存时，根据申请内存大小确定出阶内存池，并根据内存池管理 列表中阶内存池的占用情况为内存申请分配内存为：

依据申请内存大小确定选择因子，并根据选择因子确定出内存池的阶数i；

判断阶数i是否等于最高阶内存池，当阶数i内存池为最高阶内存池且最高 阶内存池存在有满足条件的管理节点，则申请内存成功，标识满足条件的管理 节点；

当阶数i内存池为最高阶内存池、但最高阶内存池不存在能够满足条件的 管理节点，则最高阶内存池生成一个管理节点，申请内存成功，标识生成的管 理节点；

当阶数i内存池不是最高阶内存池，则第i阶内存池内存向第i+L阶内存池 进行内存申请，第i+L阶内存池不是最高阶内存池时，第i+L阶内存池继续向 第i+2L阶内存池进行内存申请，以此类推，直到申请到最高阶内存池；由最高 阶内存池的管理节点分配内存给第i+nL阶，第i+nL阶接收到内存分配后，生 成管理节点，并分配内存给第i+(n‑1)L阶内存池，第i+(n‑1)L阶内存池接 收到内存分配后，生成管理节点，并分配内存给第i+(n‑2)L阶内存池，以此 类推，直到第i阶内存池接收到分配后，生成第i阶内存池的管理节点；由生成 的管理节点为内存申请进行内存分配，申请内存成功，标识生成的管理节点；

其中，i+nL为小于等于12的正整数，n、L均为小于等于12的正整数。

上述方案中，所述内存池管理列表初始化完成之后，所述申请内存时，根 据申请内存大小确定出阶内存池，并根据内存池管理列表中阶内存池的占用情 况为内存申请分配内存为：

依据申请内存大小确定选择因子，并根据选择因子确定出内存池的阶数i；

查第i阶内存池存在的所有管理节点，是否存在有满足条件的管理节点；

能够在第i阶内存池查到满足条件的管理节点，则内存申请成功，标识 满足条件的管理节点；

不能够在第i阶内存池查到满足条件的管理节点，再判断第i阶内存池剩 余内存长度是否大于等于申请内存长度；

当第i阶内存池剩余内存长度大于等于申请内存长度，生成一个管理节点， 标识所生成的管理节点；

当第i阶内存池剩余内存长度小于申请内存长度，则查第i+L阶内存池 的所有管理节点是否存在满足条件的管理节点，能够查到则确认申请内存成 功，标识满足条件的管理节点；在第i+L阶内存池中查不到满足条件的管理 节点，再判断第i+L阶内存池剩余内存长度是否大于等于申请内存长度；

当第i+L阶内存池剩余内存长度大于等于申请内存长度，生成一个管理节 点，标识所生成的管理节点；当第i+L阶内存池剩余内存长度小于申请内存长 度，查第i+2L阶内存池的所有管理节点是否存在满足条件的管理节点，

以此类推，直至查到满足条件的管理节点，申请内存成功，标识满足条 件的管理节点；或者，直至查到最高阶内存池不存在有满足条件的管理节点 且剩余内存长度小于内存申请长度，则查第i‑1阶内存池所有管理节点是否 存在有满足条件的管理节点，存在满足条件的管理节点，申请内存成功，标识 满足条件的管理节点；不存在满足条件的管理节点，继续查第i‑2阶内存池 所有管理节点，以此类推，直至能查到满足条件的管理节点，申请内存成功， 标识满足条件的管理节点；直至查到第0阶内存池仍然不存在满足条件的管 理节点，申请内存失败。

上述方案中，所述释放内存时，根据需释放内存的标记信息，对内存进行释 放为：释放内存时，查起始地址，查到起始地址之后，释放申请长度的内 存块。

上述方案中，所述内存进行释放后，该方法还包括：先判断已释放内存所 属管理节点可管理的其它内存块是否全部为空闲内存块，如果不是，则释放内 存流程结束；如果是，则释放所述管理节点；

判断在所述管理节点所属的阶内存池中，与所述管理节点具有同一个父节 点的其它管理节点可管理的所有内存块是否全部为空闲内存块，如果不是，则 释放内存流程结束；如果是，则释放与所述管理节点具有同一个父节点的其它 管理节点，同时释放所述管理节点的父节点；

继续判断与所述管理节点的父节点具有同一个父节点的其它管理节点可管 理的所有内存块是否全部为空闲内存块，如果不是，则释放流程结束；如果是， 则释放与所述管理节点的父节点具有同一个父节点的其它管理节点、释放管理 节点的祖父节点；

继续判断在所述管理节点的祖父节点的所属阶内存池中，是否有与所述管 理节点的祖父节点具有同一个父节点的其它管理节点可管理的所有内存块是否 全部为空闲内存块，如果不是，则释放内存流程结束；如果是，则释放与所述 管理节点的祖父节点具有同一个父节点的其它管理节点，释放所述管理节点的 祖父节点的父节点；

以此类推，直到判断到最高阶内存池。

本发明还提供了一种内存管理装置，该装置包括：内存申请管理模块、内 存释放管理模块和内存池管理列表；其中，

所述内存申请管理模块，用于申请内存时，根据申请内存大小确定出阶内 存池，并根据所述内存池管理列表中阶内存池的占用情况为内存申请分配内存；

所述内存释放管理模块，用于释放内存时，根据释放内存标记信息，对所 述内存池管理列表中的内存进行释放；

所述内存池管理列表，用于为内存申请管理模块和内存释放管理模块提供 内存；所述内存划分为一阶以上内存池，每阶内存池具有至少一个管理节点。

上述方案中，所述内存申请管理模块用于：

在所述内存池管理列表初始化初期阶段，依据接收到的申请内存大小确定 选择因子，再确定出阶数i；并判断第i阶内存池是否为最高阶内存池；

当判断出为最高阶内存池，查最高阶内存池中是否存在有能够满足条件 的管理节点，当查出有满足条件的管理节点时，内存申请成功，标识满足条 件的管理节点；

当判断出为最高阶内存池，且在最高阶内存池查不到能够满足条件的管 理节点时，驱动所述内存池管理列表生成最高阶内存池的一个管理节点，内存 申请成功，标识所生成的管理节点；

当判断出第i阶内存池不是最高阶内存池时，向所述内存池管理列表中的 第i阶内存池申请内存，如果第i阶内存池无管理节点，则第i阶内存池向第i+L 阶内存池进行内存申请；

当判断出第i+L阶内存池是最高阶内存池时，查最高阶内存池中是否存 在有能够满足条件的管理节点，当查出有满足条件的管理节点时，内存申请 成功，标识满足条件的管理节点；当查不到有满足条件的管理节点时，驱动 所述内存池管理列表生成最高阶内存池的一个管理节点，内存申请成功，标识 所生成的管理节点；

当判断出第i+L阶内存池不是最高阶内存池时，第i+L阶内存池向第i+2L 阶内存池进行内存申请；

以此类推，直至申请到最高阶内存池，由最高阶内存池的管理节点给第 i+mL阶内存池分配内存，第i+mL阶内存池接收分配内存后，驱动所述内存池 管理列表生成一个管理节点，由所生成的管理节点给第i+(m‑1)L阶内存池分 配内存，第i+(m‑1)L阶内存池接收到分配后，驱动所述内存池管理列表生成 一个管理节点，由所生成的管理节点分配给第i+(m‑2)L阶内存池分配内存， 以此类推，直至第i阶内存池接收到分配后，驱动所述内存池管理列表生成第i 阶内存池的一个管理节点，申请内存成功，标识所生成的管理节点；

这里，i+mL为小于等于12的正整数、m、L均为小于等于12的正整数。

上述方案中，所述内存申请管理模块还用于：

在内存池管理列表初始化完成之后，依据接收到的申请内存的大小确定选 择因子，再确定出阶数i；

查第i阶内存池存在的所有管理节点，是否存在有满足条件的管理节点，

能够在第i阶内存池查到满足条件的管理节点，则内存申请成功，驱动 所述内存池管理列表对该管理节点进行标识；

在第i阶内存池查不到满足条件的管理节点，则再判断第i阶内存池剩余 内存长度是否大于等于内存申请长度，

当第i阶内存池剩余内存长度大于等于申请内存长度时，驱动所述内存池 管理列表生成一个管理节点，并标识所生成的管理节点；

当第i阶内存池剩余内存长度小于申请内存长度时，查第i+L阶内存池 的所有管理节点是否存在有满足条件的管理节点，能够查到就确认内存申请 成功，驱动所述内存池管理列表标识满足条件的管理节点；在第i+L阶内存池 查不到，再判断第i+L阶内存池剩余内存长度是否大小等于内存申请长度，

当第i+L阶内存池剩余内存长度大于等于申请内存长度时，驱动所述内存 池管理列表生成一个管理节点，并标识所生成的管理节点；

当第i+L阶内存池剩余内存长度小于申请内存长度时，继续查第i+2L阶 内存池的所有管理节点是否存在满足条件的管理节点，

以此类推，直至查到满足条件的管理节点，内存申请成功，驱动所述内 存池管理列表标识满足条件的管理节点；

或者，直至查到最高阶内存池也不存在有满足条件的管理节点且剩余内 存长度小于内存申请长度，转向查第i‑1阶内存池所有管理节点是否存在有 满足条件的管理节点，存在满足条件的管理节点，内存申请成功，标识满足条 件的管理节点；不存在满足条件的管理节点，查第i‑2阶内存池所有管理节 点；以此类推，直至能查到满足条件的管理节点，内存申请成功，标识满足 条件的管理节点；或查到第0阶内存池仍然不存在满足条件的管理节点，确 认此次申请内存失败。

上述方案中，所述内存释放管理模块，用于在接收到释放内存请求后，查 起始地址，查到之后驱动所述内存池管理列表释放申请长度的内存块。

上述方案中，所述内存释放管理模块，还用于在释放内存后，判断释放内 存所属管理节点可管理的其它内存块是否全部为空闲内存块，如果不是，则释 放内存结束；如果是，则驱动所述内存池管理列表释放该管理节点；

之后，判断在所述管理节点所属的阶内存池中，与所述管理节点具有同一 个父节点的其它管理节点可管理的所有内存块是否全部为空闲内存块；如果不 是，释放内存结束；如果是，则驱动所述内存池管理列表释放与该管理节点具 有同一个父节点的其它管理节点，同时释放该管理节点的父节点；

然后，再判断与所述管理节点的父节点具有同一个负节点的其它管理节点 可管理的所有内存块是否全部为空闲内存块，如果不是，释放内存结束；如果 是，则驱动所述内存池管理列表释放所述管理节点的父节点具有同一个负节点 的其它管理节点，释放所述管理节点的祖父节点；

在管理节点的祖父节点的所属阶内存池中，判断与所述管理节点的祖父节 点具有同一个父节点的其它管理节点可管理的所有内存块是否全部为空闲内存 块，如果不是，则释放内存结束；如果是，则驱动所述内存池管理列表释放与 所述管理节点的祖父节点具有同一个父节点的其它管理节点、释放所述管理节 点的祖父节点的父节点；

以此类推，直到判断到最高阶内存池。

本发明所提供的内存管理方法和装置，将内存划分为一阶以上内存池，当 有进程申请内存时，内存申请管理模块根据申请内存大小确定出阶内存池，再 根据内存池管理列表中阶内存池的占用情况为内存申请分配内存；当有进程释 放内存时，根据需释放内存在内存池管理列表中的标记信息，进行内存释放； 本发明的内存池管理列表的内存块基本长度可变，灵活性强，可根据不同类型 的嵌入式系统需求，实时调整内存块基本长度，提高了内存资源利用率，减轻 了嵌入式系统资源的运行负担。

图1为本发明内存池管理列表的组成结构示意图；

图2为本发明内存管理方法的实现流程示意图；

图3为本发明内存管理装置的组成结构示意图。

在对本发明内存管理方法描述之前，先对本发明的内存池管理列表进行说 明，如图1所示，以最高阶内存池为第12阶内存池为例进行说明，所述内存池 管理列表，将内存划分为第0阶(Order)内存池‑第12阶内存池共13阶内存 池，每阶内存池具有至少一个管理节点，每个管理节点均管理256块内存块； 实质上，申请内存即为申请管理节点管理的256块内存块中的至少一块，申请 成功之后，被占用的内存块称为已申请内存块；释放内存即为释放管理节点管 理的256块内存块中的至少一块，被释放的内存块称为空闲内存块，所述空闲 内存块可以用于下一次内存申请。

这里，为方便内存池管理列表的使用，需引入内存块基本长度的概念，通 常，取内存块基本长度为2^P字节(B，Byte)(P为正整数)，那么，第0阶内 存池的每个内存块基本长度为2^P字节，第i阶内存池的每个内存块基本长度 为2^P*(2^i)字节，其中，i为1至12中任意值；

本文中，仅以所述内存池管理列表划分为从第0阶内存池到第12阶内存池 共13阶内存池为例进行说明，在实际应用中，所述内存池管理列表还可以划分 为从第0阶内存池到第Y阶内存池共(Y+1)阶内存池，其中Y为正整数，Y 的取值由嵌入式系统中的总内存容量决定，并在所述嵌入式系统启动之前预先 设置好。

为方便描述，本实施方式中选取P＝6，即基本内存块长度为2^6＝64B，那 么，第0阶内存池的每个内存块基本长度为64B，第1阶内存池的每个内存块 基本长度为64B*(2^1)＝128B，以此类推，第11阶内存池的每个内存块基本 长度为128千字节(KB，Kilo Byte)，第12阶内存池的每个内存块基本长度为 256KB；因为每阶内存池每个管理节点均可管理256块内存块，所以，第0阶 内存池的每个管理节点能够管理的内存长度为64B*256＝16KB，第1阶内存池 的每个管理节点能够管理的内存长度为128B*256＝32KB，以此类推，第12阶 内存池每个管理节点能够管理的内存长度为256KB*256＝64兆字节(MB，Mega  Byte)。

上述对内存池管理列表的介绍中，内存池阶数、每阶内存池可管理的内存 块的数量、以及每个内存块的长度可依据嵌入式系统对内存的需求而灵活设置， 是在嵌入式系统启动之前预先设置好的；同时，在嵌入式系统启动时，在所述 内存池管理列表中，预先设置第12阶内存池只具有一个管理节点，其他阶内存 池无管理节点；随着嵌入式系统的进程不断申请内存，最高阶内存池以及其它 阶内存池将会根据进程申请内存不断生成管理节点，每阶内存池可生成至少一 个管理节点。

在管理节点生成后，该管理节点的管理节点数据结构将记录以下内容：该 管理节点属于第几阶内存池，该管理节点是所属阶内存池的第几个管理节点， 该管理节点可管理的内存块的数量(256块)及能够管理的内存长度；因为每 个管理节点可管理内存块的数量为256个，所以管理节点数据结构中的比特位 图(Bitmap)可由256个二进制的比特代表，每个比特位代表该管理节点对应 位置的内存块的使用状态，比特位为0表明该位置的内存块已经被进程申请占 用；比特位为1表明该位置的内存块为空闲内存块，可被进程申请；管理节点 数据结构中的地址项：记录有进程申请到的、内存块占用管理节点可管理的内 存块的起始地址及申请长度；

例如，进程A申请到了第0阶管理内存池的第一个管理节点B的第一个内 存块的内存N，那么，在管理节点B管理节点数据结构的Bitmap位图的第一位 比特取值为0，地址项记录管理节点B的第一个内存块为起始地址以及申请到 的长度N。

本发明中，将起始地址作为内存申请一个标记项，申请长度作为内存申请 另一个标记项，将它们的集合称之为双标记。

本发明还可将所述双标记从管理节点数据结构中提取出来，将所述双标记 同申请到的内存一起在内存池中进行关联保存，因为所述双标记共占用8字节， 所以，申请长度标记项应在进程预申请内存长度大小的基础上再加上8字节。

在后面对本发明技术方案的描述中，进程申请内存长度均指进程预申请长 度再加上8字节；且均采用双标记从管理节点数据结构中提取出来的形式。

本发明提供了一种内存管理方法，将内存划分为一阶以上内存池，每阶内 存池具有至少一个管理节点；如图2所示，该方法还包括：

步骤10：申请内存时，根据申请内存大小确定出阶内存池，再根据内存池 管理列表中阶内存池的占用情况为内存申请分配内存；

这里，有进程申请内存、且阶内存池的管理节点根据所申请内存大小分配 相应内存块后，被分配的内存块会标记为已被申请占用；其中，所述阶内存池 的管理节点，在嵌入式系统启动时，仅有最高阶内存池设置有一个管理节点， 其它阶内存池无管理节点；但随着进程不断申请内存，最高阶内存池以及其它 阶内存池会根据进程申请内存不断生成管理节点，每阶内存池可生成至少一个 管理节点；

步骤11：释放内存时，根据需释放内存的标记信息，对内存进行释放。

这里，所述标记信息是指申请内存时设置的双标记，即：内存申请成功后， 占用管理节点可管理的内存块的起始地址及申请长度；

相应的，本步骤具体为：释放内存时，先查起始地址，查到起始地址 后，释放申请长度的内存块。

在步骤10中，进程A预申请内存长度大小为N(包括8字节长度)，简称 为申请内存N，依据公式(1)，计算出进程A是向第i阶内存池进行内存申请 的；

i＝log2(N/K/64)                                (1)

其中，K为选择因子，取值为正整数，K的取值由不等式组公式(2)决定；

(64*2^Log2(N/(64*K))*N/K)/N＜110％

(64*2^LOG2(N/(64*K))*256＞N                    (2)

这里，Log2结果取值向大的整数取整；公式(2)中，为减少阶内存池分 配内存的浪费，第i阶内存池为进程分配的内存不能超过申请内存N的10％， 所述10％由经验而得；第i阶内存池存在有管理节点能够提供大于申请内存N 的内存；因为内存池管理列表基本内存块长度即第0阶内存池的内存块基本长 度为64B，所以，不论进程申请内存N是否为64B的整数倍，阶内存池只能分 配给进程64B的整数倍个内存大小；当进程申请内存N不是64B的整数倍，那 么，就可能存在着部分内存的浪费，为了减小内存浪费，得出公式(2)。

在步骤10中，进程A申请内存N时存在有两种情况：第一种情况是，在 内存池管理列表初始化初期阶段，进程A进行内存申请；第二种情况是，内存 池管理列表初始化完成之后，进程A进行内存申请。

针对第一种情况，在内存池管理列表初始化初期阶段，只有第12阶内存池 具有一个管理节点point_120，其他阶内存池均不具有管理节点；这里，用point_ij 表示第i阶内存池的第j个管理节点，那么，进一步的，步骤10可以为：

依据给出的申请内存N，由公式(2)确定选择因子K，再由公式(1)确 定阶数i；

判断i是否等于最高阶数即是否等于12，当i等于12且管理节点point_120 能够满足条件时，申请内存N成功，标识管理节点point_120，直接由管理节点 point_120为进程A分配长度为N的内存；

当i等于12且管理节点point_120不能够满足条件时，第12阶内存池生成 一个管理节点point_121，由管理节点point_121为进程A分配长度为N的内存， 申请内存N成功，标识管理节点point_121；

当i不等于12，即第i阶内存池不是最高阶内存池时，进程A申请内存N 向第i阶内存池进程内存申请，但此时第i阶内存池无管理节点，那么，第i阶 内存池向第i+L阶内存池进行内存池申请(L为小于等于12的正整数)，第i+L 阶内存池不是最高阶内存池时，第i+L阶内存池继续向第i+2L阶内存池进行内 存申请，以此类推，因为内存池管理列表初始化初期阶段只有第12阶内存池存 在有管理节点，所以，最终只能由第12阶内存池的管理节点point_120给第i+mL 阶内存池(m为正整数，i+mL为小于等于12的正整数)分配64M内存，第i+mL 阶内存池接收分配内存后，生成管理节点point_(i+mL)0，由管理节点 point_(i+mL)0给第i+(m‑1)L阶内存池分配内存64B*2^(i+mL)*256，第i+(m‑1) L阶内存池接收到分配后，生成管理节点point_(i+(m‑1)L)0，由管理节点 point_(i+(m‑1)L)0分配给第i+(m‑2)L阶内存池分配内存64B*2^(i(m‑1)L)*256， 以此类推，直到第i阶内存池接收到分配后，生成第i阶内存池的第一个管理节 点point_i0，由管理节点point_i0为进程A分配内存N，进程A内存申请成功， 标识管理节点point_i0。

这里，所述管理节点满足条件即为：管理节点可提供连续多个内存块给申 请内存N，所述多个取决于申请内存N、计算出的i及第i阶每个内存块基本长 度；所述标识管理节点为：管理节点数据结构中的Bitmap位图的相应数量连续 内存块位标识为0；双标记将记录进程申请到的内存占用管理节点可管理的内 存块的起始地址及申请长度；在进行本发明的描述时，“满足条件的管理节点”、 “标识管理节点结构数据”均为此意，无需再进行说明。

在内存池管理列表初始化初期阶段，随着进程的不断申请，每一阶内存池 均具有至少一个管理节点，第二种情况即在此背景下，那么，针对第二种情况， 步骤10可以为：

依据给出的申请内存N，由公式(2)确定选择因子K，再由公式(1)确 定阶数i；

查第i阶内存池存在的所有管理节点，是否存在有满足条件的管理节点，

能够在该阶内存池查到满足条件的管理节点，则申请内存N成功，标识 该管理节点，申请内存流程结束；

不能够在该阶内存池查到满足条件的管理节点，则查第i+L阶内存池 的所有管理节点是否存在满足条件的管理节点，能够查到就确认申请内存N 成功，标识管理节点，申请内存流程结束；若在该阶内存池中查不到满足条 件的管理节点，就查第i+2L阶内存池的所有管理节点是否存在满足条件的管 理节点，

以此类推，直到或查到满足条件的管理节点，内存申请成功，标识该管 理节点，申请内存流程结束；或查到最高阶内存池所有管理节点不存在满足 条件的管理节点，那么查第i‑1阶内存池所有管理节点，是否存在有满足条 件的管理节点，存在满足条件的管理节点，申请内存N成功，标识该管理节点， 申请内存流程结束；不存在满足条件的管理节点，查第i‑2阶内存池所有管 理节点，查方法与上述方法相同，以此类推，直到或能够查到满足条件的 管理节点，申请内存N成功，标识满足条件的管理节点，申请内存流程结束； 直到或查到第0阶内存池仍然不存在满足条件的管理节点，申请内存N失败， 确认此次进程A申请失败，申请内存流程结束。

下面结合具体实施例，对实现申请内存的内存管理方法做进一步说明。

这里，以内存池管理列表基本内存块长度为64B、L＝3为例，对步骤10 进行进一步的说明。

在内存池管理列表初始化初期阶段，内存池管理列表中只有第12阶内存池 具有一个管理节点；其他阶内存池均不具有管理节点；令第12阶内存池存在的 这个管理节点为point_120，则该管理节点能够管理的内存长度为256*256 KB＝64MB；

这时，当存在有进程A申请内存大小为N＝48B时，代入公式(2)确定选 择因子K＝8，代入公式(1)，得出阶数i＝0，也就是说，需要在第0阶内存池 进行申请48B的内存，而此时第0阶内存池不具有管理节点，那么，向第0+L＝3 阶内存池进行内存申请，第3阶内存池也不具有管理节点，向第3+L＝6阶内存 池进行内存申请，第6阶内存池不具有管理节点，向6+L＝9阶内存池进行内存 申请，第9阶内存池不具有管理节点，向第9+L＝12阶内存池进行内存申请， 第12阶内存池存在有一管理节点point_120，其接收到申请后分配总长度为64M 内存给第9阶内存池；

第9阶内存池接收分配后，生成第9阶的第一个管理节点point_90，该阶 内存块基本长度为32KB，则管理节点point_90能够管理的内存长度为256*32 KB＝8M，并分配总长度为8M的内存给第6阶内存池；

第6阶内存池接收分配后，生成第6阶内存池的第一个管理节点point_60， 该阶内存块基本长度为4KB，则管理节点point_60能够管理的内存长度为256*4 KB＝1M，并分配总长度为1M的内存给第3阶内存池；

第3阶内存池接收分配后，生成第3阶的第一个管理节点point_30，该阶 内存块基本长度为512B，则管理节点point_30能够管理的内存长度为256*512 B＝128KB，并分配总长度为1M的内存给第0阶内存池；

第0阶内存池接收分配后，生成第0阶的第一个管理节点point_00，该阶 内存块基本长度即内存池管理列表的基本内存块长度64B，而进程A申请的内 存为48B，所以管理节点point_00为进程A分配其可管理的256块内存块中的 第一个内存块就已足够；管理节点point_00的管理节点数据结构中的Bitmap 位图的第一位标识为0，表明管理节点point_00的第一块内存块已经被进程申 请，同时，双标记将记录管理节点point_00管理的第一个内存块的起始地址及 进程申请到长度N。

这里，管理节点point_30生成后，分配总长度为1M的内存给第0阶内存 池，针对进程A第0阶内存池只生成了管理节点point_00就能满足进程A的需 求，而管理节点point_00能够管理的内存长度为256*64B＝16KB，远小于管理 节点point_30分配的1M内存，这说明在后续其他进程的不断申请中，对于管 理节点point_30分配的1M内存，第0阶内存池将还会生成除了管理节点 point_00之外的其他管理节点point_0X(X为正整数)，这里，称管理节点 point_00与其他管理节点point_0X为第3阶内存池的管理节点point_30的子节 点，称第3阶内存池的管理节点point_30为管理节点point_00与其他管理节点 point_0X的父节点；

以此类推，第3阶内存池的管理节点point_30与其他管理节点point_3X为 第6阶内存池的管理节点point_60的子节点，称第6阶内存池的管理节点 point_60为第3阶内存池的管理节点point_30与其他管理节点point_3X的父节 点；

第6阶内存池的管理节点point_60与其他管理节点point_6X为第9阶内存 池的管理节点point_90的子节点，称第9阶内存池的管理节点point_90为第6 阶内存池管理节点point_60与其他管理节点point_6X的父节点；

第9阶内存池的管理节点point_90与其他管理节点point_9X为第9阶内存 池的管理节点point_120的子节点，称第12阶内存池的管理节点point_120为 第9阶内存池的管理节点point_90与其他管理节点point_9X的父节点；

这里，可认为第i阶内存池的管理节点是第i‑L阶内存池对应管理节点的父 节点，第i‑L阶内存池对应管理节点是第i阶内存池的管理节点的子节点。这里， 所给出子节点、父节点的概念，将会在释放内存时用到。

至此，内存池管理列表中不仅第12阶内存池具有管理节点，第9阶、第6 阶、第3阶、第0阶内存池均具有了管理节点；随着进程不断申请内存，最终 内存池管理列表中其它阶内存池均会生成至少一个管理节点；其它阶内存池生 成管理节点的方法与上述方法相同。

内存池管理列表初始化完成之后即第0阶内存池‑第12阶内存池均具有至 少一个管理节点后，当有进程申请内存N’时，本发明的内存管理方法为：

步骤30：根据公式(2)确定出选择因子K，再根据公式(1)得出阶数i；

步骤31：查第i阶内存池存在的所有管理节点，是否存在有满足条件的 管理节点，

当在第i阶内存池能够查到满足条件的管理节点D’，继续执行步骤32；

当在第i阶内存池查不到满足条件的管理节点D’，再判断第i阶内存池 中剩余内存长度是否大于等于申请内存N’，当第i阶内存池剩余内存长度大于 等于申请内存N’，则生成一个管理节点，并标识该生成的管理节点，申请内存 流程结束；

当第i阶内存池剩余内存长度小于申请内存N’，向第i+3阶内存池进行内 存N’申请，将第i+3阶内存池作为当前阶内存池，继续执行步骤33；

所述满足条件的管理节点即为：管理节点可提供连续多个内存块给申请内 存N’；所述剩余内存长度为：第i阶内存池具有的总内存长度减去该阶内存池 已生成的管理节点占用该阶内存池的内存长度；在后面进行本发明描述中，凡 是涉及“满足条件的管理节点”、“剩余内存长度”均为此意，不再进行说明；

步骤32：申请内存N’成功，标识管理节点D’，申请内存流程结束；

所述标识管理节点为：将管理节点数据结构中的Bitmap位图的相应数量连 续内存块位标识为0；双标记将记录进程申请到的内存占用管理节点内存的起 始地址及申请长度；在后面进行本发明的描述时“标识管理节点”均为此意， 无需再进行说明；

步骤33：判断当前阶内存池是否为最高阶内存池(第12阶内存池)；

当前阶内存池不是最高阶内存池时，执行步骤34；

当前阶内存池最高阶内存池时，执行步骤35；

步骤34：查当前阶内存池所有管理节点是否存在有满足条件的管理节 点；

当该阶内存池存在有满足条件的管理节点，申请内存N’成功，标识该满足 条件的管理节点，申请内存流程结束；

当该阶内存池不存在有满足条件的管理节点，再判断该阶内存池中剩余内 存长度是否大于等于申请内存N’，当该阶内存池剩余内存长度大于等于申请内 存N’，则执行步骤36；

当该阶内存池剩余内存长度小于申请内存N’，继续执行步骤37；

步骤35：当前阶内存池是最高阶内存池时，查最高阶内存池是否存在有 满足条件的管理节点，

当在最高阶内存池查到满足条件的管理节点，那么，申请内存N’成功， 标识该满足条件的管理节点，申请内存流程结束；

当在最高阶内存池查不到满足条件的管理节点，再判断最高阶内存池中 剩余内存长度是否大于等于申请内存N’，当该阶内存池剩余内存长度大于等于 申请内存N’，则生成一个管理节点，并标识该生成的管理节点，申请内存流程 结束；

当该阶内存池剩余内存长度小于申请内存N’，执行步骤38；

步骤36：当前阶内存池生成一个管理节点，申请内存N’成功，标识该生 成的管理节点，申请内存流程结束；

步骤37：第i+3阶内存池向第i+3+3阶内存池申请内存，将第i+3+3阶内 存池作为当前阶内存池，之后按步骤33的方法申请内存，以此类推；

直到不管第i+3LL阶内存池(LL为正整数)是不是最高阶内存池，只要存 在有能够提供N’的空闲内存，那么，申请内存N’成功，标识满足条件的管理 节点，申请内存流程结束；

或者，直到第i+3LL阶内存池是最高阶内存池、且最高阶不存在能够提供 N’的空闲内存，执行步骤38；

步骤38：向第i‑1阶内存池继续查，查第i‑1阶内存池是否存在有满足 条件的管理节点，存在有满足条件的管理节点，申请内存N’成功，标识该管理 节点，申请内存流程结束；当第i‑1阶内存池未存在有能够满足条件的管理节 点，向第i‑2阶内存池查是否存在有满足条件的管理节点，查到就确定内 存申请成功，同时标识管理节点，申请内存流程结束；

查不到就向第i‑3阶内存池查是否存在满足条件的管理节点，以此类 推，当查到第0阶内存池，仍然查不到满足条件的管理节点，就确认此次 内存申请失败，申请内存流程结束。

这里，在最高阶内存池也不能申请到N’内存后，转向对第i‑LLL(LLL为 正整数)(先查第i‑1阶，再查第i‑2阶，以此类推)的原因是，依据计算 出的阶数i，只在大于等于第i阶内存池的阶内存池中进行查是不全面的，因 为本发明的每一阶内存池的内存由管理节点进行管理，存在有这种情况：第 i‑LLL阶内存池一个管理节点不能够提供足够内存给申请内存N’，但是，该阶 内存池相邻两个管理节点可能存在着大于等于N’的空闲内存，比如，相连两个 管理节点中的第一个管理节点的第230‑256个内存块与第二个管理节点的前30 个内存块同时是空闲时，这些空闲的内存块长度存在着大于内存申请长度N’ 的可能。

相应的，所述步骤11可以为：

释放内存N’时，因为申请内存N’成功后，双标记记录有申请内存N’占据 该管理节点D’内存的起始地址及申请长度，先检查记录的起始地址及申请长度 是否合法，所谓合法就是指该起始地址是否属于管理节点D’，其申请长度是否 小于管理节点D’可管理的内存块的总长度等等；

合法性检查后，在管理节点D’所属阶内存池中进行起始地址的查，查 到之后，从起始地址开始释放起始地址到尾地址的内存块，这里，所述的尾地 址为：尾地址＝起始地址+申请长度；所述释放就是内存块由已被申请占用变成 空闲内存块；此时，管理节点数据结构中的Bitmap位图中相应内存块位置标识 为1，表明该管理节点D’的该些内存块已经被释放为空闲内存块，可以用于下 一次内存申请。

在管理节点D’释放内存N’后，需要先判断管理节点D’可管理的其它内存 块是否全部为空闲内存块，若不是，则释放内存流程结束；若是，则释放该管 理节点D’；

接下来，还需判断在管理节点D’所属的阶内存池中，与管理节点D’具有 同一个父节点的其它管理节点可管理的256块内存块是否全部为空闲内存块， 若不是，则释放内存流程结束；若是，则释放与管理节点D’具有同一个父节点 的其它管理节点，同时释放管理节点D’的父节点；

然后，判断与管理节点D’的父节点具有同一个父节点(管理节点D’祖父 节点)的其它管理节点可管理的256块内存块是否全部为空闲内存块，若不是， 释放内存流程结束；若是，则释放与管理节点D’的父节点具有同一个父节点的 其它管理节点、释放管理节点D’的祖父节点；

在释放管理节点D’的祖父节点之后，判断在管理节点D’祖父节点的所属 阶内存池中，是否有与管理节点D’的祖父节点具有同一个父节点的其它管理节 点可管理的256块内存块是否全部为空闲内存块，若不是，释放内存流程结束； 若是，则释放与管理节点D’的祖父节点具有同一个父节点的其它管理节点，释 放管理节点D’的祖父节点的父节点；

以此类推，直到判断到最高阶内存池；当内存池管理列表中的管理节点全 部释放完之后，内存池管理列表为空，则可根据嵌入式系统资源需要，重新确 定内存池管理列表的阶数、基本内存块长度等，为进程申请提供内存。

基于上述内存管理方法，本发明还提供了一种内存管理装置，如图3所示， 所述装置包括：内存申请管理模块40、内存释放管理模块41和内存池管理列 表42；其中，

所述内存申请管理模块40，用于申请内存时，根据申请内存大小确定出阶 内存池，再根据所述内存池管理列表42中阶内存池的占用情况为内存申请分配 内存；

所述内存释放管理模块41，用于释放内存时，根据释放内存标记信息，对 所述内存池管理列表42中的内存进行释放；

这里，所述标记信息为申请内存时设置的双标记，包括申请内存的起始地 址及申请长度；即：在内存申请成功后，记录的占用管理节点可管理的内存块 的起始地址及申请长度；

所述内存池管理列表42，用于为内存申请管理模块40和内存释放管理模 块41提供内存。

这里，所述内存池管理列表42内容与图1相同；在所述内存池管理列表 42初始化初期阶段，只有最高阶内存池如第12阶内存池有一个管理节点，其 它阶内存池均不具有管理节点；在有进程需要申请内存时，在所述内存申请管 理模块40驱动之下所述内存池管理列表42不断生成管理节点；在有进程需要 释放内存时，所述内存释放管理模块41驱动所述内存池管理列表42进行内存 块的释放。

基于上述对内存管理方法的描述，以最高阶内存池为第12阶内存池为例， 对内存申请的两种情况进行说明：第一种情况为所述内存池管理列表42初始化 初期阶段，第二种情况为所述内存池管理列表42初始化完成之后；其中，

对内存申请的第一种情况即所述内存池管理列表42初始化初期阶段，进程 A进行内存申请的情况进行以下描述：

在所述内存池管理列表42初始化初期阶段，只有第12阶内存池具有一个 管理节点point_120，其他阶内存池均不具有管理节点，所述内存申请管理模块 40接收到进程A的申请内存N需求，依据申请内存N的大小利用公式(2)确 定选择因子K，再利用公式(1)确定出阶数i；所述内存申请管理模块40判断 i是否等于最高阶数即是否等于12，

当判断出i等于12时，所述内存申请管理模块40查最高阶内存池中的 管理节点是否能够满足条件，因此时最高阶内存池只有管理节点point_120，当 管理节点point_120是满足条件的管理节点时，标识管理节点point_120，直接 由管理节点point_120为进程A分配长度为N的内存，申请内存N成功；

当判断出i等于12，且管理节点point_120不是满足条件的管理节点时， 所述内存申请管理模块40驱动所述内存池管理列表42，令所述内存池管理列 表42生成第12阶内存池的第二个管理节点point_121，由管理节点point_121 为进程A分配长度为N的内存，标识管理节点point_121，申请内存N成功；

当所述内存申请管理模块40判断出第i阶内存池不是最高阶内存池时，所 述内存申请管理模块40向所述内存池管理列表42中的第i阶内存池进行内存 申请，但因第i阶内存池无管理节点，那么，第i阶内存池向第i+L阶内存池进 行内存申请，所述内存申请管理模块判断出第i+L阶内存池不是最高阶内存池 时，第i+L阶内存池继续向第i+2L阶内存池进行内存申请，当所述内存申请管 理模块判断出第i+L阶内存池是最高阶内存池时，如上述方法进行处理；

其中，i+mL为小于等于12的正整数，m、L均为小于等于12正整数；

以此类推，直到申请到第12阶内存池，第12阶内存池的管理节点point_120 在接收到第i+mL阶内存池内存申请后，给第i+mL阶内存池分配64M内存， 第i+mL阶内存池接收分配内存后，所述内存申请管理模块40驱动所述内存池 管理列表42生成管理节点point_(i+mL)0，由管理节点point_(i+mL)0给第i+ (m‑1)L阶内存池分配内存64B*2^(i+mL)*256，第i+(m‑1)L阶内存池接收 到分配后，所述内存申请管理模块40驱动所述内存池管理列表42生成管理节 点point_(i+(m‑1)L)0，由管理节点point_(i+(m‑1)L)0分配给第i+(m‑2)L阶内 存池分配内存64B*2^(i(m‑1)L)*256，以此类推，直到第i阶内存池接收到分 配后，所述内存申请管理模块40驱动所述内存池管理列表42生成第i阶内存 池的一个管理节点point_i0，由管理节点point_i0分配内存N，标识管理节点 point_i0，所述内存申请管理模块40确认此次申请内存成功。

对内存申请的第二种情况即所述内存池管理列表42初始化完成之后，进程 A进行内存申请的情况进行以下描述：

所述内存申请管理模块40接收到进程A的申请内存N，利用公式(2)确 定选择因子K，再利用公式(1)确定出阶数i；

接下来，所述内存申请管理模块40查第i阶内存池存在的所有管理节点， 是否存在有满足条件的管理节点，

所述内存申请管理模块40能够在该阶内存池查到满足条件的管理节点， 则申请内存N成功，所述内存申请管理模块40驱动所述内存池管理列表42对 该管理节点进行标识，所述内存申请管理模块40确认此次申请内存成功；

在该阶内存池查不到满足条件的管理节点，则所述内存申请管理模块再 判断该阶内存池剩余内存长度是否大小等于内存申请长度；

当该阶内存池剩余内存长度大于等于申请内存长度时，所述内存申请管理 模块40驱动所述内存池管理列表42生成一个管理节点，并标识该生成的管理 节点，所述内存申请管理模块40确认此次申请内存成功；

当该阶内存池剩余内存长度小于申请内存长度时，所述内存申请管理模块 40查第i+L阶内存池的所有管理节点是否存在有满足条件的管理节点，当在 该阶内存池能够查到满足条件的管理节点时，驱动所述内存池管理列表42 标识管理节点，确认申请内存N成功；当在该阶内存池查不到满足条件的管 理节点时，所述内存申请管理模块40再判断该阶内存池剩余内存长度是否大小 等于内存申请长度；

当该阶内存池剩余内存长度大于等于申请内存长度时，所述内存申请管理 模块40驱动所述内存池管理列表42生成一个管理节点，并标识该生成的管理 节点，所述内存申请管理模块40确认此次申请内存成功；

当该阶内存池剩余内存长度小于申请内存长度时，所述内存申请管理模块 查第i+2L阶内存池的所有管理节点是否存在满足条件的管理节点，

以此类推，直到所述内存申请管理模块40能够查到满足条件的管理节 点，驱动所述内存池管理列表42标识该管理节点，确认此次申请内存成功；或 者查到最高阶内存池所有管理节点仍然不存在满足条件的管理节点且最高阶 内存池剩余长度小于内存申请长度时，

所述内存申请管理模块40转向查第i‑1阶内存池所有管理节点，是否存 在有满足条件的管理节点，存在满足条件的管理节点，申请内存成功，标识该 管理节点；不存在满足条件的管理节点，查第i‑2阶内存池所有管理节点， 查过程与上述相同，以此类推，

直到所述内存申请管理模块40能够查到满足条件的管理节点，确认申请 内存N成功，驱动所述内存池管理列表42标识该满足条件的管理节点；

或者，直到所述内存申请管理模块40查到第0阶内存池仍然不存在满足 条件的管理节点，申请内存失败，所述内存申请管理模块40确认此次申请内存 N失败。

在所述内存释放管理模块41接收到进程A释放内存N’的请求，在所述内 存池管理列表42中，因为申请内存N’成功后，双标记记录有申请内存N’占据 管理节点D’内存的起始地址及申请长度，所述内存释放管理模块41需要先对 双标记记录的起始地址及申请长度进行合法性检查，所述合法性检查即为确认 该起始地址是否属于管理节点D’，申请长度是否小于管理节点D’可管理的内 存块总长度等等；

合法性检查合格后，所述内存释放管理模块41在管理节点D’所属阶内存 池中进行起始地址的查，查到之后，所述内存释放管理模块41驱动所述内 存池管理列表42释放内存N’，释放从起始地址到尾地址的内存块，所述内存 释放管理模块41驱动所述内存池管理列表42进行管理节点数据结构的更新， 即Bitmap位图中相应内存块位置标识为1，双标记为空；这里，所述的尾地址 为：尾地址＝起始地址+申请长度；所述释放内存为：释放起始地址到尾地址的 内存块即内存块由已被申请占用变成空闲内存块；

在释放内存N’后，所述内存释放管理模块41还需判断管理节点D’中可管 理的其它内存块是否全部为空闲内存块，若不是，则释放内存结束；若是，所 述内存释放管理模块41驱动所述内存池管理列表42释放该管理节点D’，同时 还需判断在管理节点D’所属的阶内存池中，与管理节点D’具有同一个父节点 的其它管理节点可管理的256块内存块是否全部为空闲内存块，若不是，则释 放内存结束；若是，则所述内存释放管理模块41驱动所述内存池管理列表42 释放与管理节点D’具有同一个父节点的其他管理节点，同时释放管理节点D’ 的父节点；

接下来，所述内存释放管理模块41再判断与管理节点D’的父节点具有同 一个父节点(管理节点D’祖父节点)的其它管理节点可管理的256块内存块是 否全部为空闲内存块，若不是，则释放内存结束；若是，所述内存释放管理模 块41驱动所述内存池管理列表42释放与管理节点D’的父节点具有同一个父节 点的其它管理节点、释放管理节点D’的祖父节点；

在释放完管理节点D’祖父节点之后，在管理节点D’祖父节点的所属阶内 存池中，所述内存释放管理模块41还需判断与管理节点D’的祖父节点具有同 一个父节点的其它管理节点可管理的256块内存块是否全部为空闲内存块，若 不是，释放内存结束；若是，则所述内存释放管理模块41驱动所述内存池管理 列表42释放与管理节点D’的祖父节点具有同一个父节点的其它管理节点，释 放管理节点D’的祖父节点的父节点；

以此类推，当所述内存池管理列表42中的所有管理节点全部释放完之后， 所述内存池管理列表42为空，则可根据嵌入式系统资源需要，重新确定内存池 管理列表阶数、基本内存块长度，进而为进程申请内存提供服务。

本发明提供的内存管理方法及装置，内存池管理列表的内存块基本长度可 变，灵活性强，可适用于不同需求的嵌入式系统；当有进程申请内存时，所述 内存申请管理模块根据申请内存大小确定出阶内存池，并根据所述内存池管理 列表中的阶内存池的占用情况为内存申请分配内存；当有进程申请释放内存时， 根据内存池管理列表中的标记信息中的起始地址及申请长度，进行内存释放； 可根据不同类型的嵌入式系统需求，实时调整内存块基本长度，提高了内存资 源利用率，减轻了嵌入式系统资源的运行负担；当然，本发明还可适用于带有 内存资源的其它操作系统及设备，如交换机、路由器等处理器。

以上所述，仅为本发明的较佳实施例而已，并非用于限定本发明的保护范 围。