一种内存连续块动态组合分配系统及方法与流程

摘要: 本发明属于计算机系统与内存管理,具体涉及一种内存连续块动态组合分配系统及方法。背景技术:1、目前主流的物理内存管理采用伙伴分配算法(buddyallocatio...
一种内存连续块动态组合分配系统及方法与流程

本发明属于计算机系统与内存管理,具体涉及一种内存连续块动态组合分配系统及方法。

背景技术:

1、目前主流的物理内存管理采用伙伴分配算法(buddy allocation algorithm),该算法具有以下特点:

2、(1)将内存按 2 的幂次划分,每个阶数(order)对应 2^order 个页面;

3、(2)系统为每个阶维护独立的空闲链表;

4、(3)分配时从对应阶查找,若无则向更高阶分裂;

5、(4)释放时检查是否存在“伙伴块”,若存在则合并。

6、buddy系统核心思想是将内存划分为大小为2的幂次(即"阶",order)的块,并通过分裂与合并机制管理空闲内存。buddy系统中每个内存块的大小为,其中page_size为系统页大小(如4kb)。内存区域内可以有多个order,每个order以链表的形式管理多个内存块,同一order的内存块大小是相同的。伙伴算法的优点是分配速度快、碎片外碎片可控,但其固有的约束导致在大块连续内存分配场景下存在严重问题,如表1所示:

7、表1 伙伴算法介绍表;

8、

约束

描述

影响

块大小约束

块大小必须是 2 的幂次页

产生内部碎片

对齐约束

order=k 的块,起始地址必须 2^k 页对齐

限制大块形成

合并约束

仅"伙伴块"可合并

阻止跨阶组合

9、上述3个约束导致即使系统中存在物理地址连续的多个空闲小块,伙伴算法也无法自动组合它们形成大块。

10、随着云计算和虚拟化技术的发展,type-i hypervisor需要管理越来越复杂的物理内存环境。现有的内存管理方案在面对大块连续内存需求时,主要面临“刚性切分”与“独立管理”的结构性矛盾。

11、现有的buddy系统将连续物理内存按对齐边界刚性切分,形成多个管理单元,并将这些单元按阶数(order)分散在不同空闲链表中独立管理,且各链表之间无任何协同机制。这种“刚性切分+独立管理”的组合产生了结构性碎片:物理地址连续的内存因处于不同链表而被逻辑隔离,无法跨链表组合。这并非传统意义上的内存碎片,而是管理机制本身导致的可达性问题——总量充足、物理连续的内存因管理结构的刚性约束而无法被有效利用。

12、虽然业界一直在探索内存池化和碎片整理技术,但大多集中在业务数据层面。针对buddy系统这种底层分配器,如何在不改变已分配内存(不迁移)、不修改核心算法(不侵入)的前提下,利用当前空闲链表的结构信息,主动识别并组合地址相邻的多个空闲块,形成逻辑上的大连续区域,是当前技术发展中亟待解决的难点。现有的静态预留方案无法适应动态变化的内存需求,缺乏一种能够基于实时空闲状态进行动态组合的高效内存管理机制。

技术实现思路

1、针对现有技术的不足,本发明提供了一种内存连续块动态组合分配系统及方法;

2、本发明要解决的核心技术问题是:现有buddy内存分配系统受块大小必须为2的幂次页、块起始地址必须满足对应阶次对齐、以及仅伙伴块可合并等机制约束,导致连续物理内存被刚性切分并分散管理于不同阶次的空闲链表中。

3、由此产生的具体技术难题是:即使系统中实际存在总量充足且物理地址连续的多个空闲块,现有buddy系统也无法跨阶、跨链表将其有效组合为满足需求的大块连续内存。这导致在大容量连续内存申请场景下(如虚拟机启动内存、dma缓冲区),出现物理上连续但逻辑上不可分配的结构性失效问题。

4、本发明旨在不迁移已分配内存、不修改现有buddy后端核心分配机制、且不依赖启动时静态预留连续内存池的前提下,基于当前空闲链表中的空闲块信息,动态识别并组合物理地址相邻的多个空闲块,形成逻辑上的大连续内存区域,同时通过加锁方式保证分配的原子性与一致性,以提高系统对大块连续内存请求的满足能力。

5、本发明技术主要应用于操作系统内核、虚拟化平台(特别是type-i hypervisor,即裸机型虚拟机监控器)以及需要大块连续物理内存的场景(如设备直通dma缓冲区)。本发明旨在通过非侵入式的方式,在不改变现有buddy系统核心机制的前提下,解决大块连续内存分配受限的问题。

6、本发明的技术方案为:

7、一种内存连续块动态组合分配系统,包括前端分配模块、后端伙伴模块和元数据管理模块;

8、前端分配模块是对外服务的统一入口,根据分配请求的特征选择最优策略;后端伙伴模块提供基础分配能力,是所有分配操作的最终执行者;元数据管理模块记录组合分配的映射关系,为释放操作提供查询服务;

9、前端分配模块内部维护双层分配逻辑;当分配请求到达时,前端分配模块首先对分配请求进行规范化处理,包括参数有效性验证、页数对齐处理、对齐要求规范化、地址范围检查及分配类型判断;规范化处理完成后,启动双路径决策机制,按照先标准后组合的策略尝试分配;

10、后端伙伴模块分配时从对应order链表查找,若无则从更高阶分裂;释放时将块归还到对应order链表并尝试与伙伴块合并;后端伙伴模块遵守对齐约束,在关键操作前进行对齐验证;

11、元数据管理模块建立连续大块与buddy管理的子块集合的映射关系,确保组合分配的正确追踪和释放。

12、一种内存连续块动态组合分配方法,通过上述内存连续块动态组合分配系统实现,包括:

13、内存申请和内存释放;

14、内存申请,包括:采用双路径决策机制,优先通过标准伙伴分配路径满足请求,失败则启动组合分配路径,按阶次降序遍历空闲链表搜索物理相邻块,先搜索再逐个分配,任何一个分配失败立即全部释放返回内存申请失败,若成功则将组合块元数据记录;

15、内存释放,包括:前端分配模块接收释放请求后,首先,查询元数据管理模块,判断释放地址是否存在对应的组合块映射记录;若有记录,则判定为组合块,进入组合释放路径;若无,则判定为标准块,直接调用后端伙伴模块的标准释放流程;

16、对于组合块,前端分配模块根据元数据记录获取子块列表,依次调用后端伙伴模块对每个子块执行独立释放;待所有子块释放完成后,前端分配模块通知元数据管理模块移除组合块的映射记录,释放元数据槽位;对于标准块,前端分配模块直接调用后端伙伴模块执行传统伙伴释放流程,包括链表插入与伙伴合并。

17、根据本发明优选的,查询元数据管理模块,判断释放地址是否存在对应的组合块映射记录;包括:

18、元数据管理模块中保存有所有组合分配成功后的映射记录,每条记录包括组合块的起始地址base_addr、子块数量part_count以及各子块的起始地址和阶次信息;

19、前端分配模块接收到释放请求后,将释放请求中的起始地址作为查询键,在元数据管理模块中逐条扫描当前有效的组合块记录,并比较地址是否与某条记录中的base_addr相同;若二者相等,则认为命中对应的组合块映射记录,释放对象为组合块;若未命中任何有效记录,则认为该释放对象不是组合分配产生的组合块,而是标准伙伴分配块。

20、根据本发明优选的,对于组合块,前端分配模块先根据命中的元数据记录读取该组合块的子块列表;每个子块记录包括子块起始地址和阶次order,计算出子块的页数为2^order;随后,前端分配模块按照子块列表逐个调用后端伙伴模块的释放接口,将每个子块作为一个独立的buddy块归还给后端伙伴系统;后端伙伴模块接收每个子块后,将子块插入对应order的空闲链表,并按buddy规则尝试与伙伴块合并;当所有子块均释放完成后,前端分配模块通知元数据管理模块删除该组合块的映射记录;元数据管理模块将记录所在槽位标记为空闲,或用最后一条有效记录覆盖槽位并减少有效记录数量;

21、对于标准块,若释放地址未在元数据管理模块中命中组合块记录,则前端分配模块认为内存块是通过标准buddy路径分配得到的普通块;此时,前端分配模块直接调用后端伙伴模块的标准释放接口;后端伙伴模块根据释放地址和页数确定对应的order,将释放块插入order空闲链表;随后计算伙伴块地址,检查伙伴块是否同样空闲且属于同一阶次;若伙伴块存在,则将二者从当前order链表中取出,合并为高一阶的空闲块,并继续向更高阶尝试合并;若伙伴块不存在或不可合并,则释放,流程结束。

22、根据本发明优选的,内存申请的具体实现过程包括:

23、前端分配模块将分配请求直接委托给后端伙伴模块,由后端伙伴模块执行传统的伙伴分配算法;当标准路径失败即执行传统的伙伴分配算法失败时,前端分配模块激活组合分配路径作为降级策略;组合分配路径包括以下步骤:

24、(1)搜索阶段:按order降序,order是buddy系统中的阶次,用于表示内存块大小;对每个遍历到的块,检查其起始地址是否满足请求的对齐要求,不满足则跳过继续下一个块;第一个通过对齐检查的候选块直接作为组合块的候选首块,记录其起始地址start、结束地址end、order值,并初始化已收集块的最小地址min_addr和最大地址max_addr,已收集块是指在组合分配搜索过程中,已经被选入候选列表、准备共同组成目标连续内存区域的若干个空闲buddy块;将候选块信息加入候选列表;候选块信息是指描述某个可用于组合的buddy空闲块的信息;

25、(2)验证与收集阶段:对后续通过对齐检查的候选块进行连续性判断,维护已收集块的物理地址范围[min_addr, max_addr];对于每个新候选块,检查其结束地址end是否等于min_addr,或其起始地址start是否等于max_addr;如果满足左侧连续条件即end==min_addr,则纳入该块,更新min_addr=start,扩展已收集范围;如果满足右侧连续条件即start==max_addr,则纳入该块,更新max_addr=end,扩展已收集范围;如果不满足连续条件,则跳过该块继续搜索;

26、当收集到足够页数,足够页数,是指:把已经选中的所有子块所包含的页数相加后,得到的总页数已经不小于本次申请所需的页数;候选列表candidates包含k个物理地址连续的子块信息,为成功情况,进入内存分配阶段;候选列表candidates是搜索和验证过程中临时保存的候选子块集合;子块信息即候选块信息;

27、当遍历完所有空闲链表仍未收集到足够页数,或候选块数量达到上限但仍不满足需求,组合分配失败,返回nomemory错误,为失败情况;上限是指一次组合分配允许使用的候选子块最大数量;需求是指本次内存申请所要求满足的条件;

28、 (3)内存分配阶段;若找到足够内存块,则逐个调用后端伙伴模块的alloc_pages_at接口进行精确分配,如果该地址的块已被分配或不存在则返回失败;当是成功情况时,所有候选块都成功申请到;当是失败情况时,某个候选块锁定失败,触发回滚阶段;足够内存块即收集到足够页数;

29、(4)回滚阶段;在任一内存分配失败时按照相反顺序释放所有已成功分配的块;

30、(5)记录元数据阶段;记录器构造组合块的元数据记录,包括以下字段:基地址base_addr、子块数量part_count、子块描述符数组parts;将构造好的组合块的元数据记录传递给元数据管理模块管理。

31、根据本发明优选的,元数据管理模块采用固定大小的数组结构compositeblocktracker,每个槽位存储一条组合块元数据记录,即总计记录若干条组合块元数据记录联合而成的大内存块;每个联合内存块由compositeblockinfo数据结构描述,compositeblockinfo数据结构记录组成联合内存块的标准buddy块的信息;

32、元数据管理模块中记录2个联合成的连续内存,存储在槽位0和槽位1中,其余槽位为空;槽位中存储compositeblockinfo数据结构,compositeblockinfo数据结构包括组合块起始地址base_addr、实际buddy块数量part_count及若干buddy块parts,每个子块part中存储每个buddy块的起始地址和阶order。

33、记录元数据阶段中,前端分配模块在所有候选子块均成功分配后,构造一条compositeblockinfo组合块元数据记录,用于描述一次组合分配结果;compositeblockinfo组合块元数据记录包括组合块起始地址base_addr、实际子块数量part_count以及子块描述符数组parts;其中,base_addr为所有子块中最小的物理起始地址;part_count表示本次组合分配实际包含的buddy子块数量;parts数组中的每个有效元素记录一个子块的起始地址和阶次order。

34、根据本发明优选的,内存释放;具体包括:

35、分配时的记录流程:组合分配成功后,前端分配模块构造compositeblockinfo记录,填充最左子块地址base_addr即组合块起始地址base_addr、part_count和子块描述符数组parts即若干buddy块parts,然后,将compositeblockinfo记录插入blocks[count]位置,递增count,完成登记;

36、释放时的查询拆分流程:接收释放请求地址,顺序扫描活跃记录,匹配base_addr;活跃记录是指compositeblocktracker中当前已经登记且尚未释放的有效compositeblockinfo记录;

37、若匹配命中,则按子块描述符数组parts逐个子块调用伙伴分配器释放所有子块后,移除追踪器记录即组合释放路径;

38、若未命中,则判定为标准块,直接走标准伙伴释放路径。

39、本发明的有益效果为:

40、1、提高大块连续内存分配成功率。本发明在不改变现有buddy后端分配机制、不迁移已分配内存、不依赖启动阶段静态预留连续内存池的前提下,利用当前空闲链表中的空闲块信息,主动识别并组合物理地址相邻的多个空闲块,形成逻辑上的大连续内存区域,从而缓解传统buddy系统因幂次分块、对齐约束和仅伙伴块可合并所导致的大块连续内存分配受限问题。

41、2、兼顾传统buddy性能与扩展能力。本发明采用“先标准分配、后组合分配”的双路径机制。对于普通分配请求,优先沿用传统buddy快速分配路径,保持原有分配效率和稳定性;仅在标准路径无法满足大块连续内存请求时,才启动组合分配路径,因此能够在尽量不增加常规分配开销的情况下扩展大块分配能力。

42、3、保持对现有分配器的兼容性。本发明将组合分配逻辑设置在前端分配模块中,后端buddy模块仍执行原有的分裂、分配、释放和合并流程,无需修改buddy核心算法,也无需改变已分配内存的位置,便于在操作系统内核、hypervisor等已有内存管理系统中集成。

43、4、保证分配与释放过程一致可靠。本发明通过元数据管理模块记录组合块与各buddy子块之间的映射关系,使组合分配结果在释放时能够被准确识别并拆分归还;同时,在组合分配过程中采用逐块精确分配和失败回滚机制,任一子块分配失败即释放已成功分配的子块,从而保证分配过程的原子性和一致性,避免资源泄漏。

44、5、降低静态预留带来的资源浪费。相比启动时预留大块连续内存池的方案,本发明基于运行时空闲链表状态进行动态组合分配,能够按需形成大块连续区域,减少长期预留但未使用的内存浪费,提高物理内存利用率。

45、6、适用于虚拟化和设备直通等场景。本发明尤其适用于type-i hypervisor、虚拟机启动内存分配、dma连续缓冲区、设备直通等需要大块连续物理内存的场景,能够提升系统在复杂内存布局下对大容量连续内存请求的满足能力。