（计算机系统结构专业论文）实时嵌入式操作系统动态内存管理研究.pdf

摘要 摘要 在操作系统的设计中，有两种内存分配策略，分别是动态内存分配与静态 内存分配。与静态内存分配策略相比，动态内存分配策略允许在运行时动态地 申请和释放一定大小的内存，这极大地提高了设计灵活性及应付突发事件的能 力。出于这个原因，动态内存分配策略在软件设计领域得到了广泛的应餍。然 而，受实时性与资源受限等约束所限，在实时嵌入式操作系统的设计中，动态 内存分配策略鲜有应用。 本文以飞行器、航空航天等典型的实时嵌入式应用为背景，以微内核抢占 式实融嵌入式操作系统盯e m s 为实现及澳l 试环境，对动态内存资源管理进行 了深入的研究。主要工作如下所述： ( 1 ) 。动态内存管理设计要求分析 本文在对若干实时嵌入式操作系统应用实例深入分析的基础上，进一步明 确了选择合适的性能参数与应用需求之间的关系，并结合本论文的应用需求， 提出了动态内存资源管理设计的实时性、高效性与可满足性要求及其体含义。 这为后续相关模块的设计与实现提出了设计要求，是本论文工作的前提。 ( 2 ) 。动态内存资源管理研究 本文将动态内存资源管理划分为动态内存请求管理与动态内存分配回收算 法两部分。动态内存请求管理从高层上决定任务是否有使用动态内存资源的权 限，尽量保证关键任务动态内存请求的可满足性，在资源受限的条件下提高了 内存资源的使用效率，保证了系统的正常运行；内存分配与回收算法则从底层 操作入手，在7 f l s f 算法的基础上，剥用“最小块数量，最小块大小 信息及“精 确”切割策略，在保证算法实时性的前提下，减少了内部碎片，同样在资源受 限的条件下提高了内存资源黪傻阁效率。 ( 3 ) 基于r t e m s 的动态内存资源管理实现及测试 雕e m s ( r e a lt i m ee x e e u t i v e 南rm 骶a r ys y s t e m s ) 是微内核抢占式实时嵌入 式操作系统。本文将动态内存资源管理模块集成于r t e m s 内核中，并自行编 写测试任务集对该模块进行功能及性能测试。测试结果不仅表明本文工作的有 效性，还为下步工作指明了方向。 关键词：嵌入式操作系统动态内存管理动态内存请求动态内存分配 a b s t r a c t a b s t r a c t t h e r ea r et w os t o r a g ea l l o c a t i o nt e c h n i q u e si no p e r a t i n gs y s t e md e s i g n ，d y n a m i c s t o r a g ea l l o c a t i o n ( d s a ) a n ds t a t i cs t o r a g ea l l o c a t i o n w i t ht h es u p p o r to fd s a ，a t a s kd e t e n n i n e st h ee x a c ts i z eo ft h e s t o r 喀er e q u i r e dd u r i n gi t sn j n n i n g ；t h e a l l o c a 王e ds t o r a g ec a nb e 行e e d 、 ，h e nn o tu s e dw b i c hc a nb eu t i l i z e df o rf u t u r e a 1 1 0 c a 芏i o n t h i st e c h n i q u eg r e a t l yi m p r 0 v e st h ef l e x i b i l i t yo fs y s t e m ，觚da l s ot h e a b i l i t yt od e a lw i t ht h eu n i n t e n t i o n a le v e n t s 。s oi ti sw i d e l vu s e di nm o d e r ns o n w a r e e n g i n e e r i n g h o w e v e r ，i nt h er e a l 一t i m ee m b e d d e ds y s t e m s ，d u et ot h eu n c o n s t r a i n e d r e s p o n s et i m eo fd s aa l g o r i t h m sa n dt h ef h g m e n t a t i o np r o b l e m ，d e v e l o p e r sa n d r e s e a r c h e r sa v o i dt h eu s eo fi t b a s e do nt h et r a d i t i o n a ih a r dr e a l t i m ed o m a i n ，a e r o s p a c ef o r e x a m p l e ，a n dt h e i h e m ss y s t e m ，ad e e pr e s e a r c hi nt h ed y n a m i c s t o r a g em a n a g e m e n ti sp e r f o r m e di n t h i st h e s i s f i r s t ，b a s e do nm ea p p l i c a t i o nr e q u i r e m e n t s ，s e v e r a lp a r a m e t e r sa r ep o i n t e do u t ， w h i c hg r e a t l ya f f e c td s a p e r f o r m a n c e t h e s ep a r a m e t e r si n c l u d ef a s tr e s p o n s et i m e ， l o wf r a g m e n t a t i o na n d s a t i s f i a b i l i t yo fs t o r a g er e q u e s t s t h i sw o r kc a nb ec o n s i d e r e d a st h ep r e c o n d j t i o no ft h i sr e s e a r c h s e c o n d ，t h i st h e s i ss e p a r a t e st h ed y n a m i cs t o r a g em a n a g e m e n ti n t ot w op a r t s ， d y n a m i cs t o r a g er e q u e s t sm a n a g e m e n ta n dd s a d y n 锄i cs t o r a g er e q u e s t s m a n a g e m e n ti sal a y e rb e t 、v e e nt a s k ss t o r a g er e q u e s t sa 1 1 dds aa l g o r i t h m s i t sg o a l i st om a x i m i z et h eu s a g eo fs t o r a g er e s o u r c e sa n d g u a r a n t e et h ec r i t i c a lt a s k ss t o r a g e r e q u i r e m e n t sf r o mt h eg l o b a li n f o m a t i o n b a s e do nt l s fa l g o r i t h m ，t h ed s a p r o p o s e di n t h i st h e s i sr e d u c e si n t e r n a lf h g m e n t a t i o nw h i l em a m t a i n1 0 wt e m p o r a l c o s t -b o t ho ft h et w o p a r r t s m a x i m i z em eu t i l i z a t i o no f m e m o 叮 i nt h e r e s o u r c e c o n s t r a i n e dr e a l t i m es y s t e m s t h i r d ，b a s e do nm er t e m ss y s t e m ，d y n a m i cs t o r a g em a n a g e m e n ti sr e a l i z e di n t h i st h e s i s b e s i d e s ，s e v e r a lt a s ks e t sa r ed e s i g n e dt op e r f o r mt h et e s t i n gw o r k t e s t s r e s u l t sn o to n l ys h o wt h ef u n c t i o n a l i t yo fd y n a m i cs t o r a g em 锄a g e m e n t ，b u ta l s o p o i n to u tt h ef u t u r ew o r kt h a ts h o u l db ec a r 五e do u t k e y wo r d s ：e m b e d d e do p e r a t i n gs y s t e m ，d y n a m i cm e m o 拶m a i 】a g e m e n t ，d y 力a m i cm e m o r e q u i r e m e n t ，d y n 锄i cm e m o r ya l l o c a t i o n i i 表格目录 表格目录 表1 1 两种内存分配策略比较2 表3 1 控制表所占空闻大小与s l 关系3 l 表4 1 判断条件的参数及其来源3 7 表4 2 任务信息4 2 袭4 3 内存请求管理时间开销4 6 表4 4 内存分配与回收算法时间野销4 7 表4 5 内存分配与回收算法碎片情况4 8 ￥王 撼懋强最 插图匿录 圈1 1t 纛s f 数据结梅篱篷心。6 图2 一i 系统a 与酩响应时间对沈圈1 0 图2 2 从打字员角度看系统性能l l 阉2 3v x w o 呔s 空闲块列表 15 圈2 4v x w b r k s 空阑块列袭2 。1 5 圈3 i 动态内存管理模块框图1 7 阁3 2 动态内存请求管理结构图1 8 窝3 3 髑麓任务鬣占有蠹存量示铡溺i 多 图3 - 4 动态内存请求管理模块流程图2 3 墅3 5 动态蠹存分驻鐾彀绻梅餮2 凄 圈3 6 空闲块及非空闲块结构示意图2 5 銎3 7 箍裂蓓毫络梅示意辫2 6 圈3 8 空闲块列袭组织结构示意图2 7 黧3 9i 毛s f 算法镯 喜| j 篆踌示铡鏊霉k ，2 s 图4 1r t e m s 应用程序结构图3 3 委蓬乏黼嚣澈s 空瓣块示意嚣3 图4 3 哑堆块示意图3 5 爨垂4 个薪鹣难3 5 圈4 5 测试1 内存占有量图4 2 慰4 6 测试2 蠹存占有量黧。，霉3 黼4 7 测试3 内存占有量图4 4 熙4 8 测试4 内存占有量躁4 5 中国科学技术大学学位论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工 作所取得的成果。除已特别加以标注和致谢的地方外，论文中不包 含任何他人已经发表或撰写过的研究成果。与我一同工作的同志对 本研究所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即： 学校有权按有关规定向国家有关部门或机构送交论文的复印件和电 子版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 保密的学位论文在解密后也遵守此规定。 作者签名： 猛圣 矽叨年6 月二日 第l 章绪论 表1 1 两种内存分配策略比较 静态内存分配动态内存分配 实时性好依赖于匹配策略 潜在不可靠因素最坏运行情况估计失误内存碎片问题 内存利用率低 依赖于碎片多少 灵活性应对突发事件能力 差 好 在实时嵌入式系统开发中，中断向量表、系统映像等诸多程序段大小在编 译和链接时是可以确定的，可以使用静态内存分配策略进行分配。此外，在实 时嵌入式系统发展初期，应用功能比较单一，对灵活性要求不高，这使得静态 内存分配成为实时嵌入式系统最常用的内存分配策略。然而，随着实时嵌入式 系统的应用越来越广泛，静态内存分配灵活性差及内存资源利用率低的缺点越 来越引起开发人员的注意。另一方面，动态内存分配策略具有良好的灵活性且 内存资源利用率较高，灵活性不仅提高了系统应对突发事件的能力，也丰富了 资源受限条件下系统的功能，与静态内存分配恰好优势互补，较高的内存资源 利用率则恰好迎合了资源受限这个客观环境。因此，为了在实时嵌入式系统开 发中更好地使用动态内存分配策略，研究越来越多的研究人员开始关注动态内 存分配的实时性及内存碎片问题。 1 2 2 研究现状 目前，实时嵌入式操作系统动态内存管理方面的研究热点有：内存资源管 理及内存分配算法等。 1 动态内存资源管理 、 在多任务环境下，所有任务都有动态内存请求的权限，然而对于不同级别 的任务，内存请求得不到满足所产生的后果是截然不同的。缺乏全局的内存资 源管理，关键任务的内存请求有可能得不到满足。为保证任务的正常运行，在 操作系统中提供动态内存资源管理是十分必要的。 在实时系统中，采用资源预留的方式为关键任务预留一定的内存资源，当 该任务需要这些资源时，可以快速地实现资源分配操作。这样做能够很好地保 证内存请求的可满足性。文献【2 】是一个技术报告，报告指出，资源预留本质上 是实时系统的一种资源管理机制。在资源预留机制的支持下，任务的最坏运行 时间具有良好的可预测性，这恰恰是实时系统调度性分析的基本要求；资源预 留机制有利于模块化设计及可重用设计。此外，该技术报告还为资源预留机制 的设计与实现提出了若干建议。在此基础上，文献 3 】采用内存资源预留机制为 服务质量敏感( q o s s e n s i t i v e ) 的应用提供了高效的内存管理方式。有两种类型的 内存预留方式可供选择：上限预留和下限预留。应用程序按照其中种方式向 2 第l 章绪论 系统提出申请，为其预留定大小的页面，麴粟该申请被仲裁通过的话，系统 将保证该内存页面在应用程序的生存期内都不会被别的程序所占用。通过在 l i n 溉2 1 4 1 8 内核中对该工作的实现及测试，结果表硝这种预留内存的管理方 式裢很大程度上提高了应用程序的可预测性和内存资源的利用效率。 在上述工作的基础上，文献问针对实时系统中提出了一转动态内存资源管 理机制，力求保证任务内存请求的可满足性，提高内存利用率。它将内存资源 视为同c p u 一样的资源来管理，在系统初始化阶段，采用资源预爨机制( f e s o 戳e r e s e r v a t i o n ) 为每个任务预留一定量的内存供其动态内存分配使用。此外，任务 还可以通过提出额外虑存资源请求得到超出其预留内存大小的存储空间。当任 务发生动态内存请求时，内存资源管理模块首先判断预留的内存空闻是否能够 满足该请求，如果可以的话，则将此请求发送绘内存分配模块；否则，内存资 源管理将分搴厅该内存请求是否会影响到其他任务的内存使用，如果对其 也任务 的内存使用没有影响，就将该请求发送至内存分配模块。【4 】提出了若干规则， 这些规则被用于上述的各个判断过程。在这种动态蠹存资源管理机制的支持下， 系统能够保证不超出预留内存大小的请求都能够得到满足，还可以保证当不影 响其他任务的内存请求时，额外内存请求也可以得到满足。然焉，为了更突出 内存资源在任务调度中的地位， 4 】中的规则仅仅是从内存资源的角度考虑请求 的可满足性，并未考虑任务不同优先级及系统实现等问题，具有定的局限性。 2 动态痰存分配回收算法 在实时系统中，关于动态内存分配算法与回收算法，研究热点主要集中在 如何提高算法的可预测性( 实时性) 及减少内存碎片方匿。可预测牲是指d s a 算法的最坏运行时间是不是确定的 5 】。在实时系统中，任务调度的目标是保证 在截止时间裁完成任务，为了实现这个强的，调度算法需要计算任务的最坏运 行时间。因此，实时系统要求d s a 算法的最坏运行时间必须是确定的。内存碎 片是指内存资源的不合理利用导致的内存请求得不到满足的情况。内存碎片包 括内部碎片和外部碎片。当分配给任务的内存块大小大于任务请求的大小时， 会产生内部碎片；外部碎片是指，系统中存在大量长度很小的内存块，但是却 不能满足大部分酶内存请求。实时嵌入式系统为资源受隈系统，动态内存空矧 有限，提高内存资源的利用率必须减少内存碎片。 在文献吲中，作者指出，当有空阑块存在，却不能够被用来满足任务的蠹 存请求时，就认为系统中存在内存碎片。对内存碎片的这个定义得到了国内外 研究人员的广泛认固。蠹存礤片的产生原因是复杂的，肉存请求序列、内存分 配策略、内存生存期等诸多因素都会导致了内存碎片的产生。研究结果表明【5 】， 对外部碎片来说，更多的是由内存请求序列所决定，而对内部碎片来说，则更 3 第1 章绪论 级 图1 1t l s f 数据结构简图 块大小是1 6 3 0 ，那么该空闲块必须切割为大小为1 5 3 6 的空闲块和大小为9 4 的 空闲块。之所以这样做，是因为t l s f 算法认为同一任务的内存请求大小总是 相近的，大小为1 5 3 6 的空闲块被释放后仍然能够插入其原来的子链表，可满足 后续的内存请求。当任务发出内存释放命令时，t l s f 算法同样首先确定被释放 的内存块从属于哪一子链表，之后判断能否进行合并操作，最后将空闲块插入 子链表中。 t l s f 算法能够在o ( 1 ) 时间内响应实时任务的内存请求，实时性很好。然而 由于在内存切割时采用了“取下限”策略，虽然这样做能够保证实时性约束， 但利用空间换时间的方式造成大量的内部碎片，内存资源利用率较低。 3 内存释放时机 在d s a 算法的研究中，不同的内存释放时机对算法的性能有很大的影响。 就目前的研究成果来看内存释放的时机有两种【1 0 】：1 ) 显式内存释放；2 ) 隐式 内存释放。显式内存释放是指任务显式地调用内存释放函数；隐式内存释放则 不必要求任务释放内存，而是采用垃圾回收的方式，每隔一段时间释放不再使 用的内存块。由于内存释放操作要将内存块插入空闲块列表的合适位置，涉及 到定位操作，因此，一般来说，显式的内存释放会影响任务运行时间的可预测 性，不利于任务调度。而隐式的内存释放是由系统负责的，可以在系统负载较 低时进行。然而，从另一方面看，在内存资源受限的实时系统中，及时的内存 释放能够有效地利用有限的内存资源，隐式内存释放则只会增加内存利用的紧 张程度。因此，权衡利弊之后，研究人员认为显式内存释放更适合实时系统 9 】， 上述伙伴算法、h a l f - f i t 算法及t l s f 算法都采用显式内存释放。 1 3 论文工作及组织结构 6 第1 章绪论 1 3 1 论文主要工作 本论文以实时嵌入式系统在飞行器与航空靛天、防务系统等强实时领域的 应用为背景，以动态内存管理机制为研究重点，旨在提高动态内存管理的实时 性、高效性及可满足健，为动态内存分配策略在实时嵌入式操作系统中的应雳 创造良好的环境，具有一定的理论价值与实践意义。具体工作包括动态内存管 理设计要求分析、动态内存管理研究、基于r t e m s 的动态内存管理实现。 1 动态内存管理设计要求分析 根据应用需求分析动态内存管理的设计要求，是本论文工作的前提。本部 分通过对若干实时嵌入式操作系统应用实例的分析，进步明确了选择合适的 性能参数与应用需求之间的关系；之后，结合本论文的应用需求，提出了动态 内存管理模块的实时性、高效性及可满足牲要求，并酒述了各要求酶具体含义。 本部分工作为第三章和第四章各模块的设计与实现提出了要求，并以此要求作 为相应实验结果的评价依据。 2 动态内存管理研究 本文将动态内存资源管理分为动态内存请求管理与动态内存分配回收算法 两部分。动态内存请求管理介予任务请求与内存分配7 回收模块之闯，旨在从全 局的角度合理地利用有限的内存资源。各任务的动态内存请求先发送至动态内 存请求管理模块，该模块结合内存请求信息与系统内存资源现状决定是否将任 务的内存请求发送至动态内存分配模块；动态内存分配分配回收模块接收发送 过来的态存分配7 释放请求，负责底层的物理内存分配回收操作。这两个部分分 别采用不同的措施，使得动态内存管理模块能够满足实时性、高效性和可满足 性要求。 3 基于鼢e m s 的动态内存管理 本文在深入分析r t e m s 内核的基础上，将动态内存管理模块集成于内核之 中，并自行编写测试任务集对该模块进行功能及性能测试。测试结果不仅表明 本文工作的有效性，还为下一步工作指明了方向。 1 3 2 论文组织结构 本文其余章节鲶组织结构如下。 第二章分析性能参数与应用需求之间的关系，结合实时嵌入式操作系统应 用场景，提出内存管理模块设计要求。 第三章设计了基于实时嵌入式操作系统的动态内存管理模块。该模块包括 两个部分：动态内存请求管理，动态内存分配与回收算法。这两个子模块协同 7 第2 牵动态内存管理的设计要求 第2 章动态内存管理的设计要求 为满足应用需求，实时嵌入式系统在投入应用之前必须进行完备的测试。 测试结果是对系统性能的刻画，同样的系统采用不同的性能参数进行测试，对 性能的评价会大相径庭。性能参数的选择取决于应用需求，它是衡量系统性能 的标尺，也是系统性能优化的依据。 本章通过分析强实时系统的若干典型应用场景，指出了动态内存管理模块 的设计要求。章节内容组织安摊如下：2 ，l 节相关知识介缓；2 2 节阐述本论文 动态内存管理模块设计要求；2 3 节分析了目前流行的实时嵌入式操作系统中的 动态浅存分配算法；2 4 节总结本章态容。 2 。嚯相关知识介绍 2 。l 。l 实时系统中任务分类 实时嵌入式操作系统中的任务，可以根据是否周期运行分类，也可以根据 其关键程度分类【ll 】。 1 周期任务与非周期任务 在实时嵌入式搡 乍系统孛，许多任务是周期健( p e 遗o d i el a s k ) 运行麓。侧如， 在飞机飞行状况监测模块中，传感器每时每刻都在对飞机的速度、高度等信息 进行检测，状态监测模块中的周期任务每隔若干毫秒采集该数据并分孝斤处理。 由于周期性任务何时运行，运行时间持续多久是在设计阶段安排好的，因此， 在任务调度时，这些任务可采用静态调度策略进行调度。 同样，在实对嵌入式操作系统中，也有许多任务不是周期运行的，英运行 时刻具有是偶然性，这类任务被称作非周期任务( a p e r i o d i ct a s k ) 。例如，飞行员 在操作飞机转弯的过程中，与转弯相关豹诸多子任务被创建并调度运行，这些 子任务就是非周期任务。非周期任务何时运行、运行时间持续多久等问题在系 统设计阶段都是未知的，对这类任务，要采用动态调度策略进行调度。 2 关键任务与非关键任务 在实时嵌入式操作系统中，如果任务在截止时间内没有完成，则会引起一 系列的后果，搬据后果的严重性，有关键任务与非关键任务之分。例如救生、 飞行控制等任务都是关键任务，关键任务如果在截止时间内没有完成，会对系 统产生灾难性的后果。在实时系统中，通常采用冗余技术来提高系统的可靠健。 9 第2 章动态内存管理的设计要求 对某一关键任务，同时运行若干个该任务的副本，只要保证其中之一在截止时 间之前完成，系统就能保持正常运行。实时系统的任务调度，其目标之一就是 保证关键任务在其截止时间前完成。 非关键任务，顾名思义，其是否准时完成对系统的正常运行影响较小。实 时系统中，在非关键任务的运行截止时间前最大化系统吞吐量也是任务调度的 目标之一。 2 1 2 实时嵌入式系统性能评价实例 选择合适的性能参数，不仅能准确地评价实时嵌入式系统的性能，也为系 统性能优化提供了依据。性能参数，必须要反映系统性能的优劣，反映系统对 哪方面的要求最看重。本小节以【l l 】中的五个例子为主，分析实时系统中动态内 存管理模块的评价依据。 e x a m p l e1 考虑实时嵌入式系统a 与b ，a 与b 系统响应时间的概率密度函数如图2 1 所示。 三 磊 c 等 蚤 兽 名 d 厶 图2 - 1 系统a 与b 响应时间对比图 从图2 1 中可以看出，系统b 的平均响应时间比系统a 的小，但系统a 的 响应时间更容易预测( 落在某一范围的概率很大) 。如果以平均响应时间为性能 参数的话，b 优于a ；如果以运行时间的可预测性为性能参数的话，a 优于b ， 这是由其响应时间的概率密度函数决定。在分时系统中，平均响应时间至为重 要，因此b 更优，而若应用需求对系统的可预测性要求较高的时候，a 则更优。 因此，可以判断出，性能参数的选择并不是固定的，是应用需求决定的。 e x a m p i e2 ： 以终端系统中的打字员为例。打字员每敲击次键盘，将会在终端上回显 1 0 第2 章动态内存管理的设计要求 对应的字符，从敲击键盘到该字符回显的时间闯隔为t 。时间t 与打字员对该系 统性能评价之间的关系如图2 2 所示。 l l f f c 髓 d c g r a d e d 、叫、 u s e 妊 r e s p o n s et i m e 图2 2 从事字员角度看系统性能 从图中可数看出，当时闻大于1 2 时，每敲击一个字符就要延迟非常久的 时间，打字员认为该系统对他来说毫无任何意义( u s e l e s s ) ；直至系统管理员将系 统响应时间优化至t 2 以下时，打字员对系统性能的评价逐渐调高；当系统管理 员继续优化系统响应时间，使其接近t 1 时，打字员已经感觉不到字符回显的时 间延迟，他认为该系统是最优的( p e r f e c t ) ：此时，如果继续优化系统响应时间， 打字员已经意识不到系统性麓的提爵了。 从该例中打字员对系统性能的评价中，可以得出如下结论：应用需求不仅 决定了性能参数的选择，还决定了性能参数取值的有效范围。 e x a m p i e 3 ： 以便携设备为考虑对象。便携设备的功能相对较为简单，一般只有一个用 户，因此系统响应时间一般都能满足用户的需求，不适合作为衡量系统性能优 劣的参数。由于便携设备大多使用电池供电，并且不易补充新能源，当系统供 电不足时，即使系统其他性能指标非常优秀，也于事无补。因此对便携设备而 言，能耗、节能就成为衡量系统性能优劣的参数。 嚣x a m p l # 叠： 考虑系统c 与系统d ，基本配置信息如下。c 拥有一个阵列处理单元，该 单元畿够在碡个时钟周额内完成2 5 6 2 5 6 规模的矩阵乘法运算，d 裂无此矩阵 运算单元；除与矩阵运算相关的指令外，c 与d 其他的指令完全相同，指令运 行所需的时钟周期数相同；d 的时钟频率是c 的2 倍。 c 与d 各项指标相近，性能大致相同，在应用中会采用哪种设计方案取决 于应用的需求。例如，在与自然语言计算、气象预报等相关的应用中，由于涉 8写基-gkori 第2 章动态内存管理的没计要求 2 内存请求空闯大小未知 在实时嵌入式系统应用中，并不是所有内存请求的数据长度都是已知的。 针对内存请求空闻大小未知的情况，如果使用静态内存分配策略，则必须以程 序最坏运行情况分配存储空间，一方砸，宝贵的内存资源得到了浪费，另一方 面，如果最坏运行情况估计失误，烈会造成系统可靠性润题。动态志存分配的 灵活性体现在待分配的存储空间长度可以在程序运行时确定。因此，在这种情 况下，使用动态内存分配策略无疑是最佳选择。 3 内存资源受限 除了运行时确定所需内存空间大小外，动态内存分配的灵活性还体现在释 放不再使用的存储空闯，这个设计策略有利于提高内存资源的希9 用率。此外， 程序中局部变量被存储于栈( s t a c k ) 中，在系统初始化的时候设定，栈空间大小 是有限的。在资源受限的实时嵌入式搡作系统中，当局部变量数据长度过大时 会造成栈空间利用率下降，甚至栈越界导致系统非正常运行。动态内存所使用 的癌存位予堆( k a 西中，与栈相比，堆有更大的空闽供程序分配使用，同时灵活 性也更好。在实际应用中，通常使用动态内存分配策略来解决数据长度过大的 存储空间分配问题。 4 周期性数据采集 在飞行器等实时领域中，对飞行离度、外界温度、湿度、速度、燃油状况 等信息的采集都属于周糍性数据采集【l l 】。数据采集是嵌入式系统与外界通信的 桥梁。通过数据采集，嵌入式系统将传感到的模拟信号转化为数字信号进行分 析处理，据此系统能够不甑地调整鲁己的状态，在变化的环境中保证正常运行。 在这种周期性数据采集的应用中，首先，数据长度有可能是未知的；其次，数 据生命期可以跨越若干数据采集周期。因此在诸多未知因素的情况下，不适合 使用静态内存分配策略。 s 偶然事件处理 飞机转弯的过程中，与转弯相关的诸多子任务被创建并调度运行。这些子 任务的运行并非周期性的，也不是预先设定好的，是由偶然的转弯动作所引起 的，对这些子任务处理郎为偶然事件处理。在这些子任务中，有可能发出动态 内存申请，诸多偶然因素( 转弯弧度、倾斜度等) 导致了数据量的不确定性， 因此，不适合使用静态内存分配策略。 上述五类情况不足以代表动态内存分配所有的应用场景，然而却是应用背 景中与动态内存管理相关的典型应用场景【l l 】，分极这些应用场景对规范动态内 存管理模块的设计要求具有指导作用。 2 。2 2 设计要求 1 3 第2 章动态内存管理的发计要求 本小节根据应用场景提取若干影响动态内存管理模块性能的参数，并以最 优化这些参数作为动态内存管理模块的设计要求。 1 可预测性( 实时性) 周期任务及关键任务都有明确的截止时间，在截止时间内没有完成任务会 造成系统的非正常运行。动态内存分配之所以没有在实时嵌入式操作系统中得 到广泛应用，时间复杂度不能满足实时系统的实时约束是其中一个主要原因。 提高动态内存管理的可预测性主要是指降低算法的时间复杂度，保证算法 最坏情况下运行时间的有界性。这是分析任务调度性的基本要求。 2 高效性 高效性是指，动态内存分配算法要有效地利用内存资源，减少内存碎片。 内存碎片包括内部碎片和外部碎片。当分配给任务的内存块大小大于任务所请 求的大小时，会产生内部碎片；外部碎片是指，系统中存在大量长度很小的内 存块，但是却不能满足大部分的内存请求。在强实时领域中，动态内存资源往 往是有限的，尽可能地提高内存利用效率是动态内存管理不应回避的任务。 3 可满足性 可满足性对动态内存管理模块的要求如下：在内存资源充足的情况下，通 过降低内存碎片保证每次合理大小的内存请求都必须得到满足；在内存资源不 足的情况下，保证关键任务的动态内存请求得到满足。可满足性要求可以看作 是对高效性要求的进一步约束。一方面，减少内存碎片是提高可满足性的途径 之一，另一方面，在内存分配过程中，结合任务类型及内存资源现状，从全局 角度进行决策。 2 3 动态内存管理举例 本节针对典型的实时嵌入式操作系统( v x w r o r k s ，r 1 e m s ，e c o s ) ，介绍其动态 内存管理方式。 1 v x w o r k s v x w o r k s 操作系统是美国风河( w i n d r i v e r ) 公司于1 9 8 3 年设计开发的一 种实时嵌入式操作系统( i 盯o s ) 。它以良好的可靠性和卓越的实时性被广泛地 应用在通信、军事、航空、航天等实时性要求极高的领域中。v x w b r k s 的动态 内存管理包括动态内存的分配与释放，内存分配算法、内存回收算法【1 2 】。 早期的v x w o r k s 采用首次适应的匹配算法，空闲块以单链表的形式被组织 起来，如下图所示，r o o t 表示头结点，f r e e 表示空闲块。 1 4 第3 章动态内存管理研究 3 。1 概述 第3 章动态内存管理研究 第二章提出的动态内存管理模块设计要求如下： 八可预测性：最坏时间复杂度有界，平均时间复杂度为常数： b 高效性：降低内部碎片及外部碎片： e 可满足牲：内存充足时，保证每次合理大小的内存请求都能得到满足； 内存不足时，保证关键任务的内存请求得到满足。 在l 。2 2 节研究现状中对常用的动态内存分配算法进行了介绍，首次适应算 法、最佳适应算法、伙伴算法都不能满足上述要求。t l s f 算法虽然实时性能优 秀，但高效性及可满足性均均有进一步优化的余地。为了更好地满足该要求， 本论文在操作系统中引入动态内存请求管理，它与动态内存分配及回收算法共 同构成动态内存管理，如图3 1 所示。 动态内存 滑求序列 内存释放请求刊内存释放算法卜_ l 侧 l j ，： 叫 动悫滤存管理 。一一，- 一一一一一一一一4 | 痰孬 ! 。，j 图3 。1 动态内存管理模块框图 本章中，3 2 节详细介绍动态内存请求管理设计细节，3 3 节介绍动态内存 分配及回收算法设计细节，3 4 节总结本章内容。 3 。2 动态内存请求管理 动态内存请求管理( m e m o r yr e q u i r e m e n tm a n a g e m e n t ，本文简称m r m ) 的结 构如图3 2 所示，与【4 】不同之处在于将任务信息弓| 入决策过程，当预罄内存充 足时，它将内存请求发送给动态内存分配模块( 图中所示) ，由该模块保证合 理大小的内存请求都能得到满足：当预鼷内存不足时，满足关键任务的额外内 存请求( 图中所示) ，而拒绝非关键任务的额外内存请求( 图中所示) 。 1 7 第3 章动态内存管理研究 动态内存 请求序列 r j 动态内存请求管理 图3 2 动态内存请求管理结构图 本节首先介绍动态内存请求管理的约柬条件与任务模型，之后介绍若干仲 裁规则，最后介绍模块工作流程。 3 2 1 约束条件与任务模型 1 约束条件 为了突出重点，本节所讨论的动态内存请求管理需要以下约束条件。 约束1 ：本文所研究的实时任务包括周期任务与非周期任务，关键任务与非 关键任务； 约束2 ：所有任务都能满足其截止时间，是c p u 可调度的； 约束3 ：内存空间大小是指物理内存空间的容量，以字节为单位：内存量包 含两部分信息，内存空间大小及其生存期：生存期以相应任务周期为单位： 约束4 ：在周期任务的单个周期运行中，如果存在不同内存空间的申请与释 放，那么约定释放动作在时间顺序上先于申请动作； 约束5 ：周期任务在每个周期的运行中都会动态申请一定的内存量，同一内 存空间的申请与释放可以由不同的任务来完成； 约束6 ：非周期任务在其运行过程中，可以通过多次的内存请求获得存储空 间，该存储空间将一直存在直至被释放； 约束7 ：实时嵌入式操作系统在初始化时，根据任务参数预留一定大小的内 存供其动态内存申请。在实际运行中，当任务所需内存大小超出预留的内存大 小时，可以提出额外内存空间申请； 约束8 ：在提出内存请求时，周期任务需要声明以下信息：每周期所需最大 内存空间大小及该空间的最长生存期( 以任务周期数为单位) ；非周期任务则仅 需提供最大内存空间大小。 2 任务模型 本节所讨论的任务模型参考文献 4 】中的任务模型，仅包括与动态内存管理 相关的信息，是操作系统实现中任务模型的一部分。 定义1 ：为满足所有任务的动态内存请求，所需总的内存大小为， m r ：m + 膨”+ 肘出其中砰代表任务所需内存空间大小；m ”代表内存碎片大 1 r 第3 章动态内存管理研究 小；m 。代表动态内存管理模块数据结构等空间开销。 定义2 ：f t l ，百。) 是周期任务集合。周期任务马可由最坏运行时间、周期、 相对截止时间1 ( r e j a t i v ed e a d l i n e ) 及预留内存量来表示，即( c i ，t i ，d i ，m j ) ，其中 c i 为最坏运行时间，t i 为周期，d i 为相对截止时间，m i 表示系统为q 预留的内 存量，1 n 。 定义3 ：g i m a x 为任务在单个周期所申请的最大内存大小；h ，为相应内存 空间的最长生存期。m i 可表示为二元组( g “，h “) 。在任务运行中，单个周 期内申请的存储空间小于等于g ? “，该存储空间最迟在h r 个任务周期被释放， g “和h i n “分别是上限值。因此根据上述模型，可以计算出任务q 在其生存期 内所占有的尚未释放的最大内存空间大小，值为g ：i l 娜h ：t l “。 图3 2 描述了周期任务五运行中所占有的尚未释放的内存空间大小变化图， 其中t 产1 0 ，h l n “= 4 。毛运行的前4 个周期中，尚未释放的内存大小呈递增状态， 但不会超过4 宰g ，双；从第4 个周期开始，内存空间大小开始发生波动。这是因 为从第4 个周期开始，t 逐渐释放前4 个周期所申请的内存空间。当释放的内 存空间大小大于新申请的内存空间大小时，所占有的内存空间减少；当释放的 内存量小于新申请的内存量时，所占有的内存空i 刨增加。例如，t = 4 0 时新申请 的内存大小为9 0 球g ，“，而此时释放的内存大小为8 0 木g ：i l 觚，因此任务占有 的内存变化量 图3 - 3 周期任务t 占有内存量示例【4 】 定义4 ：非周期任务可由起始时间2 ( r e l e a s et i m e ) 、最坏运行时间以及预留内 存量来表示，即( r ，c ，m ) 。其中r 为起始时间，c 为最坏运行时间，m 为预留内 存量。m 可以用二元组( g ，d ) 来表示，其中g 为任务内存空间请求大小上限，d 代表该内存空间的生存期。 定义5 ：截止t 时刻，系统分配出去的动态内存空间大小为m u ( f ) ， 1 t h er e i a t i v ed e a d l i n eo fat a l s ki st t l ea b s o l u t ed e a d l i n em i n u st h er e i e a s et i m e 2t h e r e l e a s et i m eo fat a s ki st h et i m ea tw h i c ha i lt h ed a t at h a ta r er e q u j r e dt ob e 百ne x e c u t i n gt h et a s ka r e a v a j i a b i e 1 9 第3 章动态内存管理研究 m ( f ) = 孵( ，) ，其中n 为任务数，孵( f ) 为任务q 截止t 时刻所占有的尚未 f = l 释放的内存空间大小，辨( f ) 岬戤。 定义6 ：截止t 时刻，系统中尚未分配的可供任务请求的内存空间大小为 m f o ) ，m f ( f ) = m r m u ( f ) ；任务q 的内存利用率为( 班( f ) = 譬， 记儿呼x 瞧啪，) 心渤。 定义7 ：周期任务t i 发出的额外内存请求可表示为拟= ( g f ，三) ，其中g ， 为额外内存空间大小，l 为存储空间的生存期；非周期任务a 也可以发出额外 内存请求，表示为刖m = ( g ，x ) ，其中g 表示额外内存空间大小，对软实时任务 x 表示任务的响应时间r ( r e s p o n s et i m e ) ，对硬实时任务x 表示任务的相对截止 时间d 。 定义8 ：m 凡( ，：) 为所有任务在【t l ，t 2 】时间段内所需内存大小。若以4 ( ，乞) 代表【t l ，t 2 】之间新申请的内存大小，以e ( f 1 ，乞) 代表【t l t 2 】之间释放的内存大小， 那么肘n ( ，乞) = ( 4 ( f l ，乞) 一只( ，乞) ) 。若在这段时间内新申请的内存大小大于 释放的内存大小，m 足( ，f 2 ) 为正值；新申请的内存大小等于释放的内存大小， 肘r ( f l ，乞) 为0 ；否则，为负值。 3 2 2 仲裁规则 1 规则 规则1 ：任务毛( n 为任务数，1 f 刀) 在t 时刻发出请求，希望得到大小 为m 的内存空间，若同时满足以下条件，则动态内存请求管理模块通过该请求， 将其发送给动态内存分配与回收模块。 a ：m u ( r ) + 朋s m ； 2 0 b ：u y + 嘉弛 若仅满足条件a ，则将此内存请求发送至额外内存