（计算机软件与理论专业论文）基于多处理机的混合型实时容错调度算法研究.pdf

哈尔滨工程大学硕士学位论文 摘要 随着实时系统在工业领域豹广泛应用，工业实时系统不仅需要保证数据 采集、控制、数据传输等周期任务在规定的时间内完成，也要保证突发事件 触发的非周期任务的及时响应，而且要保证在系统的软硬件出现故障时，实 时任务仍能满足其时间约束。由于应用的日益复杂，使得多处理机系统成为 处理这种复杂应用的有效计算手段。因此，要求工业实时计算在保证故障容 错能力的前提下能够综合处理多处理机系统中周期任务和非周期任务混合调 度问题。论文在总结工业实时系统实时任务调度特点的基础上，综合分析了 已有调度算法，针对它们用于工业实时计算时存在的问题，提出了混合型调 度算法，并通过仿真实验证明了算法的有效性和可行性。主要工作包括以下 几个方面： 针对工业实时系统中周期任务和非周期任务的特点，提出了预留处理时 间的混合型任务调度算法，其中周期任务遵循单调速率调度( r a t e m o n o t o n i c s c h e d u l i n g , r m s ) 算法在预留处理时间内调度运行，非周期任务遵循最早时限 优先( e a r l i e s td e a d l i n ef i r s t ，e d f ) 算法调度运行。非周期任务不占用预留的处 理时间，不会带来周期任务的重新分配，这在很大程度上减少了实时任务在 线调度的复杂性。 通过对周期任务在临界时刻实际执行时间的分析计算，以解析方法系统 地计算预留给周期任务的最小处理时间。基于周期任务参数的可确定性，离 线完成计算量相对较大的周期任务分配和预留处理时间计算。该方法能充分 利用处理机的有效处理时间，但没有增加系统在线开销 提出了集成容错调度算法实现多处理机系统中周期和非周期混合任务的 容错调度，以静态调度方式离线完成周期任务主版本与从版本的容错分配和 各处理机上最小预留处理时间的计算，以动态调度方式完成随机到达系统的 非周期任务的主版本与从版本的容错分配，这种静态调度与动态调度相结合 哈尔滨工程大学硕士学位论文 方法大大地降低了任务在线调度的时间开销。 关键词：容错；实时系统；实时任务调度；混合型实时任务调度 哈尔滨工程大学硕士学位论文 a b s t r a c t t h er e a l - t i m es y s t e m sa r em a d es t r i c td e m a n d so nb e c a u s eo ft h e i rw i d e a p p l i c a t i o ni ni n d u s t r y , s u c ha sf i n i s h i n gi n f o r m a t i o na c q u i s i t i o n , c o n t r o ll o o p s , d a t ac o m m u n i c a t i o nw i t h i nt h e i fd e a d l i n e s r e s p o n d i n gt oa p e r i o d i ct 弱k sa r i s i n g f r o ma r b i t r a r yc r i t i c a le v e n t si nt i m e ，a n dm a k i n gr e a l - t i m et a s ks a t i s f yt h et i m i n g c o n s t r a i n t se v e ni fh a r d w a r eo rs o f t w a r ef a u l t so c c u r m e a n w h i l e a st h e a p p l i c a t i o n sa r eg e r i n gc o m p l e xg r a d u a l l y , t h em u l t i p r o c e s s o rb e c o m e sa k i n do f e f f e c t i v ew a yt od e a lw i t ht h ec o m p l i c a t e dc o m p u t a t i o n s t h e r e f o r e ，r e a l - t i m e i n d u s t r i a l c o m p u t i n g i s r e q u i r e d t oh a n d l e p e r i o d i c a n d a p e r i o d i ch y b r i d s c h e d u l i n g t a s k si nm u l t i p r o c e s s o rs y s t e m sb a s e do nt h ep r e m i s eo ff a u l tt o l e r a n c e i no r d e rt om e e tt h ee x i s t i n gp r o b l e m si nr e a l - t i m ei n d u s t r i a lc o m p u t i n g , t h ep a p e r p r o p o s e sah y b r i ds c h e d u l ea l g o r i t h mt h r o u g hs u m m a r i z i n gt h ec h a r a c t e r i s t i c so f r e a l - t h n et a s ks c h e d u l ea n d a n a l y z i n g t h e e x i s t i n ga l g o r i t h m s ，a n d t h e e f f e c t i v e n e s sa n df e a s i b i l i t yo ft h ea l g o r i t h mi sv e r i f i e dw i t hs i m u l a t i o nt e s t t h e f o l l o w i n gr e s e a r c h e sa n dc o n t r i b u t i o n sa r ec a r r i e do u t ： c o n s i d e r i n gt h ec h a r a c t e r i s t i c so fp e r i o d i ca n da p e r i o d i ct a s k si nr e a l - t i m e i n d u s t r i a ls y s t e m s ，ah y b r i dr e s e r v a t i o np r o c e s s i n g - t i m et a s ks c h e d u l i n ga l g o r i t h m i s p r o p o s e d , i n w h i c h p e r i o d i c t a s k sa r es c h e d u l e d a c c o r d i n g t ot h e r a t e - m o n o t o n i cs c h e d u l i n g ( r m s ) a l g o r i t h mi nt h er e s e r v e dp r o c e s s i n gt i m e ， w h i l ea p e r i o d i ct a s k sa r cs c h e d u l e da c c o r d i n gt ot h ee a r l i e s t d e a d l i n e f i r s t ( e d f ) a l g o r i t h m t h es c h e d u l i n go fa p e r i o d i ct a s k sd o e sn o tc o s tt h er e s e r v e dp r o c e s s i n g t i m e , w h i c ha v o i d sr e a l l o c a t i o no fp e r i o d i ct a s k sa n dr e d u c e st h ec o m p l e x i t yo f o n l i n es c h e d u l eg r e a t l y b a s e do nt h ea n a l y s i so fe x a c te x e c u t i o nt i m eo fp e r i o d i ct a s k sa tc r i t i c a l i n s t a n t , t h em i n i m u mr e s e r v e dp r o c e s s i n gt i m eo fp e r i o d i ct a s k si sd e r i v e d s y s t e m a t i c a l l y a c c o r d i n gt ot h ed e t e r m i n a b i l i t yo fp e r i o d i ct a s kp a r a m e t e r s ，t h e a l l o c a t i o no fp e r i o d i ct a s k sa n dt h ed e r i v a t i o no fr e s e r v e dp r o c e s s i n gt i m ea r e i m p l e m e n t e do f f - l i n e t h ea l g o r i t h mc a r lm a k ef u l lu s eo ft h ea v m l a b l ep r o c e s s i n g t i m eo fp r o c e s s o rw i t h o u ti n c r e a s eo fo n l i n ec o s t a n i n t e g r a t i n gf a u l t - t o l e r a n ts c h e d u l i n ga l g o r i t h mi si n t r o d u c e dt oi m p l e m e n t 哈尔滨工程大学硕士学位论文 p e r i o d i ca n da p e r i o d i c ) a s k ss c h e d u l e n ep r i m a r y - b a c k u pa l l o c a t i o no fp e r i o d i c t a s k sa n dt h ed e r i v 砒i o no fm i n i m u mr e s e r v e dp r o c e s s i n gt i m ea l ep e r f o r m e d s t a t i c a l l y , w h i l et h ep r i m a r y - b a c k u pa l l o c a t i o no fa p e r i o d i ct a s k s i sp e r f o r m e d d y n a m i c a l l y o n c eu n e x p e c t e d a p e r i o d i c t a s k sa r r i v ei nt h e s y s t e m n c c o m b i n a t i o nb e t w e e ns t a t i ca n dd y n a m i cs c h e d u l i n gd e c r e a s e st h eo i l l i n ec o s tt oa g r e a te x t e n t k e y w o r d s ：f a u l tt o l e r a n c e ；r e a l - t i m es y s t e m ；r e a l - t i m et a s ks c h e d u l e ；h y b r i d r e a l - t i m et a s ks c h e d u l e 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本学位论文是本人在导师指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内 容外，本论文不包含其它任何个人或集体已经发表或撰写 过的作品成果。在完成论文时所利用的一切资料均已在参 考文献中列出，对本论文的研究作出重要贡献的个人或集 体均己在文中明确注明。 作者( 签字) ：望墅塑 日期：2 哆年月r 日 哈尔滨工程大学硕士学位论文 第1 章绪论 随着各种控制系统复杂性的提高， 各种实际控制领域，如工业控制系统、 分布式控制系统已越来越多地应用于 武器防御控制系统、飞行控制系统、 电站控制系统等。但是随着控制器数目的增加，系统控制器出现故障的可能 性也相应增大。在控制系统中，每个任务都有严格的时间约束( 截止时限) ， 如果控制器的故障使某些任务不能在其截止时限内完成，就有可能造成很大 的损失。为了避免控制器出现故障时造成严重后果，需要为分布式控制系统 提供一定的容错能力，保证任务仍可以满足其截止时限，以提高整个系统的 可靠性【1 捌。 实时容错调度算法是一种通过软件解决分布式实时系统容错问题的有效 方法。该方法的优点是不需要额外的硬件代价实现实对系统的可靠性。它是 在分布式系统的容错调度算法的基础上发展起来的。分布式系统目前所采用 的典型的容错技术主要是分布式投票技术【3 】、反转恢复技术1 4 j 和主从版本技 术【5 i 。 1 1 实时容错调度研究现状与存在的问题 1 1 1 研究现状 基于不同的硬件结构，实时调度容错可分为单处理机实时容错调度和多 处理机实时容错调度。在此基础之上，根据优先级确定方法的不同，每类算 法又可以分为静态优先级调度和动态优先级调度两类。 在单处理机静态实时容错调度算法中，最具代表性和实用价值的工作是 t h u e l1 6 1 提出的p r a ( p r i v a t er e s e r v a t i o na l g o r i t h m ) 和c r a ( c o m m u n a l r e s e r v a t i o na l g o r i t h m ) ，以及g h o s h 等人1 7 1 的f t r m ( f a u l t - t o l e r a n tr a t e m o n o t o n i c ) ；比较典型的动态实时容错调度算法是容错e d f 调度( f a u l t t o j e r a n t e , a r t i e s td e a d l i n ef i r s t ，f t e d f ) i s l 。 分布式系统目前所采用的典型的容错技术主要是分布式投票技术【3 】、反 转恢复技术1 4 1 和主从版本技术1 5 1 ，然而这些技术没有考虑任务的实时性问题。 而现有的分布式实时系统的容错技术主要是在主，从版本技术上发展起来的。 哈尔滨工程大学硕士学位论文 主要的实时容错调度算法有：b k c l l9 1 算法，e b k c l 【加1 算法，基于多处理机 的容错实对任务调度算法i l l l 和基于e d f 的分布式控制系统容错调度算法【1 2 1 。 1 1 1 1 单处理机实时容错调度 1 p r a 和a 叉a 算法 p r a 和c r a 均以r m 调度为基础。对于因暂态硬件缺陷或暂态软件设 计缺陷引起的实时任务运行出错，p r a 和c r a 调度出错任务利用冗余的处 理器时间再次运行，或替代任务利用冗余的处理器时间运行。p r a 和c r a 采用了不同处理器资源冗余策略，因而容错能力不同。p r a 为实时任务预留 私有的处理器空闲时间，以保证任务h 在两个连续周期边界 k s ，似1 ) 磊】内能 够重复运行( 1 似) 次，而不会导致其他任务的运行超过时限。因此，p r a 能够 保证任务t ! 在连续出现x 次错误的情况下仍能在时限到来前获得正确的运算 结果。因此，“可以被看作具有工次暂态错误容错能力的容错实时任务。与 p r a 为每个实时任务预留处理器时间不同，c r a 预留的处理器空闲时间为所 有实时任务共同拥有，其大小为c ，m 强( c 0 ，其中c ，为任务t i 的最大执 行时间。显然，c ，能够满足实时任务集在【 五，球+ 1 ) 瑚内：次容错操作的时间 需求。c r a 和p r a 实现简单，运行时的开销小，适用于任务数量较少，系 统运行中不会出现新任务，且任务出错概率较高的系统。 2 f i r m 算法 在1 9 9 8 年，以s g h o s h 为首的研究组在r m 调度的基础上，提出了容 错r m 调度。阿t m 的时问冗余策略引入了备份任务的概念。备份任务是一 个虚拟的任务，但是具有确定的资源利用率。实时系统运行时，备份任务拥 有一定的处理器资源。f t m 将这部分资源作为预留的处理器资源，为容错 操作提供保证。在系统正常运行时，备份任务拥有的处理器时间保持空闲， 当实时任务运行出错时，调度器将调度出错的任务利用备份任务的处理器时 闻进行容错操作。根据在规定时段内容错的不同要求，则备份任务的资源利 用率需求不同。如果实时系统的容错要求是规定时段的单错误容错，设备份 任务为岛，则其资源利用率为巩= m 瓢( c l 履，即实时任务的最高资源利用 率。备份任务的实例在每个周期边界就绪，在所有任务中，备份任务是优先 级最高的任务。为实现系统的容错要求，系统正常运行时，备份任务的实例 2 哈尔滨工程大学硕士学位论文 总在调度器的管理下与处于就绪状态且当前优先级最高的实时任务交换运行 次序，为该任务提供容错保证。若当前任务运行出错，剥f r r m 调用恢复算 法实现容错。 3 容错e d f 算法 容错e d f 仅考虑暂态错误，为简化分析，当任务出错时，调度器调度出 错任务再次运行。为检测任务执行是否正确，任务结束前将进行错误检测， 其开销计入任务的运行时间。在容错e d f 中，冗余处理器资源为所有任务共 享，适用于资源利用率高，出错概率低的实时应用。容错e d f 的设计目标是， 在l + 瓦“内，冗余的处理器资源保证一次容错搡作，且所有任务均满足时 限要求。因此，在两个连续的最大周期边界 k r n ，m 1 ) 砌】内，冗余的处理器 资源为m a x ( c i ) 。容错e d f 仍旧按照任务的时限先后决定任务的优先级，时 限近者优先级高。系统运行时，若当前执行的任务出错，调度器调度该任 务再次运行。在容错处理的过程中，若新就绪的任务f ，的优先级高于t l ，则 吩抢占矗 1 。1 。1 。2 多处理机实时容错调度 1 b k c l 和e b k c l 算法 b k c u 从版本后调度) 算法和e b c l 算法是秦啸和韩宗芬提出的分布 式实时容错调度算法。容错算法可以同时调度具有容错需求的实时任务和没 有容错需求的实时任务，算法的目的是在多处理器实时操作系统中，当一个 处理器失效时，具有容错需求的实时任务仍然能够在截止时限之前完成。 b k c l 算法假设系统中所有实时任务都是周期任务，各任务有相同的周期且 截止时限等于周期；分配在同一处理器上的多个任务的从版本之间没有时间 重叠。该算法首先将具有容错需求的任务集合品中的实时任务豹主版本按 计算时间非增进行排序，然后采用最大计算时间优先调度( u 叼算法调度这些 实时任务；接着将没有容错需求的任务集合s 一中的实时任务也按计算时间 非增进行排序，再用u 吓算法调度这些实时任务；最后调度集合& 中实时 任务的从版本，其方法也是先按计算时间非增对所有的从版本进行排序，然 后使用改进的最大计算时间优先调度( a l p t ) 算法调度这些实时任务的从版 本。当分布式实时系统中的节点机个数充足时，b k c l 算法给出一个有效的 3 哈尔滨工程大学硕士学位论文 实时容错调度结果；如果系统中的节点机个数不足以满足所有实时任务 韵要求。b k c l 算法输出调度失败信息。 e b k c l 算法在b k c l 算法的基础上进行改进。改进的前提是：若具有 容错需求的实时任务t i 和t j 的主版本分配在不同的处理器上，则这两个实时 任务的从版本允许被分配到同一处理器上，且两个从版本之间允许有时间上 的重叠。与b k c l 相似，e b k c l 算法首先将具有容错需求的任务集合& 中的实时任务的主版本按计算时间非增进行排序，然后采用最大计算时间优 先调度( l p t ) 算法调度这些实时任务；接着将没有容错需求的任务集合s ，中 酌实时任务也按计算时间非增进行排序，再用l p t 算法调度这些实时任务； 最后对集合& 中实时任务的从版本进行调度，具体方法如下：首先对主版本 已经分配到1 号处理器上的实盱任务的从版本进行调度，然后调度那些主版 本已经分配到2 号处理器上的实时任务的从版本，这样依次调度到k 号处理 器。在调度一个主版本分配到f 号处理器上的实时任务的从版本之前，将为 这个处理器调度长度做一个备份。通过这种方法，如果两个实时任务和t j 的主版本分配在不同的处理器上，且这两个实时任务的从版本被调度到同一 处理器上，刚允许这两个从版本之阃有对弼上的重叠。当分布式实对系统串 的节点机个数充足时，e b k c l 算法给出一个有效的实时容错调度结果；如 果系统中的节点机个数不满足所有实时任务的要求，e b k c l 算法输出调度 失败信息。 2 基于多处理机的容错实时任务调度算法 1 9 9 9 年，张拥军等人提出了一种基于多处理机的启发式实时容错调度算 法其基本思想是：在对非周期性的实时任务采用非抢占式的调度策略的基 础上，使主从备份( p r i m a r y - b a c k u p ) 技术和首次满足( 弱r s 酒t ) 的方法在多处 理机上分配和调度动态达到系统的实时任务。由于任务主版本的执行可能因 处理机故障而导致失败，因此算法通过在其他处理机上为其后备任务在截止 时限前预留一定的调度执行时间来达到容错的目的。并且通过对预留时间段 的重叠使用，以及当处理机无故障时( 任务主版本执行成功) ，回收为容错 目的预留的时间( 即后备任务的调度执行时间) ，来分配给新到达系统的任 务使用，以提高c p u 的利用率和系统对任务的接收率。 算法分为3 步t 第一是对任务的允许控制，包括任务的分配情况、任务 4 哈尔滨工程大学硕士学位论文 的执行时间和任务的截至时间；第二步采用f i r s t f i t 方法，对通过允许控制的 任务进行调度；第三步对后备任务时间段的回收，如果任务主版本正常执行 结束，则通知任务从版本所在的处理机，把原分配给任务从版本的时间段回 收，即取消任务从版本的调度。 此算法只能调度非周期实时任务，若存在周期性实时任务则把它转换成 非周期实时任务进行调度，因此调度开销较大。 3 基于e d f 的分布式容错调度算法 刘怀提出了基于主，从版本技术和e d f 算法的容错调度算法，该算法不 要求任务的周期都相同，通过设置主，从版本的任务时限来控锖4 它们的执行对 问不重叠。为了使系统具有容错能力，每一个实时任务都有主版本和从版本， 它们被分配到不同的处理器上，系统首先运行任务的主版本，如果主版本运 行正确，则其从版本不需要运行，而当主版本所在的处理器出现故障时，则 该任务在其他处理器上的从版本投入运行。调度算法分为两部分；任务分配 算法和处理器局部的调度算法。任务分配算法采用f i r s t - f i t 方法，处理器局部 调度算法采用e d f 方法调度周期性任务。同时，还给出了周期任务集合可调 度的充分条件。 1 1 2 存在的问题 综上所述，现有的容错调度算法有的只能调度单类型的实时任务，而 在现代控制系统中既存在周期性实时任务，如信号的采集；又存在非周期实 时任务，如报警信号。所以，现有的容错调度算法无法满足现代控制系统的 要求，急需研究既能调度周期性实时任务，又能调度非周期实时任务的混合 型实时容错调度算法。这正是本文研究的动机。 1 2 论文的主要研究内容 本文在总结工业实时系统实时任务调度特点的基础上，综合分析了已有 调度算法特点，针对它们用于工业实时计算时存在的问题，提出了混合型调 度算法，并通过仿真实验证明了算法的有效性和可行性。主要工作包括以下 几个方面： 针对工业实时系统中周期任务和非周期任务的特点，提出了预留处理时间 5 哈尔滨工程大学硕士学位论文 的混合型任务调度算法，其中周期任务遵循单调速率调度( r a t e m o n o t o n i c s c h e d u l i n g , r m s ) 算法在预留处理时间内调度运行，非周期任务遵循最早 时限优先( e a r l i e s td e a d l i n ef i r s t , e d f ) 算法调度运行。非周期任务不占用预 留的处理时间，不会带来周期任务的重新分配，这在很大程度上减少了实 时任务在线调度的复杂性。 通过对周期任务在关键时刻实际执行时间的分析计算，以解析方法系统地 计算周期任务的最小预留处理时间。基于周期任务参数的可确定性，离线 完成计算量相对较大的周期任务分配和预留处理时间计算。该方法能充分 利用处理机的有效处理时间，但没有增加系统在线开销。 提出了混合容错调度算法实现多处理机系统中周期和非周期混合任务的 容错调度，以静态调度方式离线完成周期任务主版本与从版本的容错分配 和各处理机上最小预留处理时间的计算，以动态调度方式完成随机到达系 统的非周期任务的主版本与从版本的容错分配，这种静态调度与动态调度 相结合方法大大地降低了任务在线调度的复杂性。 1 3 论文的组织结构 论文共分四章，其组织结构为： 第1 章是绪论。首先分析了论文的研究背景，包括控制系统的应用需求， 实时容错调度理论的研究现状，并在此基础上阐明了本文的研究动机；其次 确定论文的研究主题，归纳了主要研究内容和工作；最后对本文的组织结构 进行了介绍。 第2 章是算法的理论基础，包括容错理论和实时调度理论。本章首先介绍 了容错的基本概念和主要容错技术如硬件容错、软件容错和时间容错。其次 介绍了实时调度理论的基本知识和经典调度算法_ r m 算法和e d f 算法。 第3 章是混合型实时容错调度算法研究。首先，给出了实时任务集的描 述模型。在此基础上，提出混合型实时容错调度算法，给出算法的设计思想 并对其进行复杂度分析和性能仿真模拟分析。 第4 章是仿真演示结果和分析。建立分布式控制仿真演示系统，并利用 该系统对第3 章提出的混合型实时容错调度算法进行验证，通过对实验结果 的比较分析，进一步说明算法的性能。 6 哈尔滨工程大学硕士学位论文 第2 章算法的理论基础 相对于其他计算机系统而言，实时系统对可靠性要求十分严格。例如， 当桌面应用程序在求解某一数学问题时失败，放弃该程序的执行所损失的只 是失败前所消耗的系统资源。然而，在实时系统中，这种简单的放弃往往是 不可接受的。例如，在高炉炼钢的过程中，当出现错误时，实时系统必须能 够提供降级服务，以保证能够将钢水排出高炉，因为放弃对高炉的控制将造 成巨大的经济损失。又如，飞行控制系统若因系统某一组成部分出错而放弃 对飞机的控制必将导致灾难性的后果。因此，飞行控制系统必须具有出错导 向安全的特性，即使在出错时通过降级或其他措施保证飞行员能够使飞机安 全着陆。 由此可见，实时系统与容错技术有着密切的关系。所以本章对实时系统 的重要领：嗡一实时调度和容错技术进行了详细的讨论。 2 1 实时任务及其属性 2 1 1 任务与任务的时间属性 定义2 1 任务是指完成某一特定功能的程序模块，它是实时调度中的一 个基本单位：任务在其生命期中的某一次执行称为该任务的一个作业；具有 实时性能需求的任务称为实时任务，反之则称为非实时任务【1 3 , 1 4 。 一个实时任务的特征，通常用以下参数来描述： 定义2 2 到达时刻( a r r i v et i m e ) ：当任务己分配到除处理机以外的所有必 要资源的时候，它能够被系统调度执行，此时的状态称为就绪态。一个作业 由其他状态转变为就绪态的那个时刻称为它的到达时亥e j ( a r r i v et i m e ) 。 定义2 3 响应时间( r e s p o n s et i m e ) ：作业自它的到达时刻起，到它被完成 时刻止的时间段长度称为它的响应时间。若作业的响应时间有一个最大值限 制，那么这个最大值被称为它的相对截止时限( r e l a t i v ed e a d l i n e ) 。若一个作业 被要求在某个时刻之前完成，那么那个时刻称为它的绝对截止时限( a b s o l u t e d e a d l i n e ) 1 4 t1 5 1 。 对于实时任务，一个常见的实时性能需求是，它的所有作业都被要求在 7 哈尔滨工程大学硕士学位论文 各自的绝对截止时限之前完成。为阐述方便，本文以下用术语“截止时限” 表示绝对截止时限。 定义2 4 最坏执行时间( w o r s t - c a s ee x e c u t i o nt i m e , w c e t ) ，任务在其生命 期中的每个作业的执行时间的最大可能值。w c e t 常用来作为实时调度中任 务对处理机的可能占用情况的一个衡量值【1 6 】。 定义2 5 周期：任务被周期性地执行的前后两个作业之间的时间间隔。 2 1 2 任务的分类 根据不同的标准，任务可以有多种分类方法。 首先，按照是否具有实时性要求，可将任务分为实时任务和非实时任务。 在实时任务中，根据对实时性能要求的程度，还可以分为硬实时任务和软实 时任务两类。硬实时( h a r dr e a l d m c ) 任务要求可确定性强，具有明确的时间约 束，在某个限定时刻之前不能完成任务将导致整个应用失败；软实时( s o f t r e a l - t i m e ) 任务也对时间敏感，在发生不能满足实时要求的情况下，其影响可 能是系统部分性能的下降，但系统仍然可以运行。 其次，根据任务的作业到达时刻规律的不同，可分为周期任务( p e r i o d i c t a s k ) 、闻发任务( s p o r a d i ct a s k ) 和非周期任务( a p e r i o d i ct a s k ) 。对于周期任务， 其相邻两次作业到达时刻之间的间隔是一个固定的常数( 即周期) 。问发任务 是指相邻两次作业到达时刻之间的间隔不固定，但有一个下限值。非周期任 务的作业到达时刻没有规律。在本文的研究中不区别问发任务和非周期任务， 将它们统称为突发任务或非周期任务。 2 。1 3 任务的相关性 任务间的相关性有以下几种： 顺序相关性( 时序约束) ：这是指某些任务之间必须按照一定的先后顺序 开始运行。它是由与应用相关的处理顺序、任务间交换数据的需要或任 务间通讯而导致的。如果任务间不存在顺序相关性，则称这些任务是独 立的 资源相关性( 资源约束) ：它包括任务互斥地使用主动资源及任务共享或 互斥地使用被动资源。 优先级顺序( 优先级约束) ：高优先级的任务可以抢占低优先级任务的运 b 哈尔滨工程大学硕士学位论文 行。此外，当若干个任务同时发出运行请求时，具有最高优先级的任务 将首先占有处理器。 策略导致的约束：这是由应用的额外要求所引起的。如某些任务必须 要在某个处理机上运行或者某些任务必须要在某个特定时间运行等。 2 2 实时调度算法 在实时系统调度理论研究中，实时调度算法一直是核心问题。调度算法 的本质是在给定的任务集和资源条件下，确定何时何处执行任务，以满足每 个任务的时间约束。 2 2 1 实时调度算法概述 2 2 1 1 实时调度算法分类 实时调度算法的分类可有多种方法。常用分类方法如表2 1 所示。 表2 1 实时调度的分类方法 分类依据分类 根据任务执行序列生成的时间静态调度和动态调度 根据实时任务是否可被抢占抢占式调度和非抢占式调度 根据系统中处理器的数量单处理器实时调度和多处理器实时调度 1 静态调度和动态调度 静态调度是在任务集运行之前就产生一个静态的调度表，在运行时总是 按照调度表决定从就绪任务队列中选择哪个任务来运行。这类调度算法假设 系统中实时任务的特性( 如：w c e t 、截止期、执行次序等) 是全部已知的，适 合于问题需求确定，并且运行中不会有较大变化的情况，如简单的工业过程 控制。静态调度算法的优点是运行开销小，可预测性强。但是它的灵活性较 差，不适合动态变化的，或不可预测环境下的调度。 动态调度算法是在运行期间才决定选择哪个就绪任务来运行。它所根据 的是目前己处于就绪态的各任务的相关属性，以此来决定当前的调度序列。 这类算法能够对变化的环境做出反应，因此，这类调度算法比较灵活，适合 于任务不断生成，并且在任务生成之前，其特性并不清楚的动态实时系统， 9 哈尔滨工程大学硕士学位论文 如自行机器人控制系统。但是，动态调度算法的运行开销一般较前者大【1 4 t 1 7 】。 2 抢占式调度和非抢占式调度 在抢占式调度中，目前正在运行的任务可以被别的更紧迫和更重要的任 务中断。同时，被抢占的任务在未来可以恢复运行，且不会影响到任务的整 体时限约束。这种抢占式的调度常见于工业制造中。它的优点是比较灵活， 对资源的利用率高；但由于经常出现的上下文切换使得其的开销较大【堋。 如果在调度中不允许正在运行的任务被别的任务中断，任务一旦占有了 处理器便会一直运行直至完成，这样的调度则是非抢占式的，它比较适合于 任务运行时间都比较短的系统。其优点是省去了进行上下文切换的开销：同 时，具有更好的可预测性，更易于测试，在保证对共享资源的互斥访问上也 有较强的继承能力。非抢占式调度没有抢占式调度那样灵活，对资源的利用 率也相对较低 3 单处理器实时调度和多处理器实时调度 如果实时系统运行在一个单独的处理器上，则为实时单处理器系统。在 这种系统中对实时任务进行调度时，仅需要考虑任务在这个处理器上的运行 情况。如果实时系统运行在一个多处理器的环境下，则为实时多处理器系统， 此时在进行实时调度时，不仅要考虑任务在单个处理器上的运行情况，还要 考虑任务被分配到哪一个处理器上运行，即任务分配问题。 2 2 1 2 实时调度算法的性能评估标准 实时调度算法有多种性能评估标准，其中最常见的利1 9 】： 调度成功率：指被某算法调度成功的任务集数目与参加调度的可调度任 务集数目的比值，或指被算法调度成功的任务个数与参加调度的任务数 之比； 调度长度：将参加调度的所有任务都执行完所花费的时间； 处理器利用率：表示任务集对处理机资源的占用程度； 处理器空闲率：处理器空闲时间与处理器资源总量的比率； 吞吐量：单位时间内处理任务的个数。 值得注意的是，以上这些性能评估标准不能完全兼容，没有一个调度算 法可以同时在这几个方面均达到最佳性能。对于实时调度算法来说，调度成 哈尔滨工程大学硕士学位论文 功率是最重要的性能评估标准。算法在其他几个评估标准上的提高均不应导 致调度成功率的明显下降。 2 2 2 静态实时调度算法 静态调度方式在任务集运行之前就产生一个静态的调度表，在运行时总 是按照调度表决定的任务序列执行。主要的静态调度算法包括：单调速率调 度算法( r a t em o n o t o n i c , r m ) 1 2 0 1 、先进先出算法( f i r s ti nf i r s to u t ，f i f o ) 【2 1 1 、单 调时限算法( d e a d l i n em o n o t o n i c , d m ) 瞄捌等。 单调速率调度算法r m 是最典型的静态实时调度算法。该算法是l i n 和 l a y l a n d 2 0 1 为单处理机系统中独立的周期任务调度提出的，它按照任务的周 期给任务指定优先级，周期越短优先级越高，处理机根据优先级高低进行任 务调度。由于任务的周期不变，任务的优先级在任务执行之前就己指定，优 先级不会随着程序的执行而发生改变，所以r l v l 是一种静态调度算法。 l i u 和l a y l a n d 在文献【2 0 】中证明了r m 算法是最优的，即对于在任何其 他静态优先级算法下可调度的任务集合，在r m 算法下也是可调度的，证明 思想如下。假设一个任务集s 采用其他静态优先级算法可以调度，设t i 和 是其中两个优先级相邻的任务，它们的周期t l 死，而优先级e , = e j 。将向和 t j 的优先级互换，可以证明这时s 仍然可以调度。按照这样的方法，其他任 何静态优先级调度最终都可以转换成r m 调度。这样便证明了r m 算法在所 有静态优先级算法中是最优的。r m 算法的最优性保证了其能够广泛地应用 于各种静态优先级调度的情况，这是r m 算法受到重视的重要原因。 文献【2 0 】中还给出并证明了如下可调度性的充分条件： 定理2 1 给定任务集庐 t “t 2 ，f n ) ，如果这疗个任务的c p u 利用率满足 下面的条件： u m ( m 1 ) ，那么至少有一个处理 机分配的任务个数大于等于拼，由于只有m 个处理机，所以必然至少存在一 组互斥任务，所以此任务组是不可调度的。这就证明了这一结论。 3 1 3 故障模型 采用文献1 2 3 1 提出的故障模型：某一对刻只有一个处理机出现故障，在 第2 个故障出现之前，前一个故障已被排除并且那些因前一故障而执行失败 的任务通过运行其从版本正确结束。另外，在对任务进行容错调度的同时， 系统要能及时诊断并报告处理机故障。假设故障出现后，其他处理机能及时 得到通知，由于处理机之间通信所需时间与任务的执行时问相比非常短，因 哈尔溟工程大学硕士学位论文 此我们忽略处理机之间消息的传递时间。 3 2 调度算法研究 调度算法分为两部分：任务分配算法和局部调度算法。由于系统的实时 任务可分为两类：周期性实时任务和非周期性实时任务。所以，对这两种不 同类型的任务采用了不同的任务分配方法和任务优先级设置方法。对于周期 性实时任务，由于其属性已经确定，所以采用静态任务分配算法并设置了其 优先级以节省c p u 的调度时间；对于非周期任务采用的是动态任务分配算 法。任务优先级按照下面的方法设置；周期任务的优先级按照r m 算法设置， 但从版本的优先级低于主版本的优先级；非周期任务根据e d f 算法动态地设 置其优先级。总的来说任务优先级具有以下关系： 周期任务主版本优先级 周期任务从版本优先级) - 非周期任务优先级 任务的主版本和从版本截止期的设置方法：主要是保证同一实时任务的 主版本和从版本之间没有执行时间的重叠以及当处理机出现故障时，任务的 从版本能够顺利执行。具体的控制方法是：实时任务正主版本的截止期设置 为磊2 蕊协磊d e 一露z 玩a ，使其在嚣t p d l 内完成，即保证如果任务主版本 所在的处理机出现故障，其从版本也能有足够的时间顺利执行。如果主版本 因所在的处理机出现故障而未能在其截止期内完成，则通知从版本所在的处 理机执行从版本。从而达到容错的目的任务乃的从版本的截止期设置为 瓦t b i d i = 死d i 。 3 2 1 静态任务分配 3 2 1 1r m 算法可谓度性判定 在实时系统调度理论研究中，可调度性判定是核心闯题。这是因为，实 时任务具有时限要求，在一个或多个处理器之间调度实时任务，需要判断是 否每个任务的执行都能够在其截止时限内完成。如果每个任务的执行都能够 在其截止时限内完成，则称该调度是可行的。可调度性判定( 或称调度可行性 判定) 就是判定给定的n 个实时任务在应用某种调度算法的前提下能否产生 一个可行的调度。调度算法的设计要尽可能满足任务可调度性的要求。 1 9 7 3 年，l i u 和l a y l a n d 提出了一种适用于可抢占的硬实时周期性任务调 哈尔滨工程大学硕士学位论文 度的静态优先级调度算法速率单调( r a t em o n o t o n i c ，简称r m ) 调度算法， 并对其可调度性判定问题进行了研究。刚算法自从提出以来得到了广泛的研 究和应用，目前已有大量关于r m 算法及其各种扩展情况下的调度算法以及 实时任务在这些算法下的可调度性判定研究的文献。理论研究的问题集中在 如何找到更快、更好的可调度性判定方法，以及如何扩展r m 算法，使之更 好地满足现实实现的需求。在u u 和l a y l a n d 的研究基础上，l e h o c z k y 等人 对固定优先级算法的特征进行了更为精确的研究，并提出了r m 算法可调度 性判定的充要条件。r m 算法的可调度性判定充要条件的提出是一个重大的 突破，它提供了适用于任何情况的r m 算法可调度性判定。但是，此算法是 一个伪多项式时间的算法，复杂度较高下面给出一种复杂性为多项式的判 定方法，即定理3 1 。 定理3 1 周期任务集合拈 t 1 ，t 2 , ，t n ，7 f 毋t l + l 忍+ 1 ，i = l ，2 ，一1 能够被调度的充分必有条件是： 仲鹕一薹峪卜曲卜鸺愣h ) 其中，p j 表示小于等于石的最大整数 首先解释一下任务的临界时刻( c r i t i c a li n s t a n t ) 这一重要概念，它是l i u 和 l a y l a n d 提出来的。一个任务的临界时刻是指这个任务在这一时刻提出请求将 会有最长的响应时间。如果一个任务在其临晃时刻能够被调度，那么它在任 何时刻都能够被调度。本文所给出的r m 算法可调度性判定条件是在任务的 临界时刻进行考察的。 直观地看，当一个任务被触发时，如果有比其优先级更高的任务同时被 触发，则该任务将会因被抢占而延长其响应时间，因而一个任务的临界状态