（计算机应用技术专业论文）异构系统中基于可用性的抢占式任务调度算法研究.pdf

异构系统中肇于可用性的抢占式任务调度算法研究 摘要 在过去几十年中，异构系统已广泛用于科学和商业之中。近年来，很多学者致力于 研究异构系统中以提高应用程序性能为目的的调度算法。调度理论中的基本假设是所有 机器总是可用来处理任务的。这个假设可能在某些情况下是合理的，但当存在某种维护 要求、中断或其他机器无法处理的限制等这些使机器不可用来处理任务的情况时，它并 不是有效的，而这些约束因素实际存在于许多应用之中。 在本文中，可用性定义为一个计算节点在某一给定的时间间隔内运行的时间占总时 间的比例。现在许多高效能的应用都需要具有高可用性的计算平台，如军事应用、医疗 应用和国际商业应用等都需要非常高可用性的服务，因为只要有一个计算节点不可用都 有可能导致严重故障或致命错误。因此，为了处理维护活动和意外失败等情况，异构系 统的调度策略必须考虑到可用性因素。 为了解决这些问题，本文在对计算机系统可用性进行深入研究的基础上提出了一个 基于可用性的异构系统的任务调度模型，分析了模型的可行性并提出了对抢占式任务的 调度问题，通过对现有算法s s a c ( s c h e d u l i n gs t r a t e g yf o rm u l t i p l ec l a s s e so ft a s k sw i t h a v a i l a b i l i 哆c o m t r a i n t s ) 的改进提出了一种基于可用性、支持多优先级的抢占式任务调 度算法p - s s a c ，并建立了负载平衡探测机制，对可用性的现实应用进行了扩展。该算 法具有与现有算法近似的性能，但其可以工作在抢占模式下，且能保持可用性和响应能 力之间一个良好的平衡，提高了任务的调度成功率。 在仿真实验部分，通过g r i d s i m 模拟器构造了一个含有十六个节点的异构系统，启 用基于可用性的抢占式任务调度算法p - s s a c ，通过新算法与几个经典的算法的实验结 果的比较，表明p s s a c 算法显著提高了系统的可用性，原因在于它在分配任务给异构 结点的过程中考虑了任务的可用性需求。 关键词：异构系统；可用性约束；多类任务；优先调度；抢占式 硕十学位论文 a b s t r a c t i nt h ep a s tf e wd e c a d e s ，h e t e r o g e n e o u ss y s t e mh a sb e e nw i d e l yu s e di ns c i e n c ea n d b u s i n e s s i nr e c e n ty e a r s ，m a n ys c h o l a r sh a v ef o c u s e do nt h es c h e d u l i n ga l g o r i t h mi n h e t e r o g e n e o u ss y s t e m si no r d e r t oi m p r o v ea p p l i c a t i o np e r f o r m a n c e s c h e d u l i n gt h e o r yo ft h e b a s i ca s s u m p t i o ni st h a ta l lm a c h i n e sa r ea l w a y sa v a i l a b l et oh a n d l et h et a s k t h i sa s s u m p t i o n m a yb er e a s o n a b l ei ns o m ec a s e s b u ti ti sn o te f f e c t i v ew h e nt h e r ea g os o m ek i n do f m a i n t e n a n c er e q u i r e m e n t s , i n t e r r u p t i o no ro t h e rr e s t r i c t i o n sw h i c ht h em a c h i n ec a nn o td e a l w i t h ，t h e s em a c h i n e sc a nn o tb eu s e dt oh a n d l et h et a s k i nf a c tt h e s ec o n s t r a i n tf a c t o r sm a y b ei nm a n y a p p l i c a t i o n s i nt h i sa r t i c l e ，a v a i l a b i l i t yi sd e f i n e da sac o m p u t i n gn o d ei nag i v e nt i i n ei n t e r v a l r u n n i n gt i m eo ft h et o t a lp r o p o r t i o no ft h et i m e n o wm a n yl l i g h p e r f o r m a n c ea p p l i c a t i o n s r e q u i r eh i g h a v a i l a b i l i t yc o m p u t i n gp l a t f o r m , s u c h a s m i l i t a r ya p p l i c a t i o n s ，m e d i c a l a p p l i c a t i o n s ，t h ei n t e r n a t i o n a lb u s i n e s sa p p l i c a t i o n sa n ds oo n , r e q u i r ev e r yl l i g ha v a i l a b i l i t y o fs e r v i c e s ，a sl o n ga st h e r ei sac o m p u t i n gn o d ei sn o ta v a i l a b l em a yc a u s es e r i o u so rf a t a l f a u l t t h e r e f o r e ，i no r d e rt od e a lw i t ha c c i d e n t sa n dm a i n t e n a n c ea c t i v i t i e s ，s c h e d u l i n g s t r a t e g yi nh e t e r o g e n e o u ss y s t e m sm u s tt a k et h ea v a i l a b i l i t yf a c t o ri n t oa c c o u n t i no r d e rt os o l v et h e s ep r o b l e m s ，b a s e do nt h ei n t e n s i v es t u d yo ft h ea v a i l a b i l i t yi n c o m p u t e rs y s t e m s ，w es e tu pt h eh e t e r o g e n e o u st a s ks c h e d u l i n gm o d e lo fa v a i l a b i l i t y ， a n a l y z et h ef e a s i b i l i t yo ft h em o d e l ，p r o p o s et h es c h e d u l i n gp r o b l e mo fp r e e m p t i v et a s k s ， p r o p o s eap r e e m p t i v es c h e d u l i n ga l g o r i t h mp - s s a cw h i c hi sb a s e do na v a i l a b i l i t ya n dm o r e s u p p o r t i v ef o rt h ep r i o r i t yt a s k e s t a b l i s ham e c h a n i s mt od e t e c tl o a db a l a n c i n g ，a n de x p a n d t h er e a l i t ya p p l i c a t i o n so ft h ea v a i l a b i l i t y o nt h eb a s i so ft h ec u r r e n ta l g o r i t h ms s a c ，t h e a l g o r i t h mp s s a ch a ss i m i l a rp e r f o r m a n c ew i t ht h ee x i s t i n ga l g o r i t h m , b u ti tc a nw o r ku n d e r t h ep r e e m p t i v em o d e ，a n dc a nk e e pag o o db a l a n c eb e t w e e nt h ea v a i l a b i l i t ya n dt h er e s p o n s e t i m et oi m p r o v et h es u c c e s sr a t eo fs c h e d u l i n g i nt h es i m u l a t i o ne x p e r i m e n t s ，w ec o n s t r u c tah e t e r o g e n e o us y s t e mw i t hs i x t e e n n o d e s ，c o m p a r et h ee x p e r i m e n t a lr e s u l t sb e t w e e nt h en e wa l g o r i t h mp - s s a ca n ds o m ec l a s s i c m e t h o d sb ym a k i n gu s eo ft h eg r i ds i m u l a t o rg r i d s i m , w h i c hs h o w st h a tp - s s a ca l g o r i t h m s i g n i f i c a n t l yi m p r o v e st h ea v a i l a b i l i t yo ft h es y s t e m , b e c a u s ei tt a k e st h ea v a i l a b i l i t yn e e d so f t a s k si n t oa c c o u n tw h e na l l o c a t i n gt h et a s k st ot h eh e t e r o g e n e o u sn o d e s k e yw o r d s ：h e t e r o g e n e o u ss y s t e m s ，a v a i l a b i l i t yc o n s t r a i n t s ，m u l t i c l a s st a s k s ，p r i o r i t y 异构系统中基于可用性的抢占式任务调度算法研究 s c h e d u l i n g , p r e e m p t i v e i v 硕十学位论文 插图索引 图2 1 集群结构图一9 图2 2l v s 集群的体系结构1 0 图2 3 物理观点的系统结构1 1 图2 4 逻辑观点的系统结构。1 1 图2 5 共享多个存储模块的m i m d 结构。1 2 图3 1 集中式动态调度的结构2 0 图3 2 分布式动态调度的结构2 2 图3 3 层次式动态调度的结构2 3 图4 1 调度算法的系统模型2 9 图4 2 举例结点按可用性水平排序2 9 图5 1e d g s i m 模拟的网格系统。4 2 图5 2s i m g r i d 模拟流程框架4 3 图5 3g r i d s i m 模拟的网格系统。4 4 图5 4 到达率对算法p - s s a c 、m i n m i n 与s u f f e r a g e 的性能影响4 6 图5 5 到达率对算法s s a c 和p s s a c 的性能影响4 7 图5 6p - s s a c 的抢占增益g 4 8 v 异构系统中基于可用性的抢占式任务调度算法研究 暑昌暑暑暑詈= 皇暑詈詈詈兽昌昌鲁昌鲁昌暑皇暑鲁篁鲁昌暑昌詈昌詈暑詈詈詈詈詈昌皇= 詈= = 昌喜詈詈詈詈詈詈詈詈昌暑詈= = = 暑暑詈詈詈詈詈詈詈昌詈詈詈= = = 詈詈= = 墨詈= 詈= 鲁詈暑詈詈詈詈詈詈詈詈詈詈置暑置| 暑詈詈詈詈詈詈詈詈詈= 詈詈皇j ii i i i 附表索引 表4 1 标识名的定义3 0 表5 1 系统参数的特征4 5 v 硕士学位论文 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成 果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表 或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律后果由本人承担。 作者签名：压溆日期：帅 了月i 目 ， 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向 国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权湖 南大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 保密口，在一年解密后适用本授权书。 2 不保密函 ( 请在以上相应方框内打 ) 作者签名g 孳日期：沙7 年3 月砂日 导师签谚够吼叫年弓月乡日 硕士学位论文 1 1 选题背景 第1 章绪论 随着i n t e r n e t 技术的迅猛发展，计算机技术已进入以网络为中心的计算时期，网络 技术、性能的不断提高，高可伸缩性、高可用性、可管理性、价格有效性的网络服务技 术将成为网络服务技术的主导。而摩尔定律的慢慢失效和人们为了追求信息系统的高性 能和高可靠性，单c p u 的集成电路技术和工艺慢慢走到了技术的极限。另外，以高性 能计算机为基础的计算科学得到了长足的发展，它与理论科学和实验科学相辅相成、彼 此印证，成为人类科学研究必不可少的方法之一。在许多工业领域，如汽车、航空航天 器的设计制造、石油勘探、地震资料处理及国防( 核爆炸模拟) 等，科学计算已经成为 首选研究方法。所以并行计算平台正从昂贵专用的超级计算机转向集群系统，它是通过 高速互联网络连接起来的多台自治计算机和相关资源组成的高性能系统。对集群系统的 研究正成为一个新的研究方向。 集群计算的主要目标是通过网络互连实现全系统范围内的资源的共享，并且通过高 效的资源管理和任务调度技术实现资源的有效共享，从而提高资源利用率，获得高性能。 在集群系统中，由于各节点、多种资源、管理机制、用户和应用程序间存在大规模的异 构性，所以对资源的管理、重用、交互和共享，以及如何提高系统性能正成为一个突出 的问题【l 刀。任务调度和高效的负载平衡算法是优化系统、提高系统性能的关键所在1 3 1 ， 它不仅能合理地利用系统中的各种资源，还能平衡各节点的负载，充分发挥节点和资源 的作用。 为了有效地协调不同任务在竞争处理器时的关系，我们用任务调度器来决定处理器 在什么时候执行什么任务1 4 j 。任务调度在处理任务之间关系时，有两种策略：p r e e m p t i v e 和c o o p e r a t i v e 。在一个p r e e m p t i v e 系统中，一个任务在它的执行时间里被赋予了优先权， 这意味着任务调度器能够根据系统所处的阶段将处理器分配给其他的任务。对于需要长 执行时间的任务来说，赋予优先权是一个非常好的方法，重要性更高的任务将比重要性 低的任务更有效地利用处理器。在一个c o o p e r a t i v e 系统中，每一个任务在它的执行时间 里独占c p u ，除非任务自动放弃对处理器的控制，否则任务间的切换不会出现。有两种 基本的调度方式：静态调度( 根据时间来进行调度) 和动态调度( 根据事件来调度) 。 在静态调度方式下，提前定义了任务的执行顺序。在动态调度的方式下，一个任务在运 行其间是否被执行由系统状态来决定，任务调度器根据当前的任务状态进行调整。在动 态调度方式下，只有当存在实际需要时( 出现一个外部事件) ，处理器才执行任务，处理 器的能力将得到更有效的利用( 这与静态调度方式无关) 。所以在集群系统中，为了减少 异构系统中基于可用性的抢占式任务调度算法研究 任务执行时间和通信成本，经常采用不同的任务调度策略来提高系统的吞吐量和整体性 能。 负载平衡问题主要分为静态负载平衡和动态负载平衡。人们利用系统的相关信息， 以数学公式或者是其它方法将静态任务进行划分 5 1 并分配到集群系统的各个节点上，间 接地实现了静态负载平衡。而根据系统当前的负载状态，依照相关策略将各节点上的任 务进行调度，动态做出负载迁移的决定，直接地实现了动态负载平衡。在大部分状况下， 动态负载平衡所表现出来的系统性能明显优于静态负载平衡。因此，动态负载平衡是许 多研究学者的研究焦点 6 - 8 1 。 一个负载平衡算法一般由三个部分构成。首先制定任务放置策略的制定者使用的负 载和任务量，以及信息分配的方式；然后基于任务和计算机负载，判断是否要把一个任 务传送到其它计算机上处理：最后对于适合传送到其它计算机处理的任务，选择任务将 被传送的目的计算机。负载平衡算法的三个部分之间是以不同的方式相互作用的。放置 策略利用信息策略提供的负载信息，仅当任务被传送策略判断为适于传送之后才行动。 总之，负载平衡的目标是：提供最短的平均任务响应时间；能适于变化的负载；是可靠 的负载平衡机制。 由于集群系统构造的复杂性，节点和资源的广泛分布，以及资源动态变化，应用之 间的资源竞争对整体系统的性能影响很大。高效的负载平衡算法必须能够充分利用节点 资源、提高系统的负载平衡且减少任务的完成时间。因此，资源利用率、系统负载平衡 和任务完成时间成为评价算法性能的标准。 1 2 课题目的和意义 在现代生活中，计算机系统被广泛地应用于各个方面。无论是在军事、金融、电信 等关系到国计民生的关键性部门和行业，还是在平时的日常生活中，都广泛地使用计算 机系统处理信息。随着计算机应用的不断深入，人们对计算机系统可用性( a v a i l a b i l i t y ) 的要求越来越高。人们不仅希望能够保障关键业务数据信息的完整，而且希望网络应用 能够不问断或者在最短的时间内自动恢复，这就是所谓的计算机系统的高可用性f f n g h a v a i l a b i l i t y ) 问题。 在多样的计算机研究领域里，系统性能方面一直是研究和关注的重点。这使得过去 的几十年里，计算机系统的处理能力有了巨大的飞跃，而价格却不断下降。然而随着计 算机系统应用的普及和系统复杂性及规模的不断提高，系统故障频繁产生，而由此导致 系统维护费用在拥有全花费t c o ( t o t a lc o s to f o w n e r s h i p ) 中所占的比率越来越高，受到越 来越多的关注。 根据i d c ( i n t e r n a t i o n a ld a t ac o r p ) 针对以集群为基础提供信息服务的网站系统所做 的调查结果显示：三分之一到一半的t c o 用在系统失效的恢复和为防止系统失效所做 的准备上。公司都宣称它们的产品能达到9 9 9 9 9 的可用性，然而如今管理良好的服务 2 硕上学位论文 器的可用性只达到9 9 到9 9 9 ，也就是每年8 到小时的停机时间。以电子商务系 统为例，专门研究关键业务软件和电子商务的市场研究公司s t a n d i s hg r o u pi n t e r n a t i o n a l 进行了一项研究，尝试量化系统停机所造成的成本。数据表明，对于一个事务处理系统， 与停机相关联的成本大约为每分钟25 0 0 美元，相当于每小时1 5 万美元。事实上，与营 业高峰期停机相关联的成本估计为每分钟78 0 0 美元，也就是每小时4 6 80 0 0 美元。尽 管这些数字对于一次停机的损失只提供了保守的估计，但确实从侧面说明了企业为什么 要重视保持系统2 4 * 8 小时的正常运行。所以提高系统可用性成为现代网络应用的迫切 需要。 1 3 国内外的研究现状 在过去几十年中，异构系统已广泛用于科学和商业之中。近年来很多学者致力于研 究异构系统中以提高应用程序的性能为目的的调度算法。d o g a n 和o z g u n e r 研发了异构 分布式系统中针对优先约束任务的可靠匹配和调度算法阴。s r i n i v a s a n 和j h a 把可靠性成 本定义为处理器的故障率和任务执行时间的乘积，并将其加入到针对具有优先权约束的 任务的调度算法之中【1 0 l 。r a n a w e e r a 和a g r a w a l 针对异构系统提出了一种称为可扩展的 基于任务重叠的调度算法【l ，该调度算法的目标是通过以某种方式对任务结点的执行顺 序进行排序来优化整体性能。 如果一个或多个节点由于随机中断或定期检修而出现故障，异构系统的性能将会退 化。在另一方面，现在许多高效能的应用都需要具有高可用性的计算平台，如军事应用、 医疗应用和国际商业应用等都需要非常高可用性的服务，因为只要有一个计算节点不可 用都有可能导致严重故障或致命错误。因此，为了处理维护活动和意外失败等情况，异 构系统的调度策略必须考虑到可用性因素。 具有可用性约束的多类任务的调度问题已广泛出现在现实生活的分布式应用中，例 如可升级的网络服务器系统、分布式异构服务器和建立在高速网络上的一般多类系统。 在许多的多类应用中，新进来的请求会立即分配给结点集中的一个计算节点，其中的每 个节点通过运行一个局部排序算法来独立执行一个进程0 2 j 3 。遗憾的是，异构系统中传 统的多类任务调度算法，只注重于高吞吐量从而达到减少响应时间的目的，完全漠视多 类任务的可用性需求。然而，要想同时获得高吞吐量和高可用性是具有挑战性的，因为 他们是两个相冲突的目标。例如，分配一个关键且具有高可用性需求的任务给一个高速 但低可用性的结点，这是不能接受的。一个理想的调度计划，应该在保证任务可用性需 求的同时，还能有效地减少响应时间。 很多学者已经就对具有可用性约束的任务进行资源分配的策略做了调查研究。 s m i t h 介绍了一种有关资源可用性的数学模型，并提出了一种当有新的任务预定或分配 时能保持可用性信息的方法【1 4 】。a d i r i 等人研究了具有可用性约束的单台机器中的调度 3 异构系统中基于可用性的抢占式任务调度算法研究 问题【1 5 1 。q i 等人研发了三种启发式算法来解决维修机器时的调度工作问题1 1 6 j 。最近， k a c c m 等人研究了一种分支定界方法来解决单机可用性约束的调度问题【l 。l e e 研究了 两机调度问题，其中至少一台机器具有可用性约束【l 踟，该问题的最佳解决方案是l e e 提 出的虚拟多项式动态设计算法。m o s h c i o v 提出了在相同并行机环境下可用性约束的调度 问题1 1 9 j 。s a d f i 和o u a r d a 研究了一种动态编程的方法来解决并行机可用性约束的调度问 题【捌。越来越多的调度问题都存在于机器不能持续可用来处理的情况之中。虽然上述方 案都考虑到了可用性约束的调度问题，但他们对于异构系统中运行的多类应用程序还存 在不足，因为他们要么侧重于单一的机器、两台机器或者同构系统，而且所有这些都只 考虑单类任务的应用。为了弥补这个不足，本文陈述了异构系统中基于可用性约束的多 类任务的调度问题。具体来说，本文的目标是研发一种新颖的调度策略用于提高异构系 统的可用性，同时又能保证多类任务在平均响应时间上的良好性能。本文利用泊松分布， 设计了异构系统中基于可用性的调度算法，其中异构系统的运算能力和可用性约束是一 个先验。 1 4 本文研究内容 在前期的工作中，已经研究了嵌入式系统、集群系统和网格系统的安全性调度问题， 但是这些调度算法是专为同构系统而设计的。此外，先前的调度算法并不适合多任务与 可用性的要求。但是，本文所提出的这种算法能保持可用性和响应能力之间一个良好的 平衡。本文在对计算机系统可用性进行深入研究的基础上提出了一个基于可用性的异构 系统的任务调度模型，分析了模型的可行性并提出了对抢占式任务的调度问题，对可用 性的现实应用进行了扩展。 本文首先从异构系统的特点、层次和体系结构出发，研究了具有可用性需求的多类 任务调度模型，并根据影响任务调度的因素对任务响应时间的关系，提出了一种面向异 构系统的基于可用性的抢占式任务调度算法。具体内容如下： 1 可用性需求 调度理论中的基本假设是所有机器总是可用来处理任务的。这个假设可能在某些情 况下是合理的，但当存在某种维护要求、中断或其他机器无法处理的限制等这些使机器 不可用来处理任务的情况时，它并不是有效的【2 1 1 ，而这些约束因素实际存在于许多应用 之中。例如，在异构系统中，计算节点需要定期维护以防止出现故障。在本项研究中， 可用性定义为一个计算节点在某给定的时间间隔内运行的时间占总时间的比例。一个 多类应用由多类任务组成，每类任务都有不同的到达率、执行时间的分配和可用性需求。 2 2 1 2 任务调度 在研究分析异构系统的结构时，对异构系统进行了模型化，并对在异构系统中进行 任务调度作了深入的研究。由于异构系统侧重点的不同，任务调度有多种分类方式。常 4 硕士学位论文 见的分类有：根据调度算法和可调度性判定是在任务运行之前还是运行其间进行的，分 为静态调度、动态调度和混合调度；按照调度程序的结构或调度程序所收集调度信息的 范围，划分为集中式调度和分布式调度；按照调度程序的调度策略是否随系统状态信息 变化而自动调整，可分为自适应调度和非自适应调度两大类；按照任务调度目标的实现 程度，划分为最优调度和次优调度两类；根据被调度的任务是否可以互相抢占，分为抢 占式调度和非抢占式调度；按照任务是否允许迁移执行，分为迁移调度和非迁移调度； 按照并行分布计算模型的存储器结构，主要可分为基于共享存储的任务调度和基于分布 存储的任务调度。不同调度方式具有各自的优缺点，适应于不同的异构系统。 本文中任务调度采用的是抢占式调度，关键是可用性与平均响应时间之间的平衡问 题，因此调度算法的目的在于提高系统的可用性且保证提交任务的最佳响应时间。 3 负载平衡 在对负载平衡的研究中，可以根据对任务的划分和分配将负载平衡分为静态负载平 衡和动态负载平衡。本文针对负载平衡策略进行研究，为充分满足任务的可用性需求， 调度算法侧重于把任务分配给具有高可用性水平的一组结点。但由于一个结点的可用性 水平与它的计算速度是成正交关系的，调度算法有可能将大量任务分配给一个具有高可 用性但计算速度低的结点，那么由于负载不平衡，调度算法获得的平均响应时间必然会 受到严重影响。为了避免负载不平衡的影响，调度算法建立了一种负载不平衡探测机制 来探测系统中结点是否负载过重。 1 5 论文组织结构 按照研究工作完成的顺序，论文的组织结构和章节安排如下： 第一章为绪论，介绍本文的选题背景、课题目的和意义及国内外研究现状，并对研 究内容、整个研究使用的方法与流程做了简单的说明。 第二章为背景知识，对集群系统、分布式系统的特点、层次、模型以及可用性技术 进行了介绍，提出了本课题的研究对象和目标。 第三章为异构系统中任务调度算法研究，对任务调度方式和调度策略展开了深入的 研究，发现了影响任务调度的关键问题所在，为后面的新算法提供了理论基础。 第四章为异构系统中基于可用性的抢占式任务调度，对具有可用性需求的多类任务 进行建模，并对问题公式化，建立了负载不平衡探测机制，提出了异构系统中基于可用 性的抢占式任务调度算法。 第五章利用g r i d s i m 网格模拟器，通过新算法与几个经典的算法的实验结果的比较， 得出相关的结论。 最后是全文的总结和研究工作展望。 5 异构系统中基于可用性的抢占式任务调度算法研究 第2 章背景知识 本章首先介绍了集群系统和分布式系统的特点、类型和结构的优缺点，然后通过分 析可用性问题的研究现状、体系结构和理论研究，提出本课题研究的对象和目标。 2 1 集群系统 小型化、并行化、网络化和智能化是当今计算机发展的主要趋势，集群系统是这些 发展的主要挑战性问题之一，也是当前计算机科学的一个研究热点。集群系统是一种并 行或者分布处理系统，它由一组互连的单机组成，这些单机协调工作提供一个单一的、 完整的计算资源。它利用一定的智能机制实现动态的网络范围内的资源共享，并随着资 源供求的变化而变化。这种机制给集群带来了可扩展性，而且允许灵活地使用工作站， 因为集群或网络范围内的可用资源应该比集群中某个节点、工作站上的资源充足。智能 机制同样使得集群能支持多用户、分时共享和并行执行环境。在这种系统中，可以通过 共享资源和动态分配负载从而有效利用全局资源。有效地开发工作站集群计算能力的想 法已经在高性能计算领域内得到高度重视，当前的趋势也更倾向于这种商品化的超级计 算机。集群计算已被认为是未来解决大型科学或商业计算的主流方案。 2 1 1 集群系统的特点 集群是将普通p c 工作站、工作站或服务器通过某种方式连接起来构成的多机系统。 连接方式可以采取通过网络适配器和网络集线器，或通过将各个机器的r s 2 3 2 串口直 接连接起来，还可以通过内存通道卡和内存通道集线器的方式连接各台机器。 集群系统具有以下特点： ( 1 ) 可用性。即它们都能够在集群的某部分资源出现故障的情况下继续向用户提 供持续的服务。几乎所有的典型集群都拥有灾难恢复功能。 ( 2 ) 良好的可扩展性。只需很少的配置工作就可以方便地向集群中加入或删除工 作节点。 ( 3 ) 良好的可管理性。管理人员通过简单的操作就可以对集群中的工作节点或控 制节点进行配置工作。 集群系统一般都提供了负载平衡功能。负载平衡包括静态负载平衡和动态负载平 衡，为了最大程度地利用集群中的一切资源，集群需要具有动态负载平衡功能，它能够 通过监视集群中的实际节点的负载情况动态地进行调度的改变。 大部分集群系统都有一个主控机，它能够对集群中的机器的运行状态进行监视，而 6 硕十学位论文 且能够根据各机器的负载轻重进行任务的调度。 2 1 2 集群系统的类型 最常见的三种集群类型包括高性能科学集群、负载均衡集群和高可用性集群。 1 高性能科学集群 通常，第一种用来为集群开发并行编程应用程序，以解决复杂的科学问题。这是并 行计算的基础，尽管它不使用专门的并行超级计算机，这种超级计算机内部由十至上万 个独立处理器组成。但它却使用商业系统( 如通过高速连接来链接的一组单处理器或双 处理器p c ) ，并且在公共消息传递层上进行通信以运行并行应用程序。因此，我们会常 常听说又有一种便宜的l i n u x 超级计算机问世了。但它实际是一个计算机集群，其处理 能力与真的超级计算机相等，通常一套集群系统的配置开销要超过$ 1 0 00 0 0 。这对一般 人来说似乎是太贵了，但与价值上百万美元的专用超级计算机相比还算是便宜的。 消息传递接n ( m e s s a g ep a s s i n gi n t e r f a c e , m p l ) 是并行集群系统间消息传递层的最常 见实现。m p i 存在几种衍生版本，但在所有情况下，它为开发者访问并行应用程序提供 了一个公共a p i ( a p p l i c a t i o np r o g r a mi n t e r f a c e ，应用程序接口) ，这样开发者就不必手工 解决如何在集群的节点之间分发代码段。 2 负载均衡集群 负载均衡集群为企业需求提供了更实用的系统。如名称所暗示的，该系统使负载可 以在计算机集群中尽可能平均地分摊处理。该负载可能是需要均衡的应用程序处理负载 或网络流量负载。这样的系统非常适合于运行同一组应用程序的大量用户。每个节点都 可以处理一部分负载，并且可以在节点之间动态分配负载，以实现平衡。对于网络流量 也如此。通常，网络服务器应用程序接受了太多入网流量，以致无法迅速处理，这就需 要将流量发送给在其它节点上运行的网络服务器应用，还可以根据每个节点上不同的可 用资源或网络的特殊环境来进行优化。 负载均衡集群在多节点之间分发网络或计算处理负载。在这种情况下，区别在于缺 少跨节点运行的单并行程序。大多数情况下，那种集群中的每个节点都是运行单独软件 的独立系统。但是，不管是在节点之间进行直接通信，还是通过中央负载均衡服务器来 控制每个节点的负载，在节点之间都有一种公共关系。通常，使用特定的算法来分发该 负载。 3 高可用性集群 高可用性 i i g ha v a i l a b i l i t y , h a ) 集群的出现是为了使集群的整体服务尽可能可用， 以便考虑计算硬件和软件的易错性。如果高可用性集群中的主节点发生了故障，那么这 段时间内将由次节点代替它。次节点通常是主节点的镜像，所以当它代替主节点时，它 可以完全接管其身份，并且因此使系统环境对于用户是一致的。 7 异构系统中基于可用性的抢占式任务调度算法研究 在集群的这三种基本类型之间，经常会发生混合与交杂。于是，可以发现高可用性 集群也可以在其节点之间均衡用户负载，同时仍试图维持高可用性程度。同样，可以从 应用程序的集群应用中找到一个并行集群，它可以在节点之间执行负载均衡。尽管集群 系统本身独立于它在使用的软件或硬件，但要有效运行系统时，硬件连接将起关键作用。 高可用性集群致力于使服务器系统的运行速度和响应速度尽可能快。它们经常使用 在多台机器上运行的冗余节点和服务，用来相互跟踪。如果某个节点失败，它的替补将 在几秒钟或更短时间内接管它的职责。因此，对于用户而言，集群永远不会停机。某些 h a 集群也可以维护节点间冗余应用程序。因此，用户的应用程序将继续运行，即使他 使用的节点出了故障，正在运行的应用程序会在几秒之内迁移到另一个节点，而所有用 户只会察觉到响应稍微慢了一点。但是，这种应用程序级冗余要求将软件设计成具有集 群意识的，并且知道节点失败时应该做什么。但对于l i n u x ，大多数现在还做不到。因 为l i n u x 系统没有h a 集群标准，并且也没有公共a p i 可供应用程序开发者构建有集群 意识的软件。 h a 集群可以执行负载均衡，但通常主服务器运行作业，而系统使辅助服务器保持 闲置。辅助服务器通常是主服务器操作系统设置的镜像，尽管硬件本身稍有不同，辅助 节点对主服务器进行活动监控或心跳观察，以查看它是否仍在运行。如果心跳计时器没 有接收到主服务器的响应，则辅助节点将接管网络和系统身份( 如果是l i n u x 系统，则 是p 主机名和地址) 。 2 1 3 集群系统的结构 集群系统是由专用或通用网络上一组互联的计算单元及相关的资源构成的一个整 体，可被用户视为单一的计算环境使用【2 习。一个计算单元可以是一个具有存储器、f o 设备和操作系统的单机或者多处理器系统( p c 机、工作站或者s m p 机器) 。一个集群 一般指的是两个或者两个以上互相连接起来的计算机( 节点) 。这些节点可以放在同一 个机柜中，也可以分布在不同的地方并通过局域网连接。一个( 通过局域网) 互连的集 群对使用者和应用程序来说表现为一个单一的系统。这样的系统能够廉价地获得原来只 有昂贵的私有共享存储系统才具有的特征和优点。集群的典型结构如图2 1 所示。 网络接口硬件充当一个通信处理器并且负责在集群各节点之间通过网络或者交换 机收发数据包。 通信软件在集群各节点以及集群和外界之间提供了一个快捷、可靠的数据通信手 段。具有特殊网络或者交换机的集群经常采用积极消息以便在节点间实现快速通信。它 们实际上绕过了操作系统，去掉了很多的通信开销，从而给用户提供了到网络的直接访 问接口。 8 硕上学位论文 2 1 4 集群系统的发展趋势 图2 1 集群结构图 随着网络技术、性能的不断提高，各种平台下的网络服务技术方案应运而生。其中 影响最大的是由章文嵩博士成立的l v s ( l i n u xv i r t u a ls e r v e r ) 自由软件项目，进行l i n u x 服务器集群的开发工作。同时，l v s 项目也是国内最早出现的自由软件项目之一。该项 目针对高可伸缩、高可用网络服务的需求，给出了基于p 层和基于内容请求分发的负 载平衡调度解决方法，它通过前端一个负载调度器( l o a db a l a n c e r ) 无缝地将网络请求 调度到真实服务器上，从而使得服务器集群的结构对客户是透明的，客户访问集群系统 提供的网络服务就像访问一台高性能、高可用的服务器一样，客户程序不受服务器集群 的影响且不需作任何修改。系统的伸缩性通过在服务集群中透明地加入和删除一个节点 来达到，通过检测节点或服务进程故障和正确地重置系统达到高可用性，并在l i n u x 内 核中实现了这些方法，将一组服务器构成一个实现可伸缩的、高可用网络服务的虚拟服 务器。 l v s 集群采用p 负载平衡技术和基于内容请求分发技术。调度器有很好的吞吐率， 将请求均衡地转移到不同服务器上执行，且调度器自动屏蔽服务器的故障，从而将一组 服务器构成一个高性能的、高可用的虚拟服务器。整个服务器集群的结构对客户是透明 的，而且无需修改用户端和服务器端的程序。 为此，设计需要考虑系统的透明性、可伸缩性、高可用性和易管理性。一般来说， l v s 集群采用三层结构，其体系结构如图2 2 所示，三层主要组成部分为： 负载调度器( l o a db a l a n c 圮r ) ，它是整个集群对外面的前端机，负责将客户的请求 发送到一组服务器上执行，而客户认为服务是来自一个p 地址( 我们可称之为虚拟m 地址) 上的。 服务器池( s e r v e rp 0 0 1 ) ，是一组真正执行客户请求的服务器，执行的服务有w e b 、 9 异构系统中基于可用性的抢占式任务调度算法研究 m a i l 、f t p 和d n s 等。 共享存储( s h a r e ds t o r a g e ) ，它为服务器池提供一个共享的存储区，这样很容易使 得服务器池拥有相同的内容，提供相同的服务。 图2 2l v s 集群的体系结构 负载调度器、服务器池和共享存储系统通过高速网络相连接，如l o o m b p s 交换网络、 m y r i n e t 和g i g a b i t 网络等。使用高速的网络，主要为避免当系统规模扩大时互联网络成 为整个系统的瓶颈。 2 2 分布式系统 2 2 1 分布式系统概述 未来对计算速度、系统可靠性和成本实效性的要求必将促使发展另外的计算机模型 来替代传统的冯诺依曼结构的计算机。随着计算机网络的出现，一个新的梦想成为可能 分布式计算。当用户需要完成某项任务时，分布式计算提供尽可能多的计算机处理能 力和数据的透明访问，同时实现高性能与高可靠性的目标。 对分布式系统我们使用如下定义： 一个分布式系统是一个对用户看起来像普通系统，然而运行在一系列自治处理单元 ( p r o c e s s i n ge l e m e n t ，p e ) 上的系统，每个p e 有各自的物理存储器空间并且信息传输延 迟不能忽略不计，且在这些p e 间有紧密的合作。系统必须支持任意数量的进程和p e 的动态扩展。图2 3 和2 4 从物理的和逻辑的观点表示了这样一个系统 在硬件结构上，尽管所有的分布式系统都是由多个自治处理单元构成的，但可以用 不同的方法将硬件组织起来，形成不同的系统。按照体系结构划分，当前典型的分布式 系统可分为两种：共享存储多处理机和分布存储多计算机。如果结点间通过公用存储器 中的共享变量实现相互通信，就称为多处理机( m u l t i p r o c e s s o r ) ；如果结点间使用消息传 递方式来实现相互通信，就称为多计算机( m u i t i c 0 l p l l t e r s ) 渊。 1 0 硕士学位论文 图2 3 物理观点的系统结构 图2 4 逻辑观点的系统结构 共享存储多处理机属于紧密耦合的分布式系统，采用共享主存通信。由于处理机与 主存之间互连网络带宽有限，所以当处理机数增多时，访问主存的冲突概率会加大，互 连网络会成为系统性能的瓶颈。但由于是单一地址空间，所以较易于编程。 分布存储多计算机属于松散耦合的分布式系统。由于每个计算结点的本地存储器容 量较大，所以运算时所需的绝大部分指令和数据均可取自本地存储器。当不同计算结点 上的进程需要通信时，就可通过接口进行消息交换。在有的松散耦合的多计算机系统中， 其计算结点本身就是一台完整的计算机，这样就演变成了现代的集群系统。这种松散性 耦合结构易于扩展，但多地址空间却使编