动态内存管理在面向嵌入式实时系统中的研究

动态内存管理的基本任务就是有效地对动态内存进行分配、回收，并同时保证系统的快速性、可靠性和稳定性。当系统请求分配内存时，系统需要从所有空闲块中找到一个合适的空闲块进行分配；当用户不再使用而将某块内存释放时，系统需要回收这一内存块，以备在新的请求产生时重新进行分配。为此，系统需要建立一个与内存当前使用情况相对应的内存描述，用来记录所有与内存分配、回收相关的信息。而如何记录这些信息并进行分配与回收，便成为各种算法的最根本区别。

　　1 嵌入式系统中内存管理技术的特点

实时系统分为硬实时系统和软实时系统。硬实时系统是指系统中各任务不仅要执行无误而且要做到准时；软实时系统是指系统中各任务运行的越快越好，并不要求限定某一任务必须在多长时间内完成。可以看出动态内存分配是绝对不能用于硬实时系统的，因为动态分配具有时间不确定性（分配时间与内存块数量有关），而且动态分配可能产生分配不成功的情况。所以对于硬实时系统，只能采用静态内存分配方式。静态分配是指在编译或链接时将程序所需的内存空间分配好，这样不会出现分配失败的情况。

1.1 静态分配与动态分配

静态分配为系统提供了最好的可靠性与实时性。对于那些对实时性和可靠性要求极高的需求，就只能采用静态分配方式。但采用静态分配就必然会使系统失去灵活性。因此必须在设计阶段考虑所有可能的情况，并对所有的需求做出相应的空间分配。一旦出现没有考虑到的情况，系统就无法处理。此外静态分配方式也必然导致很大的浪费，因为必须按照最坏情况进行最大的配置，而在实际运行中可能只用到其中的一小部分。

动态分配为系统提供了很大的灵活性，而且在内存的利用率和系统功能扩展等方面也都明显地优于静态分配。
大多数系统采用静态分配和动态分配相结合的方式。由于嵌入式系统本身各个任务的可靠性、实时性要求不尽相同，通常会有一部分任务对可靠性与实时性没有特别严格的要求。这些任务对一定的延时与失败是可以接受的。因此对于这样的一部分任务，就可以采用动态分配方式来满足它们部分或全部的内存需求。而对于那些有严格时限要求的任务，为了保证任务的可靠性和实时性，就应采用静态分配方式。

1.2 动态分配的技术要求

（1）快速性：由于嵌入式系统对实时性要求较高，所以内存分配过程要尽可能地快。在嵌入式系统中，由于还不能采用通用操作系统中复杂而完善的内存分配策略，所以一般都采用简单、快速的内存分配方案。

（2）可靠性：由于嵌入式系统对可靠性的要求较高，所以内存分配过程也要具备高可靠性。但由于各个嵌入式系统之间对可靠性的要求不尽相同，对内存分配的可靠性要求也就各不相同。通常，可靠性要求极高的系统不采用动态分配。

（3）高效性：由于在嵌入式系统中内存资源都相对有限，所以为了保证程序的正常运行，内存管理系统要尽可能高效地使用内存，减少不必要的浪费。

　　2 伙伴系统

2.1 伙伴系统原理

伙伴（buddy）系统的基本原理就是按照2的幂次方大小对内存进行分配，以此得到很高的分配速度和回收速度。例如：对于10KB的空间请求，伙伴系统会分配16KB的空间来满足。因为内存空闲块大小均为2的幂次方，所以需要16KB,这是满足10KB的最小空间；同样对于70KB的空间请求，伙伴系统会分配128KB的空间来满足。

2.2 伙伴系统存在的问题

伙伴系统比那些按大小而不按块的整数倍地址分配的算法有更多的优点。其优点为当一个大小为2的K次幂的块被释放后，存储管理只需要搜索2的K次幂字节大小的块以判定是否需要合并。那些允许内存块以任意形式分割的策略需要搜索所有的空闲块表。相比之下，伙伴系统更快。

但是对于内存利用率来说，伙伴系统是极其低效的。问题出自所有的内存请求都必须以2的幂次方大小的空间来满足，一个35KB的请求需要分配64KB的空间，其余的29KB被浪费了。在极端情况下内存资源有近50%被浪费。

　　3 连续的内存分配

3.1 问题提出

伙伴系统的内存管理方式对空间的使用存在极大的浪费。在某些情况下还会由于资源的浪费，导致后继的内存请求得不到满足，进而严重地影响程序的正常功能。

试考虑：系统共有1MB内存空间可用，采用伙伴系统进行管理。有如下请求：请求A,300KB;请求B,300KB;请求C,50KB.结果如表1所示。

由表1中可以看出：伙伴系统对空间的浪费是极其严重的，即使在物理内存充足（1MB）的情况下，也会产生请求（650KB）无法满足的情况。

由于在嵌入式系统中，一般都没有虚拟内存的支持，所以当内存请求无法得到满足时，将严重影响程序的正常功能。因此为了保证程序的正常功能，就要提高内存的利用率，尽可能地满足程序的内存请求。所以在对伙伴系统进行分析的基础上，提出了连续的内存分配方式。

3.2 连续的内存分配原理

从上例不难看出，只要采用连续的内存分配方式（即分配与请求大小相等的空间来满足请求），便不难使请求C得到满足，而且还会有很大的剩余空间继续用来满足其他的内存请求。结果如表2所示。

连续的内存分配方式明显不同于其他以块为单位进行分配的内存管理方法。它采用连续分配的方式，按照请求空间的实际大小来进行空间分配。

3.3 连续的内存分配实现方法

为了提高内存空间的利用率，采用按请求的实际大小来分配空间，而不是按块的整数倍大小来分配空间。

基本方法就是将所有独立块（空闲块和使用块）按物理地址的先后顺序组织成一个双链表，每个块中存放块本身的一些独立信息。分配空间时，需要查找整个链表以找到最优适配的空闲块，之后再将此空闲块分裂成二块，一块用来满足请求，另一块则作为空闲块插入链表。空间释放时，只需根据链表便可以方便地找到与其相邻的物理块，在空间合并处理完成之后再将新的块插入链表。

但事实上，由于在分配过程中只需要在空闲块中查找最优适配块，所以可以采用一个单独的链表将所有的空闲块链接起来，这样可以极大地加快空间分配时空闲块的查找速度。

另外，从对伙伴系统的分析可知，将所有的内存空闲区保留在一个或多个按空闲区大小排序的链表中将使内存分配很快。所以借鉴伙伴系统的实现方式，可以将单个的空闲分区链组织成多个链表间有序的空闲分区链。在动态内存操作频繁的情况下，这将会提高系统内存分配的效率。

由于以上的方式容易产生许多小的不能继续使用的空闲区，所以在进行空间分配时，如果分配所得的空闲区小于某一特定值，则不再进行空间分配，而是将整个空间作为请求结果返回。

综上所述，可以将内存块组织成二个双链表，即空闲块链表和物理块链表。

（1）空闲块链表：将所有的空闲块按链表间有序的方式组织成多个独立的空闲链表。空间分配时，根据空间的大小选择相应的链表进行查找。若查找成功，则在空间分配处理完成之后，将已分配空间返回给请求；若查找失败，则在更大空间的链表中继续查找；若直到全部链表查找完成仍未找到合适的空闲块，则认为此次分配操作失败。

（2）物理块链表：将所有独立块（空闲块和使用块）组织成一个双链表，链表中各节点之间是按照物理地址的先后顺序链接的，每个块中存放块本身的一些独立信息。空间释放时，可以不需查找，而直接根据这一链表找到与释放块相邻的块。再根据相邻块中的相关信息就可以方便地进行内存块的合并操作。

具体实现时，可以将这二个链表的控制信息与用户空间独立存放，避免控制信息被意外地破坏。也可以利用物理块本身来存放这些控制信息，得到更好的空间利用率和更好的灵活性。

3.4 连续的内存分配工作方式

首先假定空间不再进行分配的最小值为1KB,即当空间分裂时所得的空闲区小于1KB时，将不再进行空间分配。
分别保留大小为1KB、2KB、4KB、8KB字节等直到大于内存总容量大小的链表。例如对于容量为1 024KB的内存，有从1KB字节到2 048KB字节的12个链表。初始时，所有内存都是空闲的，2 048KB的链表包含一个1 024KB的空闲区（每个链表存放所有小于链表本身字节数、大于等于前一链表的字节数的内存块，2 048KB的链表存放所有小于2 048KB大于等于1 024KB的内存块）。其他的链表均为空，内存最初的情况如图1所示。为表示方便，图中使用单链表来表示链接关系。实线表示物理块链表指针，短划线表示空闲块链表指针，虚线表示空指针。对于物理块链表，灰色块表示已分配块，白色块表示空闲块。

当有一个300KB的内存请求（用A表示）产生时，系统找到512KB链表的表头。因为这个链表中可能包含满足请求所需的最小空间。之后按照最佳适配（best fit）算法，在链表中搜寻是否有够用的最小空闲区。此时512KB的链表为空，1 024KB的链表也为空，所以最终在2 048KB的链表中找到1 024KB可用空间。将此空间分割成大小分别为300KB和700KB的块，700KB的块（大于最小块1KB）插入到1 024KB的链表中，300KB的块则返回给请求A.
接着，又有一个300KB（用B表示）和一个50KB（用C表示）的内存请求。结果如图2所示。

现在块B被释放。此时，根据物理块链表，可以方便地找到与B邻接的物理块A和物理块C.由于块A和块C都未被释放，所以不需要进行合并操作。因为块B的大小介于256KB和512KB之间，所以将块B插入到512KB的空闲链表中，结果如图3所示。

接着，块C被释放。此时根据物理块链表可知与块C邻接的为块B和块F,并且二块都为空闲状态。将块B和块F从512KB空闲块链表中删除，再将三块合并成一个700KB的块（用F表示）插入到1 024KB的空闲链表中，结果如图4所示。

最后当块A被释放时，块A与块F合并成1 024KB的块，回到最初只有1 024KB空闲区的情况。