RTOS动态分区内存管理机制的优化设计

　　引 言

　　在嵌入式领域中，嵌入式实时操作系统(RTOS)正得到越来越广泛的应用。采用嵌入式实时操作系统可以更合理、更有效地利用CPU的资源，简化应用软件的设计，缩短系统开发时间，更好地保证系统的实时性和可靠性。内存资源作为嵌入式系统中极为重要的资源之一，其管理机制历来是嵌入式系统设计的重点和难点。内存管理机制的优劣程度极大地影响着嵌入式系统的整体性能，因此在嵌入式RTOS的内存管理机制中必须满足以下3个要求：

　　①实时性。在嵌入式RTOS中不仅要求调度机制的实时性，资源的分配和回收的实时性也十分重要。

　　②可靠性。嵌入式系统的应用领域决定了嵌入式RTOS必须具有高可靠性，而内存管理的可靠程度直接影响RTOS的可靠性，因此内存管理的可靠性也必不可少。

　　③高效性。由于嵌入式系统资源的稀缺性，因而高效的资源管理机制也同等重要。

　　1 动态分区内存管理机制

　　1．1 动态分区内存管理概述

　　在许多小型嵌入式系统中并未实现虚拟内存机制，动态分区内存管理机制仍然是首选。分区存储管理是满足多道程序设计的最简单的存储管理方法，它允许多个用户程序同时存在系统内存中，即共享内存空间。早期的分区存储管理采用固定分区的方法，把内存空间分成若干个大小不等的区域，称为分区。每个用户程序(作业、进程)调入内存后，占用其中1个分区，程序运行完成后释放该分区。这种存储管理方法的主要问题是内存使用效率极低，很快就被淘汰了。取而代之的是动态分区存储管理技术。图1显示的是动态内存管理的数据结构。

　　1．2 动态分区内存分收算法及其性能分析

　　在动态内存分配机制中一般采用两种设计方案：最佳适应算法和首次适应算法。最佳适应算法要求所有的空闲内存块按照内存块的大小，由小到大链接在一起。首次适应算法中所有的空闲内存块都是按地址由小到大链接的。图2显示了这2种算法的流程(假设系统申请的内存块大小为n)。

　　最佳适应算法和首次适应算法在分配内存的流程上是一致的，然而由于空闲内存块的组织形式不同，其分配的性能也不尽相同。最佳适应算法由于每次分配都是首先分配与所要求的内存块大小最接近的空闲内存块，因而其内存利用率相对较高。然而由于在内存回收过程中需要合并那些地址相邻的空闲块，最佳适应算法往往需要遍历整个空闲区链表以寻找符合条件的内存块。而首次适应算法由于是按照地址的顺序相连，因而在内存回收方面有着最佳适应算法无法比拟的性能。

　　图3显示了在几种不同情况下，动态分区内存回收机制所采取的策略。

　　在A中，释放区回收后合并成新内存块f，其首地址为f1内存块的首地址，大小为f1和R内存块的大小之和。在B中，释放区回收后合并成新内存块f，其首地址为R内存块的首地址，大小为f1和R内存块的大小之和。在C中，释放区回收后合并成新内存块f，其首地址为f1内存块的首地址，大小为f1和R以及f2内存块的大小之和。在D中，释放区回收后不进行合并，直接插入空闲区链表并返回。

　　动态分区内存的分配机制有效地避免了内存内部碎片的存在，同时在内存回收策略中使用合并算法也极大地减少了内存外部碎片存在的可能性。然而，当系统需要分配大量的小块内存时，动态分区内存管理机制的性能却并不令人满意。其不足之处主要存在以下2个方面：

　　①当系统分配大量的小块内存后，其空闲区表或空闲区队列将会变得异常庞大。无论是首次适配算法还是最佳适应算法都需要遍历空闲区搜索合适的内存块，因此过于庞大的空闲区结构使搜索算法变得低效。

　　②系统在某些特定的时刻往往会对大量的小块内存进行频繁分配和回收。频繁地对小块内存进行分割分配和合并回收，其实时性表现得并不令人满意。

　　基于以上2点，如何在动态分区内存管理机制的基础上优化小块内存的管理机制，成为提高动态分区内存管理性能的关键因素之一。

　　2 小块内存动态缓存分配机制

　　大部分实时操作系统内存分配机制并未对大块内存和小块内存的分配做出不同的算法设计，然而在实际分配过程中，很难用一种分配算法兼顾大小内存的高效分配。针对动态分区内存管理机制中对小块内存分配的局限性，提出了小块内存动态缓存机制。该机制在继承了动态分区管理机制优良性能的同时，优化了小块内存的管理，对内存管理的实时性和高效性都有一定提高。系统中同时存在2种内存数据结构，分别为小块内存和大块内存设计。大块内存依旧采取动态分区内存管理机制，而小块内存采取动态缓存分配。小块内存数据结构如图4所示。

　　假设小块内存最小为1字节，并以2的指数递增，最大为512字节。这也就意味着当系统需要分配或释放小于或等于512字节的内存时，会执行小块内存操作。图5和图6分别是小块内存的分配和回收流程(图中j代表需操作的小块内存对应的缓存号，若申请120字节则j对应为8；min代表小块内存最大的缓存号，如图中min＝9)。

　　图7是对小块内存操作算法的简单模拟。小块内存缓存区从上到下依次缓存512～64字节的内存块。有4个操作过程：分配64字节→分配128字节→回收64字节→回收128字节。

　　①分配64字节。初始状态小块内存缓存区为空，此时将会执行大块内存分配操作并将1 KB内存分割缓存到小块内存缓存区。在分配64字节内存时，系统自动探测到了128字节、256字节和512字节处的缓存区已经处于饥饿状态，因此也将会分配其缓存区1块内存。

　　②分配128字节。由于系统存在该大小的缓存，因此直接获取并返回。

　　③回收64字节。由于释放后，系统中64字节大小的内存块可以合并，因此合并后链入上一级缓存区。

　　④回收128字节。内存块再次进行合并操作，最终调用大块内存释放操作，从而回到原始态。

　　图7所示的内存操作只是一个非常简单的模拟，实际系统内存的分配和回收是非常复杂和不确定的，而小块内存动态缓存分配机制的性能在这种情况下表现得尤为突出。总体而言其具有以下几点优势：

　　①快速性。因为使用了缓存机制，所以在大部分情况下，小块内存释放后依旧在缓存区中，当系统再次分配该大小的内存块时就极为快速。

　　②自适应性。在分配小块内存的过程中，算法能检测出处于饥饿状态的内存块大小，并依次为它们所在的缓存区分配1块相应大小的内存块。

　　③动态性。在小块内存的回收过程中，该算法将对内存块进行合并重组。假若某时刻先前从大块内存中分配的1 KB内存块全部被小内存块释放，其经过重组后必定能重新添加到大内存块存储区。

　　3 优化后的系统内存管理机制

　　图8和图9分别是优化后系统分配和回收内存的算法，图中的max代表的是小块内存的最大值。当不能得到所需的小块内存，或者释放小块内存最终合并成大块内存时，分别调用大块内存分配和释放操作，从而保证小块内存和大块内存操作能很好地协作，增强了系统的稳定性。

　　结 语

　　尽管在引入小块内存动态缓存分配机制后，系统在分配小块内存时会存在一定的内存内部碎片，但由于小块内存本身很小以及大块内存的动态分区管理机制，很好地降低了系统中由于存在内存碎片而带来的风险。在实际模拟测验1中，经优化过的动态分区内存管理机制能在一定程度上提高系统的实时性及可靠性，在嵌入式RTOS的设计中具有实际的意义。