（计算机应用技术专业论文）并行任务调度系统ldpvm的设计与实现.pdf

华中科技大学硕士学位论文 摘要 f 任务调度是并行分布计算中最为基本、最为关键的问题之一，是影响并行分布 计算执行效率的一个关键因素。随着基于并行分布处理的高性能计算的日益普及， 如何针对不同的具体应用与并行分布系统环境，而采用有效的调度方法来提高系统 的执行性能，已愈来愈成为人们研究的热点7 p v m 是最为重要的并行编程环境之一。 围绕p v m 环境下l n l ：x 集群系统的并行任务调度系统的设计问题，提出了套解决 方案，实现了一种采用负载预测方式的集中式的动态调度算法。 提出了一种利用人工神经网络技术预测系统负载的方法。采用人工神经网络中 应用得比较广泛的b p 网络，利用任务在结点上的历史执行信息，预测结点的负载 变化情况。与通常的方法相比，预测方式的信息更加确切，使得在此基础上设计的 调度算法的性能有了一定的提高。 根据不同的编程模式包括基本模式和协作模式分别提出不同的调度策略。对于 基本模式的并行任务，采用任务队列的方式进行调度；对于协作模式的并行任务， 选择一组合适的结点执行。对于有一些特定要求的任务采用特定的策略选择合适的 结点执行。 最后，对实现的任务调度系统l d p v m 与p v m 系统的性能进行了比较。测试项目 包括基本模式下和协作模式下的各个结点分配的任务数目及任务响应时间比较。实 验结果表明，在结点处理能力不同的环境下，l d p v m 的性能要远高于p v m 的性能。 关键词：负载平衡：任务调度：人工神经网络；负载预测 华中科技大学硕士学位论文 a b s t r a c t a so n eo ft h em o s tf u n d a m e n t a l a n d i m p o r t a n tp r o b l e m s i np a r a ll e l d i s t r i b u t e dc o m p u t i n g ( p d c ) t a s ks c h e d u l i n gi sak e yf a c t o rt h a t h a sm u c h i n f l u e n c eo nt h ee x e c u t i o ne f f i c i e n c yo fp d c w i t ht h e i n c r e a s i n g p o p u l a r i z a t i o no fh i g hp e r f o r m a n c ec o m p u t i n gb a s e do np a r a l l e l d is t r i b u t e d p r o c e s s i n g ，f o rd i f f e r e n ta p p l i c a t i o n sa n dp d ce n v i r o n m e n t s ，t h eq u e s t i o n o fh o wt ot a k ee f f i c i e n ts c h e d u l i n gs t r a t e g i e st oi m p r o v es y s t e mp e r f o r m a n c e h a sm o r ea n dm o r eb e c o m et h er e s e a r c hf o c u s p a r a l l e lv i r t u a lm a c h i n e ( p v m ) iso n eo ft h em o s t i m p o r t a n tp a r a l l e lp r o g r a m e n v i r o n m e n t g i nt h is d i s s e r t a t i o n as o l u t i o nf o c u s e do n d e s i g np r o b l e m so f p a r a l1 e l t a s k s c h e d u l i n gs y s t e mo f l i n u xc l u s t e r si np v mi s p r e s e n t e da n d ac e n t r a l s c h e d u li n ga i g o r i t h mu s i n gh o s tl o a dp r e d i c t i o ni s i m p l e m e n t e d ah o s t 1 0 a dp r e d i c t i o nt e c h n i q u eu s i n ga r t i f i c i a ln e u r a in e t w o r k ( a n n ) isp r o p o s e di nt h isd i s s e r t a t i o n b pn e t w o r k ，w h i c hisw i d e l yu s e di na n n isa d o p t e dt op r e d i c tt h ec h a n g i n go fh o s tl o a ds t a t u eb yu s i n gt h ee x e c u t i n g h i s t o f i c a li n f o r m a t i o no ft a s k s c o m p a r e dw i t ht h en o r m a im e t h o d ，t h e p r e d i c t e di n f o r m a t i o ni sm o r ea c c u r a t e w h i c hh a si m p r o v e dt h ep e r f o r m a n c e o fs c h e d u l i n ga i g o r i t h m d i f f e r e n ts c h e d u l i n ga l g o r i t h m sa r ep r e s e n t e dr e s p e c t i v e l yt od i f f e r e n t p r o g r a mm o d e l si n c l u d i n gb a s i cm o d e la n dc o o p e r a t i o nm o d e l t h et a s kq u e u e m o d ei su s e df o rp a r a l l e lt a s k so fb a s i cm o d e l ag r o u po fs u i t a b l en o d e s a r es e l e c t e dt oe x e c u t e p a r a l l e l t a s k so f c o o p e r a t i o n m o d e l s p e c i a l d o l i c i e sa r ea d o p t e dt os e l e c ts u i t a b l en o d e sf o rs o m et a s k sw h i c hh a v e s p e ci a l n e e d f i n a l l y ，ap e r f o r m a n c ec o n t r a s t o fp v ma n dl d p v m ，at a s k s c h e d u l i n g s y s t e mi m p l e m e n t e d i nt h i sd i s s e r t a t i o n i sp r e s e n t e d t h e e x p e r i m e n t s c o n s i s to ft h en u m b e ro ft a s k sa s s i g n e dt oe a c hn o d ea n dr e s p o n s et i m ei n b a s i cm o d e la n dc o o p e r a t i o nm o d e l t h ee x p e r i m e n tr e s u l t ss h o wt h a t ，i nt h e e n v i r o n m e n t so fh o s t sw i t hd i f f e r e n tp r o c e s s i n gp o w e r s ，t h ep e r f o r m a n c eo f l d p v mi sm u c hh i g h e rt h a nt h a to fp v k e y w o r d s ：l o a db a l a n c i n g ：t a s ks c h e d u l i n g ；a r t i f i c i a ln e u r a ln e t w o r k ；l o a d p r e d i c t i o n 华中科技大学硕士学位论文 1 1 问题的提出 l 绪论 随着工作站和p c 机性能的迅速提高和价格的日益下降，以及高速网络的发展，利用 由一群以网络技术连接起来的工作站或p c 机而构成的集群系统作为并行分布计算的平 台，r 益受至u 广泛的重视和欢迎。基于网络的并行技术方法已经被证明是一种有生命力、 高效的方法。松散耦合计算机上的群计算或并行处理是一项迅速发展的技术，为实现高 性能的应用提供了巨大的潜力。 使用工作站集群系统运行并行应用程序越来越成为代替专用，特别是昂贵的并行计 算机平台的发展趋势。为了支持集群系统的并行处理，人们从不同的角度入手，研制出 各种各样的并行程序设计环境。有的从程序设计语言的角度出发，在程序设计语言中引 入了有利于并行性开发的语言元素，这样的系统有l i n d a 9 ：，e m e r a l d 等，前者是基于分 布式共享存储计算模型的，而后者是基于消息传递的计算模型。1 ；还有的从程序辅助开 发工其的角度出发，开发了并行操作原语库，如p v m 。：、卿i 等，它们都是基于消息传递 的计算模型。 在集群系统并行分布计算中，并彳亍任务的调度方案极大的影响了应用程序的运行性 能。在实际应用领域中，由于集群系统结构和程序本身的不确定性，往往需要在运行时 进行动态调度，以实现负载平衡。 按照不同的应用层次，并行分布计算中的调度问题可以分为两大类，即任务层调度 和作业层调度，有时也把它们两者统称为并行分布计算中的任务调度问题。在本论文中， 我们把前者称为任务调度，把后者称为作业调度。 集群系统下并行分布计算的负载平衡的目的主要有： 1 资源共享。此类负载平衡面向的主要是作业的调度问题。观察表明，在大部分时 矧罩工作站基本处于空闲状态。即使在利用率较高的时间段，也有相当数量的机器空闲。 采用负载平衡技术，将作业分配到空闲工作站上运行，既能缩短作业的平均响应时蚓， 又可以显著提高工作站的利用率。目前这方面的研究已经进入实用商品化阶段。比较著 名的产品有i b m 公司的l l ( 1 0 a dl e v e r l l e r ) ，p l a n t f o r m 公司的l s f ( 1 0 a ds h a r i n g f a c i l i t y ) 等。 华中科技大学硕士学位论文 2 提高并行 生能。此类负载平衡面向的主要是任务调度问题，目的只有一个，如何 缩短并行任务的运行时| 日j 。由于并行模式的多样性，这方面的研究工作也比较多。 集群系统中并行处理的核心机制在于如何进行任务或作业的分配和调度，而任务 或作业的分配则取决于各计算结点负载信息的获取和处理技术。如何获取、使用收集本 地结点的负载信息及任务或作业的调度算法是负载平衡系统的重要研究方向。 p v m 是集群系统上最流行的用于并行计算的并行程序开发平台之一。它面向的主要 是计算密集型的并行任务计算问题。它允许一组异构计算机组成一个灵活的紧凑的并行 计算资源。用户可以用p v m 构造一个全互联结点集的虚拟机。用户可以动态创建和管理 许多进程在此虚拟机上运行。p v m 流行的原因是：它受到很好的技术支持，拥有很大的 用户群：支持有各种体系结构、浮点形式和操作系统版本的异构系统集群；可免费获得 和容易安装：提供直截了当和易学的用户接口。 但是，p v m 并没有提供足够的负载平衡能力，而是把它留给编写p v m 应用程序的程 序员来处理。它缺少一个有效的全局任务调度系统，主要表现在以下两个方面： 1 缺少空闲机的选择机制：它不测量各个结点的负载信息，因此不能动态选择空闲 机。 2 任务调度机制过于简单：它启动用户进程时采用r o u n d r o b i n 方法，即不考虑处 理机负载情况，将待分配任务平均分配到各个结点上，每个结点分配的任务数基本相同， 最多相差个任务。这种分配方法仅按任务数均分，没有考虑任务和处理机的差异，因 此，在实际运行时，各结点负载情况可能差异很大。 一些研究者已经注意到p v m 的任务调度问题，并研究开发出具有调度功能的p v m 的 增强版本，如d y n a m i t ep v m “，妒。6 1 ，d p v m ”。等。d p v m 采用分布式调度方法，利用c p u 利用率为负载指标，采用任务排队机制，将队列中的任务分配到负载最轻的结点上，并 通过进程迁移机制实现主人优先和关机迁移等功能。d y n a m i t ep v m 采用集中式调度方法， 根据任务的不同的负载要求如c p u 处理能力、内存需求等，选择合适的结点进行分配， 并采用进程迁移机制实现容错及避免结点负载过重。但是，由于任务调度算法的多样性， 如集中式和分伟式调度，和操作系统的多样性，如d y n a m i t ep v m 只支持s o l a r i s ，肝、，m 支持h p u n i x ，s u no s ，i b ma i x 等，但它们都不支持l i n u x ，因此，这方面还有很多需 要研究。 为了充分发挥集群系统并行计算的能力，研究集群系统的负载平衡技术，提高p 程序的并行效率和加速比，我们在基于l i n u x 的集群系统上，利用p v m 系统的接口，初 步实现一个动态任务调度系统。与d y n a m i t ep v m ，忡v m ，d p v m 等系统相比，我们的系统 支持l i n u x ，采用了多项负载指标表示结点的负载情况，并采用了负载预测机制判断结 华中科技大学硕士学位论文 点负载情况，对结点的负载情况掌握得更细致。由于时间有限，我们的系统没有进程迁 移机制，无法实现任务的迁移及其它一些容错功能，因此，和上述系统相比，功能上有 所欠缺，是一个不完整的负载平衡系统。 1 2 国内外发展概况 对负载平衡系统的研究一直是集群系统研究的热点。目前，已经有很多为“高性能 计算”的集群负载平衡系统，由于对其研制的侧重点和应用范围不同，因此，它们各自 具有不同的性能和功能特点，目前应用得比较广泛的是作业级的动态负载平衡系统。一 些典型的系统介绍如下： 1 l s f p l a t f o r m 公司的l s f 系统( l o a ds h a r i n gf a c i l i t y ) 是一个用于异构群集计算机 的作业级负载平衡系统”。它侧重于对并行和顺序作业进行作业管理和负载共享，支持 检查点操作、可用性、负载迁移和单一系统映象。 在集群中每一个服务器结点上有两个l s f 守护进程运行。一个是负载信息管理器 ( 1 0 a di n f o r m a t i o nm a n a g e r ：l i m s ) ，它定期收集和交换负载信息；另一个是远程执行 服务器( r e m o t ee x e c u t i o ns e r v e r ：r e s ) ，它为作业提供透明的远程执行。 每个服务器结点上的l i m 负责收集这个结点的静态和动态资源信息。静态资源信息 包括结点类型、c p u 因子、结点的最大存储容量、本地磁盘的最大可交换空间等。动态 资源信息包括c p 利用率、可用交换空间、可用存储器、登录的用户数、过去1 5 秒内运 行队列长度等。对于动态资源信息，l i m 每隔l 、3 0 或1 2 0 秒更新次。 l i m 采用集中式的调度策略。在系统中存在一个主l i m ，剩下的作为从l i m 。从l i m 定期向主l i m 传递它们的负载向量。主l i m 将这些负载向量合并起来成为集群的负载矩 阵，它拥有所有服务器的负载信息并分派所有的集群作业。 l s f 支持多种调度策略，包括先来先服务、公平共享、抢占和独占。 2 m o s i x m o s i x = 9 = 为l i n u x 核心增添了集群计算的功能。在m o s i x 集群环境中，用户无需对应 用程序进行修改，或将应用程序与库连接起来，或将应用程序分配到不同的结点上运行。 m o s i x 会自动将这些工作透明地交给别的结点来执行。 m o s i x 的核心是适应性的资源管理算法，它对各结点的负载进行监测并做出相应的 回应，从而提高所有进程的整体性能。它使用抢先的进程迁移方法来在各结点中分配和 华中科技大学硕士学位论文 再分配进程，从而充分利用所有的资源。适应性的资源管理算法具体上又包括适应性的 负载平衡算法、内存引导算法和文件i o 的优化算法。这些算法都对集群中的资源使用 情况的变化做出响应，如结点上的不平衡的负载分布或由于内存不足而导致的过多的磁 盘换入换出。在这种情况下，m o s i x 将进程从一个结点迁移到另外个结点上，从而均 衡负载或将进程迁移到有足够的内存空间的结点上。 由于m o s i x 是在l l x 的核心中实现的，因此它的操作对应用程序而言是完全透明 的。可以用它来定义不同的集群类型，这些集群中的机器可以相同也可以不同。 与l s f 集群系统不同的是，m o s i x 集群中的每个结点既是主结点又是服务结点，不 存在主控结点。对于那些在本地结点创建的进程而言，该结点就是一个主结点：对于那 些从远方结点迁移过来的进程而言，该结点就是服务结点。这意味着可以在任意时刻向 集群中增加结点或从集群中删除结点，都不会对正在运行的进程产生不良的影响。m o s i x 的另外一个特性就是它的监测算法能够监测每个结点的速度、负载、可用内存、i p c 以 及i or a t e 。系统使用这些信息来决定将进程发送到哪个具体的结点上。当在某个结 点上皂1 3 建了一个进程以后，该进程就在这个结点上执行。当该结点的负赣超过了一定的 闽值以后，就将该进程透明地迁移到别的结点上继续执行。 其它一些典型系统包括c o n d o r “、l o a dl e v e l e r 等。c o n d o r 系统是w is c o n s i n m a d i s o n 大学研究的作业调度系统。它的设计目的是调度长运行时间的计算作业，充分 利用空闲工作站或p c 进行计算，并保证当用户开始使用机器时及时撤走它调度的后台任 务。它可以运行在大多数u n i x 平台工作站或p c 集群计算机上。l o a dl e v e l e r 是i 蹦公 司在c o n d o r 的基础上进行改进后的系统。除了拥有c o n d o r 的负载平衡、断点迁移等功 能外，还增加了系统动态配置、个人用户权限保护等功能。 从以上一些系统的介绍中，我们可以看出目前集群系统负载平衡技术发展的些特 点： ( 1 ) 大多数系统采用动态负载平衡技术，在系统运行过程中，不断根据运行时各结 点的负载情况，把作业或任务动态分配到各个结点上； ( 2 ) 系统采用多项负载指标来表示结点的负载情况，并用阈值将结点区分为轻载结 点和重载结点： ( 3 ) 系统多采用进程迁移技术，避免系统中出现过多的重载结点： ( 4 ) 采用多种技术维护系统的健壮性，以避免因一个结点发生故障而导致整个系统 崩溃。 华中科技大学硕士学位论文 1 3 课题的目的，意义及实验条件 负载平衡技术是并行计算领域的研究重点。目前，这方面的研究还呈现百花齐放的 态势，针对不同的硬件环境和应用的需求，存在不同的负载平衡技术和系统。这些系统 设计、实现的方式互不相同且各有特点，很难将它们进行比较。负载平衡的理论技术还 在不断的发展中，如何将这些理论技术与实际系统联合起来，一直是人们研究的重点。 目前这方面的工作还处在研究的前端，在技术上会有很多的困难，但也存在很多可以填 补的空白因此希望我们的系统能够为这方面的研究作一些探索性的工作。 随着集群系统的推广和普及，基于集群的负载平衡技术的研究和负载平衡系统的研 制，越来越成为人们关注的重点。负载平衡技术在集群系统中的应用，可以极大的提高 集群系统的并行处理能力，使人们不再依赖昂贵的专用的大型并行计算机系统，大大节 省人力、物力和财力。任务调度系统是实现负载平衡技术的重要组成部分，是负载平衡 的关键所在。p v m 是集群系统中重要的并行编程环境，拥有广大的用户群和良好的技 术支持。研究集群系统上基于p v m 的任务调度系统，对于研究负载平衡技术以及提高 用户程序的并行效率都有着积极的现实意义。 我们的系统主要针对的是在异构环境下( 这里的异构，指的是集群中的各个结点的 硬件环境包括c p u 处理能力、内存总量等是不同的，但各个结点在操作系统级是同构 的) 对一组并行任务的调度问题。在异构环境下，p v m 的调度策略不太适合，为我们 的系统的实现提供了有利的契机。系统最终的目标是缩短用户并行程序的执行时间，提 高并行效率。 我f 研制这样的一个系统的目的主要有两点： ( 1 ) 研制和完善一个实用的集群任务调度系统，初步实现动态负载平衡，并力争 在理论方面有所突破，为以后开发类似的系统和更高层次的并行应用软件打下- 轻实的基 础。 ( 2 ) 保护用户已有的资源，使用户在不用对程序进行大的修改的时提下，就能提 高系统的并行性，缩短用户程序的执行时间。 本系统的研制的主要实验条件为： p c 机若干台； 操作系统是r e dh a tl i n u x7 2 ： 并行编程环境p 、俺1 3 4 3 。 华中科技大学硕士学位论文 l - 4 论文的内容及组织 本课题研究基于l i n u x 的p c 集群系统上一个实用的动态任务调度系统的实现。 我们将以p v m 为基础，利用p v m 的并行环境，实现这个任务调度系统。主要的研究 内容包括以下几个方面： 1 负载指标的选择与收集 负载指标被负载平衡系统用来表示系统结点的负载情况。现在大多数的负载平衡系 统采用的是单一的负载指标。尽管单一指标实现容易，但是，单一负载指标不能完全反 映系统的负载情况。我们采用了多项负载指标的方式来表示结点的负载信息。我们将研 究了l i n u x 系统内核，掌握这些负载指标的得到方式，并编程实现一个基于l i n u x 的负载信息收集子系统。 2 负载信息的预测 我们将利用人工神经网络，对结点未来的负载信息的情况进行判断和预测，并利用 预测的负载信息对任务进行调度，使得任务调度策略的效率更高。我们将选择合适的神 经网络，对此神经网络的原理、特性进行分析，并对预测的结果进行评估。 3 任务调度方法 获得系统各个结点的负载信息后，必须按照一定的算法，根据各个结点的负载情况， 选择合适的结点，把任务分配到该结点上。我们根据不同的用户任务要求以及不同的并 行计算的模式，设计了不同的任务调度方法。我们将研究p v m 的任务调度机制，并采 用了外挂式方式，通过提供用户函数接口库，实现了我们提出的调度方法。 本文的研究内容包括7 个部分： 第一章为绪论，介绍了课题的背景、国内外发展概况以及主要的研究内容等： 第二章介绍了任务调度和负载平衡的一些基本概念、分类，消息传递模型及其代表 m p i ，p v m 的介绍： 第三章介绍了我们的系统l d p v m 的组成结构： 第四章介绍了负载信息收集与负载信息预测系统： 第五章介绍了l d p v m 的任务调度方法： 第六章对l d p v m 的系统性能进行了测试和分析； 第七章是本论文的总结和对今后工作的展望。 6 华中科技大学硕士学位论文 2 研究背景及相关概念 2 1 任务调度分类及典型算法 作为集群系统的重要组成部分，集群的任务调度一直是人们研究的重点。在集群系 统中，一个大的任务往往由多个子任务组成。这些子任务被分配到各个处理结点上并行 执行。在由异构处理结点构成的集群系统中，由于各个结点的处理能力不同，相同的任 务在其上的运行时间和资源占有率都有所不同。当整个系统任务较多时，分配给各结点 的负载可能并不均衡，整个系统利用率就会刚氐。因此，如何有效的将各个子任务均衡 的分布到不同的处理结点并行计算，使各个结点的综合利用率达到最大，是研究调度策 略和负载平衡的目的。 2 1 1 任务调度分类 从不同的角度出发，任务调度问题有不同的分类方法，下面所述的各种分类方法比 较全面地反映了设计一个任务调度算法时要考虑的各种因素。 1 按照何时执行结点分配操作划分 按照何时决定每个任务的执行结点，任务调度方法可以分为静态调度和动态调度。 静态调度是指在并行程序编译时，针对用户程序中的各种信息，如各个任务的计算量的 大小，依赖关系和通讯关系等，以及系统本身的状况，如网络结构、各处理器结点处理 能力等，对用户程序中的并行任务作出静态分配决策，在运行该程序的过程中将任务分 配到相应的结点。静态方法要求知道完整的任务依赖关系和准确的任务执行时间，在实 际应用中，多用于理论研究和辅助工具。动态调度是指在应用程序在运行过程的各个阶 段中，不断地根据运行时各个结点的负载情况，将并行任务动态地分配到各个结点，负 载轻的结点分配较多的任务。动态调度可操作性强，可以实时调度，但是它不可避免地 会带来额外开销【幔”l 。 。 2 按照调度目标的实现要求划分 按照调度目标的实现要求划分，任务调度可分为最优调度和近似最优调度，后者也 华中科技大学硕士学位论文 经常称为启发式任务调度。最优调度一般是指静态调度，如果一个调度算法能在多项式 复杂度的时间内获得最佳的调度结果，那么称为有效的最优调度算法，但是，只有在极 少数隋况下才存在有效的最优调度算法4 1 ，大部分最优调度算法所需的执行时i 刈随着任 务数或结点数目的增加而呈指数增长。因此，实际应用中，常采用启发式任务调度方法 u 5 , 1 6 1 把各个任务分配到各结点上，它虽然不能确保获得最优解，但可以获得最优调度的 近似解。 3 按照并行分布计算模型划分 按照并行分布计算模型的存储器结构，主要可以分为基于共享存储的任务调度和基 于分布存储的任务调度。在共享存储的计算模型上进行任务调度时，一般不需要考虑通 讯延迟，这时任务调度的注重点在于如何最大限度地获得并行程序任务间的并行性。而 在分布存储的计算模型上进行任务调度时，通讯延迟的存在使得任务调度更为复杂，如 果无视通讯延迟的存在，而只考虑尽量增大并行执行时间，那么，就有可能在较多的结 点上的执行效率还不如在较少的结点上的执行效率：同样，如果没有完全开发任务之间 的并行性，那么各个结点就没有得到充分的利用，因此，调度程序必须在尽可能利用各 任务之间的并行性和尽量减少通讯开销之间进行折中【l 7 i 。 4 按照调度程序结构或调度信息范围划分 按照调度程序的结构或调度程序所收集的调度信息的范围，任务调度可分为集中式 调度和分布式调度。在集中式调度方法中，由一个叫做中心调度服务器的结点来收集全 局调度信息，其它结点把它们的负载状况信息传送给中心调度服务器，并由中心调度器 作出调度决定。集中式调度程序的一般结构见图2 1 。而分布式调度则由各个结点自身 的调度程序根据局部范围的一些结点的负载信息来进行调度，它的最大优点在于具有良 好的可扩展性【l “。分布式调度程序的一般结构见图2 2 。集中式调度的主要优点是实 现比较简单，但在结点数目较多的大规模并行分布系统中，由于各结点与调度服务器的 通讯成为瓶颈，所以调度开销比较大阱”i 。 5 按照调度程序所执行的调度操作划分 按照调度程序执行调度操作时是否允许任务抢占执行，任务调度可分为抢占式调度 和非抢占式调度。由于抢占执行方式所引起的环境切换会增加系统开销，所以在一般情 况下不常采用，用的较多的地方是在以分时方式实现的群调度【“1 ( g a n gs c h e d u l i n g ，有 时也称为联合调度，即c o - s c h e d u l i n g ) 方案中。与抢占执行调度操作类似的还有任务是 华中科技大学硕士学位论文 小蚪塑 图2 1 集中式调度程序的一般结构 图2 2 分布式调度程序的一般结构 否允许迁移( m i g r a t i o n ) 执行。一般地，编译时对任务进行的结点分配有时称为初始分 配，如果应用程序任务启动执行后，某些任务可以被重新移到其它结点上执行，这也是 可抢占执行方式的种形式。 6 按照调度策略是否动态变化划分 按照调度程序的调度策略是否随着系统状态信息变化而自动调整，任务调度可分为 自适应调度脚矧和非自适应调度。自适应调度的基本思想是根据调度程序在以前一段 时间内的执行效果，以及当前系统状态信息( 主要包括系统资源和任务负载情况) 自动 修正，调整程序的执行机制。由于它们是通过收集当前系统状态信息来动态修正调度策 略的，所以般都属于动态调度方法。而非自适应调度方法一旦确定调度算法的调度策 略，那么在并行程序执行过程中，固定地按照这些调度策略进行任务调度。 华中科技大学硕士学位论文 2 1 2 动态调度算法的组成 静态调度算法要求事先知道完整的任务依赖关系和准确的任务执行时间。这些要求 在实际应用中很难得到满足。因此，在集群系统的任务调度问题中，大多数的系统采用 的是动态调度算法。本论文主要考虑的也是动态调度算法。 动态算法的组成包括四个部分： 1 转移策略 动态算法的转移策略主要处理这样的问题：决定在什么条件下一个进程可以从一个 机器上迁移到另一个机器上。决定何时可移动进程的一个非常简单且有效的方法是使用 静态门限1 ( t h r e s h o l d ) ，当超过它时说明机器的负载太重，需要向网络其它结点转移 一部分工作。有些研究者瑚1 使用两个门限值将机器负载大小分类为轻的、中等的和重的， 并认为仅当超过重载门限时才迁移进程。这样的系统使用的转移策略时重载结点触发进 程迁移。但是某些研究者 2 9 1 持相反的看法，认为轻负载机应主动接受其他重载结点的进 程，极端的情况时仅向空闲机迁移进程。 某些转移策略采用相对策略，它们使用两机的负载差值，若两机的负载差值超过某 值则进行迁移。另一种使用负载差方法是，根据对远程机负载的当前估计值决定其是否 迁移，周期地检查本地进程在远程其它结点上的可能响应时间，若有较大的改进( 考虑 了迁移开销) ，则迁移此进程。 2 选择策略 一旦转移策略确定了发送者，选择策略将选择哪个任务被转移。一个简单的选择策 略是选择新产生的任务作为被转移的对象。这种做法是盲目的，例如短任务转移后任务 响应时间的改进抵消不了转移的开销。要对任务响应时问的改进和转移歼销迸行估计， 必须获得任务的性质和不同系统环境对不同任务响应时间的影响。 从任务占用资源的情况来看，任务可分为三类：c p u 类( 大量使用c p u 而很少访 问磁盘) 、1 0 类( 大量访问磁盘而很少使用c p u ) 以及普通类( 使用c p u 和磁盘均很 少) 。大量使用c p u 同时具有大量i o 操作的任务极少。 负载平衡只需迁移极少数长时间运行并且大量使用c p u 资源的任务。迁移短任务 必将导致其响应时间的增加，这将浪费大量的调度开销。 3 定位策略 定位策略负责选择一组结点，轮流访问它们以从中选择一个来执行拟调度的任务。 0 华中科技大学硕士学位论文 一般来说，选择的范围越大，带来自额外歼销也越大。根据定位策略的不同，算法可以 分为集中式调度和分布式调度。 4 信息交换策略 信息交换策略用于确定何时、到何处收集有关系统中其它结点的哪些状态信息。它 可以分为以下三种： ( 1 ) 需求驱动策略：当一个结点变为发送者或接收者时，才收集其它结点的状态 信息，如文献【2 8 的策略就是仅当某个处理机根据本地负载状态，认为本结点处在重载 状态时才请求网络中其它结点的负载信息。 ( 2 ) 周期策略：各结点周期性的收集系统的状态信息。这个周期值必须仔细选择， 周期太短会产生不稳定性，并且频繁的负载交换将产生附加的开销；周期太长则不精确。 ( 3 ) 状态变化驱动策略：只有当某结点的状态发生某种程度的改变时才发稚其状 态信息恤j ，它与需求驱动策略的不同是发布本结点的信息，而不是收集其它结点的 状态信息。 2 1 3 几种典型的动态调度算法 1 中心任务调度策略 中心任务调度策略是集中式的调度方法。它让一个特定的结点充当计算任务分配器 的角色，我们称之为调度服务器，完成计算任务的结点为计算结点。调度服务器为了。掌 握负载分布的情况，需要维护一个全局的结点负载情况表。 计算结点按照一定的周期向调度服务器报告结点的负载情况。在任务启动时，调度 服务器根据结点负载情况表，选择合适的结点，分配计算任务。计算结点执行分配给它 的计算任务。在执行过程中，调度服务器根据收集到的结点信息判断结点的状况，发出 任务迁移指令，控制任务从重负载结点向轻负载结点流动。 中心任务调度的优点显而易见：调度服务器掌握了所有结点的当前的负载情况，因 此它可以在综合各种因素的基础上找到最佳的任务分配及迁移方式。但是当计算结点数 目很多时，计算结点与中心结点的通讯开销增大，降低了负载平衡的效率。 2 发送者启动策略 发送者启动策略、接收者启动策略和自适应策略都没有中心结点，每个结点只和 华中科技大学硕士学位论文 部分结点进行通讯，交换负载信息。它们都是分布式的调度方法m 1 。 发送者启动策略引入一个阂值m 来把所有的结点划分为轻负载结点和重负载结 点。所有当前负载t m 的结点都被称为重负载结点，t & ， 则h k = l 。g - - l k ，否则饥= o ，那么卅k 为： ( ，p l “w ) h 。 mk 2 f 一 h ， 随后该结点就可以按照帆向各个相关结点发送任务了。 发送者启动策略由发送者来激发负载的分配。显然，当整个系统处于轻载时，发送 者能够比较容易地找到接收者，此时该算法比较稳定而有效；但在整个系统处于重载时， 该算法会引起系统的不稳定，因为此时发送者不仅不容易找到接收者，而且查询开销还 会增大系统的负载。 3 接收者启动策略 接收者启动策略与发送者启动策略除了是由轻负载结点启动，要求其它结点把任务 发送给它之外，其它基本相同。接收者启动策略同样引入m 以区分轻、重负载结点， 引入相关域以确定交互范围。在启动时，所有结点开始执行计算任务，经过一段时间后， 一旦某个结点发现自身成为轻负载结点，就试图在其相关域内均匀地分布负载。具体地， 设该轻负载结点的负载为，p ，相关域中有k 个结点，其负载分别为0 ，f k ，则；f 均 负载k 为： 1k 三一2 南( 善d 华中科技大学硕士学位论文 为了达到均匀分布，应求得相关域中每个结点应该传递给轻负载结点的负载最讯。 我们首先引入权抚以避免负载从相关域中负载更轻的结点被迁移到该结点。如果l 。 ，k ，则气= 七一l 。，否则魄= o ，男1 3 _ , m k 为： ( la w 一，) ht mk 2 育 h t t = i 随后该结点就可以按照仇发出接收任务的请求了。 该策略在整个系统重载的情况下因多数结点处于重载，负载分配活动将趋于微弱， 不会引起系统的不稳定，优于发送者启动策略。但由于接收者找到发送者时，任务可能 已经启动，因此需要支持抢先式任务转移，付出的代价较昂贵。在轻负载情况下，接收 者启动策略就没有发送者启动算法有效。 4 自适应策略 负载的分配引起系统不稳定的主要原因是由于发送者对所有结点不加区分地探询造 成的，以上算法的缺点在于它们不能适应系统状态的变化，而自适应策略根据系统状态 的变换改变某些参数来适应负载的变化。稳定的发送者自适应策略使用探询期间收集的 信息( 而不是象前面的算法那样把它们丢弃掉) ，把系统结点分为“发送者超载”、“接 收者，欠载”和负载适度结点。通过一个由发送者表、接收者表、负载适度结点表组成 的数据结构，在每个结点上维持关于结点状态的知识，起初每个结点假定其它所有结点 都是接收者。在每个结点上使用个状态向量来记录它在系统中所有其它结点上所属的 表，即发送者表、接收者表或负载适度结点表。 算法的位置策略包括发送者启动部分和接收者启动部分。发送者启动部分是当一个 结点成为发送者时在该结点上触发的，发送者探询接收者表头的那个结点，以确定它是 否还是一个接收者，发送者的状态向量被修改，以指出在这个被选择的结点上发送者目 前属于发送者表。被探询的结点把该发送者的结点标识号从它目前所在的表移到自己的 发送者表的表头，并通知发送者自己目前是一个接收者、发送者或是负载适度结点。更 新它的状态向量以反映在发送者结点上将属于哪个表。在接到该回答后，如果这个被探 询的结点还是一个接收者，就把新产生的任务转移过去，否则就把这个被探询的结点号 从接收者表中除去，并根据回答信息把它放到负载适度结点表或发送者表的表头。 接收者启动部分由下面的协议完成：当一个结点变成接收者时，它仅仅通知那些被 误传了它的当前状态的结点，这些被误传了信息的结点就是那些其接收者表中没有包含 华中科技大学硕士学位论文 该接收者标志号的结点。这些信息在该接收者的状态向量中可以获得。然后，更新该接 收者的状态向量以反映在所有那些被误传了消息的结点上它目前属于接收者表。该算法 具有较好的性能和稳定性。 2 2 并行程序设计模型 程序设计模型是一种程序抽象的集合，给程序员提供了一幅计算机硬件软件系统 的透明简图。并行程序设计模型是专门为各类并行机系统设计的以不同执行范式丌发并 行性的模型。 程序并行性的开发取决于进程间的通信i p c 的实现方法。并行程序设计的基本问 题主要集中在相同或不同的处理机上的并行进程的规范说明、创建、挂起、再生、迁移、 终止以及同步等方面的问题。下面介绍以不同执行范式来开发程序并行性的五种并行程 序设计模型： 1 共享变量模型 该并行程序设计的基础是利用公用存储器中的共享变量来实现进程间的通信口c 。 使用这种模型所遇到的主要问题包括临界区的保护性访问、存储器的一致性、存储操作 的可分性、快速同步、共享的数据结构以及快速数据移动技术。 2 消息传递模型 所谓基于消息传递的并行程序设计，是通过显式地发送和接收消息来实现处理机问 的数据交换。消息传递所产生的通信延迟比访问公用存储器中共享变量的延迟要长。消 息传递模型的关键问题是如何把程序代码和数据集分布或复制到所有处理结点t 。同时 还要考虑计算时间和通信开销之间的权衡问题。 3 数据并行模型 数据并行的主要思想是在多个计算结点上对不同的数据集，同时执行相同的指令或 程序段。数据并行程序要求预先分布好的数据集。因此，并行数据结构的选择会使数据 并行程序设计差别很大。数据并行程序设计强调的是局部计算和数据寻径操作。 4 面向对象模型 在这种模型中，对象是动态建立和控制的，处理是通过在对象间发送和接受消息来 完成的。该模型将低级对象( 如进程、队列和信号灯) 组合起来形成高级对象。 5 函数和逻辑模型 函数程序设计语言强调程序的函数性，程序执行后不应有副作用。函数的计算结果 与它的参数的计算结果无关意味着在一个函数程序动态创建的结构中所有的参数都可以 华中科技大学硕士学位论文 并行计算；逻辑程序设计模型采用隐式搜索策略并支持逻辑推理过程中的并行性。函数 和逻辑程序设计模型应用于大量并行处理的人工智能应用领域。 上述五种并行程序设计模型中，由于消息传递的程序设计要求用户很好地分解问 题，组织不同进程的数据交换，并行计算粒度大，处理$ r k 2 _ 间为松散耦合，特别适合大 规模可扩展并行计算。消息传递模型是当前并行计算领域中一个非常重要的并行程序设 计模型，被当前所有的分布式存储或分布共享存储m p p 、共享存储s m p 和工作站网络 n o w s 所支持。p v m 和m p i 是消息传递模型的典型代表。 2 3 消息传递模型特点及典型代表 消息传递具有如下特征： 1 多进程化：消息传递程序由多个进程组成，其中每个进程具有自己的控制线程 且可执行不同代码。 2 异步并行性：消息传递程序的进程异步执行。使用一些专用的操作对进程进行 同步。 3 分离的地址空间：并行程序的进程驻留在不同的地址空间。进程间的交互需要 执行专用的消息传递操作完成。 4 显示交互：程序员必须解决所有的交互问题，包括数据映射、通信、同步和聚 集。 5 显示分配：工作负载和数据需要用户用显式方法分配给进程。 当前，最为流行的消息传递并行编程环境为p v m 和m p i 。这两种标准库已经在所 有类型的并行计算机匕实现，极大地增强了消息传递程序的可移植性。 2 3 1p v m 概述 1 p v m 简介 f v m ( f a r a u e lv i r t u a lm a c h i n e ) ：f f - 行虚拟机，是一种基于局域网络的异构编程环境， 是能使群松散连接的计算机用来作为一台计算机资源的软件系统。p v m 系统在基于 相关集群中各结点机的操作系统上，为用户提供并行运行的环境。p v m 系统基于的机 种允许异质，所处的网络可以是异构。p v m 具有通用性强及袭用规模小的特点，即适 合t c p i p 网络环境，又适用于m p p 大型并行系统。 p v m 支持异构的分布计算环境，其结点机可以是并行机、向量机、工作站和m p p 华中科技大学硕士学位论文 等，互连网络可以是e t h e m e t 、f d d i 、a t m 等，操作系统可以是o s f 1 、a 、s u no s 、 l q t r i x 、h p u x 、l 【n i x 等in 系列。p v m 软件系统分为p v m 服务器及p v m 库两 部分组成。p v m 属于自由软件，源代码公丌，因而得到各个大学、研究机构