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

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

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

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

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

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

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

　　（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空闲区的情况。

　　4 结 论

动态内存管理一直是计算机领域的一项重要技术。动态内存管理给用户提供了比较大的自由度，用户可以从系统分区中申请内存块，也可以从用户内存区申请内存块。这样增加了系统的灵活性，同时也限制了大量碎片产生的可能（在不频繁删除建立系统内存分区的前提下）。也增加了部分c 代码的可移植性。