CN106095577A - 基于多路处理器的共享内存的优化处理方法及装置 - Google Patents

Abstract

本发明提供了一种基于多路处理器的共享内存的优化处理方法及装置。优化处理方法包括：基于多路处理器的共享内存的优化处理方法，其特征在于，优化处理方法包括：对多路处理器环境下的Linux内核进行数据结构修改，数据结构修改包括在free_area数据结构中新增数据结构链表；根据修改后的free_area数据结构，对多路处理器环境下的共享物理内存的块分配算法进行块分配优化；根据修改后的free_area数据结构，对块释放函数进行块释放优化。相比于现有伙伴算法而言，本发明的上述技术能够减小时间开销，提升物理内存的使用效率，以及降低内存碎片率。

Description

基于多路处理器的共享内存的优化处理方法及装置

技术领域

本发明涉及计算机技术，尤其涉及一种基于多路处理器的共享内存的优化处理方法及装置。

背景技术

随着大数据的流行，在多路处理器的内存优化方面还有很多工作要做，然而在当前的底层物理内存管理无论是从内存碎片还是使用效率来说都存在不足，针对于大数据处理时，往往会需要小而多的物理内存，这样频繁的使用物理内存，势必会导致内存管理的低效。为了提高系统的内存使用效率，在Linux内核中使用了伙伴(Buddy)算法，以提高物理内存的使用效率，然而，伙伴算法在多路处理器的环境下，其内存使用效率较低，且内存碎片率较高。

发明内容

在下文中给出了关于本发明的简要概述，以便提供关于本发明的某些方面的基本理解。应当理解，这个概述并不是关于本发明的穷举性概述。它并不是意图确定本发明的关键或重要部分，也不是意图限定本发明的范围。其目的仅仅是以简化的形式给出某些概念，以此作为稍后论述的更详细描述的前序。

鉴于此，本发明提供了一种基于多路处理器的共享内存的优化处理方法及装置，以至少解决目前多路处理器环境下的内存使用率较低、且内存碎片率较高的问题。

根据本发明的一个方面，提供了一种基于多路处理器的共享内存的优化处理方法，其特征在于，优化处理方法包括：对多路处理器环境下的Linux内核进行数据结构修改，数据结构修改包括在free_area数据结构中新增数据结构链表；根据修改后的free_area数据结构，对多路处理器环境下的共享物理内存的块分配算法进行块分配优化；根据修改后的free_area数据结构，对块释放函数进行块释放优化。

进一步地，数据结构修改包括在free_area数据结构中增加新的free_list_delay数据结构链表。

进一步地，块分配优化包括：优先在新增的free_list_delay数据结构链表中查找空闲内存；当在新增的free_list_delay数据结构链表中查找到空闲内存时，确定完成块分配优化；当在新增的free_list_delay数据结构链表中未查找到空闲内存时，在原始的free_list数据结构链表中继续查找空闲内存，在找到空闲内存之后，确定完成块分配优化。

进一步地，块释放优化包括：将原始的free_list数据结构链表中的伙伴块合并时机转移到新增的free_list_delay数据结构链表中。

根据本发明的另一方面，还提供了一种基于多路处理器的共享内存的优化处理装置，该优化处理装置包括：数据结构修改模块，其被配置用于对多路处理器环境下的Linux内核进行数据结构修改，数据结构修改包括在free_area数据结构中新增数据结构链表；块分配优化模块，其被配置用于根据修改后的free_area数据结构，对多路处理器环境下的共享物理内存的块分配算法进行块分配优化；块释放优化模块，其被配置用于根据修改后的free_area数据结构，对块释放函数进行块释放优化。

进一步地，数据结构修改模块被配置用于在free_area数据结构中增加新的free_list_delay数据结构链表。

进一步地，块分配优化模块被配置用于：优先在新增的free_list_delay数据结构链表中查找空闲内存；当在新增的free_list_delay数据结构链表中查找到空闲内存时，确定完成块分配优化；当在新增的free_list_delay数据结构链表中未查找到空闲内存时，在原始的free_list数据结构链表中继续查找空闲内存，在找到空闲内存之后，确定完成块分配优化。

进一步地，块释放优化模块被配置用于：将原始的free_list数据结构链表中的伙伴块合并时机转移到新增的free_list_delay数据结构链表中。

本发明的基于多路处理器的共享内存的优化处理方法及装置，通过对多路处理器环境下的Linux内核进行数据结构修改、块分配优化以及块释放优化，实现对共享物理内存的优化，相比于现有伙伴算法而言，能够减小时间开销，提升物理内存的使用效率，降低内存碎片率。

通过以下结合附图对本发明的最佳实施例的详细说明，本发明的这些以及其他优点将更加明显。

附图说明

本发明可以通过参考下文中结合附图所给出的描述而得到更好的理解，其中在所有附图中使用了相同或相似的附图标记来表示相同或者相似的部件。所述附图连同下面的详细说明一起包含在本说明书中并且形成本说明书的一部分，而且用来进一步举例说明本发明的优选实施例和解释本发明的原理和优点。在附图中：

图1是示意性地示出本发明的基于多路处理器的共享内存的优化处理方法的一个示例性处理的流程图；

图2是示意性地示出图1所示的步骤S120中的块分配优化处理的一种可能处理的流程图；

图3是示意性地示出块分配优化的一种可能处理的流程图；

图4是示意性地示出块释放优化的一种可能处理的流程图；

图5是示意性地示出本发明的基于多路处理器的共享内存的优化处理装置的一个示例的结构框图；

图6是示意性地示出在一个例子中采用本发明的基于多路处理器的共享内存的优化处理方法所得到的延迟合并算法与现有技术中的伙伴算法的时间开销对比结果图；

图7是示意性地示出在一个例子中采用本发明的基于多路处理器的共享内存的优化处理方法所得到的延迟合并算法与现有技术中的伙伴算法的内存碎片率对比结果图。

本领域技术人员应当理解，附图中的元件仅仅是为了简单和清楚起见而示出的，而且不一定是按比例绘制的。例如，附图中某些元件的尺寸可能相对于其他元件放大了，以便有助于提高对本发明实施例的理解。

具体实施方式

在下文中将结合附图对本发明的示范性实施例进行描述。为了清楚和简明起见，在说明书中并未描述实际实施方式的所有特征。然而，应该了解，在开发任何这种实际实施例的过程中必须做出很多特定于实施方式的决定，以便实现开发人员的具体目标，例如，符合与系统及业务相关的那些限制条件，并且这些限制条件可能会随着实施方式的不同而有所改变。此外，还应该了解，虽然开发工作有可能是非常复杂和费时的，但对得益于本公开内容的本领域技术人员来说，这种开发工作仅仅是例行的任务。

在此，还需要说明的一点是，为了避免因不必要的细节而模糊了本发明，在附图中仅仅示出了与根据本发明的方案密切相关的装置结构和/或处理步骤，而省略了与本发明关系不大的其他细节。

本发明的实施例提供了一种基于多路处理器的共享内存的优化处理方法，其特征在于，优化处理方法包括：对多路处理器环境下的Linux内核进行数据结构修改，数据结构修改包括在free_area数据结构中新增数据结构链表；根据修改后的free_area数据结构，对多路处理器环境下的共享物理内存的块分配算法进行块分配优化；根据修改后的free_area数据结构，对块释放函数进行块释放优化。

下面结合图1描述本发明的基于多路处理器的共享内存的优化处理方法的一个示例的处理流程100。

如图1所示，处理流程100开始于步骤S110。

在步骤S110中，对多路处理器环境下的Linux内核进行数据结构修改。然后，执行步骤S120。

其中，该数据结构修改例如包括：在free_area数据结构中新增数据结构链表。

根据一种实现方式，步骤S110中的数据结构修改可以为：在free_area数据结构中增加新的free_list_delay数据结构链表。这样，在修改后的free_area数据结构中，存在新增的free_list_delay数据结构链表以及原始的free_list数据结构链表。

在步骤S120中，根据修改后的free_area数据结构，对多路处理器环境下的共享物理内存的块分配算法进行块分配优化。

根据一种实现方式，步骤S120中的块分配优化可以包括如图2所示的步骤S210和S220。

如图2所示，在步骤S210中，在新增的free_list_delay数据结构链表中查找空闲内存。

当步骤S210中在新增的free_list_delay数据结构链表中查找到空闲内存时，跳出步骤S120，则步骤S120结束，继续执行步骤S130。

当步骤S210中在新增的free_list_delay数据结构链表中未查找到空闲内存时，继续执行步骤S220。

在步骤S220中，在原始的free_list数据结构链表中继续查找空闲内存。这样，能够在原始的free_list数据结构链表中找到空闲内存。步骤S120结束，然后执行步骤S130。

此外，图3还示出了块分配优化处理的另一个示例的处理流程。

如图3所示，块分配优化处理开始之后，执行步骤S301。

在步骤S301中，判断当前内存是否充足？若充足，则执行步骤S302；否则，执行步骤S303。

在步骤S303中，通过调用守护进程释放内存，然后返回执行步骤S301。

在步骤S302中，通过阶数order找到相应的free_area数据结构。然后执行步骤S304。

在步骤S304中，通过迁移类型migratetype确定free_list数据结构链表。然后执行步骤S305。

在步骤S305中，判定在free_list_delay数据结构链表中是否有空闲内存？若在free_list_delay数据结构链表中有空闲内存，执行步骤S306；否则，执行步骤S310。

在步骤S306中，调用expand函数删除已分配出去的内存，然后执行步骤S307。

在步骤S307中，将空闲块分配到相应的进程(其中，相应的进程是指用户请求空闲内存的那个进程)，然后执行步骤S308。

在步骤S308中，将剩余内存块放入free_list数据结构链表中。然后执行步骤S309。

在步骤S309中，返回内存块page地址。块分配优化处理结束。

在步骤S310中，判定在free_list数据结构链表中是否有空闲内存？若在free_list数据结构链表中有空闲内存，执行步骤S306；否则，执行步骤S311。

在步骤S311中，阶数order自加。然后执行步骤S312。其中，“阶数order自加”是指更新当前阶数order，并且，更新后阶数的值等于更新前阶数的值加1。

在步骤S312中，判定“current_order<MAX_ORDER”是否成立？即，判定当前order是否小于最大order。若成立，则执行步骤S305；否则，执行步骤313。

在步骤S313中，缩减预留给系统的内存。然后执行步骤S301。

如图1所示，在步骤S130中，根据修改后的free_area数据结构，对块释放函数进行块释放优化。

根据一种实现方式，步骤S130中的块释放优化例如可为：将原始的free_list数据结构链表中的伙伴块合并时机转移到新增的free_list_delay数据结构链表中。

图4示出了块释放优化处理的另一个示例的处理流程。

如图4所示，块释放优化处理开始之后，执行步骤S401。

在步骤S401中，通过当前order确定对应的链表的阶数。然后执行步骤S402。

在步骤S402中，通过迁移类型枚举结构找到相应的链表。然后执行步骤S403。

在步骤S403中，通过要释放的内存块的地址(如id)得到该内存块的伙伴块的地址(如id)。然后执行步骤S404。

在步骤S404中，判定步骤S403中得到的伙伴块是否空闲？若是，执行步骤S405；否则，执行步骤S406。

在步骤S406中，将空闲内存块释放到free_list链表中，然后结束块释放优化处理。

在步骤S405中，判定该伙伴块是否在free_list数据结构链表中？若是，执行步骤S407；否则，执行步骤S408。

在步骤S407中，将空闲内存块释放到free_list_delay数据结构链表中。然后结束块释放优化处理。

在步骤S408中，在free_list_delay数据结构链表中寻找要释放的内存块的伙伴块。然后执行步骤S409。

在步骤S409中，合并要释放的内存块及其伙伴块，并且当前阶数order自加。其中，“当前阶数order自加”是指更新当前阶数order，并且，更新后阶数的值等于更新前阶数的值加1，即current_order++，然后执行步骤S410。

在步骤S410中，判定“current_order<MAX_ORDER”是否成立？即，判定当前order是否小于最大order。若成立，则执行步骤S404；否则，执行步骤S411。

在步骤S411中，将合并后所得的内存块链接至current_order(当前阶数)对应的free_list链表中。然后结束块释放优化处理。

通过以上描述可知，本发明的基于多路处理器的共享内存的优化处理方法，其通过对多路处理器环境下的Linux内核进行数据结构修改、块分配优化以及块释放优化，实现对共享物理内存的优化。实验结果表明，利用本发明的上述优化处理方法所得到的延迟合并算法，相比于现有伙伴算法而言，能够减小时间开销，提升物理内存的使用效率，降低内存碎片率。

此外，本发明的实施例还提供了一种基于多路处理器的共享内存的优化处理装置，该优化处理装置包括：数据结构修改模块，其被配置用于对多路处理器环境下的Linux内核进行数据结构修改，数据结构修改包括在free_area数据结构中新增数据结构链表；块分配优化模块，其被配置用于根据修改后的free_area数据结构，对多路处理器环境下的共享物理内存的块分配算法进行块分配优化；块释放优化模块，其被配置用于根据修改后的free_area数据结构，对块释放函数进行块释放优化。

下面结合图5来描述本发明的基于多路处理器的共享内存的优化处理装置300的一个示例。

如图5所示，优化处理装置500包括数据结构修改模块510、块分配优化模块520和块释放优化模块530。

其中，数据结构修改模块510用于对多路处理器环境下的Linux内核进行数据结构修改，数据结构修改包括在free_area数据结构中新增数据结构链表。

根据一种实现方式，数据结构修改模块510所执行的“数据结构修改”处理例如是在free_area数据结构中增加新的free_list_delay数据结构链表。

块分配优化模块520用于根据修改后的free_area数据结构，对多路处理器环境下的共享物理内存的块分配算法进行块分配优化。

根据一种实现方式，块分配优化模块520所执行的“块分配优化”处理例如包括：优先在新增的free_list_delay数据结构链表中查找空闲内存；当在新增的free_list_delay数据结构链表中查找到空闲内存时，确定完成块分配优化；当在新增的free_list_delay数据结构链表中未查找到空闲内存时，在原始的free_list数据结构链表中继续查找空闲内存，在找到空闲内存之后，确定完成块分配优化。

块释放优化模块530用于根据修改后的free_area数据结构，对块释放函数进行块释放优化。

根据一种实现方式，块释放优化模块530所执行的“块释放优化”处理例如为：将原始的free_list数据结构链表中的伙伴块合并时机转移到新增的free_list_delay数据结构链表中。

通过以上描述可知，本发明的基于多路处理器的共享内存的优化处理装置，其通过对多路处理器环境下的Linux内核进行数据结构修改、块分配优化以及块释放优化，实现对共享物理内存的优化。实验结果表明，利用本发明的上述优化处理装置所得到的延迟合并算法，相比于现有伙伴算法而言，能够减小时间开销，提升物理内存的使用效率，降低内存碎片率。

优选实施例

下面描述本发明的基于多路处理器的共享内存的优化处理方法的一个优选实施例。

通过对多路处理器环境下的伙伴算法进行分析，能够发现其不足。

首先，通过对Linux内核中free_area数据结构的修改，增加新的free_list_delay数据结构链表。

接着，通过修改后的free_area结构，对共享物理内存的块分配的算法进行优化(即块分配优化)。块分配优化即：首先先到新增的free_list_delay数据结构链表中查找空闲内存，在查找不到时再到原始的free_list数据结构链表中查找空闲内存，以保证最近频繁使用的空闲内存能够得以复用，从而能够提升内存分配的速度。

然后，通过修改后的free_area结构以及延迟合并策略，对块释放函数进行优化(即块释放优化)。块释放优化即：将合并时机移到新增的数据结构链表中。

其中，延迟合并策略也即，在原始链表中不进行伙伴块合并，而是保留两空闲伙伴块以提供下次的分配使用。这样，能够降低伙伴块频繁合并的时间，节省物理内存管理的总体时间，从而能够提升效率。

下面，基于龙芯实验平台对通过以上优化处理方法所得到的延迟合并算法进行测试，分别从时间、内存使用效率、内存碎片等指标来对本发明的优化处理方法的有效性进行验证。

其中，在时间指标上，采用可移动内存池算法对内存分配的时间进行测试，内核会调用__get_free_pages入口函数，其实际分配物理内存的函数为__rmqueue_smallest，在此函数进行对物理内存申请方式的优化，通过测试可得，延迟合并算法的时间开销明显比伙伴算法降低了，如附图6所示。

然后，对Linux系统的内存碎片进行测试，碎片分为外部碎片和内部碎片，采用如下公式计算内存碎片中的内部碎片率fi，

fi＝∑Ri/∑Qi

该式中，Ri为请求分配的页框数量，页框大小为4KB，Qi为系统实际分配的页框数量，两者进行比值，即为所得理论的内部碎片率fi。外部碎片率f的计算如下公式，

f＝mm_free/total

其中mm_free表示没有拥有的内存量，total表示系统物理空间总量，f则表示外部碎片率的大小，其与伙伴算法的对比如图7所示。由图7可以看出，利用本发明能够降低内存碎片率。图7中的纵坐标对应内存碎片率。

需要说明的是，优化处理方法是在Linux内核中完成的，从数据结构、块分配、块释放函数采用延迟策略进行对算法的优化，在free_area数据结构中的原始free_list链表的基础上增加了一个free_list_delay链表结构，并采用延迟合并的方式对内存块的申请进行控制，在函数__get_free_pages中进行块的请求，将其优先申请free_list_delay中的空闲内存，其优化代码的一个示例如下：

内存块释放的入口函数为free_one_page，其代码优化如下：

然后在块释放时将伙伴块的合并时机放入新增free_list_delay链表中，将原始free_list链表中的空闲块保留得以复用，从而降低内存块的合并与分裂时间，提升物理内存的使用效率。

与现有的伙伴算法对比，结果表明：利用本发明的优化处理方法对多路处理器环境下的共享内存进行优化，所得到的延迟合并算法相比于现有的伙伴算法而言，从时间开销、内存使用效率、内存碎片等角度均更具有优势，结果如图6-7所示，由此表明本发明的优化处理方法的处理效果较好。

尽管根据有限数量的实施例描述了本发明，但是受益于上面的描述，本技术领域内的技术人员明白，在由此描述的本发明的范围内，可以设想其它实施例。此外，应当注意，本说明书中使用的语言主要是为了可读性和教导的目的而选择的，而不是为了解释或者限定本发明的主题而选择的。因此，在不偏离所附权利要求书的范围和精神的情况下，对于本技术领域的普通技术人员来说许多修改和变更都是显而易见的。对于本发明的范围，对本发明所做的公开是说明性的，而非限制性的，本发明的范围由所附权利要求书限定。

Claims (10)

1.基于多路处理器的共享内存的优化处理方法，其特征在于，所述优化处理方法包括：

对多路处理器环境下的Linux内核进行数据结构修改，所述数据结构修改包括在free_area数据结构中新增数据结构链表；

根据修改后的free_area数据结构，对所述多路处理器环境下的共享物理内存的块分配算法进行块分配优化；

根据修改后的free_area数据结构，对块释放函数进行块释放优化。

2.根据权利要求1所述的基于多路处理器的共享内存的优化处理方法，其特征在于：

所述数据结构修改包括在所述free_area数据结构中增加新的free_list_delay数据结构链表。

3.根据权利要求1或2所述的基于多路处理器的共享内存的优化处理方法，其特征在于，所述块分配优化包括：

优先在新增的free_list_delay数据结构链表中查找空闲内存；

当在新增的所述free_list_delay数据结构链表中查找到空闲内存时，确定完成所述块分配优化；

当在新增的所述free_list_delay数据结构链表中未查找到空闲内存时，在原始的free_list数据结构链表中继续查找空闲内存，在找到空闲内存之后，确定完成所述块分配优化。

4.根据权利要求1-3中任一项所述的基于多路处理器的共享内存的优化处理方法，其特征在于，所述块释放优化包括：

将原始的所述free_list数据结构链表中的伙伴块合并时机转移到新增的所述free_list_delay数据结构链表中。

5.基于多路处理器的共享内存的优化处理装置，其特征在于，所述优化处理装置包括：

数据结构修改模块，其被配置用于对多路处理器环境下的Linux内核进行数据结构修改，所述数据结构修改包括在free_area数据结构中新增数据结构链表；

块分配优化模块，其被配置用于根据修改后的free_area数据结构，对所述多路处理器环境下的共享物理内存的块分配算法进行块分配优化；

块释放优化模块，其被配置用于根据修改后的free_area数据结构，对块释放函数进行块释放优化。

6.根据权利要求5所述的基于多路处理器的共享内存的优化处理装置，其特征在于，所述数据结构修改模块被配置用于在所述free_area数据结构中增加新的free_list_delay数据结构链表。

7.根据权利要求6所述的基于多路处理器的共享内存的优化处理装置，其特征在于，所述块分配优化模块被配置用于：

优先在新增的free_list_delay数据结构链表中查找空闲内存；

当在新增的所述free_list_delay数据结构链表中查找到空闲内存时，确定完成所述块分配优化；

当在新增的所述free_list_delay数据结构链表中未查找到空闲内存时，在原始的free_list数据结构链表中继续查找空闲内存，在找到空闲内存之后，确定完成所述块分配优化。

8.根据权利要求6或7所述的基于多路处理器的共享内存的优化处理方法，其特征在于，所述块释放优化模块被配置用于：

将原始的所述free_list数据结构链表中的伙伴块合并时机转移到新增的所述free_list_delay数据结构链表中。

9.根据权利要求1-8中任一项所述的基于多路处理器的共享内存的优化处理方法，其特征在于，所述块分配优化的步骤包括：

步骤S301、判断当前内存是否充足：若充足，执行步骤S302；否则，执行步骤S303；

步骤S303、通过调用守护进程释放内存，返回执行步骤S301；

步骤S302、通过阶数order找到相应的free_area数据结构，执行步骤S304；

步骤S304、通过迁移类型migratetype确定free_list数据结构链表，执行步骤S305；

步骤S305、判定在free_list_delay数据结构链表中是否有空闲内存：若在free_list_delay数据结构链表中有空闲内存，执行步骤S306；否则，执行步骤S310；

步骤S306、调用expand函数删除已分配出去的内存，执行步骤S307；

步骤S307、将空闲块分配到相应的进程，执行步骤S308；

步骤S308、将剩余内存块放入free_list数据结构链表中，执行步骤S309；

步骤S309、返回内存块page地址，结束所述块分配优化；

步骤S310、判定在free_list数据结构链表中是否有空闲内存：若在free_list数据结构链表中有空闲内存，执行步骤S306；否则，执行步骤S311；

步骤S311、阶数order自加，执行步骤S312；

步骤S312、判定“current_order<MAX_ORDER”是否成立：若成立，执行步骤S305；否则，执行步骤313；

步骤S313、缩减预留给系统的内存，执行步骤S301。

10.根据权利要求1-9中任一项所述的基于多路处理器的共享内存的优化处理方法，其特征在于，所述块释放优化的步骤包括：

步骤S401、通过当前order确定对应的链表的阶数，执行步骤S402；

步骤S402、通过迁移类型枚举结构找到相应的链表，执行步骤S403；

步骤S403、通过要释放的内存块的地址得到该内存块的伙伴块的地址，执行步骤S404；

步骤S404、判定步骤S403中得到的伙伴块是否空闲：若是，执行步骤S405；否则，执行步骤S406；

步骤S406、将空闲内存块释放到free_list链表中，结束所述块释放优化；

步骤S405、判定该伙伴块是否在free_list数据结构链表中：若是，执行步骤S407；否则，执行步骤S408；

步骤S407、将空闲内存块释放到free_list_delay数据结构链表中，结束所述块释放优化处理；

步骤S408、在free_list_delay数据结构链表中寻找要释放的内存块的伙伴块，执行步骤S409；

步骤S409、合并所述要释放的内存块及其伙伴块，并且当前阶数order自加，执行步骤S410；

步骤S410、判定“current_order<MAX_ORDER”是否成立：若成立，执行步骤S404；否则，执行步骤411；

步骤S411、将合并后所得的内存块链接至current_order对应的free_list链表中，结束所述块释放优化。