文献标识码:A
文章编号: 0258-7998(2012)11-0034-03
内存池方式的内存管理是一种可计量、高效的内存管理方式,它具有减少内存碎片、提高分配速度、防止内存泄漏等优势[1]。目前在国内基于内核的内存池大多基于Linux内核[2]。本文主要基于Nucleus操作系统内核来介绍内存池静态与动态分配在TD-LTE无线综合测试仪移植中的研究与应用,阐述了在不同分配方式中的内存池结构、分配算法以及适用环境。
1 静态方式分配内存池
静态内存池管理方式中内存池分为池(pool)和块(partition)。之所以称之为静态管理方式,是因为在使用过程中块的大小是固定的(即在创建过程中块大小是确定的)。静态内存池的整体结构如图1所示,池和块都有自己的头,池是由双向循环链表链接而成,块是由单向链表链接而成,每一块的头中还包含了自己属于哪一个池的属性。可用块的信息以单向链表的形式存储于池头中,并且可用块与已经分配的块的个数都在池头中有记录。
1.1 静态内存池的创建
池头中的主要参数包括内存池控制块指针、内存池名(只取8个字符)、起始地址、内存池总大小(字节为单位)、内存池分块大小(字节为单位)、挂起方式(先进先出或按优先级)等,图2是仿真器上运行过程中静态内存池结构体截图。
对图2中两个结构体链表参数说明如下:(1)pm_created:当前已经创建的内存池,采用双向循环链表连接,插入方式是在最后一个节点和首节点间填充;(2)pm_available_list:存储当前还可用partition的链表,结构与块的头部结构header_ptr相同(PM_OVERHEAD=8 B小块的头header_ptr:单向链表,内部有指向下一小块的指针和所属大块的控制块地址)。
在Nucleus内核中,内存池的创建主要由函数PMC_Create_Partition_Pool负责,创建流程如下:调用过程中首先进行参数合法性检测;然后在池头(控制块)中写入各个参数,创建链表;之后是一个重要的循环体,负责初始化partition链表,分配所有的partition,每个partition的大小在分配时需要在函数传入参数值的基础上加8 B,用来存储header_ptr;最后在内存池线程保护后将新的内存池插入内存池链表并计数。
1.2 静态内存池的分配
在TD-LTE无线综合测试仪中分配前由协议栈提供所需要分配的大小,这里主要是放置协议内部配置信息与层间交互原语。由于这些信息的大小固定,只是有几种不同大小的固定模式,所以很适合采用静态分配的方式来分配内存,只需要根据数据大小选择密度合适的内存池即可。移植过程中使用了不同大小的partition构建不同密度的内存池,因此,可根据申请partition的大小来判定用那种密度的内存池,以减少内部碎片的大小。这种方法可以有效避免空间浪费[3],同时又可提高分配效率。
在Nucleus内核中静态内存池的分配主要由函数PMC_Allocate_Partition负责,其主要参数为内存池指针(指向调用的内存指针,不能为NULL,设置为可用内存地址即可)、分配大小和挂起标志位。函数中主要判断内存池指针是否合法、内存池与partition是否匹配、指向调用的内存指针是否合法、任务挂起标志位是否有效。其分配流程如图3所示。过程如下:调用内核函数TCT_System_Protect(TCT_Protect)保护内存池同步互斥通道。判断是否还有可用partition,若有,则将可用数量减1、分配数量加1并更新pm_available_list以及将指向调用内存指针赋值为当前分配的partition地址(partition地址要+8 B删去头);若没有,则将任务挂起直至有可用Partition才恢复。最后解保护并返回。
1.3 静态内存池的释放
系统采用PMC_Deallocate_Partition函数来完成释放。流程如下:调用内核函数保护内存池同步互斥通道。判断是否有等待任务,若有,则分配给这个任务当前partition,再判断当前任务是否允许被抢占,允许就调用TCT_Control_To_System抢占当前任务、激活等待内存的任务;若没有,则等待任务,将当前partition重新接入到可用partition列表的头部。最后调用TCT_Unprotect解保护。
2 动态方式分配内存池
动态内存池也分为池和块两个部分,动态池直接由双向循环链表实现连接。内部块是动态分配的,由最小可分配空间来限制块的最小值。与静态分配不同,动态分配块也由双向循环链表来链接。创建时的初始结构为两个块,在申请时动态分割。图4是仿真器上运行过程中动态内存池与块的结构体截图。
池控制块结构中dm_memory_list与块头结构体相同,池通过dm_memory_list来完成块搜索;块头结构中dm_memory_pool与大块头结构相同,通过它来比配大块。
2.1 动态内存池的创建
初始化完成时的内存结构:初始化创建完成时内存池中有2个块,1个大小为总大小减去32 B,包含自己的头DM_OVERHEAD=16 B,设置为可以状态free=‘0x01’;1个大小为16 B,只有自己的头,没有空间,设置为不可以状态free=‘0x00’。因此,此时的可用空间为除去池的控制块外的总大小减去32 B。初始化结构如图5所示(没有将池控制块表示出来)。
创建时,首先为控制块指针赋值,内存池大小与最小分区大小进行字对齐校正;判断控制块指针、起始地址、最小分配空间、挂起标志是否合法。创建过程如下:初始化控制块中的各个参数,并按图5初始化小块、创建小块双向循环链表,与静态分配相同需要先进行线程保护再加入到池动态内存池链表。
2.2 动态内存池的申请
动态申请主要用于操作系统内模块(如任务、队列等)的堆栈分配与模块占用空间的分配。由于在TD-LTE无线综合测试仪中这些分配的空间大小浮动不定,因此需要使用动态分配内存。Nucleus中动态分配采用首次匹配原则,每一次申请内存时动态分配申请大小加16 B(这个16 B的头对应剩下的可用空间)的内存池空间,并把分配过的部分设置为不可用状态free=‘0x00’。
负责实现的函数是DMC_Allocate_Memory。首先进行各种参数的合法性检测,然后将分配空间size小于最小分配空间的分配空间大小赋值为最小空间,对size进行字对齐处理,调用线程保护后采用首先匹配法来找适用空间,即:在循环体中先判断free标志,是空闲块(free=‘0x01’),则算出减去本次分配的头后所剩的空间,当此空间大于本次请求size时进行分配,小于时则移动到下一个块;若不是空闲块,则直接把剩余空间设置为0进行后面小于size时移动到下一个块的判断。注意:这里用到了控制块中的dm_search_ptr属性(结构与小块的头相同),该属性用于记录开始匹配的起始位置,作为判断循环体结束的条件之一,如果循环到此处,就表示没有找到可分配空间。图6是动态分配的流程图。
循环结束后判断是否找到可用于分配的块,若找到则进行是否需要分割该可用块的判断。条件是这个可用块的大小大于或等于本次所需空间size+头大小+最小分配空间的值,若满足此条件则分割出一个新块并对其加头初始化,再计算出剩余可用空间;不满足此条件则直接计算剩余可用空间。分配的空间标志为非空闲后,把所分配空间的地址赋给指向调用的内存指针(注意去头)。为提高效率,还需要进行一个简单处理,即判断如果在搜索块时一次性匹配成功,则将dm_search_ptr移向下一个块。
如果没有找到可用块则将任务挂起等待,没有采用挂起模式则直接返回NULL给指向调用的内存指针,最后调用TCT_Unprotect解保护。图7是分配第一块内存后动态内存池的结构。
2.3 动态内存池的释放
释放过程与静态类似,需要注意的是,如果相邻块有空闲块需要合并,则合并后把dm_search_ptr指向当前合并的空闲块。
动态分配内存的算法复杂度要高于静态分配,从时间复杂度来看,静态分配是O(1)、动态是O(n)。但是动态分配的内存利用率要高于静态分配内存[5],在实际应用中要结合具体情况决定采用何种分配方式。在本设计中合理使用了两种分配方式:在静态分配中进行密度的动态判断,在动态分配中进行静态的最小分配大小匹配。动、静相结合,使操作系统在分配中尽可能地节约内存的同时,有效减少了内存碎片。本分配方式已经运用于TD-LTE无线综合测试仪中,在实现操作系统基本内存管理功能的同时,满足了TD-LTE无线综合测试仪对系统内存资源和调度时间的设计要求。
参考文献
[1] 冯宝祥,王桂棠.嵌入式实时操作系统Nucleus PLUS在S3C2410A上移植的实现[J].电子设计应用,2007(5):104-106.
[2] 王小银,陈莉君.Linux内核中内存池的实现及应用[J]. 西安邮电学院学报,2001,16(4):40-43.
[3] 张磊,王忠仁.嵌入式系统中一种池式内存管理中应用 [J].实验科学与技术,2007,5(2):150-152
[4] LMAS S H.An application-level memory management service[C].ICTTA 2008.3rd International Conference on.7-11 April 2008:1-4.
[5] MUTSCHLER D W.Enhancement of memory pools toward a multi-threaded implementation of the Joint integrated mission model(JIMM)[C].WSC 06.Proceedings of the Winter.3-6 Dec.2006:856-862.