基于RM与EDF的实时混合调度算法研究

通过对实时系统中静态调度算法RM和动态调度算法EDF的研究与分析,针对两种调度算法在实际应用中的问题,提出了一种基于阈值6的混合调度算法,将RM与EDF调度算法相结合,并从数学角度描述了混合调度算法的可调度性与实时任务的周期、执行时间等属性之间的关系,给出了混合调度算法可调度性的充分必要条件。最后用实验验证了混合调度算法的有效性。

Em b dd d Te h ol y e e c n og

基于 R与 E F的实时混合调度算法研究术 M D黄仁，建章，李程平 ( .庆大学计算机学院，庆 403; 1重重 0 0 0 2重庆理工大学会计学院，庆 4 0 5 ) .重 0 0 4摘要：通过对实时系统中静态调度算法 RM和动态调度算法 E F的研究与分析，对两种调度 D针

算法在实际应用中的问题，出了一种基于阈值的混合调度算法， R与 E F调度算法相结合，提将 M D 并从数学角度描述了混合调度算法的可调度性与实时任务的周期、行时间等属性之间的关系，出执给

了混合调度算法可调度性的充分必要条件。最后用实验验证了混合调度算法的有效性。 关键词：实时系统；率单调调度算法；速最早截止期限优先调度算法；可调度性中图分类号：T 3 6 2 P 1 .文献标识码：A 文章编号：0 5— 9 8 2 1 )2 0 2— 3 2 8 7 9 (0 0 1— 0 9 0

S u y o c d lng a g rt m s d o RM nd EDF t d f s he u i l o ih ba e n aHUAN Re L in Z a g, HE G n, IJa h n C NG ig Pn 2( . olg f C mp trS in e C o g ig Unv ri, h n qn 0 0 0, hn 1 C l e o o ue ce c, h n qn iest C o g ig 4 0 3 C ia; e y

2 C l g fA cu t g,U i ri fC o gigfrSi c& Tc nlg,C og i 00 4, hn ) .ol eo co ni e n nv sy o hn q o c n e e t n e ehooy h nqn 4 0 5 C ia gAb ta t B su yn n n lzn tt s h d l g l o t m RM a d y a c c e u i g a g rt m s r c: y t d i g a d a a y i g sa i c e u i ag r h c n i n d n mi s h d l lo i n h EDF n h r a—t i t e e l i me s s m,ami g t t e p o l m o h s t ag rt ms n r c ia a p ia in, ti p p r r s ne a mie s h d l

g a g r h yt e i n a h r b e f t e e wo lo h i p a t l p l t s h s a e p e e td x d c e u i l o t m i c c o n i wi t r s o d 6 t wa h c mb n t n o t h e h l .I h s t e o i ai f RM c e u ig a g r h a d EDF c e u i g ag rt m.Ou p p r d s rb d h e a o s h d l l o t m n n i s h d l lo h n i r a e e c e te r l i t n hp b t e n t e s h d lb l y o h mi e s h d ln lo i m a d h r p ris f r a -t a k,s c s e id,e e u— i s i e w e h c e ua i t f t e o i x d c e u i g ag r h t n t e p o e t o e l i e me t s s u h a p r o xct

i g t n rs n e h n c s a y a d s f ce t c n i o f t e s h d lb l y f t e n i me a d p e e t d t e e e s r n u in o d t n o h c e u a i t o h mi e c e u i g ag rt m.An h n t e i i i x d sh d l lo h n i d te he cen y f he i f i c o t mi e s e uln ag rt x d ch d i g lo hm i e a u td i s v a e by x e me t . l e p r i n s

Ke r s: r a - i y tm; y wo d e l t me s s e RM s h d l g a g r h; DF s h d l g a g r h; c e u a i t c e u i l o t m E c e u i l o t m s h d lb l y n i n i i

实时系统是指能够在确定时间内执行计算或者处

用面较窄，定性差。如果将两者结合将是一条有效的稳

理事务并且对外部的异步事件做出及时响应的计算机系统…。实时系统最大的特点是时间的确定性，实时即性。由于实时调度算法是实时系统的核心算法，影响是实时系统实时性的最大因素，此，实时调度算法的因对研究具有重要的意义。

解决途径。本文

在这方面进行了探索，出了一种崭新提的混合调度算法，验证了算法的有效性。并

1相关工作对一些符号、念、语进行如下定义：概术——

第 i实时任务；个

R速率单调 ( ae Mo oo i)法是一种静态分配 M Rt n tnc算优先级的算法，根据任务的周期来分配优先级，期它周越小，务的优先级越高 i。而最早截止期限优先 E F任 s】 D( al s D a l e Frt算法是一种动态分配优先级的算 E ret edi i ) i n s法，根据任务的紧迫程度来分配优先级 l。在现有实它 4 l

n—任务集合中任务的数量；—e——任务的执行时间； i

p——任务] r周期； i的f—系统运行的时间，≥ 0;— t——

任务的释放时间；

时系统中，算法和 E F算法是使用最多的两种实时 RM D调度算法。是，两种算法都是在系统中单独使用，但这适

d—任务 的相对时间限 (对于释放时间 ) —相；

D——任务的绝对时间限。

基金项目：庆市科技攻关计划项目 ( S C,0 9 2 4 )重 C T 2 0 AC 1 3

《电子技术应用》2 1年第3卷第 1期 00 6 2

2 9