（计算机软件与理论专业论文）基于dnaga的最早截止期限优先调度算法优化.pdf

太原理丁大学硕士研究生学位论文 基于d n a g a 的最早截止期限优先调度算法优化 摘要 实时调度算法是嵌入式实时系统设计和实现的关键问题之一，也是保 障实时系统两个必备特性( 时限性和可靠性) 的重要方法，是实时系统中重要 而活跃的研究领域。 在众多的实时调度算法中，速率单调( r a t e m o n o t o n i c ，r m ) 和最早截止 期限优先( e a r l i e s td e a d l i n ef i r s t ，e d f ) 分别是静态调度和动态调度领域中经 典的调度算法。r m 算法属于静态调度算法，在系统运行前决定任务的调度， 实现简单，在满足前提条件的情况下可以保证实时任务集的成功调度。e d f 算法属于动态调度算法，在系统运行时决定任务的调度，c p u 利用率可以 达到1 0 0 ( 理想情况下) 。虽然r m 和e d f 算法以其各自所具备的优良性 能在嵌入式实时系统中得到了广泛应用，但是我们也不能忽视它们本身存 在的实时性问题。 本文是在考虑“任务调度开销时间”的情况下，通过优化e d f 调度算 法中各个任务的启动时间来提高e d f 调度算法的实时性能的。 首先介绍实时调度算法的应用背景：实时系统、嵌入式系统、实时操作 系统和嵌入式实时操作系统。 接着对现有的实时调度模型、实时调度基本理论、调度策略和实时调度 算法进行了分析和研究。对r m 和e d f 实时调度算法进行了详细分析，并 举例说明了它们的调度过程。 然后介绍了本文用到的优化算法一d n a 遗传算法( d e o x y r i b o n u c l e i c a c i dg e n e t i ca l g o r i t h m ，d n a g a ) ，及其基本理论和操作方法，并说明了 d n a ( d e o x y r i b o n u c l e i ca c i d ) 算法的生物学基础和遗传算法的基本理论。 最后，通过使用d n a g a 对e d f 调度算法中各个任务的启动时间进行 离线优化，离线计算各实时任务的启动时间，运用这些优化的启动时间作 太原理。r 大学硕十研究生学位论文 为在线实时系统使用e d f 调度算法的参数进行实时任务调度，以此来提高 实时系统的实时性能。本文模拟了基于d n a g a 的最早截止期限优先调度 算法的优化调度，并比较了优化前后因抢占引起的调度开销。实验结果表 明：使用d n a 遗传算法可以对实时任务的启动时间进行优化，可以减少实 时任务因抢占引起的调度开销。说明了使用d n a 遗传算法对e d f 调度算 法进行优化的可行性和有效性。该结论对实时调度算法的研究和使用有一 定的理论和实践意义。 本文的创新之处在于使用d n a 遗传算法对e d f 调度算法中各个任务的 启动时间进行优化，实现了d n a 遗传算法在嵌入式实时调度算法领域的运 用。 关键词；嵌入式实时系统，实时调度，e d f 调度算法，d n a 遗传算法 i i 太原理工大学硕士研究生学位论文 o p t i m i z a t i o no fe a r l i e s td e a d l i n ef i r s t s c h e d u l i n ga l g o r i t h mb a s e d0 nd n a g a a b s t r a c t r e a l - t i m es c h e d u l i n ga l g o r i t h mi so n eo fk e yp r o b l e m sf o rt h ed e s i g na n d r e a l i z a t i o no fe m b e d d e dr e a l - t i m es y s t e m i ti sa l s oa l li m p o r t a n tm e t h o dt h a t e n s u r e st i m er e s t r i c t i o na n dr e l i a b i l i t yo fr e a l - t i m es y s t e m r e a l t i m es c h e d u l i n g i sa ni m p o r t a n ta n da c t i v er e s e a r c hf i e l d a m o n gt h es c h e d u l i n ga l g o r i t h m s ，r m ( r a t em o n o t o n i c ) a n de d f ( e a r l i e s t d e a d l i n ef i r s t ) a r et w ok i n d so fc l a s s i c a ls c h e d u l i n ga l g o r i t h m s r mi sag o o d a l g o r i t h mi nt h ef i e l do fs t a t i cs c h e d u l i n g r md e c i d e dt a s ks c h e d u l i n go r d e r b e f o r es y s t e mr u n n i n g ，a n di ti se a s yt oc a r r yo u t i fp r e c o n d i t i o n sa r em e t ，r m c a ns c h e d u l er e a l t i m et a s ks e t ss u c c e s s f u l l y e d fi sag o o da l g o r i t h mi nt h e f i e l do fd y n a m i cs c h e d u l i n g e d fd e c i d e dt a s ks c h e d u l i n go r d e rd u r i n gs y s t e m r u n n i n g t h ec p uu t i l i z a t i o no fe d fs c h e d u l i n ga l g o r i t h mc a nb e10 0 i n p e r f e c tc o n d i t i o n a l t h o u g hr i v la n de d fh a v em a n ye x c e l l e n tp e r f o r m a n c e s a n da r eu s e dv e r yb r o a d l yi ne m b e d d e dr e a l t i m es y s t e m ，w ec a l ln o ti g n o r et h e i r s h o r t c o m i n g sf o rr e a l t i m ep e r f o r m a n c e c o n s i d e r i n gs c h e d u l i n gs p e n d i n g ，r e a l - t i m ep e r f o r m a n c eo fe d fs c h e d u l i n g a l g o r i t h mw a si m p r o v e db yo p t i m i z i n gr e l e a s et i m eo f t a s k si nt h i st h e s i s f i r s t l y , t h eb a c k g r o u n d ( r e a l t i m es y s t e m ，e m b e d d e ds y s t e m ，r e a l - t i m e o p e r a t i n gs y s t e ma n de m b e d d e dr e a l t i m eo p e r a t i n gs y s t e m ) o fr e a l t i m e s c h e d u l i n ga l g o r i t h m sw e r ei n t r o d u c e d s e c o n d l y , r e a l t i m es c h e d u l i n gm o d e l s ，r e a l t i m es c h e d u l i n gb a s i ct h e o r y , r e a l - t i m e s c h e d u l i n gs t r a t e g i e s a n dr e a l - t i m e s c h e d u l i n ga l g o r i t h m sw e r e i i i 太原理一 大学硕士研究生学位论文 a n a l y z e d r ma n de d fw e r er e s e a r c h e di nd e t a i l s s o m ee x a m p l e sw e r eu s e dt o e x p l a i nt h es c h e d u l i n gp r o c e s so fr ma n de d f t h i r d l y , t h et h e o r yo fd n a g a ( d e o x y r i b o n u c l e i ca c i dg e n e t i ca l g o r i t h m ) w a si n t r o d u c e d a n d ，t h eb i o l o g yf o u n d a t i o no fd n a a l g o r i t h ma n dt h et h e o r y o f g e n e t i ca i g o r i t h mw e r ei l l u s t r a t e d f i n a l l y , t h er e l e a s et i m eo ft a s k sb ye d fs c h e d u l i n gw a so p t i m i z e do f f - l i n e b a s e do nd n a - g a a n dt h e n ，t h eo p t i m i z e dr e l e a s et i m ew a su s e df o r s c h e d u l i n gr e a lt i m et a s ks e t s t h eo p t i m i z e ds c h e d u l i n gp r o c e s so fe d f s c h e d u l i n ga l g o r i t h mb a s e do nd n a g aw a ss i m u l a t e db ys o f t w a r ei nt h i s t h e s i s c o m p a r e dw i t ht h es c h e d u l i n gs p e n d i n gf o rp r e e m p t i o nb e f o r eo p t i m i z e d b ys i m u l a t i n ge x p e r i m e n t ，t h es c h e d u l i n gs p e n d i n gf o rp r e e m p t i o na f t e r o p t i m i z e dw a sr e d u c e d t h ee x p e r i m e n tr e s u l t ss h o wt h a tt h er e l e a s et i m ec a nb e o p t i m i z i n gb yd n a g a i ts h o w e dt h ef e a s i b i l i t ya n dv a l i d i t yo fm e t h o dt h a t o p t i m i z er e l e a s et i m eb yd n a g a t h ec o n c l u s i o n so ft h i st h e s i s c a nb e r e f e r e n c ef o rt h e o r ya n da p p l i c a t i o no f r e a l - t i m es c h e d u l i n g a l g o r i t h m t h ei n n o v a t i n go ft h i st h e s i si st h a to p t i m i z et h er e l e a s et i m eb yd n a - g a t h i st h e s i sa c h i e v e dt h ec o m b i n a t i o no ft h ed n a g aa n de m b e d d e dr e a lt i m e s c h e d u l i n ga l g o r i t h m k e yw o r d s ：e m b e d d e dr e a l - t i m e s y s t e m ，r e a l - t i m es c h e d u l i n g ，e d f s c h e d u l i n ga l g o r i t h m ，d n a g a 声明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外。本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 论文作者签名： 塑1 3 亟 日期： 趔z ! ! 虚 关于学位论文使用权的说明 本人完全了解太原理工大学有关保管、使用学位论文的规定，其 中包括：学校有权保管、并向有关部门送交学位论文的原件与复印 件；学校可以采用影印、缩印或其它复制手段复制并保存学位论文； 学校可允许学位论文被查阅或借阅；学校可以学术交流为目的。 复制赠送和交换学位论文；学校可以公布学位论文的全部或部分内 容( 保密学位论文在解密后遵守此规定) o 喜 签名： 茎! j 塑日期：趔z ：! 应 导师签名： 日期：赴1 2 ：兰三 ， 太原理工大学硕士研究生学位论文 1 1 选题背景 第一章绪论 实时性( r e a l t i m e ) 是指系统能够在给定的限定时间内完成任务并对外部事件做出及 时响应。限定时间的范围因实时应用要求的不同而有较大的变化，可以从微秒级到分钟 级。实时与快速是有区别的，实时要求快速，但实时不等于快速，快速是无时间限制的， 是从事件发生到系统响应之间的时间越短越快越好。虽然实时也给人们快速的感觉，并 r 且它也要求系统在一定程度上能快速响应。但是，实时是有时间余量和时间期限的。 实时任务( r e a l t i m et a s k ) 是指在时间期限内启动，在规定时间内完成的任务。实时系 统与非实时系统的本质区别就在于实时系统中的任务都有时间限制，实时任务必须在其 截止时间内开始和完成。截止时间可以划分为开始截止时间和完成截止时间两种。开始 截止时间要求任务在某个时间内必须开始执行；完成截止则要求任务在某个时间内必须 完成。 实时系统( r e a l t i m es y s t e m s ) 是指计算的正确性不仅取决于程序的逻辑正确性，也取 决于计算结果产生的时间口1 。如果系统的时间约束条件得不到满足，将会导致系统出错。 实时调度( r e a l t i m es c h e d u l i n g ) 是指在有限的系统资源下，为一系列任务决定何时以 及在哪个处理器上运行，并分配任务运行所需要的资源，以保证其时间和资源得到满足。 调度的实质是资源的分配，包括给任务分配相应的资源和时间从而保证任务的实时性要 求。 实时调度算法( r e a l t i m es c h e d u l i n ga l g o r i t h m ) 的研究起源于l i u 和l a y l a n d 在1 9 7 3 年 提出的r m 与e d f 调度算法【2 1 。他们对这两个算法的可调度性判定条件和调度特性进行 了详细的研究，但在讨论这两个算法时，他们提出了几个前提假设，分别为 3 1 ： ( 1 ) 所有的任务请求都是周期性的，具有硬时限要求，即必须在限定的时限内完成； ( 2 ) 任务的时限要求仅限于一个任务必须在该任务的下一个请求发生之前完成； ( 3 ) 任务之间都是独立的，每个任务的请求不依赖于其他任务请求的开始或完成； ( 4 ) 每个任务的运行时间是不变的，这里任务的运行时间是指处理器在无中断情况下 用于处理该任务的时间： ( 5 ) 调度和任务切换的时间忽略不计； ( 6 ) 任务之间是可抢占的； 太原理工大学硕士研究生学位论文 ( 7 ) 所有任务的分配都在单处理器上进行； 这些假设条件一方面方便了问题的讨论和模型的建立，但另一方面也限制了整个理 论系统的实用性。后来，研究者们对这些限定条件提出了挑战，产生了很多杰出的成果。 在研究中，比较普遍的方法是：在其它假设条件成立前提下，先让某一个假设不成立， 进行调度模型的建立和调度算法的理论研究。本论文就是在其它假设条件成立的前提 下，假设条件( 5 ) 不成立，对e d f 调度算法进行研究。 1 2 实时调度研究现状 随着信息技术，计算机技术和移动技术的发展，世界迎来了一个新的时代，那就是 以嵌入式系统为核心的“后p c 时代”。伴随着电子技术的不断发展和数字信号处理与 人机交互界面等相关技术的不断成熟和完善，嵌入式系统己经有了较好的发展。嵌入式 系统有着无比广阔的市场需求和发展前景。一般来说，嵌入式系统是硬件与软件的结合， 将特定的软件固化在一定的硬件环境上的实用系统。嵌入式软件与嵌入式硬件共同构成 了嵌入式系统。 嵌入式系统通常都具有特定的功能。当我们使用电器，使用手机时，我们都会接触 到一些不同功能的嵌入式系统。绝大多数的嵌入式系统，都具有实时性能的要求，我们 就把这样的系统称为嵌入式实时系统( e m b e d d e dr e a l - t i m es y s t e m ) 。同样，一个实时系统 也有可能在资源上受到限制，从而具有嵌入式特性。 随着实时系统应用范围的不断扩大，系统复杂性不断提高，以及应用背景的不同， 对实时调度理论提出了许多新的要求： ( 1 ) 超负荷运行调度 实践中，有的实时系统不能保证足够的时间来处理所有的任务，无法保证所有的任 务在时间约束内完成，即出现超负荷运行的情况，此时如何处理和调度任务就非常重要。 在任务调度的研究领域，很多是针对系统超负荷的情况进行研究的。 ( 2 ) 多处理器调度、 多处理器系统是指整个系统内包含有多个处理器单元，各处理器可以同时并发工 作。在多任务单处理器系统中，多个任务在宏观上是并发的，但在微观上是顺序执行的。 在多处理器系统中，多个任务可以分别在不同的处理器上执行，宏观上和微观上都是并 发的。按照多处理器的结构，多处理器系统可以分为紧耦合系统和松耦合系统两种。紧 耦合系统是多个处理器通过共享内存空间来交换信息的系统，而松耦合系统是多个处理 2 太原理工大学硕七研究生学位论文 器通过通信链路来链接和交换信息的系统。 现在的普通p c 机也逐步跨进了双核时代。随着实时应用的日趋复杂，多处理器系 统因其高性能和可靠性，逐渐成为处理复杂应用的有效方法。多处理器实时系统的调度 算法是一个重要的研究课题。 ( 3 ) 实时任务的混合调度 基于前提：系统中存在硬实时的周期任务，且它们的c p u 利用率小于l ，同时存在 软实时的非周期任务。调度目标是在保证硬实时周期任务截止期的前提下，尽可能的提 高软实时的非周期任务的响应速度。当两种类别不同的任务放在一起进行调度时，必须 优先让硬实时周期任务得到响应，保证其满足截止期限，从而保证系统的可靠性。 一般有下面几种典型的混合调度方法【4 】 5 6 1 1 7 ： 基于调度服务器模型的软实时任务调度算法。此算法是为了缩短硬实时周期任务 和软实时非周期任务混合调度中软实时非周期任务的响应时间以及防止软实时非周期 任务错过其截止期限而提出的调度算法。通常有：后台执行法、资源保留法和挪用法三 种基于服务器模型的任务调度算法。 软实时任务灵活调度模型及算法。灵活调度是软实时调度发展的一个趋势。灵活 调度不需要我们事先确定任务的最坏截止时间和预留系统资源数量，不需要对实时任务 的类型加以区分。在灵活调度模型中，实时系统被当作一个控制系统，任务通常被看作 各种采样信号，其目的是通过反馈控制维持实时系统负载的稳定性和系统资源的高利用 率。 弱硬实时模型及调度算法。弱硬实时能够准确而科学地对软实时任务的实时特性 进行界定和分类，使研究者可以方便地对不同的软实时任务进行定量分析。在弱硬实时 系统中，实时任务可以错过截止期限，但任务错过的截止期限必须可预知且被限制在一 定的范围内。 虽然此后对实时调度算法的分析和研究又进行了多方面的扩展，如有资源共享的周 期任务、有非周期任务运行的情况、在分布式实时系统下的调度算法等等。不过，这些 扩展都是以r m 或e d f 为基础，r m 和e d f 调度算法在实时调度领域中占有重要地位。 对经典的r a m 和e d f 算法的研究一直都是理论研究喁1 1 9 1 1 1 0 1 的一个重点。 1 3 论文的组织结构 本文总体上是通过使用d n a 遗传算法对实时系统中一个较通用的动态优先级调度 算法一e d f 调度算法的启动时间进行离线优化，离线计算各实时任务的启动时间，运用 3 太原理工大学硕十研究生学位论文 这些启动时间作为在线实时系统使用e d f 算法的参数进行实时任务调度，来提高实时 系统的实时性能。最后用模拟的方法比较了优化前和优化后的系统调度时间开销，从模 拟实验结果看出，通过使用d n a 遗传算法( d n a 遗传算法主要是指以d n a 编码的遗 传算法，在第四章进行了详细介绍) 可以对实时任务的启动时间进行优化，可以减小调 度过程中抢占引起的调度开销，从而提高嵌入式实时系统的实时性能。 进一步，本论文共分为六章。第一章介绍本论文的选题背景，实时调度现状等内容， 主要是对论文的概况介绍。第二章详细说明实时系统以及嵌入式实时操作系统。对嵌入 式系统和实时操作系统等内容作了阐述。该章主要是对本论文应用背景的分析和研究。 第三章对本论文的主要操作对象一实时调度作了详尽的分析和研究。介绍了现有的实时 调度理论、策略和算法，通过实例对r m 和e d f 调度算法进行了分析和说明。第四章 对本论文要用到的优化算法一d n a 遗传算法进行了分析。分别介绍了遗传算法和d n a 计算，最后对d n a 遗传算法进行了说明和分析。第五章对优化的具体方法、内容和过 程进行了详细分析和研究。通过模拟实验说明使用该方法进行优化的可行性和有效性， 改善了抢占式最早截止期限优先( e d f ) 算法的实时调度性能。该结论可以为实时调度 算法的研究和使用提供一定的参考。若应用于实践，可以提高嵌入式实时系统的实时性 能。 4 太原理工大学硕士研究生学位论文 第二章实时系统 2 1 实时系统的特性及其分类 实时系统( r e a l - t i m es y s t e m ) 是具有实时性的计算机系统，是计算机的应用与科学计 算在控制领域应用两者相结合的结果。实时系统与非实时系统之间最大的区别就是要满 足处理与时间的关系。实时系统最重要的能力要求就是必须满足在一个事先设定好的时 间限制内对外部和内部的事件进行响应和处理的能力。 2 1 1 实时系统特性 实时系统一般应具备以下几个重要的特性： ( 1 ) 实时性 实时系统结果产生的时间有着严格的要求，只有符合时间要求的结果才是正确的。 任务必须在其截止期限内完成，以保证系统所产生的结果在时间上的正确性。 ( 2 ) 可靠性 可靠性主要包含两个方面的含义：一方面指系统的正确性，即系统本身要连续稳定 运行，系统所产生的结果在返回值和运行时都是正确的；另一方面指系统的健壮性，即， 如果系统出现了错误或外部环境与预先假定的外部环境不符合，系统检查出故障后要有 一定的补救措施及故障排除功能，系统仍然可以处于可预测状态，仍可以安全地带错运 行。 ( 3 ) 并行性 一般来说，实时系统通常有多个外部输入端口。因此，这就要求系统具有一定的并 行处理能力，以便能同时响应来自不同端口的输入信号。 ( 4 ) 可预测性 实时系统的任务必须在一定的限度内开始或截止，而这个限度是根据系统需要定义 的。这意味着系统对来自外部输入的反映必须全部是可预测的，即使在最坏的条件下， 系统也要严格满足截止期限。 5 太原理工大学硕士研究生学位论文 2 1 2 实时系统分类 根据实时任务侧重点不同可将实时系统进行多种分类。如，按系统的可扩展性可分 为专用系统和开放系统；按系统的集中性可分为集中式系统和分布式系统。下面是两种 常用的分类方法： 根据任务的作业到达时刻规律的不同，可分为周期性和非周期性。对于周期任务， 其相邻两次作业到达时刻之间的间隔是一个固定的数值，即周期。非周期任务的作业到 达时刻则没有规律。随着实时理论的发展，人们又将非周期任务进行了细化，分为一般 非周期任务和零星任务【“1 。零星任务是非周期任务的极端情况，其出现的规律更加难以 预测。由于周期任务的到来比较规律，所以在实时系统中，周期任务的执行比较容易保 障。而一般非周期任务和零星任务则由于发生不规律，通常不容易保障。 按对截止期限的要求程度可分为硬实时( h a r dr e a l t i m e ) 和软实时( s o nr e a l t i m e ) 。硬 实时要求可确定性强，具有明确的时间约束，对系统有很高的实时要求，对操作系统有 严格的实时限制，系统必须及时的对事件做出反应，绝对不能发生错过截止期限的情况。 如果在某个限定时刻之前不能完成任务则导致整个实时应用的失败。软实时也对时间敏 感，而且要求其基本上满足实时性要求。软实时允许系统在重负载的情况下发生错过截 止期限的情况，一般不会造成大的危害，不至于影响全局。硬实时系统和软实时系统在 选择实时调度算法上有较大区别。基于优先级调度的算法可以满足软实时系统的实时需 求，而且可以提供高速的响应和较大的系统吞吐率。而对硬实时系统来说，需要使用的 算法就应该是调度方式简单，反应速度快的调度算法。 在现实世界中，硬实时应用和软实时应用都大量存在，并可能在同一个系统中共存。 而且，随着实时应用的发展，实时概念也在不断地发展变化。传统意义上的软实时任务 概念不能够准确地描述一些新出现的软实时系统，从而进一步根据响应时间将实时系统 分为了三种类型： ( 1 ) 弱实时系统 弱实时系统是使各个任务运行的越快越好，没有严格限定某一任务必须在多长时间 内完成。弱实时系统更多地关注软件运行的结果正确与否及安全性能等其他方面，而对 任务执行时间的要求相对较宽松。一般它的响应时间可以是数十秒或更长，并可能随着 系统负载的轻重而有所变化。 ( 2 ) 一般实时系统 一般实时系统是弱实时系统和强实时系统的折衷。在错过截止期限后，其计算结果 6 太原理工大学硕+ 研究生学位论文 的价值是降低而不是变为0 。它的响应时间可以在秒的数量级上。如p d a 、手机等就属 于一般实时系统。 ( 3 ) 强实时系统。 在强实时系统中，各个任务不仅要保证执行过程和结果的正确，同时还要保证在系 统能够允许的时间内完成任务。错过截止期限后，任务计算结果的价值变为0 。它的响 应时间在毫秒或者微秒的数量级上。这对于安全和军事领域的软硬件系统来说是至关重 要的。 2 2 嵌入式系统 嵌入式系统( e m b e d d e ds y s t e m ) 是指以应用为中心、以计算机技术为基础、软硬件可 剪裁、适应应用系统对功能、可靠性、成本、体积和功耗严格要求的专用计算机系统。 可以说，嵌入式系统就是应用软件和系统硬件的一体化，它集成了计算机技术、半导体 微电子技术、数据传输技术、传感器技术，体现了当代最新技术的发展。硬件部分通常 由嵌入式处理器、内存、i o 端口及一些与应用密切相关的控制和电子、机械系统组成。 软件部分通常由嵌入式操作系统和应用软件组成，高端的应用可能还会使用到图形平 台。 嵌入式处理器是硬件的核心内容，有4 位、8 位、1 6 位、3 2 位、6 4 位的微处理器 可供选择。通常从功能和应用方向可将嵌入式处理器分为以下几种： ( 1 ) 嵌入式微处理器。嵌入式微处理器目前主要有a m l 8 6 8 8 ，3 8 6 e x ，s c - 4 0 0 ，p o w e r p c ，6 8 0 0 0 ，m i p s ，a r m s t r o n ga r m 系列等。 ( 2 ) 嵌入式微控制器。其典型代表是在控制系统中广泛应用的单片机，即将整个计算 机系统集成到一块芯片中。最有代表性的通用系列有8 0 5 1 ，m c s 9 6 系列以及m c 6 8 h 系 列等。 ( 3 ) 嵌入式d s p 处理器( e m b e d d e dd i g i t a ls i g n a lp r o c e s s o ge d s p ) 。此种处理器是专 门为信号处理设计的，其在系统结构和指令算法方面都进行了特殊设计。目前主要的嵌 入式d s p 处理器主要有t i 公司的t m s 3 2 0 c2 0 0 0 c 5 0 0 0 系列，i n t e l 的m c s 2 9 6 和 s i e m e n s 的t r i c o r e 等。 嵌入式系统在硬件上受到很多限制，使得软件同普通软件有所不同，而这些硬件和 软件的不同区分了嵌入式系统的不同发展阶段。嵌入式系统的发展，大致经历了以下四 个阶段： 7 太原理工大学硕士研究生学位论文 第一阶段是以单芯片为核心的可编程控制器形式的嵌入式系统。这种系统大部分应 用于专业性极强的工业控制系统中，一般没有操作系统的支持。此阶段系统的主要特点 是：系统结构和功能相对单一，处理效率较低，存储容量较小，几乎没有用户接口。 第二阶段是以嵌入式c p u 为基础、以专用简单操作系统为核心的嵌入式系统。这一 阶段系统的主要特点是：c p u 种类较多，通用性较弱；系统开销小，效率高；操作系统 具有一定的兼容性和扩展性；应用软件较专业，用户界面不够友好；系统主要用来控制 系统负载以及监控应用程序运行。 第三阶段是以嵌入式操作系统为标志的嵌入式系统。这一阶段系统的主要特点是： 嵌入式操作系统能运行于各种不同类型的微处理器上，兼容性好；操作系统内核精小、 效率高，并且具有高度的模块化和扩展性；具备文件和目录管理、设备支持、多任务网 络支持、图形窗口以及用户界面等功能；具有大量的应用程序接口，开发应用程序简单， 嵌入式应用软件丰富。 第四阶段是以基于i n t e r n e t 为标志的嵌入式系统，这是一个正在迅速发展的阶段。 目前大多数嵌入式系统还孤立于i n t e m e t 之外，但随着i n t e m e t 的发展以及i n t e m e t 技术 与信息家电、工业控制技术等结合日益密切，嵌入式设备与i n t e m e t 的结合将代表着嵌 入式技术的真正未来。 在实际应用中，人们常常并不对实时系统、嵌入式系统，以及嵌入式实时系统三者 进行明确的区分。嵌入式系统强调系统的资源受限方面，实时系统更多的是强调系统的 实时性方面。 下图简单表示了三者之间的关系： 宾时系统 嵌入式系统 图2 - i 实时系统，嵌入式系统与嵌入式实时系统 f i g u r e2 - 1r e a l - t i m es y s t e m ，e m b e d d e ds y s t e ma n de m b e d d e dr e a l t i m es y s t e m 8 太原理工大学硕士研究生学位论文 2 3 实时操作系统 2 3 1 实时操作系统及其一般特征 实时操作系统( r e a lt i m eo p e r a t i n gs y s t e m ，r t o s ) 是指使计算机能及时响应外部事件 的请求，在规定的时间内完成对事件的处理，并控制所有实时设备和实时任务协调一致 地工作的操作系统。实时操作系统是实时系统的核心，是能够保证实时系统中实时任务 处理响应时间要求的操作系统。实时操作系统表现为实时系统在启动之后运行的一段背 景程序，应用程序是运行在这个基础之上的任务。r t o s 的首要任务是调度一切可利用 的资源完成实时任务，其次是提高计算机系统的使用效率，其重要的特点是满足对时间 的限制和要求。r t o s 根据各个任务的要求，进行资源管理、消息管理、任务调度、异 常处理等工作，使各实时任务在适当的时间获得其所需的资源，从而满足其相应的时限 要求。 实时操作系统在体系结构上大致分为两类：事件触发结构( e v e n t - t r i g g e r e d ) 和时间触 发结构( t i m e - t r i g g e r e d ) 。在基于事件触发结构的实时操作系统中，系统的任何行为都来 源于其对一定事件的响应；而在基于时间触发结构的实时操作系统中，系统的任何行为 都来源于其对系统同步时钟的响应。 实时操作系统一般包括以下特征： ( 1 ) 异步事件响 立：异步事件是指无一定时序关系随机发生的事件； ( 2 ) 切换时间和中断延迟时间确定； ( 3 ) 抢占式调度：为确保响应时间，实时操作系统必须允许高优先级的任务可以抢占 低优先级任务的执行： ( 4 ) 优先级中断和调度：必须允许用户定义中断优先级和被调度任务的优先级； ( 5 ) 同步：同步和协调共享数据； 2 3 2 实时操作系统的发展 早期的实时操作系统只是一个小而简单的、带有一定专用性的软件，其功能较弱， 可以认为是一种实时监控软件。它一般为用户提供对系统的初始化管理以及简单的实时 时钟管理。这个时期，实时应用较为简单，应用软件，实时监控软件和硬件运行平台往 往紧密联系在一起。 9 太原理工大学硕士研究生学位论文 随着应用的发展，早期的r t o s 显示出明显的不足。实时操作系统经过多年的发展， 先后从实模式进化到保护模式，从微内核技术进化到超微内核技术，在系统规模上也从 单处理器的r t o s 发展到支持多处理器的r t o s 和网络r t o s ，在操作系统研究领域中 形成了一个重要分支。r t o s 的发展主要经历了两个阶段：专用实时操作系统和通用实 时操作系统。 ( 1 ) 专用实时操作系统 用户为满足自身开发需要而研制与特定硬件相匹配的专用实时操作系统。它一般只 适用于特定的硬件环境，缺乏严格的评测，移植性也不太好。这类专用的实时操作系也 被称为r e a l t i m e o p e r a t i n gs y s t e m d e v e l o p e d i n h o m e ，是早期用户为了满足自身开发需 要而研制的。 ( 2 ) 通用实时操作系统 随着计算机硬件的系统化、标准化，以及对实时操作系统功能要求的增强，用户自 己开发实时操作系统变得越来越困难，并且将延长开发周期、增加成本。为此出现了专 业的实时操作系统开发商，他们研究通用的实时操作系统，并尽可能地适应各种应用需 求，使实时系统的系统软件与应用软件分离，用户更多的集中精力于应用软件的开发， 而由开发商提供系统软件的支持。 随着通用实时操作系统出现，国际实时性标准也相应出台。大多数实时操作系统采 用的是p o s i x 1 b - 1 9 9 3 实时性标准。这个标准规定了优先调度方法，用户内存页的锁定 方法，实时信号，增强进程间通讯机制和时钟以及一系列其他特性。与此相关的还有 p o s i x l 0 0 3 1 ( 编程接口) 标准和p o s i x l 0 0 3 2 ( 控制台和工具软件) 标准等。在各种专用 r t o s 中，一些多任务的机制，如基于优先级的调度、实时时钟管理、任务间的通信、 同步互斥机构等基本上是相同的，不同的只是面向各自的硬件环境与应用目标。时间上， 相同的多任务机制是能够共享的，因而可以把这部分很好地组织起来，形成一个通用的 实时操作系统内核。这类实时操作系统大多采用软组件结构，以“标准组件”构成通用 的实时操作系统。 通用实时操作系统一方面在r t o s 内核的底层将不同的硬件特性屏蔽掉；另一方面， 对不同的应用环境提供了标准的、可裁减的系统服务软组件。这使得用户可根据不同的 实时应用要求以及硬件环境选择不同的软组件，也使得实时操作系统开发商在开发过程 中减少了重复性工作。 1 0 太原理 二大学硕士研究生学位论文 2 4 几个代表性的嵌入式实时操作系统 嵌入式实时操作系统是一种实时的、支持嵌入式系统应用的操作系统软件。它是嵌 入式系统包括硬、软件系统极为重要的组成部分，通常包括与硬件相关的底层驱动软件、 系统内核、设备驱动接口、通信协议、图形界面、标准化浏览器等。从长远的意义上来 讲，嵌入式实时操作系统的研究和开发能够使嵌入式系统软件工业更有效、更专业化的 分工、减少社会重复劳动、提高劳动生产率。 ( 1 ) v x w o r k s v x w o r k s 是美国w i n d r i v e rs y s t e m 公司推出的实时操作系统，是一个运行在目标机 上的高性能、可裁减的实时操作系统。它以优良的可靠性和卓越的实时性被广泛地应用 在通信、军事、航空和航天等高精尖技术及对实时性要求极高的领域中。v x w o r k s 的开 放式结构和对工业标准的支持，使嵌入式系统开发者只需做少量的工作即可设计出有效 的适合于不同用户要求的实时操作系统。 v x w o r k s 是一个单内核系统，是一个专用的面向宿主机客户机的解决方案。一台 u n i x 宿主机用来做软件开发和运行程序的非实时部分，一个名为w i n d 的v x w o r k s 内 核负责在客户机上运行实时任务。不同的计算机之间通过t c p h p 网络协议进行通讯。 v x w o r l 【s 是不兼容u n i x 的，但是它也提供部分p o s i x 接口功能，主要是p o s i x l 0 0 3 1 b 中关于实时扩展的部分。大部分v x w o r k s 的应用程序接口是其独有的。所以，v x w o r k s 不适宜现有的许多需要保护以及基于其它的传统操作系统的实时应用。 在v x w o r k s 中，内核和进程运行在相同的地址空间，这使进程间切换变得非常快， 并且减少了系统调用陷阱的发生。后台运行的连接器可以动态加载任务以及系统模块， 这一特性是专门为系统剪裁性设计的。这些特性使基于v x w o r k s 的开发相对简单，但 是，这个系统也是相当脆弱的，某个小模块的错误有可能导致整个系统瘫痪。 ( 2 ) p s o s y s t e m p s o s y s t e m 是美国系统集成公( i n t e g r a t e ds y s t e m sl n c ，i s l ) 根据几十年从事嵌入式 实时系统理论研究与实践活动而设计开发的嵌入式实时操作系统。其集成了一整套嵌入 式软件的模块、工具和服务，是一个模块化、高性能的实时操作系统，专为嵌入式微处 理器设计，在通讯领域的嵌入式系统中占有重要的地位。它提供一个完全的多任务环境， 在定制的或是商品化的硬件上提供高性能和高可靠性。p s o s y s t e m 允许开发者根据每个 应用的特殊要求对操作系统的功能和服务进行裁减和配置。这种设计使得开发人员对简 单的独立设备及复杂的具有容错功能的多处理器系统都可以灵活配置，可以让开发者将 太原理 大学硕士研究生学位论文 操作系统的功能和内存需求定制成每个应用所需的系统。开发者可以利用它来实现从简 单的单个独立设备到复杂的和网络化的多处理器系统。它提供了基于标准化开放系统的 完整多任务环境。其设计宗旨是为了实现高效、可靠、易于使用的嵌入式实时软件，以 支持用户自己设计的或商业化的硬件系统。它还提供了一套集成化的交叉开发工具以支 持应用系统的开发，该集成环境可在p c 机或工作站上运行，同时所有开发工具可通过 多种连接机制与目标机通信。 ( 3 ) w i n d o w sc e w i n d o w sc e 是一个3 2 位的抢先式、多任务，并具有强大通信能力的w i n 3 2 嵌入式 操作系统，是微软专门为信息设备、移动应用、消费类电子产品，嵌入式应用等非p c 领域而设计的操作系统产品。它具有高度的定制特性，支持多任务和多线程特性，可以 方便地为特殊的需要而进行改变。它的内核提供内存管理、抢先多任务和中断处理功能。 内核的上面是图形用户界面g u i 和桌面应用程序。在g u i 内部运行着所有的应用程序， 而且多个应用程序可以同时运行。w i n d o w sc e 以多种方式将一个虚拟的桌面计算机置 于掌上或置于口袋中，是专门为体积小、资源要求低和便携式的机器而设计的。 微软还提供了i n t e lx 8 6 处理器的w i n d o w sc e 仿真环境，它为w i n d o w sc e 应用程 序的开发提供了一个仿真的外壳，这大大地减少了对目标设备的需要。w i n d o w sc e 的 仿真与真的操作系统几乎完全一样，因此完全可以在该仿真平台上进行应用程序的开 发、测试和集成工作。所有这些开发工具包都带有一套很好的组件，比如远程进程浏览， 远程注册表编辑器，远程监控，远程对象存储等等。w i n d o w sc e 还支持w i n 3 2a p i ， 因而使得开发者能够快速而容易的进行应用程序的开发。它还支持串口或红外连接通 信，提供的串口通信可以通过r s 2 3 2 接口实现，支持连接在r s - 2 3 2 口上的m o d e