（计算机软件与理论专业论文）分布式异构系统中任务调度问题的研究.pdf

摘要 随着计算机应用范围的日益扩大，分布式异构系统( d h s ，d i s t r i b u t e d h e t e r o g e n e o u ss y s t e m ) 逐渐成为解决复杂应用问题的有效工具。d h s 利用一组异构 的计算机来协作完成应用任务，以期获得最好的执行效果。d h s 中的任务调度问题， 对发挥系统的并行性能和保持负载平衡具有非常重要的意义。该问题已被证明是n p 完全问题，无法在多项式时间内找到最优解，所以促使人们不懈地研究如何设计调 度算法，用有限的代价获得更好的解。目前常用的方法就是启发式算法和随机搜索 的近似方法。 在本文中研究了主从式d h s 中的调度算法问题，对其进行数学建模，定义并分 析了主从式d h s 在稳定运行阶段的系统特性。对于树形的主从结构，本文给出了达 到稳定运行阶段的集中带宽( b a n d w i d t h c e n t r i c ) 调度策略，并证明了稳定运行阶 段的最优性。 在本文中我们提出了两种主从式d h s 下的任务调度算法。首先给出了启发式算 法i 删( i m p r o v e dm i n m i n ) ，该算法可以解决d h s 环境下，独立的、带优先权和时 限的任务的调度问题。随后根据主从式d h s 稳定运行阶段的特点，提出了一种集中 带宽的渐进最优算法，并从理论上证明该算法在评估时间段t 趋向于无穷大时，可 以取得最优解。 另外，我们还对文中提出的两种算法分别进行了仿真实验，其仿真结果证明了 我们算法的优越性。 关键词：分布式系统，异构系统，启发式算法，任务调度 t h ed i s t r i b u t e d h e t e r o g e n e o u ss y s t e m h a sb e e nu s e dt os o l v e c o m p l e xa p p l i c a t i o n s a l o n gw i 也t h ed e v e l o p m e n to f t h ec o m p u t e r d i s t r i b u t e dh e t e r o g e n e o u ss y s t e mi st h e c o o r d i n a t e du s eo f v a r i o u sr e s o u r c e sw i t hd i f f e m m c a p a b i l i t i e st os a t i s f yt h er e q u i r e m e n t s o f 蜊n g t a s km i x t u r e s n 圮h e t e r o g e n e i t yo ft h er e s o u r c e sa n dt a s k si na h e t e r o g e n e o u s s y s t e mi se x p l o i t e dt om a x i m i z e t h ep e r f o r m a n c eo rt h ec o s t - e f f e c t i v e n e s so ft h es y s t e m t h et a s ks c h e d u l i n ga l g o r i t h mp l a y sav e r yi m p o r t a n tr o l ei n e n h a n c i n gt h i ss y s t e m s p a r a l l e lp e r f o r m a n c ea n dm a i n t a i n i n gi t sl o a db a l a n c e t h es c h e d u l i n gp r o b l e m h a st u r n e d o u tt ob ean p c p r o b l e m a n d o p t i m a ls o l u t i o n sc a nn o th ef o u n di np o l y n o m i a lt i m e s o ， m a n yp e o p l em a k eg r e a te f f o r t so nf i n d i n gab e t t e ra l g o r i t h mt of i n dab e t t e rs o l u t i o n w i t h i nl i m i t e dc o s t a tp r e s e n t ，p e o p l eo f t e nu s eh e u r i s t i ca l g o r i t h ma n da p p r o x i m a t e a l g o r i t h m i nt h i sp a p e r , w er e s e a r c ht h et a s ks c h e d u l i n gi nm a s t e r - s l a v eh e t e r o g e n e o u ss y s t e m w em o d e lac o l l e c t i o no f h e t e r o g e n e o u sr e s o u r c e sa n dt h ec o m m u n i c a t i o n l i n k sb e t w e e n t h e ma st h en o d e sa n de d g e so fa nu n d i r e c t e dg r a p h w ed e f i n ea n da n a l y z et h eb a s e m o d e la n di t s s t e a d y s t a t e o p e r a t i o n f o rat r e e s h a p e dp l a t f o r mg r a p h ，w eg i v e a b a n d w i d t h - c e n t r i cs c h e d u l i n g s t r a t e g y t oa c h i e v et h eo p t i m a ls t e a d ys t a t e i nt h i s p a p e r , w eg i v e t w ot a s k s c h e d u l i n ga t g o r i t h m s i nt h em a s t e r - s l a v e h e t e r o g e n e o u ss y s t e m f i r s tw eg i v eah e u r i s t i ca l g o r i t h m i m ma l g o r i t h m ，i tc a nb e u s e dt od y n a m i cm a p i n d e p e n d e n tt a s k sw i t hp r i o r i t i e sa n dd e 瓤沁t h e nw ep r e s e n ta b a n d w i d t h c e n t r i ca s y m p t o t i c a l l yo p t i m a la l g o r i t h ma c c o r d i n gt ot h es t e a d ys t a t eo ft h e m a s t e r - s l a v eh e t e r o g e n e o u ss y s t e m ，a n dw e p r o v e d i t so p t i m a l i t yb y t h e o r y i nt h i s p a p e r , w eg i v es i m u l a t i o n st o b o t ha l g o r i t h m s t h es i m u l a t i o np r o v e dt h e a d v a n t a g eo f t h ea l g o r i t h m sf b r t h e r k e yw o r d s ：d i s t r i b u t e ds y s t e m ，h e t e r o g e n e o u ss y s t e m ，h e u r i s t i ca l g o r i t h m ，t a s k s c h e d u l i n g 第一章绪论 1 1 引言 第一章绪论 现代计算机时代从1 9 4 5 年开始到现在，经历了半个多世纪。从1 9 4 5 年到1 9 8 5 年，计算机一直是庞大昂贵的设备。然而，从8 0 年代开始，两项技术的进步改变了 这种局面：一是功能日益强大的微型计算机的发展；二是高速局域网的出现。这两 项进步的直接结果是：通过高速网络，将许多处理单元连接起来构成一个计算系统 的做法变得可行，并且非常容易。这种系统通常称为分布式系统。分布式系统已成 为计算机领域中的研究热点。著名学者j h g i l d e r 早在1 9 7 6 年就预言，下一代计 算机体系结构的关键与核心必然是以分布式结构为主的“1 。 分布式系统的求解过程大体分为四个步骤： 1 任务分解：指把一个大任务划分为可并行执行的相关子任务的过程。 2 任务调度：指将这些子任务分配到各个并行处理机上，并安排处理机上子任 务的执行次序的过程。 3 并行运算：指这些子任务在被分配的处理机上进行并行运算。 4 解的合成：指将子任务的运行结果合成为整个大任务的运行结果。 其中任务调度这一步骤对发挥系统的并行计算能力、提高系统吞吐量具有非常 重要的影响。良好的调度算法可以充分运用系统中每个处理机的计算能力，避免有 的处理机没有可执行的任务，而有的处理机等待执行的任务排起了长队，致使总任 务的执行时间较长。 1 2 求解组合最优化问题的方法 分布式系统的任务调度问题属于组合最优化问题，它通常是由目标函数和约束 条件两部分构成。 最优化问题可分为函数优化问题和组合优化问题两大类，其中函数优化的对象 是一定区间内的连续变量，而组合优化的对象则是解空间中的离散状态。 将满足所有约束条件的解空间s 称为可行域，可行域中的解称为可行解；将可 行域中使目标函数最小的解称为最优解。对于最大化问题，可将目标函数转化为最 小化问题求解。 当s 为离散集合构成的解空间时，最优化问题称为组合最优化问题，其研究对 象可视为是在有限集合上定义的函数在各种条件下的极值问题。从理论上来说，这 类问题若有解，总是可以用枚举的方法找到，这意味着以枚举为基础发展起来的分 青岛大学硕士学位论文 枝定界法具有普遍适用性。但实际上，对于大规模的问题，分枝定界法通常是不能 实际使用的。该方法的计算时间一般为输入数据量的指数函数，计算时间会迅速增 加到现代计算工具难以承受的地步。 根据计算复杂性的理论，一个好的算法，其计算时间作为输入数据量的函数应 该有一个多项式作为上界，这样的算法被称为多项式时间算法。在组合优化中，至 今还没有，似乎也不可能发现普遍适用的多项式时间算法。一个多项式时问算法问 题被称为多项式时间内的可解问题，或者称为“p 问题”。组合优化中多数问题属于 一类不知道是否为p 问题的问题，称为“n p 问题”。其中，也包括所谓的“n p c 问题 ( n p 完全性问题) ”。在这类问题里，只要有一个被证明是p 问题，那么它们全部是 p 问题。至今已经发现属于n p c 问题的数目有几千个之多。分布式系统的任务调度 问题已被证明是n p c 问题。3 。一般认为，n p c 问题不会是p 问题，因此，对n p c 问题， 既然没有准确的多项式时间算法，比较现实的妥协方法是采用多项式时间近似算法。 近似方法分为启发式方法( h e u r i s t i cm e t h o d ) 和随机搜索方法两种。启发式方 法就是运用启发信息，应用某些经验或规则来使搜索沿着某个被认为最有希望的前 沿区段扩展。启发式方法较多地依赖于对问题构造性质的认识和经验，适用于解决 不太复杂的问题。随机方法不依赖于问题的性质，从解空间中随机地选择多个解， 检查这些解的可行性，在可行解集中选择最好的解。 1 3 分布式系统任务调度的意义 在一个分布式系统环境中，大部分结点在大部分时间内都处于低利用率状态。 n , j , i - i 大学b e r k e l e yn o w 研究小组的研究结果表明：即使在每天下午最繁忙的时候，平 均也有近6 0 的结点处于空闲可利用状态。分布式系统中这些闲置结点，如果不加以 合理的利用的话，其c p u 等计算资源就白白的浪费了。而实际上在一个局域网或高速 网络内，在适当的任务调度机制的控制与管理下，可以充分利用这些闲置结点来执 行大规模并行计算。 另外在分布式系统中，很可能出现负载不平衡的现象。当一些处理机处于重载 时，另一些处理机却处于轻载或闲置状态，这种负载的不平衡将直接影响分布式系 统的整体性能。这就有必要在分布式系统中，按任务的静态分配和动态调度要求做 到负载平衡，以提高系统性能。 在论及任务调度的必要性时，r i c h a r df f r e u n d 等人列举过一个假设具有多层 并发度计算需求的计算实例【3 j 。经计算分析表明，“该程序对于普通串行机需要运行 1 0 0 个时间单位，对于向量机需要5 0 个时问单位，而采用由5 种机器构成的分布式系 统，计算过程仅需5 个时间单位。显然，后者所付出的代价是：必须进行适当的任务 分解、分配和调度。” 第一章绪论 可见，任务调度策略是影响分布式系统性能的关键问题之一，为了最大限度的 提高系统的资源利用率和减少任务的平均响应时间，必须采取有效的任务调度策略， 合理地分配子任务到各个工作结点机上，保证总任务在最短的时间内完成。 1 4 分布式系统任务调度现状 任务分配问题是分布式系统中的一个核心问题之一。目前已经证明分布式系统 的任务分配问题是n p 完全问题，只有在三种特例下，任务调度算法才可以在多项式 时间内找到最优解。所以现在通常采用启发式算法寻求任务调度的次优解。但是由 于具体系统的千差万别，任务分配追求目标的不同，人们在设计算法时，对于任务 调度韵时机，调度目标的实现要求，紧迫性任务的响应问题和任务迁移问题的不同 考虑，提出了许多不同的算法。为了比较清楚的介绍任务调度问题的研究现状，我 们以两种常用的系统来分别介绍已经有的算法。 1 集群系统中任务调度问题 近年来，随着计算机体系结构以及通讯技术的发展，在并行处理技术中，采用 高带宽( h i g hb a n d w i d t h ) 、低延时( l o wl a t e n c y ) 的通讯网络，以高性能的工作站集 群系统( w o r k s t a t i 0 1 qc l u s t e rs y s t e m ) 作为并行计算的平台越来越多的引起了人们 的重视。集群系统的基本思想在于将一些主机利用通信网络连接起来，用户将这个 松耦合的计算机系统当作一个统一的计算资源来使用，从而获得较高的计算能力和 性能价格比。 任务调度可以分为静态调度和动态调度。静态调度是在程序执行前运行的，对 于所有的信息，如任务的前驱限制关系图和数据交换产生的额外开销等都是事先知 道的。分布式系统中研究最早的是同构集群的任务调度。最早的静态任务调度算法 是基于优先级的调度算法。随后许多学者分别从不同的出发点设计了不同的算法“ 司 。 静态算法虽然简单，但由于集群系统结构和程序本身的不确定性，往往需要在运 行时进行动态调度。文献 7 通过任务再分配来维持负载平衡，对运行中动态产生的 任务进行分配。由于集群系统中实现进程迁移有非常重要的应用需求，可以实现集 群内部的负载分担，解决突发性负载不平衡问题，以及主人优先使用原则，文献 8 对集群系统中的进程迁移做了研究，论述了进程迁移的意义、实现设计目标，还提 出和分析了其实现机制的主要关键技术，对我们研究进程迁移提供了很好的参考。 随着计算机应用系统的日趋复杂，问题计算强度的不断提高，异构计算系统由 于其高性能而逐渐成为处理这些复杂应用的有效手段。k h o k h a re ra 1 将异构计算 定义为“组织和协调一组高性能机器，使它们能够得到有效的最大程度的利用，从 而为具有不同计算需求的大计算量任务提供超级的计算速度”。对于异构集群的研究 青岛大学硕士学位论文 主要侧重于负载平衡以及冲突开销。文献 9 首次为异构计算的任务分配调度提出了 最优选择策略( o s t ) 的数学模型，后来o s t 被扩展到增大最优选择策略( a o s t ) ，异构最 优选择策略( h o s t ) ，和遗传最优选择策略( g o s t ) 。文献 1 0 考虑到任务的计算量和 通信量以及处理机的速度对任务的均衡分配的影响，提出了异构集群的并行任务均 衡分配算法。文献 1 1 通过对影响并行计算性能的主要参数的分析，提出一个基于 人工智能a + 算法的最优处理机分配算法，为高性能的异构集群系统并行计算提供理 论支持。文献 1 2 比较了异构计算系统下的1 1 种静态调度算法，文献e 1 3 比较了异 构计算系统下的8 种动态调度算法。 2 实时任务的调度 在研究实时任务调度时，通常将任务分为周期性的( p e r i o d i c ) 和非周期性的 ( a p e r i o d i c ) 两大类。而实时应用依据应用的性质不同，可分为硬实时( h a r d r e a l t i m e ) 和软实时( s o f tr e a l t i m e ) 。硬实时应用指任务在指定期限内必须完 成，否则整个实时应用的效率立即降为零，即会造成灾难性后果；软实时应用指任 务在指定期限内必须完成，否则整个实时应用的效益可能呈线性下降，直至为零。 对于周期任务，考虑最多也最为成熟的是静态算法。在一系列静态算法中，有 的着重于使整个系统取得最小的计算与通信负载“”，有的力求使处理机之间的负载 相对均衡“”3 ，有的则以使各个处理机结点中的最大计算时间取得最小值为目标“”。 由于静态算法固有的局限性，人们进行了动态算法的研究。文献 1 8 根据周期任 务执行时间或子任务数量的统计特性，提出了预测算法p a a ( p r e d i c t i n ga l l o c a t i o n a l g o r i t h m ) ，实现了多任务的动态调度。 硬周期实时任务的调度有两种典型算法”，一种采用固定优先级方案，称为速 率单调( r a t em o n o t o n i c ，r m ) 算法；另一种采用动态优先级方案j 称为最后期限 驱动( d e a d l i n ed r i y e n ，d d ) 算法。前者按任务的周期长短分配优先级，周期越短， 优先级越高；后者动态分配优先级，任一时刻，最后期限近的任务优先级高。文献 1 9 中还证明，r m 算法是固定优先级方案中的最优算法，而d d 算法是动态优先级 方案中的最优算法。随后文献 2 0 采用信号同步的方法提出了r g 算法。文献 2 1 利用处理机复制任务的方法提出s d b s 算法。文献 2 2 对软实时任务提出了实时自适 应动态调度算法r t s a d s 。文献 2 3 认为传统的以搜索为基础的分配算法，在解决 系统抖动问题上需要付出很大的代价，于是它从减少抖动的角度出发，提出了一种 基于模拟退火思想的非传统周期实时任务调度算法，并证明该算法比附、d d 更灵活 简单。 客错是实时系统的一个重要要求。实时系统中每个任务的执行往往有严格的时 间约束( d e a d l i n e ) ，若由于处理机的故障导致某些任务不能在其d e a d l i n e 之前完 成，就可能造成重大损失。为了避免处理机出现故障时造成严重后果，需在这些实 第一章绪论 时系统中提供一定的容错能力以提高整个系统的可靠性。文献 2 4 ，2 5 提出在不同的 处理机上调度任务的多个版本运行来达到容错的目的，而文献 2 6 使用了空闲处理 机备份的方法。它们的基本思想都是为可能因故障而失效的任务在其d e a d l i n e 之前 预留足够的时间，以便任务失效后重新被调度运行，并能在其d e a d l i n e 之前完成。 其不足之处是系统无故障时，为容错预留的时间被浪费了，导致c p u 利用率不高。 为此，文献 2 7 提出了一种主从备份技术( 1 j r i m a r y b a c k u p ) 和首次满足( f i r s t f i t ) 的方法提高系统的利用率。文献 2 8 提出了两种分布式实时系统的容错调度算法： 副版本后调度算法( b k c l ) 和无容错需求后调度算法( n f r l ) ，保证了在一个结点机 失效的情况下，具有容错需求的实时任务仍然可在截止时间内完成。 1 5 本文所做的工作 已有的研究对分布式系统的任务调度问题都提出了不同的静态或动态算法，这 些算法大都是集中在同构的基础上的。本课题的主要任务是研究异构系统的运行机 理，探索一种更适合异构分布式系统的任务调度方法。具体有： 1 本文用无向图表示主从异构系统，并对其基础模型进行数学建模，用一个线 性方程组定义了主从异构系统的稳定运行状态。对于树形的主从异构系统，我们给 出了获得稳定运行阶段的集中带宽( b a n d w i d t h c e n t r i c ) 调度策略，并证明了稳定 运行阶段的最优性。 2 提出了两种主从异构系统下的任务调度算法。第一个是启发式算法 i m m ( i m p r o v e dm i n m i n ) ，该算法可以解决异构系统环境下，独立的、带优先权和时 限的任务调度问题。第二个是带宽集中的渐进最优算法。根据主从异构系统的稳定 运行阶段的特点，并从理论上证明该算法在评估时间段t 趋向于无穷时，可以取得 最优解。 3 我们对文中提出的两种算法分别进行了仿真实验，其仿真结果证明了我们算 法的优越性。 1 6 论文内容安排 本文内容安排如下：第一章是绪论；第二章介绍分布式系统及其任务调度问题； 第三章介绍了丰从异构系统下的数学模型，作为我们提出的调度算法的数学基础； 第四章介绍了针对主从异构系统模型，我们提出的两种算法：i m m 调度算法和集中 带宽的渐进最优调度算法；并且对我们提出的算法进行了仿真实验，分析了我们提 出的算法的优越性；第五章是总结与展望。 青岛大学硕士学位论文 第二章分布式系统及其任务调度问题 2 1 分布式系统概述 未来对计算速度、系统可靠性和成本实效性的要求必将促使发展另外的计算机 模型来替代传统的冯诺依曼结构的计算机。随着计算机网络的出现，一个新的梦 想成为可能分布式计算。当用户需要完成某项任务时，分布式计算提供尽可能 多的计算机处理能力和数据的透明访问，同时实现高性能与高可靠性的目标。 对分布式系统我们使用如下定义： 一个分布式系统是一个对用户看起来像普通系统，然而运行在一系列自治处理 单元( p e ) 上的系统，每个p e 有各自的物理存储器空间并且信息传输延迟不能忽略不 计。在这些p e 间有紧密的合作。系统必须支持任意数量的进程和p e 的动态扩展。图 2 1 和2 2 从物理的和逻辑的观点表示了这样一个系统。 图2 1 物理观点的系统结构图2 2 逻辑观点的系统结构 在硬件结构上，尽管所有的分布式系统都是由多个自治处理单元构成的，但可 以用不同的方法将硬件组织起来，形成不同的系统。按照体系结构划分，当前典型 的分布式系统可分为两种：共享存储多处理机、分布存储多计算机。如果结点问通 过公用存储器中的共享变量实现相互通信，就称为多处理机( m u l t i p r o c e s s o r s ) ； 如果结点间使用消息传递方式来实现相互通信，就称为多计算机( m u l t i c o m p u t e r s ) 2 9 1 。 共享存储多处理机属于紧密耦合的分布式系统，采用共享主存通信。由于处理 机与主存之间互连网络带宽有限，所以当处理机数增多时，访问主存的冲突概率会 加大，互连网络会成为系统性能的瓶颈。但由于是单一地址空间，所以较易于编程。 分布存储多计算机属于松散耦合的分布式系统。由于每个计算结点的本地存储 器容量较大，所以运算时所需的绝大部分指令和数据均可取自本地存储器。当不同 计算结点上的进程需要通信时，就可通过接口进行消息交换。在有的松散耦合的多 第二章分布式系统及其任务调度问题 计算机系统中，其计算结点本身就是一台完整的计算机，这样就演变成了现代的集 群系统。这种松散性耦合结构易于扩展，但多地址空间却使编程较困难。 分布式系统与集中式系统相比，有其自身的优点： 1 性能价格比高。由高性能结点处理机组成的并行系统，具有很强的处理能力， 它还可能具有任何价位上的大型机都无法达到的性能。例如，美国o a kr i d g e 国家实 验室的一组并行程序测试表明，基于网络的1 1 台i b mr s 6 0 0 0 i 作站组成的并行系统， 其性能达n o 7 g f l o p s 。但相对同等性能的m p p 等系统来说，价格要便宜的多。 2 可复用性强。系统中的机器既是普通的工作站，又是并行系统中的一个结点 处理机，这样可以资源共享，充分利用现有的机器设备。 3 可以支持多种平台。由于分布式系统一般是靠高层的软件提供并行计算环 境，因此，在异构系统的支持方面具有得天独厚的优势。因此用户可以根据应用要 求选择不同的结点处理机( 如工作站、船p 系统等) 来构造集群。 4 可扩展性。这也是分布式系统结构的一个非常突出的优势。一般来说，在系 统通信允许的情况下，增加系统中结点的个数，就能提高分布式的整体性能。 5 用户编程方便。分布式系统中，程序的并行化只是在原有的c ，c + + 或f o r t r a n 串行程序中，插入相应的通信原语。用户使用的仍然是熟悉的编程环境，不用适应 新的环境，这样就可以继承原有的软件财富。 6 高可靠性。通过将任务交由多个机器共同承担，单个芯片的故障只会让一台 机器停下来，而其他的机器将继续工作。对于一些关键性应用来说，例如控制核反 应堆或飞机，使用分布式系统来达到高可靠性是最主要的考虑因素，并且在负载增 加时分布式系统较集中系统更容易扩展。 正是由于分布式系统的这些优点，许多公司和研究部门都推出了基于分布式结 构的并行计算机，如i b m 的s p ，中国曙光公司的超级服务器d a w n 2 0 0 0 ，都是基于集 群结构的。计算机分布式系统作为重要的并行计算系统，在大学、研究所和重点实 验室广泛构建，得到了越来越多的应用。对于分布式系统来说，应该满足以下要求 的属性： 1 任意数目的进程。每个进程也被称作一个逻辑资源。 2 任意数目的p e 。每个p e 也被称作一个物理资源。 3 通过消息传递的通信。这提供了比主从方式更合适的合作式消息传递方式。 4 合作式进程。进程问以一种合作的方式交互。 5 资源故障独立。没有任何单个逻辑或物理的资源故障会导致整个系统的瘫 痪。 6 故障化解。系统必须提供在资源故障的情况下重新配置系统拓扑和资源分配 的手段。 青岛大学硕士学位论文 2 2 分布式并行系统的分类 1 s i m d 型 s i m d ( s i n g l ei n s t r u c t i o na n dm u l t i p l ed a t a ) 机器是指单指令流多数据流并 行机，即指系统中各功能部件或处理机对多组数据执行相同的指令流或操作。s i m d 机器在任何时刻只有条指令在执行。所以该类计算机的主要特征是：同步的、确 定的。 2 共享存储m i m d 型 m i m d ( m u l t i p l ei n s t r u c t i o na n dm u l t i p l ed a t a ) 并行机指多指令流多数据流 并行机，即指系统中的各处理机在各自唯一的数据流上执行各自的指令流，与其他 处理机无关。m i m d 并行机按内存分布和访问方式的不同又可分为三种：共享存储m i m d 并行机、分布存储m i m d 并行多处理机、分布共享存储m i m d 并行机。其中的共享存储 m i m d 并行处理机是指多台处理机通过互联网络共享一个统一的内存空间或多个存储 器模块，各处理机可直接访问所有的数据，通过共享内存实现处理机间的通信和协 调。 例如：图2 3 给出了共享多个存储模块的m i m d 并行机结构。 l访存互联网络 图2 。3 共享多个存储模块的m i 结构 3 分布存储m i m d 并行处理机 为突破共享存储并行机系统中处理器与内存系统间的瓶颈，分布存储m i m d 并行 多处理机应运而生。该系统中每台处理机都有自己的局部存储器，构成一个单独的 结点，结点之间通过网络互联相互连接。每台处理机只能访问局存，不能访问其他 处理机的存储器，他们之间的协调以消息传递的方式进行。 分布存储m i m d 并行处理机主要包括m p p ( m a s s i v e l yp a r a l l e lp r o c e s s o r s ) 和 集群( c l u s t e r ) 系统两种形式。 第二章分布式系统及其任务调度问题 2 3 分布式系统中引起负载不平衡的原因 分布式系统中的负载不平衡是指在系统中出现有的结点机一直在运行，处于重 载状态，而有的结点机却处于空闲状态。 在分布式系统中引起负载不平衡的因素非常多，可归纳为以下各点： 1 异构机器：各主机的计算能力不一。 2 同步：通信延迟使各个任务交换数据时，需要进入阻塞状态，直至消息传递 完成才能继续计算。 3 机器负载：虚拟机中某些主机上可能正执行一些非并行的其它进程，降低这 些机器的计算能力，若此问题与同步问题同时出现，必将引起分布式系统的计算能 力大幅下降。 4 网络负载：由于分布式系统中的网络环境为多用户共享，如果网络处于繁忙状 态，将导致任务间的通信延迟增大，在此情况下进行同步，将引起负载不平衡，一 些并行程序，同一时间在各任务之间交换数据，是造成网络负荷过重的原因之一， 最终亦将使负载不平衡。 5 任务划分：以数据分解为主的并行程序，较易达到负载平衡，但以功能分解为 主的并行程序，由于各部分功能的计算量不一，较难达到负载平衡。 6 任务分配：分布式系统中各主机可同时运行多个任务，每个任务以进程的形式 同时存在，若一些主机分配到较多的任务，一些主机分配到较少任务，可能引致负 载不平衡。 为了避免系统中出现负载不平衡的状态，需要采取一定的调度策略，合理地分 配和调度任务到各个工作结点机上，保证总任务在最短的时间内完成，或者保证系 统的其他性能指标达到最优。 2 4 调度问题的一般模型 调度问题在不同的领域有不同的描述方法，一般在分布式系统中，构成调度的 基本元素有三个，即并行应用程序，资源系统以及应用程序调用资源所依据的一定 策略与规则。调度问题就是在满足并行应用程序和资源系统约束条件的基础上，设 计一个有效的调度系统来管理应用程序如何调用这些资源，并使得整个系统性能指 标达到最优或近似最优。它的一般模型如图2 ，4 所示。 图2 4 调度问题的一般模型 9 青岛大学硕士学位论文 分布式系统中的任务调度问题就是根据一定的调度规则和调度策略，把组成并 行程序的一组任务或构成工作负载的一组作业，按照一定执行时序分配到系统中的 多个计算结点上，以期取得较好的系统执行性能。目前许多基于并行分布计算处理 的高性能计算中心的计算环境是由多种并行机或网络工作站系统构成的异构多机应 用系统，并且某些并行机的内部计算结点也可能是异构的，这时不同的应用层次对 任务调度有不同的要求。 2 5 任务调度的分类 d c m a r i n e s c u 等3 将分布式并行计算分为两种模式，一种模式是任务分解为 一些独立的子任务，各个子任务在相应的处理机上并行执行，中间不需要进行同步， 不需要交换彼此的中间结果，最后将子任务汇集成最终结果。另一种模式是协作模 式，计算过程中，各个子任务需要其它予任务的中间结果，也就是它们之间需要同 步，同时开始和同时结束。 文献 3 1 中按算法并行实现的难易程度、通信方式，将具体应用问题分为：( 1 ) 同步( s y n c h r o n o u s ) 问题，即并行计算开始启动时，各任务进程之间的通信( 同步) 方 式和数据交换量大小便已确定，且不随计算的发展而变化；任务进程一般只与它相 邻近的进程进行通信，且每隔一定的计算步长，任务进程之间均同步一次。例如量 子染色动力学( q c d ) 及流体动力学中的数值模拟问题。( 2 ) 松散同步( l o o s e l y s y n c h r o n o u s ) 问题，相对于同步问题，它一般允许任务进程之间的通信( 同步) 方式 和数据交换量大小可随计算的发展而发生变化。例如，等离子体数值模拟、矩阵的 并行l u 分解、自适应多重网格算法、并行优化等等。( 3 ) 非规则松散同步( i r r e g u l a r l o o s e l ys y n c h r o n o u s ) 问题，即各任务进程之间的相互通信( 同步) 关系随计算的 发展不可预知地动态变化，是实现并行最困难的一类问题。例如，基于动态网格生成 的计算流体力学问题。( 4 ) 独立并行( i n d e p e n d e n tp a r a l l e l i s m ) 问题，即任务进程 之间只存在少量的通信与同步，基本可以保持相互独立并行计算。例如，并行随机数 产生器。( 5 ) 异步( a s y n c h r o n o u s ) 问题，即各任务进程从事相互独立的不同工作，极 少需要通信和同步，例如，并行博弈问题。 对于独立并行和异步问题，由于进程间关系较简单，所需的通信少，负载的分 配在时间上没有严格的限制，因而可以采用本是作业一级的负载共享技术，在各个 处理器不同的合适的时段分配其负载。文献 3 2 提出了在异构工作站中的最优化共 享负载的算法。 从不同的角度出发，分布式系统中的任务调度问题有不同的分类方法，下面所 述的各种分类方法同时也比较全面地反映了设计一个任务调度算法时需要考虑的各 种因素。 1 0 第二章分布式系统及其任务调度问题 1 、静态调度和动态调度 按照何时决定每个任务的执行处理机，任务调度方法主要可分为静态调度和动 态调度。静态调度是指在并行程序编译时，就决定每个任务的执行处理机及执行时 序，经常用于任务关系比较确定的情况下：动态调度则是在并行程序运行过程中，根 据当前任务调度及系统执行情况，l 临时决定每个任务的执行处理机及起始执行时刻， 动态调度主要用于任务关系和任务量大小不确定的情况下，但它不可避免地会带来 额外开销。混合调度是介于静态调度和动态调度之间的一种调度方法。在编译时先 静态调度一部分任务，剩余部分则采用动态调度方法在系统运行过程中给它们分配 处理机。静态调度又叫做确定性调度，而动态调度又叫做负载平衡。 2 、集中式调度和分布式调度 按照调度程序的结构或调度程序所收集调度信息的范围，分布式系统中的任务 调度方法可划分为集中式调度和分布式调度。在集中式调度方法中，由一个叫作中 心调度器的处理机来收集全局调度信息，其它处理机把它们的状态信息传送给中心 调度器，并由中心调度器作出调度决定。而分布式调度则是由各自处理单元的调度 程序根据局部范围内的一些调度信息来进行任务调度，其最大优点在于具有良好的 可扩展性。集中式调度的主要优点在于实现比较简单，但在结点数较多的大规模并 行分布系统中，由于各结点与调度服务器的通讯成为瓶颈，所以调度开销比较大； 分布式调度一般都是动态的。 3 、自适应调度和非自适应调度 按照调度程序的调度策略是否随系统状态信息变化而自动调整，分布式系统中 的任务调度可分为自适应调度和非自适应调度这两大类。自适应调度的基本思想就 是根据调度程序在前一段时间内的执行效果，以及当前系统状态信息( 主要包括系统 资源和任务负载情况) 自动修正调度程序的执行机制，由于它们是通过收集当前系统 状态信息来动态修正调度策略，所以一般都是动态的。而非自适应调度方法则一旦 确定任务调度算法的调度策略，那么在并行程序执行过程中就固定地按照这些调度 策略来进行任务调度，即使某些不确定因素( 如动态产生的任务) 使得调度效率比较 低，那么也必须等到非执行状态时，再来修正调度策略。 4 、抢占式调度和非抢占式调度 按照调度程序执行调度操作时是否允许任务抢占执行，可分为抢占式调度和非 抢占式调度。如果一个任务一旦占有处理单元，那么它就不能被中断执行，而是必 须直运行完毕后j j + 释放该处理机，这种情形即为非抢占执行方式，相反如果允许 任务被中断执行而把它所在的处理单元让给其它任务执行，这种情形即为抢占执行 方式，当然这必须假定被抢占任务最终还能获得它所要求的执行时间。 5 、最优调度和次优调度 青岛大学硕士学位论文 按照任务调度目标的实现程度，分布式系统的任务调度划分为最优调度和次优 调度两类。前者以系统的最优调度为目标，获取系统的最高并行度；后者则追求一 种次优调度，以用户要求的时限为标准，达到较高的并行度。因为任务调度问题是 一个n p c 问题没有在多项式时间内找到最优解的算法，所以通常采用启发式算法， 以得到问题的近似最优解。 6 、迁移调度和非迁移调度 按照任务是否允许迁移执行，任务调度可分为两大类：第一类是非迁移调度。 即当一个进程创建时就已决定好它应在的位置，一旦把它放在某台处理机上，它将 一直在那台处理机上运行直至完成。无论它所在的机器负载有多重，也无论有多少 其它的处理机空闲，它都不能移动。另一类是迁移分配调度，即使一个任务已经开 始运行，它也可以移动。这种迁移调度策略能更好地平衡负载，但实现起来非常复 杂。 7 、基于共享存储的任务调度和基于分布存储的任务调度 按照并行分布计算模型的存储器结构，主要可分为基于共享存储的任务调度和 基于分布存储的任务调度这两大类。在共享存储的计算模型上进行任务调度时，一 般不需要考虑通讯延迟，这时任务调度的着重点在于如何最大限度地获得并行程序 任务间的并行性。而在分布存储的计算模型上进行任务调度时，通讯延迟的存在使 得任务调度更为复杂，如果无视通讯延迟的存在，而只考虑尽量增大并行执行时间， 那么有可能在较多处理器上的执行效率还不如在较少处理器上的执行效率随着目前 网络工作站集群系统的广泛应用，尤其是网络带宽的不断提高，基于分布存储的任 务调度问题显得越来越重要。 2 6 异构系统中任务的动态调度问题 2 6 1 动态任务调度策略 静态调度策略在调度前，并行程序的各子任务执行位置己经确定，而且经常用 于任务关系比较确定的情况，但实际的并行程序较难满足此限制，并在执行中存在 众多不确定因素，如： 1 并行程序任务中的循环次数事先不能确定。 2 条件分支语句到底执行哪个分支，在程序执行前不能完全了解。 3 每个任务的负载大小事先不能确定。 4 任务间的数据通讯量大小只有在运行时才能确定。 而且在结点机的负载波动较大时，应考虑采用动态负载平衡的任务调度策略。在分 布式系统中，动态负载平衡就是系统根据当前的系统状态与负载分布的情况，对各 个结点上的工作负载进行动态的调整，使待分配的或者已分配给重载结点的任务， 第二章分布式系统及其任务调度问题 通过通讯设备迁移到轻载结点上去，从而提高系统资源的利用率，减少任务的平均 响应时间。 动态任务分配策略具有超过静态调度策略的执行潜力，能够相互交换系统的状 态信息决定系统负载的分配，能够适应系统负载变化情况，比静态调度策略更灵活、 有效。动态调度策略利用系统状态的短期波动来提高性能，由于它必须收集、储存 并分析状态信息，因此动态调度策略会产生比静态调度策略更多的系统开销，但这 种开销常常可以被抵消掉。 2 6 2 动态任务的调度结构 动态任务调度算法按照调度程序的结构或调度程序所收集调度信息的范围，可 以分为集中式调度算法和分布式调度算法，层次式调度算法。 2 6 2 1 集中式的调度策略 集中式的调度策略系统中有一个负责调度的主机负责搜集系统负载信息。它维 护着一个任务分配表，并且根据系统负载状况来分配任务。其它的主机都是计算主 机，计算主机只负责接收任务，如图2 5 所示 图2 5 集中式动态调度的结构 这种策略的优点是：( 1 ) 调度主机拥有全局信息，易于进行决策并保持负载平衡， 易于跟踪执行情况。( 2 ) 算法比较容易实现，适用于结点数目比较少的网络环境，在 总线形网络上有比较好的性能。 这种策略的缺点是：( 1 ) 单个调度主机要处理大量消息，特别当任务增多时，冲 突增多，调度主机明显成为瓶颈( 2 ) 在调度主机收集所有计算主机的信息时，计算主 机需要等待，浪费了计算主机的处理能力。 在集中式调度策略中，单一的调度结点会成为瓶颈，为了消除调度结点的瓶颈 问题首先需要分析调度结点要处理的负载。调度结点的负载主要由三部分组成：( 1 ) 与所有任务结点的通信，包括发送任务开始所需的参数和接收任务结束时的结果； 青岛大学硕士学位论文 ( 2 ) 调度结点做出决策前，收集所有计算结点的负载信息；( 3 ) 调度结点根据收 集的信息，做出任务调度策略，从而保持整个系统的负载平衡。 基于对调度结点的负载分析，调度策略主要应考虑分散调度结点的负载，使其 不再成为瓶颈，为此可以采用计算结点主动报告策略：把调度结点的第二部分负载 ( 即调度结点收集所有计算结点的信息) 交给计算结点处理。即由计算结点主动、自 适应的定期计算自身的负载，然后发送给调度结点。调度结点在进行决策时，不必 再去收集计算结点的信息，而是根据当前已有的计算结点发来的信息做出决策，这 就减少了计算结点的等待时间，充分利用了计算结点的计算能力。 主动报告策略采用了周期性收集策略和状态变化策略相结合的策略收集负载信 息，计算结点在下列情况下向调度结点发送负载信息： 1 负载变量超过其给定的阈值 2 负载变化量超过其给定的差值： 3 上述两种情况均未成立但达到一定时限： 4 调度结点发来请