论文部分内容阅读
基于网络的计算是当前国内外研究的热点,特别是随着网格计算的提出,
许多学者对此进行了大量的研究工作,使得网格计算由最初的以协议为中心的
体系架构转变为基于服务的体系架构。尤其是目前提出的服务和资源分离的面
向服务的体系架构,认为服务是无状态的,而资源是有状态的。这样,执行一
个服务的资源可以分布在不同的地域,亦即它们可以动态地加入和撤离网格计
算环境,而呈现出分布、异构、动态的特征。因此,在网格计算环境下,保证
QoS的任务调度就变得十分复杂。
在网格环境中,有效的任务调度是取得高性能的关键。由于网格用户是独
立地向网格计算环境提交任务,因此,网格计算环境下任务的执行呈现分布、
并发的特点。如何有效安排完成任务的资源,以及如何在资源上安排任务的执
行顺序是保证QoS所必需解决的问题。由于Petri网具有描述事件的并发、异
步、动态等特性的能力,因此,在任务调度问题上得到越来越多的应用。本文
利用Petri网(特别是高级Petri网)这一形式化工具模拟与分析网格计算环境
下任务的调度问题,建立了适合于网格任务调度的描述与分析模型。这对于进
一步丰富Petri网的概念与模拟能力,推进网格计算,尤其是任务调度的研究
具有重要的理论价值与实际意义。
本文综述了网格计算的发展与研究现状,特别是详细论述了现有任务调度
的各种模型和算法。在此基础上,给出了适合于网格计算,特别是以服务为中
心的任务调度算法。从理论上对Petri网本身进行了研究,结合T-时间Petri网
建立了适合描述网格计算环境下任务调度的一些模型和算法。同时,提出并研
究了用于网格计算的服务管理模型和算法,以及网格计算环境下独立任务调度
的算法,并将本文得到的结果应用于实际项目中,取得了较好的应用。
本文工作的主要贡献表现在如下几个方面:
(1)针对网格环境下实际资源是有限的特点,提出了有界Petri网同步距
离的计算方法,为模拟任务调度的Petri网建模和分析提供了评价手段。
(2)Petri网是一个并发模型,但是,现有的可达图隐含了这种并发关系,
而且它的状态空间是爆炸性增长,这样不利于分析模型的性能。为此提出了Petri
网并发可达图及其构造算法,使得Petri网的分析能力进一步增强。
(3)基于Petri网虹吸的网格任务(资源)调度模型与算法是实现有效调
度的一种重要手段,然而,对于极小虹吸的计算还没有一个有效的算法。本文
通过研究Petri网的结构特征,提出了计算Petri网所有极小虹吸的有效计算方
法。
(4)针对大规模任务的稳态调度问题,本文通过研究T-时间Petri网,提
出了主从任务调度的T-时间Petri网模型与算法。从我们提出的并发可达图中得
到了稳态调度的一个优化策略。
(5)结合DS证据理论,提出了网格计算环境下服务管理的模型。该模型
的最大特点在于,通过全局服务管理器实现任务在服务上的有效分配。用户需
要的服务不是在全局服务目录中查找,而是在自己的服务目录中查找,从而提
高了服务的发现效率,有效地解决了服务发现问题。全局服务管理器管理一个
虚拟的全局服务目录,动态更新用户服务目录而不是针对用户的每一次服务请
求,因而有效地解决服务中心的瓶颈问题。同时,全局服务管理器监视服务的
执行情况以及资源的QoS保证情况,为保证任务的完成选择有QoS保障的资
源提供了充分的证据。
(6)针对网格结点的特点(它可以是一个处理机、一个机群或一个局域网),
研究了独立任务在同构和异构环境下的调度问题。首先,给出了同构环境下独
立任务的调度算法。对于异构环境下任务的调度问题,众所周知,Min-min
(Max-min)启发式算法被认为是独立任务调度性能评价的标准。然而,由于
Min-min算法首先映射短任务而会出现负载不平衡,这主要是因为它没有全面
地考虑处理机的性能和全局动态负载均衡。本文首先给出了评价处理机性能的
一种简易实用的评价方法,并以此给出了考虑全局负载均衡的任务调度顺序,
然后给出了调度在相应处理机上的两个算法。举例与模拟试验表明,所给的调
度算法在调度时间与调度性能方面均优于Min-min(Max-min)算法。
关键词:网格计算,任务调度,调度模型与算法,全局服务管理器,Petri网,并发可达图,极小虹吸子网,T-时间Petri网