（计算机软件与理论专业论文）分布式实时系统任务调度算法的设计和实现.pdf

靼川大学顺+ 学位论文 分布式实时系统任务调度算法的设计和实现 计算祝软件与理论 研究生：余科攀指导老师：洪玫 随着计算机应用范围的r 益扩大，分布式实时系统应用越来越广泛。其中， 对任务调度的问题是分布式实时系统个关键的问题。合理的分布式实时系统 豹任务镄菠舞法对发挥系统豹并行髓能、保证实时任务的可溺凄性、以及傈持 网络的负载平衡都具有非常重要的意义。 论文在分摄了分布式实时系统任务豹缝季句和常见实时任务调度算法的基硝 上，着熏研究了多层分布式系统结构下实时任务的调度算法。论文研究的分布 式实时系统任务调度算法采用层次式的任务涸度策略，对分布式系统的调度层 次分两级：任务分配和任务调度。任务分配处理选择任务在什么结点上执行， 分配决策必须在调度执行决策之自f 做出。任务调度则涉及到将在同一结点的任 务按怎样的方式进行调度执行。任务分配器设置在中心服务器端。中心服务嚣 端响应实时任务请求，并按照加权轮转法分配实时任务到各个执行结点，各执 行结点按照速率优先调度算法对本遗实时任务进行调度执行。 针对分布式实时任务的多机执行的特点，为了满足任务的合理分配及系统 的负载平衡，论文研究了将任务分配到结点的调度方法，提出了基于加权轮转 的任务分配机制。根据结点处理能力的不同，采用加权队列的方法在处理能力 强的结点上分配更多的任务，而对处理能力弱的结点分配较少的任务，这样可 以合理分配任务并使任务得到尽快处理，也解决了结点处理能力不同而造成的 负载压力的问题。 分布式实时系统在同一结点上有多任务执行的特点，并嚣实时任务具有时 四川大学颂十学位论文 限要求，调度实时任务要求每个任务的执行都能够在其截止期限内完成。因此， 保证实时任务的可调度性是实时系统调度中的关键问题。单调速率( r 劬算法是 实时任务调度的基本算法，论文分析了系统采用速率单调调度算法的任务可调 度性，并在结点任务调度上使用速率单调调度算法。 关键词：分布式实时系统，任务分配，任务调度，加权轮转调度算法( w r r ) ， 速率单调调度算法( r m ) 四川大学硕士学位论文 t h e d e s i g na n d r e a l i z a t i o no ft a s k s c h e d u l i n ga l g o r i t h mi nd i s t r i b u t e dr e a l - t i m es y s t e m s s p e c iair y ：c o m p u t e rs o f t w a r ea n d t h e o r y g r a d u a t e ：y uk e - j u n s u p e r vis o r ：h o n gm e i t h ed i s t r i b u t e dr e a l - t i m e s y s t e m h a sb e e nu s e d w i d e l ya l o n g w i t ht h e d e v e l o p m e n to ft h ec o m p u t e r t h ep r o b l e mo f t a s ks c h e d u l i n gi sa k e yp r o b l e mi n t h ed i s t r i b u t e dr e a l t i m es y s t e m t h er e a s o n a b l et a s ks c h e d u l i n ga l g o r i t h mp l a y sa v e r yi m p o r t a n tr o l ei ne n h a n c i n gt h i ss y s t e m sp a r a l l e lp e r f o r m a n c ea n da s s u r i n gi t s s c h e d u l a b i l i t y , m a i n t a i n i n gi t sl o a db a l a n c ei nn e t w o r k i nt h i sp a p e r , w er e s e a r c hr e a l t i m et a s ks c h e d u l i n ga l g o r i t h mi nt h eh i e r a r c h y d i s t r i b u t e d c o m p u t e rs y s t e mb ya n a l y z i n gt a s ks c h e d u l i n gf r a m e w o r ko ft h e d i s t r i b u t e dr e a l t i m e s y s t e ma n dc o m m o n l yu s e da p p r o a c h e s t or e a l t i m e s c h e d u l i n 吕w ep r e s e n tt h es c h e d u l i n gs t r a t e g yt h a ti n c l u d e st w oh i e r a r c h i e s ：t a s k a s s i g n m e n ta n dt a s ks c h e d u l i n g t a s ka s s i g n m e n ti sd o n et od e t e r m i n eo nw h i c h n o d ee a c ht a s ke x e c u t e s t a s ks c h e d u l i n gi sd o n et od e t e r m i n et h ew a yo ft a s k p e r f o r m a n c ei nt h es a m en o d e t a s ks c h e d u l i n gm e c h a n i s mi sm o u n t e dt h ec e n t e r s e r v e r t h ec e n t e r5 e i n e rr e s p o n d sr e a l t i m et a s kr e q u e s ta n dt h e nd i s p a t c h e st h e t a s k st ot h en o d e sb yw e i g h t e dr o u n d r o b i na p p r o a c h a c c o r d i n gt 0r a t em o n o t o n i c s c h e d u l i n ga l g o r i t h m t h el o c a lr e a l t i m et a s k sa r es c h e d u l e da n de x e c u t e di nt h e n o d e a c c o r d i n gt ot h ec h a r a c t e r i s t i c so fd i s t r i b u t e dr e a l t i m et a s k s , f o rm e e t i n gt a s k a s s i g n m e n tr e a s o n a b l ya n dl o a db a l a n c i n g ，w ep r e s e n ta na s s i g n m e n tm e c h a n i s m 四川大学硕十学位论文 b a s e do nw e i g h t e dr o u n d r o b i ns c h e d u l i n ga n dt h a ti sa w a yt h a tt h et a s ki sa s s i g n e d t ot h en o d e a c c o r d i n gt od i f f e r e n tc a p a c i t i e so ft h en o d e s , w ed i s p a t c hm o r et a s k st o t h em o r ee f f i c i e n tn o d e s ，a n dt h e nl e s st a s k st ot h ei n e f f i c i e n tn o d e s 。s ot h et a s k sc a n b ea s s i g n e dr e a s o n a b l ya n db eh a n d l e de f f i c i e n t l y , a n dt h en o d e s l o a dp r e s s u r ec a n b ea l l e v i a t e d t h ed i s t r i b u t e dr e a l - t i m es y s t e mh a so n eo ft h ec h a f a c t e r st h a tl o t so ft a s k sa r e e x e c u t e di nt h es a m en o d e r e a l t i m et a s kh a sd e a d l i n e ，w h e ne v e r yt a s ki s s c h e d u l e d ，a n di tc a nm e e ti t sd e a d l i n e a s s u r i n gr e a l - t i m et a s ks c h e d u l a b i l i t yi sak e y p r o b l e mf o rt h er e a l t i m es y s t e m s r a t em o n o t 0 1 l i “r m ) s c h e “l i n ga l g o r i t h mi so n e o ft h es c h e d u l i n ga l g o r i t h m si nr e a l - t i m es y s t e m s t h i sp a p e ra n a l y s e st a s k s c h e d u l a b i l i t yt e s t su n d e rr ma l g o r i t h m ，a n dd i s c u s s e st a s ks c h e d u l i n gi nt h en o d e b yr a t em o n o t o n i cs c h e d u l i n ga l g o r i t h m k e y w o r d s ：d i s t r i b u t e d r e a l - t i m e s y s t e m s ，t a s ka s s i g n m e n t ，t a s k s c h e d u l i n g , w e i g h t e dr o u n d r o b i n ( w r r ) a l g o r i t h m r a t e m o n o t o n i c ( r m ) a l g o r i t h m i v 四川大学碗十学位论文 1 绪论 1 1 研究背景 随着计算机与自动控制技术的发展，现在，实时系统的应用非常广泛，如 数字控制、指挥控制、信号处理以及电信系统等，而这些系统每天都在为我们 提供重要的服务。当人们开车上路时，实时系统控制汽车的发动机和刹车闸， 并控制交通信号灯；当飞机飞行时，实时系统调度并监控飞机的起飞和降落、 控制其飞行、维持其航线，并且使其远离危害；当人们高兴时，还可以借助实 时系统玩跳子游戏和调动驾驶来娱乐。计算机和网络上也运行实时系统，不过 与个人计算机和工作站上运行的一些非实时系统应用( 如编辑器和网络浏览器) 不同，它们通常是在后台运行的。当实时系统正确运行且状态良好时，总使人 们忘记它们的存在。 实时系统是能及时响应外部发生的随机事件，并以足够快的速度完成对事 件的处理的计算机应用系统。所谓外部事件是指与计算机相连接的设备( 探测 设备、控制对象、键盘等) 提出的服务要求，如数据采集、情报检索、控制器 输出等。 由此可见，实时系统具有如下特点 1 ： ( 1 ) 对外部事件的响应必须在一定时间内完成。例如，雇员上下班排队打 卡时，计算机须在几秒钟内捕获卡片上的数据，如果在下一张卡片插入时末获 取数据，该数据就会丢失。同样，要求的各种输出也必须在一定时间内完成。 事实上，数据的获取、处理、已处理数据的输出，都需在特定的时问内完成。 这一时间的总和叫做系统的反应时间，其范围一般从几毫秒到几秒，缩短反应 时问是设计实时系统的关键。 ( 2 ) 必须满足一定的峰值负荷要求。一个实时系统的负荷可能是很不均匀 的，有时负荷重，有时负荷轻，甚至有可能大部分时间没有被充分利用，但整 个系统必须满足一定的峰值负荷要求。例如，实时雇员考勤系统，早上和晚上 上下班时，该系统频繁的工作，从打卡机上捕获和处理数据的能力必须满足雇 员上下班记录出勤情况的要求，而该系统在其余大部分时间没有被充分利用。 四i t l 大学硕士学位论文 ( 3 ) 与实时系统相关的另一个重要问题是，由于输入数据由系统本身捕获， 因此，该数据只有在系统中才有效，而且只能通过系统来访问。也就是说，在 故障发生时，不仅失去由系统执行的功能，而且也会失去有关的数据，使系统 不可能恢复工作，因此实时系统可靠性至关重要。 实时任务调度算法是实时系统设计和实现的关键。它的好坏，直接影响到 系统的吞吐量( 单位时日j 内系统可以处理任务的数量) 、系统的响应时间，甚 至是任务能否得以成功调度。由于实时系统的侧重点不同，实时调度亦有多种 分类方式。以下是一些常见的实时调度分类 2 5 ： ( 1 ) 按对实时性能要求的程度，实时任务可以分为硬实时( h a r d r e a l - t i m e ) 和软实时( s o f tr e a l - t m e ) 两类。 对于硬实时和软实时的定义并不统一，目前比较常用的有2 种： 从任务的结果上考虑：硬实时有很强的可确定性要求，具有明确的时间约 束，任务必须在其截止期限内执行完毕，在某个限定时刻之前不能完成任务将 导致整个应用失败；软实时也对时间敏感，但偶尔发生的不能满足严格实时要 求的情况是允许的，不过是不受欢迎的。 从任务完成的价值函数上来考虑：硬实时任务在超过截止期后，任务的价 值函数将大幅下降，甚至跌到负值；软实时任务在超过截止期后，任务的价值 函数，随任务的延迟逐渐减小。 ( 2 ) 根据任务是在一个或多个处理器上运行，分为单处理器实时调度和多 处理器实时调度。 多处理器实时调度又可分为局部调度和全局调度。单处理器调度主要需要 考虑是，在何时把系统唯一的处理器分配给哪个任务。而多处理器不仅要考虑 任务在单个处理器上的运行情况，还要考虑把任务分配到哪一个处理器上运行， 即处理器分配问题。 ( 3 ) 根据调度顺序产生的时机和方式可分为静态调度( s t a t i c s c h e d u l i n g ) 和动态调度( d y n a m i cs c h e d u l i n g ) 。 静态调度是在任务集运行之前就产生一个静态的调度表，在运行时总是按 照调度表决定从就绪任务队列中选择哪个任务来运行，这类调度算法假设系统 中实时任务的特性( 如：最坏情况执行时间、截止期、执行次序等) 全部是已 2 四川大学硕十学位论文 知的。它的可调度性分析是脱机地进行。这类调度算法适合于问题需求确定， 并且运行中不会有较大变化的情况，如简单的工业过程控制。静态调度算法的 优点是运行开销小，可预测性强。但是它的灵活性较差，不适合动态变化的， 或不可预测环境下的调度。动态调度算法是在运行期间才决定选择哪个就绪任 务来运行，它所根据的是目前已处于就绪态的备任务的相关属性，以此来决定 当前的调度序列。这类算法能够对变化的环境做出反应，因此，这类调度算法 比较灵活，适合于任务不断生成，并且在任务生成之前，其特性并不清楚的动 态实时系统，如自行机器人控制系统。但是，动态调度算法的运行开销一般较 前者大。 ( 4 ) 根据任务的作业到达时刻规律的不同，可分为周期任务( 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 ) 调度。 对于周期任务，其相邻两次作业到达时刻之间的间隔是一个固定的常数( 即 周期) 。问发任务是指相邻两次作业到达时刻之间的间隔不固定，但有一个下限 值。非周期任务的作业到达时刻没有规律。 ( 5 ) 根据调度方法是否具有自适应功能，可分为自适应调度和非自适应调 度。 由于实时任务的调度足直接影响分布式实时系统性能的关键因素，因此研 究分布式实时系统的任务调度策略是十分有必要和有意义的。 1 2 实时任务调度算法的研究现状与发展趋势 1 2 1 单处理器调度 计算机硬件及实时应用不断发展，单处理器系统的调度理论逐渐成熟，调 度技术也在不断丰富和发展，并在实际中得到了广泛的应用。目前 对单处理器 调度算法主要有： 速率单调调度算法( r m ) r m ( r a t em o n o t o n i cs c h e d u l i n g ) 调度算法在实时调度算法中起到过很大 3 四川大学硕卜学位论文 的作用。r m 算法是针对周期任务而占的优先级调度算法，任务的调度优先级由 任务周期确定，周期越短的任务，优先级别越高；周期越长的任务，优先级别 越低。这种定义优先级别的方法容易理解，周期任务总应该在下一个周期到来 之前完成当前这个周期，否则就会错过时限，较短周期的任务应该尽量先调度先 完成，以免错过任务时限。 截止时间单调调度算法( d m ) d m ( d e a d l i n em o n o t o n i cs c h e d u l i n g ) 调度算法是在跚算法之后发展起 来的一种固定优先级调度算法。在d m 调度算法中，任务优先级由任务时限来决 定，时限宽度越小，优先级别越高，时限宽度越长，优先级别越低。采用任务 时限作为任务优先级别是基于这种思想：时限宽度越小的任务，越需要紧急处 理，否则使得任务越过其时限而得不到调度，从而影响系统的实时性。 最早时限优先调度算法( e d f ) e d f ( e a r l l e s td e a d l i n ef i r s ts c h e d u l i n g ) 调度算法表示时限最早的任 务优先调度。e d f 算法是调度理论中一个很重要的动态调度算法，e d f 调度算法 对同步周期任务组是最佳调度算法。在e d f 算法中，任务调度优先级定义为： 碡如) 一t ，西厅j 是任务时限。这种调度优先级定义方式，表明了在每个时刻， 都要计算下个时刻系统中哪个任务的时限最小，从而决定了系统在下个时刻应 该调度哪个任务。e d f 调度算法在每个时刻都要计算处于等待调度状态的任务 调度优先级，工作量比较大，系统下个时刻调度的任务是不确定的，与系统中 其它任务有关系，这种方法使得系统适应性比较好。 m l l f 调度算法 l l f 是l e a s tl a x i t yf i r s t 的缩写。l l f 算法和e d f 算法可看作同类型的 调度算法，e d f 调度算法以最近时限的任务作为最先调度的任务，优先级计算 公式为：盔詹) - t ，l l f 算法是以剩余时间最少的任务作为最先调度的任务，优 先级计算公式为西矗j - t - e i 厅 m l l f 是m o d i f i e dl e a s tl a x i t y 的缩写。m l l f 调度算法相对于e d f 和l l f 调度算法来说，是更为普遍的最佳调度算法，其优 先级计算公式为：函厅) t ，x e i “ f 取值在0 到l 之间。 4 四川大学硕十学位论文 1 2 2 多处理器调度 多处理器调度有局部调度和全局调度两类实时调度方法。局部调度将任务 分配给特定处理器，每个处理器维护本地任务等待队列，调度是局部化的。全 局调度将所有等待调度的任务组成全局等待队列，等待处理器调度，处理器允 许调度任务时，选择优先级最高的任务执行，调度是全局化的。 全局p f a i r 公平调度算法 p f a i r 调度是指系统中各个实时任务按比例公平使用共享资源，共享资源可 指处理器或其他共享资源。p f a i r 公平调度算法核心是确定子任务调度优先级。 目前有3 种p f a i r 调度算法 6 ；p d 、p f 、p d 2 。这3 种调度算法都是将子 任务时限作为调度优先级，不同之处在于：当两个子任务时限相同时，确定任 务优先级方式不同。p d 2 是在p d 算法基础上发展而来的更有效的调度算法，引 入了组时限概念，当子任务时限相同时，根据任务组时限确定优先级，如果组 时限也相同，则认为这两个任务调度优先级相同，处理器可任意选择一个任务 调度。 局部调度算法 局部调度的工作过程是：首先给各个任务分配处理器，任务分给处理器后， 任务调度可看做单处理器实时任务调度。经过2 0 多年的发展，单处理器系统中 的实时调度技术相对成熟，有一系列从算法到可行性分析的工具。因此，局部 调度算法是目前多处理器流行的调度算法。而目前常用的局部调度算法是 e d f - f f 算法。它是采用f f ( f i r s tf i t 任务分配给第1 个可接受它的处理器) 方法分配处理器：各个处理器按照e d f 算法调度任务。 1 2 3 分布式实时调度 为了充分利用分布式环境中多处理机的并行处理能力，以及提高系统性能 并保证任务的实时性，一个任务往往根据不同的数据约束关系和计算要求分解 成多个子任务。对于任务的分配，是将分解后的若干子任务指派到分布式系统 的各个节点机或节点内的各个处理器上的过程；而任务调度是根据予任务间的 5 四川i 大学硕士学位论文 数据约束关系合理地安排每个处理机上子任务的执行顺序的过程。 这里介绍两种分布式实时调度算法：以r m s 为基础的广义r m s 调度；以风 车调度s r 为基础的d s r 调度 7 9 。 ( 1 ) g r m s g r m s 将r m s 用于分布式实时系统，对跳s 的一些基本概念如可调度性、可 抢占性等进行了扩展，同时还引入了一些概念，如系统一致性等。 g r s 算法的实现步骤为： 1 ) 将子任务分配到各个站点； 2 ) 将分布式任务的端到端死线分配给每个子任务： 3 ) 同步每个子任务的周期； 4 ) 每个结点按r m 或死线r m 来调度； 5 ) 进行可调度性检验。 ( 2 ) d s r 在一些实时系统中，任务必须以距离约束的方式执行。距离约束是指：同 一任务两次相继完成的时间间隔应该总是小于或等于某一段时间，这样的实时 系统称为距离约束任务系统( d c t s ) 。 问题描述：令x = x ， 是一分布式系统的事务( 分布式任务) 集，l i n ， 系统的结点数为m ，r 。是运行在结点n ，上的事务x 。的任务，r 。，的距离约束为d ， 执行时间为c ”不失一般性，设d i d i + 。另外，假设所有事务都有同样的执 行结点顺序，这罩的事务由运行在不同结点的一组连续任务组成。 d s r 算法产生多点风车调度周期，可以保证分布式实时系统中任务调度无 抖动。d s r 有如下定理： 定理给定一个分布式d c t s 集x ，n 个事务运行在m 个结点上。设 p j ) c 口d ，为结点n j 的密度，如果对于，巧p ) i 2 1 和，则x 用d s r 可调度。 分布式实时系统的任务调度是在分布式系统调度的基础上，尽量增加任务 并行度、减少并行运行时任务日j 的通信开销和等待时间，使实时任务的响应速 度尽可能快，任务的执行时间尽可能短，从而改善系统负载的均衡性，最终优 6 四川大学硕士学付论文 化系统运行效率。因为实时环境下的调度算法总是在满足周期任务的时间约束 条件后，才考虑尽量缩短弱实时非周期任务的响应时间，所以对周期性任务的 调度问题足分布实时系统任务调度策略研究的核心问题。 综上所述可知，对实时系统的调度算法研究很多，每一种算法对有其研究 的特性。当前实时任务调度算法研究的主要方向集中在硬实时与软实时相结合 的任务调度、在多种条件制约下的任务调度、单处理器调度和分布式实时调度 算法等。对于各自的特定的实时系统的环境，给出了特定的实时系统所存在的 问题的优化调度算法。因此，对实时调度算法的研究，是实时领域的一个重要 的研究课题。 1 3 分布式系统任务调度的意义 在一个分布式系统环境中，大部分结点在大部分时间内都处于低利用率状 态。加州大学b e r k e l e yn 0 w 研究小组的研究结果表明：即使在每天下午最繁忙 的时候，平均也有近6 0 的结点处于空闲可利用状态。分布式系统中这些空闲 结点，如果不加以合理的利用，其c p u 等计算资源就白白的浪费了。而实际上在 一个局域网或高速网络内，在适当的任务调度机制的控制与管理下，可以充分 利用这些闲置结点来执行大规模并行计算 1 0 。 另外，当一些处理器处于重载时，另一些处理机却处于轻载或闲置状态， 在系统中就出现了负载不平衡的现象。负载的不平衡对分布式系统的整体性能 有直接影响。因此，要提高系统性能，就有必要在分布式系统中，要求任务的 分配和调度做到负载平衡。 在论及任务调度的必要性时，r i c h a r df f r e u n d 等人列举过一个假设具有 多层并发度计算需求的计算实例 1 0 。经计算分析表明，“该程序对于普通串 行机需要运行1 0 0 个时间单位，对于向量机需要5 0 个时间单位，而采用由5 种机器构成的分布式系统，计算过程仅需5 个时间单位。显然，后者所付出的 代价是：必须进行适当的任务分解、分配和调度。” 7 四j i l 大学颂七学位论文 1 4 本文主要工作 本课题的主要任务是设计和实现分布式实时任务调度算法。具体有： 1 分析了分布式任务调度的结构，将系统分成层次式的予系统，以分散其 集中式控制整个系统的负载平衡。论文采用层次式的任务调度策略，对分布式 系统的调度层次分两级：任务分配和任务调度。任务分配处理选择任务在什么 结点上执行，分配决策必须在调度执行决策之i i f 做出。任务调度涉及到将任务 按怎样的方式进行调度执行。 2 针对分布式实时任务的多机执行的特点，为了满足任务的合理分配及系 统的负载平衡，论文研究了将任务分配到结点的调度方法，提出了基于加权轮 询的任务分配机制。根据结点处理能力的不同，采用加权队列的方法在处理能 力强的结点上分配更多的任务，而对处理能力弱的结点分配较少的任务，这样 可以合理分配任务并使任务得到尽快处理，也解决了结点处理能力不同而造成 的负载压力的问题。 3 针对分布式实时系统的特点及实时任务的特点，在结点上任务的调度， 论文采用速率单调调度算法进行分析。讨论了速率单调调度算法的可调度性， 并在结点任务调度上使用速率单调调度算法详细分析了任务的可调度性，最后 简要讨论了任务的执行。 1 5 本文的内容组织结构 第一章介绍了实时调度算法的研究背景，并总结了实时任务调度算法的研 究现状与发展趋势及分布式系统中任务调度的意义，最后总结了本文主要工作 和本文的内容组织结构。 第二章分析了分布式任务调度主要的结构：集中式调度，分布式调度和层 次式调度，并对实时调度理论进行了研究，主要分析了常见的几种静态和动态 调度算法，最后一节分析了本文使用的两种调度方法。 第三章详细设计了分布式系统实时任务调度算法的总体结构，并对两层结 构进行了详细的设计分析。 第四章主要讨论了分布式系统实时任务调度算法的实现，主要分为三个部 8 四川大学硕士学位论文 分：第一部分概述了研究采用的试验平台；第二部分实现了用固定权值的加权 轮转调度算法和动态权值的加权轮转调度算法进行任务分配；第三部分是用速 率单调调度算法对结点上的任务进行调度分析。 第五章首先总结了算法的评价标准，然后简要评价了本文研究的分布式实 时系统任务调度算法。 第六章对本文所做工作进行总结，并提出对分布式实时任务调度算法的进 一步改进。 9 四川大学硕士学位论文 2 分布式任务调度及实时调度理论研究 2 1 分布式任务调度概述 2 1 1 分布式系统任务调度结构 在分布式系统中，任务调度算法按照调度程序的结构或调度程序所收集调 度信息的范围，可以分为集中式调度算法、分布式调度算法和层次式调度算法 1 0 。 2 1 i 1 集中式调度算法 集中式调度算法系统中有一个负责调度的主机负责搜集系统负载信息。它 维护着一个任务分配表，并且根据系统负载状况来分配任务。其它的主机都是 计算主机，计算主机只负责接收任务，如图2 一l ： 图2 - i 集中式调度结构 这种策略的优点是： ( 1 ) 调度主机拥有全局信息，易于进行决策并保持负载平衡，易于跟踪执 行情况。 ( 2 ) 算法比较容易实现，适用于结点数目比较少的网络环境，在总线型网 络上有比较好的性能。 这种策略的缺点是： ( 1 ) 单个调度主机要处理大量信息，特别当任务增多时，冲突增多，调度 四川大学颂十学位论文 主机明显成为瓶颈。 ( 2 ) 在调度主机收集所有主机的信息时，计算主机需要等待，浪费了计算 主机的处理能力。 在集中式调度策略中，单一的调度结点会成为瓶颈，为了消除调度结点的 瓶颈问题首先需要分析调度结点要处理的负载。调度结点的负载主要由三部分 组成： ( 1 ) 与所有任务结点的通信，包括发送任务开始所需的参数和接收任务结 束时的结果： ( 2 ) 调度结点做出决策前，收集所有计算结点的负载信息； ( 3 ) 调度结点根据收集的信息，做出任务调度策略，从而保持整个系统的 负载平衡。 基于对调度结点的负载分析，调度策略主要应考虑分散调度结点的负载， 使其不再成为瓶颈，为此可以采用计算结点主动报告策略。 2 1 1 2 分布式调度算法 分布式调度算法是根据局部范围内的一些结点机的负载信息来进行负载平 衡调度操作，不再有一个集中的调度主机，每个主机只与一部分主机通信。按 负载平衡调度的启动者来划分，这类调度策略主要有：发送者驱动策略，接收 者驱动策略和混合驱动策略。 分布式的调度算法的主要优点是可扩放性好，适合结点数较多的大规模并 行分布系统。主要缺点是：( 1 ) 算法复杂，难于实现；( 2 ) 没有全局信息， 难于跟踪程序运行。 图2 - 2 分布式调度结构 四川大学硕士学位论文 可以采用分组的方法来加以改进。分组的方法是按照相邻的结点进行分组， 每个组选定一个结点作为该组的调度结点。调度结点通常是该组结点与其它组 结点相连的通信关键结点，如图2 - 2 。根据具体情况可将所有结点分为两类： 调度结点和计算结点。不过，这里的调度结点不再是只限于一个结点，可能是 多个结点，这样调度结点的负载就被分布了。 2 i 1 3 层次式调度算法 层次式调度算法是根据集中式、分布式方法的优缺点结合而成的一种任务 调度方法，它将系统分成层次性的子系统，在不同层次上特殊的结点作为负载 平衡决策的调度结点，以分散其集中式控制整个系统的负载平衡。 这哩只介绍两层调度，调度结点依据它们的功能分为两层。所有的调度结 点依据它们的调度关系形成一棵树，如图2 - 3 。首先有一个总的调度结点一一 第一层调度结点，第一层调度结点可按任务复杂性派生多个子调度结点一一第 二层调度结点，并由第二层调度结点来直接分配任务给计算机结点。 图2 3 层次式调度结构 一层调度主机 二层调度主机 计算主机 将上述调度结点的第一部分和第三部分工作分布到多个调度结点，每个第 二层调度结点只负责调度一部分任务，第一层调度结点负责管理第二层调度结 点，第一层调度结点不直接调度任务，而是根据任务之间的耦合关系将所有任 务分成一组到多组，分给不同的第二层调度结点处理。任务划分的基本原则是 四川大学硕十学位论文 尽可能使消息传递本组化，即划分后的任务组与任务组之间的通信尽可能少， 大部分的通信应在任务组内。此外，还需要考虑以下几个方面的因素： 1 调度结点的能力。即根据调度结点的能力确定是否需划分，应分为几组。 2 划分后的各个任务组的任务数须相差不大。 通过这种层次调度，将原来一个调度结点要完成的工作，分布到多个调度 结点来完成，从而较好的解决调度结点的瓶颈问题。 2 1 2 分布式系统中引起负载不平衡的原因 分布式系统中的负载不平衡是指在系统中出现有的结点机处于空闲状态， 而有的结点机一直在运行，处于重载状态。 在分布式系统中引起负载不平衡的因素非常多，如： 1 任务分配：分布式系统在同一结点上有多任务执行的特点，每个任务以进程 的形式同时存在，若一些结点上分配到较多的任务，一些结点分配到较少任 务，可能引至负载不平衡。 2 任务划分：以功能分解为主的并行程序，由于各部分功能的计算量不一，难 达到负载平衡，然而以数据分解为主的并行程序，较易达到负载平衡。 3 同步：通信延迟使得各个任务交换数据的时候，要进入阻塞状态，直至消息 传递完成才能继续计算。 4 机器负载：主要是指虚拟机中某些主机上可能正执行一些非并行的其它进 程，降低这些机器的计算机能力，若此问题与同步问题同时出现，必将引起 分布式系统的计算能力大幅下降。 5 网络负载：由于分布式系统中的网络环境为多用户共享，网络处于繁忙状态， 将导致任务间的通信延迟增大，负载过重，在此情况下进行同步，将引起负 载不平衡。造成网络负载过重的原因之一就是一些并行程序在同一时间各任 务之间交换数据，这样将使负载不平衡。 还有各主机的计算能力不同等。因此，对于系统中出现负载不平衡的情况， 需要采取一定的调度策略，合理地分配任务，并调度任务到各个工作结点上， 保证总任务尽快完成，或者保证系统的其他性能达到最优。 四 1 l 大学硕七学位论交 2 2 调度算法概述 调度算法用于决定在任一时刻哪一个就绪的任务将获得c p u 的执行权利。 本文中讨论的调度算法主要有两个：加权轮转调度算法和基于优先级的抢占式 调度。 我们将加权轮转调度算法的思想用在任务分配中；而基于优先级的调度方 式，是目前在硬实时系统中主要采用的实时调度方式，基于一般情况，抢占式 调度优于非抢占式调度，所以在这罩采用基于优先级的抢占式调度。 按照优先级的分配方式，实时调度算法又可分为静态( s t a t i c ) 和动态 ( d y n a m i c ) 两种。静态调度算法( 也称为固定调度算法) 是指任务的优先级一 经分配，在整个任务的执行过程中将不再改变；而动态调度算法中任务的优先 级可以在执行过程中改变。 下面我们给出几个常用的实时调度算法： 2 2 1 常见静态调度算法 速率单调调度算法( r m ) r m ( r a t em o n o t o n i cs c h e d u l i n g ) 调度算法在实时调度算法中起到过很大 的作用。这种算法执行起来很简单，很容易理解。跚s 算法是针对周期任务而言 的优先级调度算法，任务的调度优先级由任务周期确定，周期越短的任务，优 先级别越高；周期越长的任务，优先级别越低。这种定义优先级别的方法容易 理解，周期任务总应该在下一个周期到来之前完成当前这个周期，否则就会错 过时限，较短周期的任务应该尽量先调度先完成，以免错过任务时限。 在采用r m 调度算法时，任务要进行调度可行性检查，检查r m 调度算法能否对 这种任务组产生合理的调度。r 调度算法在任务周期等于时限的同步实时任务 系统中，是最佳调度算法。 r m 算法的优点是易于实现，运行时的开销较小，但它也存在不足之处。 截止时间单调调度算法( d m ) 截止时间单调调度( d e a d l i n em o n o t o n i cs c h e d u l i n g ) 是在速率单调调度 1 4 四川大学硕士学位论文 的基础上发展起来的。它采用按截止时间来分配任务的优先级。截止时间短的 任务优先级高，截止时间长的任务优先级低。 截止时间调度具有与速率单调算法相同的优点。运行开销小，可调度性测 试简单等。在任务的截止时间小于或等于其周期的情况下，截止时间单调调度 已被证明是静态最优的调度算法 1 1 ，因此截止时间算法中放松了对任务的周 期必须等于其截止时间的限制。 速率单调调度和截止时间调度理论已发展的较为成熟，由于它们的调度性 能和易实现性都较好，被广泛的应用于实时系统中，是实时调度的支柱。 2 2 2 常见动态调度算法 最早时限优先调度算法( e d f ) 最早时限优先调度( e a r l i e s td e a d l i n ef i r s t ) 算法是一种时限驱动的动 态可抢占优先级实时调度算法。在e d f 的实时调度模型中，包含由n 个实时 任务组成的任务集n ( t 。1 。，t ) ，且所有实时任务必须满足以下限制条 件： 1 ) 所有实时任务均为周期任务，且周期大于或等于时限； 2 ) 所有实时任务必须在其时限到来前结束； 3 ) 所有实时任务相互独立； 4 ) 所有实时任务均具有恒定的运行时间。 e d f 以任务的时限与当前时刻的距离确定任务的优先级( 我们将这一距离 称为时限距离) ，距离越近，优先级越高，反之则越低。因此，e o f 总是选择当 前最迫切需要完成的任务获得处理器。 e o f 调度算法的最大优点是处理器的利用率可达1 0 0 。除此，由于任务的 优先级是动态变化的，因而能很好地支持周期动态变化的任务。然而，e d f 调 度算法也存在有不足之处，如不能预测任务计算的成功性、瞬时过载时的非确 定性等。 最小松弛度优先调度算法( 札f ) m l f 调度算法针对e d f 调度算法的局限性，m l f 不仅考虑了任务的时限 网川大学碗 学位论文 d i ，而且考虑了任务ti 的运行时间c i 。松弛度l i 定义为l i = 时限时问一当前 时间一还需要的运行时间= 时限时间d i 一运行时间c i ，其物理意义为：即使任 务ti 被延迟l i 个时间单元，任务ti 也能在时限d i 到达之前完成其计算。在 札f 调度算法中，松弛度l i 的值越小，其优先级越高，反之则越低，且具有最 小l i 值的任务先执行。 1 4 l f 调度算法同e d f 调度算法一样，也属于动态调度算法，其处理器的利 用率也可达1 0 0 ，但与e d f 调度算法不同的是，m l f 调度算法考虑了任务的运 行时间c i ，而e d f 调度算法则未考虑。同e d f 调度算法一样，在任务量瞬时 过载的情况下，帆f 调度算法也不能控制或预测任务的失败与成功，因此也不 能保证关键任务成功地完成其计算。 动态调度算法与静态调度算法相比，具有更好的适应性，并且能够达到更 好的性能，但是动态调度算法本身就较为复杂，并且实现也相对困难，而静态 调度算法无论是在理论上还是实践中，相对就里简单，因此本文在结点中考虑 的单处理机调度算法选择速率单调调度算法。 2 3 本文采用的调度方法 2 3 1 加权轮转调度方法 加权轮转调度算法( w r r ) 1 2 1 3 的基本思想就是给每一个子队列分配一 个权值，然后根据权值来调度不同的子队列中的数据包。对于w r r 调度算法而言， 在每一个分组( 数据包) 的大小一致时，能提供很好的公平性，但如果分组的 大小不一致，就会对分组较小的队列带来不公平。w r r 调度算法的权值是固定分 配的，如果某一服务等级的分组到达速率较大，而其他服务等级的分组到达比 较平稳时，由于每一服务等级的存储容量有限，可能会导致到达速率较大的服 务等级的分组大量丢失，而其他服务等级的数据存储单元大量空闲，造成不必 要的分组丢失。但是如果采用存储单元的动态分配机制，可能会引起其他服务 等级的分组丢失，不恰当的存储单元动态分配机制还可能会导致低优先级的数 据饥饿现象。因此，对于w r r 的改进就显得特别重要。但是这个算法有一个突出 1 6 四川大学硕士学位论文 的优点就是开销小，容易实现。 由于权值固定分配的特性，w r r 调度算法不能实时地调整各子队列的权值。 因此，在许多文献中基于w r r 的这种缺陷，提出了如何调整各子队列的权值进行 w r r 算法的改进，但是在这些算法中，设计较为复杂，实现较为困难，本文基于 以上原因，提出一种基于贫富尽量平均分配原则的w r r 算法，虽然在w r r 算法的 改进中采用的是固定w i 值，但是这是一种改进权值的发展方向的基础，通过 这个基本的改进权值的方法，那么以后在实际应用中，可以基于这个基本思想， 采用预测或者动态评估w i 值，而无须再用测量器或其它较复杂的手段来确定 w i 值。 2 3 2 速率单调调度算法 l i u 和l a y l a n d 于1 9 7 3 年1 月发表了“s e h e d u l i n ga l g o r i t h mf o r m u l t i p r o g r a n m i n gi nah a r dr e a lt i m ee n v i r o n m e n t ”一文 1 3 3 ，从此速率 单调分析这个术语诞生了。在这篇实时调度理论的经典论文中，l i u 和l a y l a n d 提出了一个简单有效的按实时任务的发生频率来分配任务的优先级的方法。任 务发生的频率越高，分配的优先级也就越高，这种优先级的分配方法被称为速 率单调算法( r m a ：r a t em o n o t o n i ca l g o r i t h m ) 。 r m 调度算法在实时调度算法中起到过很大的作用。这种算法执行起来很简 单，很容易理解。i i j l 算法是针对周期任务而言的优先级调度算法，任务的调度 优先级由任务周期确定，周期越短的任务，优先级别越高；周期越长的任务， 优先级别越