（计算机软件与理论专业论文）并行分布计算中的调度问题研究.pdf

中国科学技术大学博l 学位论文 摘要 调度问题( s c h e d u l i n gp r o b l 鲫) 是组合优化中的一类基本问题，其核心 内容是如何高效的使用稀缺资源，即将一些任务有效的安排在若干台机器上进 行处理，而使某个目标达到最优。根据任务特性、机器特性和优化目标的不同， 调度问题包含了成百上千个不同的调度模型。 应用数学、计算机科学、管理科学等不同领域中的众多学者出于各自领域的 兴趣，都对调度问题进行研究，在理论上和应用上均得到了许多重要结果。在并 行分布计算中存在着大量的调度问题。这些调度问题解决的好坏对于并行分布计 算系统的性能有着直接的影响，因此针对这些调度问题进行算法研究，可以充分 有效的提高并行分布式系统的能力，具有重要的理论价值和广泛的应用前景。 本文就并行分布式环境下的调度问题进行了研究，具体内容有： ( 1 ) 具有中断时间代价的一致并行调度问题的研究：证明了这是一个n p _ h a r d 问题，给出了一个时间复杂度为d ( n l o g ”+ 州) 的脱线近似算法，其近似比小于等 于1 4 0 8 2 5 ：分析了该问题的在线特性，给出一个线性时间复杂度的在线近似算 法，其竞争比为2 。 ( 2 ) 存在可用性限制的机器模型上的在线调度问题研究：考虑了两类不同模 型上l s 算法的性能以及问题本身的下界：在任何一个时刻至少有一台机器可用 的问题中，证明l s 算法的竞争比为m + 1 ；在任何一个时刻至多有一台机器不可 用的机器模型，证明l s 算法的竞争比为3 ，并给出最优在线算法的竞争比下界 为2 5 。最后通过实验模拟说明l s 算法用于存在可用性限制的机器环境上时， 具有良好的实际性能。 ( 3 ) 分布式网络上任务调度问题研究：针对一种已有的分布式计算模型( 单 位长度的任务由处理器独立产生，没有全局控制，彼此通信需要花费时间) ，研 究了在线性网络上的任务有效调度问题。通过考虑算法中任务处理时间和通信时 间之间的平衡，给出了一个近似比为5 8 8 的分布式算法，该算法无需全局信息， 且处理策略简单。对该问题的近似比下界也做了研究，证明了该问题不存在近似 比小于1 1 6 的算法。同时，研究了改进后的分布式计算模型中环状网络上的算 法，得到了近似比为3 4 4 的有效算法。 中国科学技术大学博士学位论文 ( 4 ) 类似于s e t i h o m e 的大规模p 2 p 计算系统中的调度策略研究：提出了 相应的理论模型来描述其中的任务调度问题。在此基础上，评估现有的几种不同 的调度策略，设计了新的根据具体的网络环境和计算资源进行选择的调度策略， 通过理论分析和实验分析说明该策略较之现有策略有更好的性能，并将该调度策 略应用于实际系统中。 本文的主要贡献和创新有： ( 1 ) 提出了具有中断时间代价的致并行机调度问题，给出了近似比为常 数的近似算法，证明了问题求解难度和近似难度； ( 2 ) 研究了多台机器条件下具有不可用时段的调度问题，分析了经典在线 算法的性能并证明了问题的近似难度； ( 3 ) 针对线性网络和环状网络，研究了分布式计算环境下的任务调度模型， 证明了问题的难解性，给出了近似性能良好的调度算法； ( 4 ) 研究了对等计算环境下任务调度问题，给出了相应的调度模型，针对 已有策略的不足设计了新的策略。 关键词：调度问题，并行计算，分布式计算，近似算法，f 界 中国科学技术大学博上学位论文 a b s t r a c t s c h e d u l i n gp r o b l e m sa r eo n ek i n do fb a s i cp r o b l e m s i nc o m b i n a t i o n o p t i m i z a t i o n t h e ya r ec 。n c e r n e dw i t ht h eo p t i m a la 1 1 0 c a t i o no fs c a r c e r e s o u r c e st oa c t i v i t i e so v e rt i m e m o r eg e n e r a l l y ，s c h e d u l i n gp r o b l e m s i n v 0 1 v ej o b st h a tf 【| u s tb es c h e d u l e do nm a c h i n e ss u b j e c tt oc e r t a i n c o n s t r a i n t st o o p t i m i z e s o m e o b j e c t i v e f u n c t i o n f o rd i f f e r e n c eo f m a c h i n ee n v i r o n r n e n t ，s i d ec o n s t r a i n t sa n dc h a r a c t e r i s t i c s ，o p t i m a l i t y o b j e c t s ，s c h e d u l i n gp r o b l e m sc o n t a i nt h o u s a n d so fd i f f e r e n ts c h e d u l i n g m o d e l s m a n yr e s e a r c h e r si nd i f f e r e n tf i e l d s ， s u c ha sa p p l i e dm a t h e r n a t i c s ， c o m p u t e rs c i e n c e ，m a n a g es c i e n c e ：h a v ea c h i e v e dl o t so fi m p o r t a n tr e s u l t s o ns c h e d u l i n gp r o b l e m si nb o t ht h e o r ya n da p p l i c a t i o n i np a r a l l e la n d d i s t r i b u t e dc o m p u t i n g ，t h e r ea r eam a s so fs c h e d u l i n gp r o b l e m s s o l v i n g t h e s e s c h e d u l i n gp r o b l e m s h a sa s t r o n gi m p a c t o nt h e p a r a l l e l a n d d i s t r i b u t e dc o m p u t i n gs y s t e m s t oi m p r o v et h ep e r f o r m a n c eo ft h ep a r a l l e l a n dd i s t r i b u t e ds y s t e m se f f e c t i v e l y ，r e s e a r c ho nt h ea l g o r i t h m so ft h o s e s c h e d u l i n gp r o b l e m sa r e v a l u a b l ei nt h e o r ya n dp r a c t i c e i nt h i sp a p e r ，s o m es c h e d u l i n gp r o b l e m si np a r a l l e la n dd i s t r i b u t e d c o m p u t i n ga r e s t u d i e da sf 0 1 1 0 w s ( 1 ) ap r e e m p t i v es c h e d u l i n gp r o b l e mi sp r e s e n t e d ， i nw h i c ha n a d d i t i o n a lt i m ec o s ti sn e e d e di faj o bi si n t e r r u p t e do n c e t h i sp a p e r s h 。w st h a tp r o b l e mi san p h a r dp r o b l e m ， p r e s e n t sa no f f l i n e a p p r o x i m a t i o na l g o r i t h mw i t ht i m ec o m p l e x i t yo fo ( n l o g n + m ) a n da p e r f o r m a n c er a t i on om o r et h a n1 4 0 8 2 5 t h eo n 一1 i n ep r o p e r t yi sa l s o s t u d i e da n da no n 一1 i n ea l g o r i t h mw i t hl i n e a r i t yt i m ec o m p l e x i t ya n da c o m p e t i t i v er a t i oo f2i sp r o p o s e d ( 2 ) w ec o n s i d e r st h eo n l i n es c h e d u l i n go ni d e n t i c a lm a c h i n e sw i t h m a c h l n ea v a i l a b i l i t yc o n s t r a i n t sa n da n a l y z eo ft h ep e r f o r m a n c eo ft h e l sa l g o r i t h ma n dt h el o w e rb o u n do nt w ot y p i c a lm a c h i n em o d e l s ：1 t h e r e d ! 璺羔! 兰垫查查兰堡兰垒鲨苎 i sa tl e a s to n em a c h i n ea v a i l a b l ea ta n y t i m e ， a n dg i v et h ec o m p e t i t i v e r a t i oo ft h el sa l g o r i t h mi sm + 1 ：2 t h eu n a v a i l a b l et i m eo ft h em a c h i n e s d on o to v e r l a pa n ds h o wt h ec o i i l p e t i t i v er a t i oo ft h el s a l g o r i t h mi s3 ， w ef u r t h e rg i v et h el o w e rb o u n do ft h eo n l i n ep r o b l e mi s2 5 w e c o m d a r e t h ep e r f o r m a n c e so ft h el sa l g o r i t h ma n dt h e t y p i c a lo f f 一1 i n ea l g o r i t h m ( l p t ) b yp r o g r a 哪i n g ，a n da sas 0 1 u t i o n ，w es h o wt h a tt h ep e r f o r m a n c eo f t h el sa l g o r i t h i i 】i s g o o di np r a c t i c e ( 3 ) w ea i m sa ta ne x i s t e dd i s t r i b u t e dc o m p u t i n gt h e o r e t i c a lj l 】o d e l ， i nw h i c hp r o c e s s o r sg e n e r a t eu n i tj o b si n d e p e n d e n t l y ， n oc o n t r o la n dt h e c o m m u n i c a t i o n so f p r o c e s s o r s s h 。u l d s p e n d t i m e t h e j o bs c h e d u l i n g p r o b l e mi nli n e a rn e t o r k si ss t u d i e d t h i sp a p e rc o n s i d e r st h eb a l a n c e s o f j o bp r o c e s s i n ga n dc o m m u n i c a t i o n so f p r o c e s s o r s a n d p r o p o s e s a d i s t “b u t e da l g o r i t h mw i t h o u t a n yg l o b a li n f o r m a t i o na n dc o m p l i c a t e d o p e r a t i o n ，w h i c hh a sap e r f o r m a n c er a t i on om o r et h a n5 ，8 8 t h e1 0 w e rb o u n d i sa i s os t u d i e di nt h i s p a p e r i ts h o w st h a tt h e r ei sn od i s t r i b u t e d a l g o r i t h mw h i c ha p p r o x i m a t i o nr a t i ol e s st h a n1 1 6 t h ea l g 。r i t h m so n r i n g sa r ea l s os t u d i e d 0 na nu p d a t e dm o d e l ，a na l g o r i t h mi sp r e s e n t e d ， _ 出i c hyi e l d ss c h e d u l e so fl e n g t hn o r et h a n3 4 4t i m e so p t i m a l ( 4 ) i nt h ea p p l i c a t i o n so fp 2 pc o m p u t i n g1 i k es e t i h o m e ，t h es c h e d u l i n g p r o b l e mo fc o m p u t a t i o nc o m p o n e n t si sa nij i l p o r t a n ti s s u et o i m p r o v et h e p e r f o r m a n c e w ep r o p o s eat h e o r e t i c a lm o d e lo fp 2 pc o m p u t i n ga p p l i c a t i o n i 九 l a r g e s c a l ep l a t f o r m c o n c e r n i n g t h e s c h e d u l i n g o f c o m p u t a t i o n c o m p o n e n t s b a s e do nt h em o d e l ， w ee v a l u a t et h ep e r f o r 丁n a n c eo fd i f f e r e n t s c h e d u l i n gm e c h a n i s m st oc h o o s eap r o p e rs c h e d u l i n gs t r a t e g yf o r t h e a p p l i c a t i o na c c o r d i n gt ot h ec o r r e s p o n d i n gn e t w o r ke n v i r o n m e n ta n d c o m p u t i n gr e s o u r c e s f i n a l l yw em a k et h ec o m p a r i s o n sa m o n gd i f f e r e n t s e h e d u l i n gs t r a t e g i e sa n ds u g g e s t i o n st oi m p r o v et h ep e r f o r m a n c eo ft h e a p p 】i c a t i o n i nt h i s p a p e r ， t h em a i nc o n t r i b u t i o n sa n di n n o v a t i o n sa r es h o w na s f 0 1 o w s ： - 5 。 中国科学技术大学博上学位论文 ( 1 ) an e wp r e e m p t i v es c h e d u li n gp r o b l e mi sp r e s e n t e d ， i nw h i c ha n a d d i t i o n a lt i m ec o s ti sn e e d e di faj o bi si n t e r r u p t e do n c e t h eh a r d n e s s o ft h i sp r o b l e mi sp r o v e da n da na l g o r i t h mw i t hc o n s t a n ta p p r o x i m a t i o n r a t i oi sg i v e n ( 2 ) t w oo n l i n es c h e d u l i n gp r o b l e m so n i d e n t i c a lm a c h i n e sw i t h m a c h i n ea v a i l a b i l i t yc o n s t r a i n t sa r ec o n s i d e r e da n dt h ep e r f o r m a n c eo f t h el sa l g o r i t h ma n dt h el o w e r b o u n d sa r es t u d i e d ( 3 ) o na ne x i s t e dd i s t r i b u t e dc o m p u t i n gt h e o r e t i c a lm o d e l ，j o b s c h e d u l i n gp r o b l e m si nl i n e a ra n dr i n gn e t w o r k sa r es t u d i e d t h eh a r d n e s s o ft h o s ep r o b l e m si sp r o v e da n da l g o r i t h m sw i t hg o o dp e r f o r m a n c ea r e p r e s e n t e d ( 4 ) at h e o r e t i c a lm o d e l i s g i v e nf o rp 2 pc o m p u t i n ga p p l i c a t i o ni n 1 a r g e s c a l ep l a t f o r mc o n c e r n i n gt h es c h e d u l i n go fc o m p u t a t i o nc o m p o n e n t s b a s e do nt h em o d e l ，t h ep e r f o r l a ，n c e so fd i f f e r e n ts c h e d u l i n gm e c h a n i s m s a r ee v a l u a t e da n da n e ws c h e d u l i n gs t r a t e g yi sa l s oc o n t r i b u t e d k e y w o r d ：s c h e d u l i n gp r o b l e m s ，p a r a l l e lc o m p u t i n g ，d i s t r i b u t e dc o m p u t i n g 气p p r o x i m a t i o na l g o r i t h m s ， l o w e rb o u n d 6 中国科学技术大学博上学位论文 绪论 本章摘要：并行分布式计算是计算机学科中重要的研究领域。 调度问题是该领域中长期存在的研究问题，相应的研究结果和 研究方法众多。本章先给出一些基本概念，然后描述当前研究 的一些基本问题和它们具有的相关特点，最后给出全文的内容 概爱- 。 1 1 前言 并行分布式计算是计算机学科中重要的研究领域，在科学研究、社会生产生 活中具有广泛的应用【】“。在过去的几十年里，随着并行分布式计算研究和应用 的发展，相应的研究成果众多，并形成了从并行体系结构5 垮0 并行算法( 6 j ，再到 并行编程【7 j 的完整的学科体系。在并行分布式计算中，理论研究和应用研究联系 密切。许多理论上的研究成果在实际系统中得到应用，而应用中常常会产生新的 研究问题。 调度问题( s c h e d u l i n gp m b l e m ) 是一类组合优化问题，在计算机及通信等许 多领域有着广泛的应用，在理论上又与算法设计、复杂性理论关系密切，因而引 起了许多学者的研究兴趣辟1 ”。调度问题研究的是：在资源有限的条件下，为一 中国科学技术大学博士学位论文 组任务进行资源最优分配的问题。有关调度问题的研究在计算机科学、应用数学、 管理科学等学科都得到广泛开展。在并行分布式计算中，任务调度是最基本的研 究问题之一，也是优化并行分布式系统的重要因素。有关的研究方法丰富，研究 成果众多。 调度问题在不同的领域有许多不同的描述方法。一般地，构成调度问题的基 本元素有三个，即资源集( r e s o u r c es e t ) 、消费者集( c o n s 啪e rs e t ) 及这些资 源为这些消费者服务所依据的一定规则( r u l e s ) ，调度问题就是在满足资源集和 消费者集约束条件的基础上，设计一个有效的调度系统来管理消费者如何高效地 使用这些资源，并使得一些系统性能指标达到最优或近似最优。 图1 1 并行分布式计算中的调度问题 在并行分布式计算中，调度问题的描述如图1 1 所示。组成一个并行程序的 子任务、多用户系统下的作业、工厂中的生产作业或银行中的顾客相当于消费者， 并行分布系统中的处理单元、工厂中的机器或银行中的出纳相当于资源。调度规 则和策略多种多样，比如先来先服务( f i r s tc o m ef i r s ts e r v e ) 就是个典型的调 度策略，但它只适合于某些情形，如银行服务可以使用，但未必适用于工厂车间 中的生产作业。 调度性能和调度效率是评价一个调度系统优劣程度的两个方面。每个调度问 题都有自己特定的一些性能测试指标( 有时也称为系统性能指标) ，如生产车间 的产品产量、并行分布计算中一个并行应用程序的执行时间、多用户系统下作业 的平均响应时间( r 船p o n s et i m e ) 或系统吞吐率( s y s t e mt i l r o u g h p u t ) 等，作为 调度系统它的目标就是要尽量优化这些指标，调度性能( s c h e d u l i n gp e r f o 瑚a n c e ) 也就是通过这些指标的取值来反映，它直接体现了调度结果的好坏。例如，如果 把并行应用程序的执行时间长度作为性能指标，那么能产生较短执行时间的调度 系统较优。调度效率( s c h e d u l i n g e 历c i e n c y ) 主要指调度系统本身的复杂度，如 果两个不同的调度系统产生相同的调度结果，那么复杂度小、简单明了的调度系 中国科学技术大学博士学位论文 统较优。在并行分布计算中，调度系统的复杂度主要指调度算法( s c h e d i l l i n g a l g o m m ) 的时间复杂度，调度问题一般都具有n p 完全难度，各种取得最优或 近似最优的调度算法必须具有多项式时间复杂度时，才是有效的调度算法。 下面给出并行分布式计算中调度问题的一些基本特征和相应分类。 l 、静态调度与动态调度 按照何时决定每个任务的执行处理器号，并行分布计算中的任务调度方法主 要可分为静态调度、动态调度和混合调度这三类。静态调度( s t a t i cs c h e d u l i n g ) 是指在并行程序编译时，就决定每个任务的执行处理器及执行时序，它经常用于 任务图比较确定的情况下。而动态调度( d y n a m i cs c h e d m i n g ) 则是在并行程序 运行过程中，根据当前任务调度及系统执行情况，i 临时决定每个任务的执行处理 器及起始执行时刻。动态调度主要用于任务图不确定的情况下，但它不可避免地 会带来额外开销。混合调度( h y b r i ds c h e d u l i n g ) 是介于静态调度和动态调度两 者之间的调度方法，它在编译时先静态调度部分任务，而剩余部分则采用动态调 度方法在系统运行过程中来给它们分配处理器。 2 、最优调度和启发式调度 按照调度目标的实现要求来划分，并行分布计算中的任务调度可分为最优调 度( o p t i m a ls c h e d u l i n g ) 和近似最优调度( s u b o p t i m a ls c h e d u l i n g ) ，后者也经 常称为启发式任务调度( h e u r i s t i cs c h e d u l i n g ) 。最优调度一般是指静态调度，如 果一个调度算法能在多项式复杂度的时问内获得最佳调度结果，那么称之为有效 的最优调度算法。但是，只有在极少数情况下才存在有效的最优调度算法1 2 ，3 】， 大部分最优调度算法所需的执行时间随任务数或处理器数目的增加而呈指数增 长。因此，经常采用启发式任务调度方法来把各任务调度分配到各处理器上，它 虽然不能确保获得最优解，但可以获得最优调度的近似解。在后面我们谈到静态 调度方法时就是按最优算法和启发式算法分类进行讨论。 3 、集中式调度和分布式调度 按照调度程序的结构或调度程序所收集调度信息的范围，并行分布计算中的 中国科学技术人学博士学位论文 任务调度方法可划分为集中式调度和分布式调度两大类。在集中式调度 ( c e n 仃a l i z e ds c h c d l l l i i l g ) 方法中，由一个叫作中心调度器的处理器来收集全局 调度信息，其它处理器把它们的状态信息传送给中心调度器，并由中心调度器作 出调度决定。而分布式调度( d i s m b u t e ds c h e d l i n g ) 则是由各自处理单元的调度 程序根据局部范围内的一些调度信息来进行任务调度，它的最大优点在于具有良 好的可扩放性( s c a l a b i l i t y ) 。集中式调度的主要优点在于实现比较简单，但在节 点数较多的大规模并行分布系统中，由于各节点与调度服务器的通信成为瓶颈， 所以调度开销比较大。分布式调度一般都是动态的。 4 、可中断调度和不可中断调度 按照是否允许任务中断执行，可分为可中断调度( 又称抢占式调度， p r e e m p t i v es c h e “1 i n g ) 和不可中断调度( n o n - p r e e m p t i v es c h e d u l i n g ) 。如果一个 任务一旦占有处理单元，那么它就不能被中断执行，而是必须一直运行完毕后才 释放该处理器，这种情形即为非抢占执行方式；相反，如果允许任务被中断执行 而把它所在的处理单元让给其它任务执行，这种情形即为抢占执行方式，当然这 必须假定被抢占任务最终还能获得它所要求的执行时间。 5 、共享存储结构调度和分布存储结构调度 按照并行分布计算模型的存储器结构，主要可分为基于共享存储的任务调度 和基于分布存储的任务调度这两大类。在共享存储( s h a r c dm e m o r y ) 的计算模 型上进行任务调度时，一般不需要考虑通信延迟，这时任务调度的着重点在于如 何最大限度地获得并行程序任务间的并行性。而在分布存储( d i s t r i b u t e d m e m o r y ) 的计算模型上进行任务调度时，通信延迟的存在使得任务调度更为复 杂，如果无视通信延迟的存在，而只考虑尽量增大并行执行时间，那么有可能在 较多处理器上的执行效率还不如在较少处理器上的执行效率；同样，如果没有完 全开发任务之间的并行性，那么并行系统中处理器就没得到充分利用，因此，调 度程序必须在尽可能利用各任务之间的并行性和尽量减少通信开销之间进行折 衷。 中国科学技术大学博士学位论文 1 2 问题描述 调度问题的研究作为运筹学的一个分支，除了计算机科学研究者外，许多应 用数学研究者也在这个领域进行研究工作。在应用数学学科，“s c h e d u l i i l g ”问题 通常被称为“排序”问题。在计算机学科中，“排序”一词已经被普遍接受为代 表“s o r t i n g ”的含义，即将给定的无序的数列处理为有序的数列，因此通常称之 为“调度”问题。对于有关调度问题的其他术语的表达上，在数学学科和计算机 学科也存在着类似的不同。为了避免混淆，本文中的有关术语在第一次出现时， 会给出相应的英文描述。 根据实际应用中的不周情况，存在很多种调度问题，目前被研究过的就有几 百种。如上一节对于并行分布计算中的调度问题的描述，可以任务个调度问题 可由三方面的特征来刻画：机器环境( 如单机、一致并行机等) 、问题的限制条 件( 如是否为抢先调度、任务是否有释放时间、任务之间是否存在前驱关系等) 、 问题的目标函数( 如最小化停机时间，最小化延迟时间等) 。 调度问题在不同的研究领域有着不同的表示方法，这里采用三部分表示方法 来自 1 0 】，是当前比较流行的表示方法。 调度问题可以表示为三个部分口i i y ：口为机器环境，为限制条件，目标 函数。先给出一些符号表示：第，个任务用，表示，胛表示任务的个数，p ，表示 任务，的执行长度；第j 台机器用m ，表示，垅表示机器的个数。用表示一个 任务安排表，用j ，( ) 表示任务，在任务安排表中开始执行的时刻( 在没有混 淆的情况下，可以省略不写) ；c 表示任务，在任务安排表中执行完毕的时 刻。f 表示任务执行并释放的时刻。分别描述如下： 机器环境有单机，一致并行机( i d e n t i c a lp 眦l i e lm a c h i n c s ) ，无关并行机 ( u n r c l a t e d p a r a l l e l m a c h i n e s ) ，分别用1 ，e r 来表示，如图1 2 所示。 f o n e m a c l l i n ee n 访o m m e m 1 m u l 蛐m a c 脚i e n t 器1 竺竺景篱e r 图1 2 机器环境的分类 中国科学技术大学博十学位论文 其中一致并行机中任务在任何一台机器上都有相同的执行时间；无关并行机 中各个任务在不同的机器上会有不同的执行时间。另外在车间调度( s h o d s c h e d u l i n g ) 中，用o ，f ，j 分别表示任意车间调度( 0 p e ns h o ps c h c d l l l 证g ) ，流 水线车间调度( f 1 0 ws h o ps c h e d u l i n g ) 和任务车间调度( j o bs h o ps c h e d u l i n g ) 。 车间调度是指一个任务由很多个操作组成，每个操作必须在某一个机器上执行这 些操作，而且同一个任务中的操作不能同时执行。任意车间调度中每个任务的操 作可以以任意的顺序执行，任务车问调度中的每个任务中的操作必须以特定的顺 序执行( 这种顺序与任务相关) ，流水线车间调度中的每个任务包含m 个操作( 分 别要在m 台机器上执行) ，并且所有任务中的操作必须按照同样的顺序执行。 限制条件：对于调度问题，存在许多限制条件，其中主要是针对任务。 0 表示任务t ，允许执行的开始时刻，称为发行时间，q ，表示任务，完成后的 释放时间，p 咖玎表示是否是抢先调度，即是否允许一个任务在执行时，中断执 行，而后再在同一台机器或其他机器上继续执行。矽f f 是指任务中是否存在一种 相互依赖的前驱关系，即一个任务必须在它的前驱任务都完成以后才能够执行。 目标函数：存在很多种不同的目标函数，其中主要有两类目标函数：一类是 m i n 瞰，另一类是m i n s u m 。m i n m a x 是指最小化关于c 的一个非降函数对任 意的，上的最大值，如m i n c m 。，m i n k 。等。l i l i n - s u m 是指最小化一个关于c ，的 和式，如m i n c ，m i n _ c ，等。 j 一般的调度问题都可以描述为以上三个部分的组合。比如 1 1 0j k ：在单个机器上，每个任务，除了处理时间p ，外，还有其允许执 行的开始时刻r ，。问题的优化目标为最小化任务的延迟时间。 1 | ，p r p c l 一：在单个机器上，每个任务，除了处理时间p ，外，还有其允 许执行的开始时刻_ ，此外任务之间还存在相互依赖的前驱关系。问题的优化目 标为最小化任务的延迟时问。 p 1 | c m 。：在多台一致并行机上，每个任务i ，仅有一个参数处理时间p ，。问 题的优化目标为最小化任务全部执行结束的时间。 中国科学技术大学博l 二学位论文 p 0 f 瓯。：在多台一致并行机上，每个任务除了处理时间p ，外，还有其 允许执行的开始时刻_ 。问题的优化目标为最小化任务全部执行结束的时间。 r 1 1c 。：在多台无关并行机上，每个任务j ，除了处理时间n 外，还有其允 许执行的开始时刻_ 。问题的优化目标为最小化任务全部执行结束的时间。 问。 0 i c 。：任意车间调度。问题的优化目标为最小化任务全部执行结束的时 列c m 。：任务车间调度。问题的优化目标为最小化任务全部执行结束的时间。 1 i f q ：在单个机器上，每个任务t ，仅有一个参数处理时间丹。问题的优 化目标为最小化任务的执行结束时间之和。 l l o ，舯圳。q ：在单个机器上，每个任务，除了处理时间p ，外，还有 ， 其允许执行的开始时刻r ，此外任务之间还存在相互依赖的前驱关系。问题的优 化目标为最小化任务的执行结束时间加权之和。 这些组合产生了成千上万个不同的调度问题，其中许多被研究者关注并得到 了相应的研究结果。 1 3 研究现状 对于已有各种调度模型的计算复杂度的研究结果很多，许多调度问题都已经 得到多项式时间的算法，或者被证明了固有的难解性。其中也还有许多悬而未决 的问题，比较著名的有三机调度问题f 1 ”。相关的计算复杂性最新成果可见【1 6 】。 已有的调度问题虽然众多，但根据实际中的情况，近年来依然有新的更为实际的 模型被研究者们陆续提出，并加以研究。 ( 1 0 】中列出了有关调度问题的数千篇文献，对于已有的调度问题做了相当充 分的综述。这里不打算做类似的综述，丽是尝试对与并行分布式计算相关的调度 问题按照研究的特点进行分类。 如图1 3 所示，对于并行分布式计算中的调度问题的研究往往先从实际问题 中提取出相应的调度模型，然后对该模型进行研究，之后再将相应的结果应用于 中国科学技术大学博上学位论文 解决实际问题。 图1 3 调度问题研究过程 这一过程包含了三个方面的工作，即 ( 1 ) 问题的建模：这一个方面的工作指的是从实际系统中提取最为重要的 因素，得到相对简单且能够反映原有问题特性的调度模型。并行分布 式系统不断发展，其中调度问题也不断出现。有关建模的研究工作， 需要研究者对于系统或者实际问题本身有较深入的了解和认识。这方 面的工作是由并行分布式计算领域内的研究者完成的【1 7 。2 1 】。 ( 2 ) 模型的研究：对于已经明确的调度模型，进行有效的算法设计与分析， 也包括对于模型本身下界的研究。许多调度问题是n p 难解问题，在 尸尸的假设下不存在多项式时间的完全算法【2 2 】；对于在线调度问 题和分布式调度问题，由于信息的不完全，也往往不存在有效的完全 算法。对于这些问题，通常需要进行近似算法的研究。这方面的研究 往往与算法设计与分析【2 3 1 、计算复杂性理谢2 ”、图论算法【25 1 、网络流 算法等理论研究相关联。 ( 3 ) 研究结果的应用：将以后的一些研究成果应用于求解实际中的问题， 或者应用于实际的系统之中。对于实际系统，由于各种参数比较复杂， 一般难以进行理论分析。实验分析成为研究的主要手段【2 7 _ 3 1 】。 “问题建模一模型研究一系统应用”作为有机的一个整体，具有密切的联系。 本文的研究工作涉及以上这三个方面，针对并行分布式计算中的调度问题加以研 究。 中国科学技术大学博士学位论文 1 4 对于当前研究现状的一点认识 d i j k s 仃a i ”l 曾经说计算机科学研究领域有两种人：数学家和工程师( 原文是“欧 洲人”和“美国人”) 。二者的区别在于，数学家( 欧洲人) 倾向于把技术探寻当 成一种理论研究，而工程师( 美国人) 则宁愿视之为一项工程实践。数学家看重 原理和模型，看重认识的先天性和推导的优美性，工程师则更注重实验和例证， 注重在反复试错中趋近真理。对于调度问题的研究，也同样存在d i i k s t r a 所指出 的情况。【9 】中再谈到如何进一步从事调度问题研究的时候，给出的建议是或者 采用新的方法研究经典的调度模型，或者是研究新的更为实际的调度模型。近年 来相关研究的进展也体现了这样两个方向。 在本文从事研究的过程中，发现对于调度问题的研究有两个基本的出发点。 一是出于对调度问题本身的研究兴趣，另一个则是是出于对于实际系统性能提高 的应用要求。这里称前者为调度问题的理论研究，后者为调度问题的应用研究。 调度问题的理论研究往往是基于个人的研究兴趣，所以研究者往往并不考虑 模型与实际系统的联系与差别，也不考虑研究结果的应用。当然，这些理论研究 的成果。往往会启发应用研究者。此类研究所关注的调度问题模型一般非常明确， 相对简单。对于其上算法进行分析评价的方法也以理论分析为主。 调度问题的应用研究则通常是为了提高实际系统的应用性能。而实际系统的 调度问题往往比较复杂，所抽象出的调度模型通常也并不简单。对于这种模型， 理论分析十分困难，许多时候会使用实验分析的方法来验证算法的性能。 由于研究的出发点不同，调度问题的理论与应用之间存在着一定的距离。尽 管如此，由于调度问题本身具有的特点，在两者之间依然存在着密切的联系。在 本文的研究工作中，注重理论研究和应用研究之间的联系，以期缩小两类研究之 间的距离，让理论研究结果在实际系统中取得好的应用效果。 1 5 本文组织 基于以上的研究思路，我们首先对于通过对若干调度问题进行理论上的研 究，其中包括研究已有的调度模型和提出新的调度模型；在具有一定的理论基础 后，结合实际中的并行分布式系统，研究并行分布式系统中的调度问题。 中国科学技术丈学博士学位论文 本文的组织如下： 第一章：绪论。先给出一些基本概念，然后描述当前研究的一些基本问题和 它们具有的相关特点，最后给出全文的内容概要。 第二章：具有中断时间代价的调度模型。提出了一种具有中断时间代价的抢 先调度问题( p l p 加聆( 占) c m 。) ：在抢先调度中一个任务发生一次中断总的执行 时间会增加一个6 ，该问题在工程任务分配、分布式计算和网络通讯等实际问题 中有着广泛的应用背景。文中证明了这是一个n p - h a r d 问题，给出了个时间复 杂度为d m f p 卯+ 砌的脱线近似算法l p t w r a p ，其近似比小于等于1 4 0 8 2 5 ，并 分析了p l p 砌n ( d ) | c m 。的在线特性，给出一个线性时间复杂度的在线近似算法， 其竞争比为2 。 第三章：具有不可用时间段的调度模型。本文主要考虑存在可用性限制的机 器模型上的在线调度问题，假设每一台机器均存在不可用时间段。分析了两种模 型下的性能：1 在任何一个时刻至少有一台机器可用的机器模型上，证明l s 算 法的竞争比为m + l ；2 在任何一个时刻至多有一台机器不可用的机器模型，证明 l s 算法的竞争比为3 ，并给出最优在线算法的竞争比下界为2 5 。并通过编程给 出了l s 算法与典型的脱线算法l p t 之间的性能比较。 第四章：分布式线性网络上的任务调度算法研究。针对一种已有的分布式计 算的理论模型( 单位长度的任务由处理器独立产生，没有全局控制，彼此通讯需 要花费时间) ，研究了在线性网络上的任务有效调度问题。通过考虑了算法中任务 处理时间和通讯时间之间的平衡，给出了一个近似比为5 8 8 的分布式算法，该算 法无需全局信息且处理策略简单。对该问题的近似比下界也做了研究，证明了该 问题不存在近似比小于1 1 6 的算法。 第五章：分布式环网调度模型。给出环状网络结构上的分布式调度近似算法。 在调度模型中，任务在处理机间传送所需的时间，与处理机间的路径长度成正比， 反映了环状网络结