内存分配的方法及装置

本发明涉及计算机领域，具体而言，涉及内存分配的方法及装置。

在如软件编程的计算机应用中，经常涉及内存资源的动态申请和释放。 比如创建一个线程时需要为该线程分配栈空间，当该线程被删除时需要回收 对应的栈空间。关于内存管理，业界已存在多种算法，各有其优缺点。评价 一款内存算法的优劣，主要有性能、利用率、可靠性、可格式化等要素。

内存算法主要分为静态内存算法、块内存算法、分割合并式内存算法等 几大类。静态内存算法性能很高，但只能申请内存资源而不能释放内存资源， 一般用在初始化阶段。块内存算法性能也很高，可动态申请或释放内存资源， 但其可分配的内存资源的大小受到内存块的大小的限制，而且利用率也比较 差。分割合并式内存算法可满足任意大小的内存资源的申请或释放，利用率 也高，但现有算法的性能比较差。

例如，一种块内存算法是指将内存池等分成若干个页：申请内存资源时， 若对应内存块的块类型的链表不为空则从该链表中摘取一个内存块，否则申 请一个空闲的内存页，将该空闲的内存页按对应的内存块的大小进行等分， 释放内存资源时，若内存页中的所有内存块都空闲，则回收该内存页并挂入 空闲的内存页的链表。但是，该算法会导致页内碎片与块内碎片，并且最大 可申请的内存资源的大小不能超过最大内存块的大小。

例如，另一种块内存算法是指每个内存块的块类型都维护一个空闲链 表：申请内存资源时，先检查对应的链表是否为空，如果不为空则从链表中 摘取一个内存块，否则根据分配指针再划分一个当前大小的内存块；释放内 存资源时，直接将当前释放的内存块挂到对应块类型的空闲链表中。但是， 该算法容易导致块内碎片，最大可申请的内存资源的大小不能超过最大内存 块的大小，并且已被划分出的内存块不能格式化为其它块类型。

例如，一种分割合并式内存算法是指可按任意大小划分内存块，并且当 内存块被释放时可以对前后紧邻的空闲内存块进行合并。在该算法中，为了 迅速查到适合的内存块，将所有空闲内存块维护成一个平衡二叉树。但是， 该算法涉及二叉树结点的申请、释放、查和平衡操作，因此性能比较差。

本发明实施例提出了内存分配的方法及装置，旨在解决现有内存分配中 无法兼具高性能、高利用率和申请任意内存大小的问题。

一方面，提出了一种内存分配的方法，包括：将空闲内存块串接到相应 的空闲链表中，所述空闲链表的头指针维护在大小为N的空闲链表头数组 中，所述空闲链表头数组中头指针指向的相应的空闲链表的索引为n，其中 所述N为正整数，所述n为0至N‑1的整数，索引为n的空闲链表用于串接 大小为X的空闲内存块，其中X大于或等于2n且小于或等于2n+1‑1；当申请 的内存的大小为Y时，从索引为m+1的空闲链表开始、在索引为m+1的空 闲链表与索引为n的空闲链表之间确定第一个非空的空闲链表，其中所述m 小于或等于N‑1，Y大于或等于2m且小于或等于2m+1‑1；提取所述第一个非 空的空闲链表中的第一个空闲内存块，按照所述申请的内存的大小分配第一 个空闲内存块。

在第一方面的第一种可能的实现方式中，所述当申请的内存的大小为Y 时，从索引为m+1的空闲链表开始、在索引为m+1的空闲链表与索引为n 的空闲链表之间确定第一个非空的空闲链表包括：当申请的内存的大小在2m 至2m+1‑1之间时，从索引为m+1的空闲链表开始、在索引为m+1的空闲链 表与索引为n的空闲链表之间，通过与所述空闲链表头数组对应的位图确定 第一个非空的空闲链表，其中所述位图中的每个位标示所述空闲链表头数组 中对应的空闲链表是否为空。

结合第一方面或第一方面的第一种可能的实现方式，在第二种可能的实 现方式中，还包括：若所述第一个空闲内存块中存在未分配的剩余空闲内存， 根据所述剩余空闲内存的大小将所述剩余空闲内存对应的空闲内存块串接 到相应的空闲链表中。

结合第一方面或第一方面的第一种可能的实现方式或第一方面的第二 种可能的实现方式，在第三种可能的实现方式中，所述将空闲内存块串接到 相应的空闲链表中包括：以双向链表的形式将所述空闲内存块串接到空闲链 表中。

结合第一方面或第一方面的第一种可能的实现方式或第一方面的第二 种可能的实现方式或第一方面的第三种可能的实现方式，在第四种可能的实 现方式中，所述将空闲内存块串接到相应的空闲链表中包括：在内存释放时， 合并地址相连的空闲内存块为新的空闲内存块，将所述新的空闲内存块串接 到相应的空闲链表中，其中所述空闲内存块的地址存储在空闲内存块的控制 头中。

第二方面，提出了一种内存分配的装置，包括：串接单元，用于将空闲 内存块串接到相应的空闲链表中，所述空闲链表的头指针维护在大小为N的 空闲链表头数组中，所述空闲链表头数组中头指针指向的相应的空闲链表的 索引为n，其中所述N为正整数，所述n为0至N‑1的整数，索引为n的空 闲链表用于串接大小为X的空闲内存块，其中X大于或等于2n且小于或等 于2n+1‑1；确定单元，用于当申请的内存的大小为Y时，从索引为m+1的空 闲链表开始、在索引为m+1的空闲链表与索引为n的空闲链表之间确定第 一个非空的空闲链表，其中所述m小于或等于N‑1，Y大于或等于2m且小 于或等于2m+1‑1；提取单元，用于提取所述第一个非空的空闲链表中的第一 个空闲内存块，按照所述申请的内存的大小分配第一个空闲内存块。

在第二方面的第一种可能的实现方式中，所述确定单元用于：当申请的 内存的大小在2m至2m+1‑1之间时，从索引为m+1的空闲链表开始、在索引 为m+1的空闲链表与索引为n的空闲链表之间，通过与所述空闲链表头数 组对应的位图确定第一个非空的空闲链表，其中所述位图中的每个位标示所 述空闲链表头数组中对应的空闲链表是否为空。

结合第二方面或第二方面的第一种可能的实现方式，在第二种可能的实 现方式中，所述串接单元还用于：若所述第一个空闲内存块中存在未分配的 剩余空闲内存，根据所述剩余空闲内存的大小将所述剩余空闲内存对应的空 闲内存块串接到相应的空闲链表中。

结合第二方面或第二方面的第一种可能的实现方式或第二方面的第二 种可能的实现方式，在第三种可能的实现方式中，所述串接单元用于：以双 向链表的形式将所述空闲内存块串接到空闲链表中。

结合第二方面或第二方面的第一种可能的实现方式或第二方面的第二 种可能的实现方式或第二方面的第三种可能的实现方式，在第四种可能的实 现方式中，所述串接单元具体用于：在内存释放时，合并地址相连的空闲内 存块为新的空闲内存块，将所述新的空闲内存块串接到相应的空闲链表中， 其中所述空闲内存块的地址存储在空闲内存块的控制头中。

由此可见，本发明实施例由于采用空闲链表头数组协助内存分配，从而 空闲内存块根据大小串接到空闲链表头数组，可以在短时间内查到满足申 请大小的空闲内存块，并且通过链表串接空闲内存块有利于提高性能。此外， 本发明实施例能够在具有高性能的同时，兼具碎片少、可申请任意内存大小 的特点。

为了更清楚地说明本发明实施例的技术方案，下面将对本发明实施例中 所需要使用的附图作简单地介绍，显而易见地，下面所描述的附图仅仅是本 发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的 前提下，还可以根据这些附图获得其他的附图。

图1是根据本发明实施例的内存分配的方法的流程图。

图2示出根据本发明实施例的内存分配中空闲链表头数组与位图的关 系。

图3示出了根据本发明实施例的内存分配中空闲内存块的结构示意图。

图4是根据本发明实施例的内存分配的装置的结构示意图。

图5是根据本发明另一实施例的内存分配的装置的结构示意图。

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行 清楚、完整地描述，显然，所描述的实施例是本发明的一部分实施例，而不 是全部实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创 造性劳动的前提下所获得的所有其他实施例，都应属于本发明保护的范围。

以下将结合附图详细描述本发明实施例的内存分配的方法。如图1所示， 包括以下步骤。

11，将空闲内存块串接到相应的空闲链表中，所述空闲链表的头指针维 护在大小为N的空闲链表头数组中，所述空闲链表头数组中头指针指向的相 应的空闲链表的索引为n，其中所述N为正整数，所述n为0至（N‑1）的 整数，索引为n的空闲链表用于串接大小为X（2n比特≤X≤2n+1‑1比特）的 空闲内存块。

具体而言，系统中存在多个空闲链表，该空闲链表的头指针维护在空闲 链表头数组中。例如，该空闲链表头数组的大小为N，也就是说明共有N个 空闲链表。将大小为N的空闲链表头数组按照从小到大的顺序编号，例如从 0至N‑1。进一步地，可以将顺序编号n作为空闲链表的索引，以区分出每 个空闲链表中串接的空闲内存块。可以将其大小为X（2n比特≤X≤2n+1‑1 比特）的空闲内存块串接到索引为n的空闲链表中。例如，大小为1比特的 空闲内存块串接到索引为0的空闲链表中；大小为2或3比特的空闲内存块 串接到索引为1的空闲链表中；大小为4至7比特的空闲内存块串接到索引 为2的空闲链表中；以此类推，大小为2n至2n+1‑1比特的空闲内存块串接到 索引为n的空闲链表中。

这样，所有空闲内存块都可以串接到不同的空闲链表中，但由单一的空 闲链表头数组统一管理和串接，便于查空闲内存块以及任意大小空闲内存 块的申请。

此外，空闲内存块还可以双向链表的形式串接到空闲链表中，这样当某 一空闲内存块插入空闲链表或从空闲链表中删除时，与其相关的串接在同一 空闲链表中的空闲内存块能快速串接，以避免由于空闲内存块的移动对性能 造成的不利影响。

12，当申请的内存的大小Y（（2m比特≤X≤2m+1‑1比特）时，从索引为 （m+1）的空闲链表开始、在索引为（m+1）的空闲链表与索引为n的空闲 链表之间确定第一个非空的空闲链表，其中所述m小于或等于（N‑1）。

具体而言，当确定需要申请的内存的大小在2m比特至2m+1‑1比特之间 （其中，m小于或等于（N‑1））时，可以从索引为（m+1）的空闲链表开始、 在索引为（m+1）的空闲链表与索引为n的空闲链表之间进行查。例如， 从索引（m+1）开始，按照从小到大的索引的顺序，即（m+2）、（m+3）……， 直到确定第一个非空的空闲链表。

需要说明的是，索引大于m的空闲链表中串接的空闲内存块的大小一定 大于2m+1‑1比特。也就是说，从索引为（m+1）的空闲链表开始查到的空 闲内存块的大小可以满足请求的内存的大小2m比特至2m+1‑1比特。那么， 从索引为（m+1）的空闲链表开始逐一查得到的非空的空闲链表中串接的 空闲内存块一定满足请求的内存的要求。

进一步地，为了减少确定第一个非空的空闲链表的时间，可以引入位图 （bitmap），该bitmap具有N个位，分别标识空闲链表头数组中对应的N个 空闲链表的状态，例如“0”是空的空闲链表，“1”表示非空的空闲链表。 因此，当申请的内存的大小在2m至2m+1‑1比特之间时，从索引为（m+1）的 空闲链表开始、在索引为（m+1）的空闲链表与索引为n的空闲链表之间， 通过与所述空闲链表头数组对应的bitmap中各个位的值确定第一个非空的 空闲链表，因为位图中的每个位标示所述空闲链表头数组中对应的空闲链表 是否为空。例如，可以从索引为（m+1）的空闲链表对应的位图中的位开始 确定第一个“1”，该取值为“1”的位所标示的空闲链表就是确定的第一个 非空的空闲链表。

13，提取所述第一个非空的空闲链表中的第一个空闲内存块，按照所述 申请的内存的大小分配第一个空闲内存块。

若所述第一个空闲内存块中存在未分配的剩余空闲内存，根据所述剩余 空闲内存的大小将所述剩余空闲内存对应的空闲内存块串接到相应的空闲 链表中。

例如，申请的内存大小Y为10比特，由于10比特在23比特至23+1‑1 比特之间，即m为3。根据步骤12确定的方法，从索引为4的空闲链表开 始查第一个非空的空闲链表。例如确定索引为4的空闲链表为空、索引为 5的空闲链表为非空，则从索引为5的空闲链表中确定第一个空闲内存块， 假设为32比特。于是，提取该32比特，将其中10比特分配给申请的内容， 此时剩余空闲内存为22比特。该剩余空闲内存作为新的空闲内存块串接到 对应的空闲链表中，例如22比特在24比特至24+1‑1比特之间，即m为4， 也就是说，该新的空闲内存块将串接到索引为4的空闲链表中。如前所述， 由于该索引为4的空闲链表之前为空，当插入该新的空闲内存块之后，该索 引为4的空闲链表将不为空，因此对应的位图中的位将从“0”变为“1”。

可以理解，在分配完内存之后形成的新的空闲内存块串接到对应的空闲 链表中时，若该对应的空闲链表原不为空（即存在空闲内存块），那么该新 的空闲内存块就顺序地串接到该对应空闲链表的最后。

此外，由于每个空闲内存块的控制头中保存有该空闲内存块的起始地址 以及前后紧邻的空闲内存块的起始地址等信息，因此每次当内存释放时，地 址相连的空闲内存块将合并为新的空闲内存块，并被串接到相应的空闲链表 中，此时合并前的空闲内存块将从原来所在的空闲链表中删除。

由此可见，本发明实施例可以在短时间内查到满足申请大小的空闲内 存块，并且通过链表串接空闲内存块有利于提高性能。此外，本发明实施例 能够在具有高性能的同时，兼具碎片少、可申请任意内存大小的特点。

下面以最大内存为4G比特为例，对本发明实施例的内存分配的方法进 行具体描述。

一般地，采用二进制表示申请的内存的大小，例如0b{0}1xxx，其中{0} 表示1前面可能有0个或多个零。容易理解，无论1后面的xxx是何内容， 如果将1变成10，xxx全部变成0，则总有10yyy>1xxx（这里yyy表示xxx 的对应位全部变成0）。在最大内存为4G比特的情况中，内存的大小最多为 32位二进制数。

通常，可以通过汇编指令直接得到所有空闲内存块的最左边的1的下标 （例如，0‑31）。在一个空闲链表头数组中维护空闲链表的头指针，以空闲 内存块的最左边的1的下标（在汇编指令中从高位到低位依次为31‑0）作为 空闲链表头数组中空闲链表的数组索引，即将所有最左边的1的下标相同的 空闲内存块挂接在同一个空闲链表中。如图2所示，索引为2的空闲链表可 挂接的空闲内存块的大小为4比特至7比特；索引为n的空闲链表可挂接的 空闲内存块的大小为2n比特到2n+1‑1比特。

当申请大小为uiSize的内存时，首先利用汇编指令得到最左边的1的下 标，假定为m。为确保空闲链表中的第一个空闲内存块就满足uiSize，则从 索引为m+1开始搜索。若索引为m+1的空闲链表不为空，则取该空闲链表 中的第一个空闲内存块。若索引为m+1的空闲链表为空，则判断索引为m+2 的空闲链表，依次类推，直到到非空的空闲链表或索引达到31。这里，m 小于或等于30。

为避免逐级判断空闲链表是否为空，考虑定义一个32位的位图全局变 量（例如，其下标值从高位到低位依次为0‑31）。若索引为m的空闲链表非 空，则位图的下标为m的位被置“1”，否则置“0”。位图的下标为31的位 在初始化时直接置1。于是从索引为m+1的空闲链表开始查第一个非空的 空闲链表，例如可以首先将位图的副本的0到m位均置“0”，然后获取副本 的最左边的1的下标，若不等于31，即为第一个非空的空闲链表的数组索引。 如果硬件支持，位图也可按获取最右边的1的方式处理。

所有的空闲内存块都以双向链表形式串接在空闲链表中。若从空闲链表 中获取的第一个空闲内存块比较大，即分割出一个大小为uiSize的内存块后， 剩下的剩余空闲内存仍至少可做一次最小分配，如图3所示，即剩余空闲内 存的大小大于控制头（CtrlHead）的大小，则将剩余空闲内存形成的新的空 闲内存块调整串接到对应的空闲链表中。

一般而言，空闲内存都携带控制头，该控制头可以是实际的内存控制头 或者内存控制头的指针或索引。由于控制头中存储有本空闲内存块的起始地 址和大小、本空闲内存块的状态（例如占用或空闲）以及前后紧邻的空闲内 存块的地址等，因此可以在内存释放过程中，根据上述地址信息可以将空闲 内存块进行合并。

下面将结合图4描述根据本发明实施例的内存分配的装置。

在图4中，内存分配的装置40包括串接单元41、确定单元42和提取单 元43。

其中，串接单元41用于将空闲内存块串接到相应的空闲链表中，所述 空闲链表的头指针维护在大小为N的空闲链表头数组中，所述空闲链表头数 组中头指针指向的相应的空闲链表的索引为n，其中所述N为正整数，所述 n为0至N‑1的整数，索引为n的空闲链表用于串接大小为X的空闲内存块， 其中X大于或等于2n且小于或等于2n+1‑1。

可选地，串接单元41还用于若所述第一个空闲内存块中存在未分配的 剩余空闲内存，根据所述剩余空闲内存的大小将所述剩余空闲内存对应的空 闲内存块串接到相应的空闲链表中。

可选地，串接单元41用于以双向链表的形式将所述空闲内存块串接到 空闲链表中。

可选地，串接单元41具体用于在内存释放时，合并地址相连的空闲内 存块为新的空闲内存块，将所述新的空闲内存块串接到相应的空闲链表中， 其中所述空闲内存块的地址存储在空闲内存块的控制头中。

确定单元42用于当申请的内存的大小为Y时，从索引为m+1的空闲链 表开始、在索引为m+1的空闲链表与索引为N的空闲链表之间确定第一个 非空的空闲链表，其中所述m小于或等于N‑1，Y大于或等于2m且小于或 等于2m+1‑1。

进一步地，确定单元42可以用于当申请的内存的大小为Y时，从索引 为m+1的空闲链表开始、在索引为m+1的空闲链表与索引为n的空闲链表 之间，通过与所述空闲链表头数组对应的位图确定第一个非空的空闲链表， 其中所述位图中的每个位标示所述空闲链表头数组中对应的空闲链表是否 为空。

提取单元43用于提取所述第一个非空的空闲链表中的第一个空闲内存 块，按照所述申请的内存的大小分配所述第一个空闲内存块。

由此可见，本发明实施例可以在短时间内查到满足申请大小的空闲内 存块，并且通过链表串接空闲内存块有利于提高性能。此外，本发明实施例 能够在具有高性能的同时，兼具碎片少、可申请任意内存大小的特点。

图5是本发明的内存分配的装置50另一个实施例的示意框图。装置50 包括处理器51、存储器52、输入设备53和输出设备54等，通过总线相互 通信。其中，处理器51调用存储器52存储的程序，可以执行上述内存分配 方法实施例的各个步骤。

处理器51用于执行存储器52存储的本发明实施例的程序，并通过总线 与其他装置双向通信。

存储器52可以是包括随机存取存储器（RAM，Random Access Memory） 和只读存储器（ROM，Read‑Only Memory）、或任何固定的存储介质、或可 移动的存储介质，用于存储可以执行本发明实施例的程序和/或本发明实施例 中待处理的数据。

存储器52和处理器51也可以整合成应用本发明实施例的物理模块，在 该物理模块上存储和运行实现该本发明实施例的程序。

可选地，内存分配的装置50还可以包括输入设备53和输出设备54。

例如，输入设备53可以包括键盘、鼠标等任何合适的装置，用于接收 用户的输入或来自其他设备的输入，并发送给处理器51。

例如，输出设备54用于将音频信号的比特分配的结果输出，可以是显 示器、打印机等。

应理解，在本发明实施例中，术语“和/或”仅仅是一种描述关联对象的 关联关系，表示可以存在三种关系。例如，A和/或B，可以表示：单独存在 A，同时存在A和B，单独存在B这三种情况。另外，本文中字符“/”，一 般表示前后关联对象是一种“或”的关系。

本领域普通技术人员可以意识到，结合本文中所公开的实施例描述的各 示例的单元及算法步骤，能够以电子硬件、或者计算机软件和电子硬件的结 合来实现。这些功能究竟以硬件还是软件方式来执行，取决于技术方案的特 定应用和设计约束条件。专业技术人员可以对每个特定的应用来使用不同方 法来实现所描述的功能，但是这种实现不应认为超出本发明的范围。

所属领域的技术人员可以清楚地了解到，为描述的方便和简洁，上述描 述的系统、装置和单元的具体工作过程，可以参考前述方法实施例中的对应 过程，在此不再赘述。

在本申请所提供的几个实施例中，应该理解到，所揭露的系统、装置和 方法，可以通过其它的方式实现。例如，以上所描述的装置实施例仅仅是示 意性的，例如，所述单元的划分，仅仅为一种逻辑功能划分，实际实现时可 以有另外的划分方式，例如多个单元或组件可以结合或者可以集成到另一个 系统，或一些特征可以忽略，或不执行。另一点，所显示或讨论的相互之间 的耦合或直接耦合或通信连接可以是通过一些接口，装置或单元的间接耦合 或通信连接，可以是电性，机械或其它的形式。

所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作 为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方， 或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或 者全部单元来实现本实施例方案的目的。

另外，在本发明各个实施例中的各功能单元可以集成在一个处理单元 中，也可以是各个单元单独物理存在，也可以两个或两个以上单元集成在一 个单元中。

所述功能如果以软件功能单元的形式实现并作为独立的产品销售或使 用时，可以存储在一个计算机可读取存储介质中。基于这样的理解，本发明 的技术方案本质上或者说对现有技术做出贡献的部分或者该技术方案的部 分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储介质 中，包括若干指令用以使得一台计算机设备（可以是个人计算机，服务器， 或者网络设备等）执行本发明各个实施例所述方法的全部或部分步骤。而前 述的存储介质包括：U盘、移动硬盘、ROM、RAM、磁碟或者光盘等各种 可以存储程序代码的介质。

以上所述，仅为本发明的具体实施方式，但本发明的保护范围并不局限 于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，可轻易 想到变化或替换，都应涵盖在本发明的保护范围之内。因此，本发明的保护 范围应所述以权利要求的保护范围为准。