一种适用于网格环境的基于可靠性代价的作业调度系统

摘要

本发明为一种适用于网格环境的基于可靠性代价的作业调度系统。如图1所示，整个系统分为三层：第一层为作业提交接口模块1，第二层为作业调度模块2，以及底层为网格资源平台7。从工作原理上说，本发明的核心为第二层的作业调度模块，它包括预调度模块3、调度决策模块4、作业完成时间预测模块5和资源信息模块6。本发明系统提出作业运行时间预测模型和资源可用性预测模型。作业运行时间预测模型基于数学模型，资源可用性预测模型基于马尔科夫模型，具有很高的准确性和通用性。本发明系统根据作业服务质量需求和资源特点的不同分别采用复制容错策略、主副本异步运行复制容错策略和重试容错策略，具有很高的灵活性和有效性。同时，本发明系统支持计算密集型作业和数据密集型作业，具有很好的通用性。本发明与现有的调度系统相比，具有支持更多的并发用户、提高资源的利用率、通用性好、可扩展性好、系统吞吐率高等优点。

说明书

技术领域

本发明属于网格计算领域，具体涉及一种适用于网格环境的基于可靠性代价的作业调度系统。

背景技术

网格整合了分布在Internet上动态的、自治的、异构的网络资源(包括高速互联网、计算机、大型数据库、传感器、远程设备等)，它屏蔽了资源的动态性、异构性和分布性，为用户提供一种高效的资源共享和协同工作环境。网格技术一经提出，便吸引了学术界和工业界的极大重视，并取得了飞速的发展。网格区别于传统分布式高性能计算的优势如下：(1)有效利用广域分布的资源；(2)实现异构组织间的高效协作；(3)有效解决计算密集性和数据密集性任务；(4)基于OGSA的思想使得工作流更趋于“服务流”。网格为复杂的、庞大的科研任务提供了有效的问题解决途径，例如：飞行器设计、基因排序、大气环境分析等。

网格资源多属于不同的组织机构，大部分资源是非专有资源，可以动态加入和离开。另外，资源共享模式的改变、软硬件故障以及网络瘫痪都可以导致网格资源的不可用。因此资源的动态性导致网格作业失败频繁发生，用户服务质量无法保证。因此，网格环境下的作业调度面临许多新的挑战。因此，为了更好地发挥网格的丰富资源和可扩展性等优点，建立可靠地作业调度成为网格系统性能好坏的关键所在。

网格资源以服务形式呈现给用户，用户通过向网格系统提交作业来享用各种网格资源。网格作业调度系统在接收到用户的作业后，根据用户的QoS要求与信息中心进行交互，匹配出合格的网格服务资源集。然后，作业调度系统根据特定的调度策略，为用户作业选择最佳的资源。现有的作业调度策略多基于性能驱动模型、经济驱动模型和信任驱动模型[参见K.Krauter，R.Buyya，and M.Maheswaran，A Taxonomy and Survey of Grid Resource Management Systemsfor Distributed Computing，Software Practice and Experience，32(2)：135-164，February 2002.]。性能驱动模型侧重于提高系统吞吐率、作业执行效率等性能相关指标；经济驱动模型侧重于在满足用户QoS需求的前提下，选择收费最低的资源服务；信任驱动模型则是根据资源的历史服务情况(譬如：资源故障率、运行作业成功率等)为每个资源建立信任模型，基于该模型，进行可信任的作业调度。当作业执行过程中因资源故障或其他原因中断时，系统采取一定的容错策略。目前常用的容错策略有：检查点、多点复制和重试等。检查点策略定期地保存作业的运行结果及状态，当资源发生故障时，系统将作业回滚到故障前系统记录的检查点，经过状态恢复后从该检查点处重新执行，而不是从头开始执行，从而节省了资源并降低了作业的丢失率；多点复制策略把作业同时调度到两个以上不同的资源节点执行，只要有一个资源节点正常运行，就可以保证作业成功执行；重试策略即在作业发生故障时，将作业再调度，作业可以调度到本资源节点或者其他资源节点。

传统的作业调度系统没有充分考虑网格环境下资源的动态性，造成作业故障频繁发生。另外，传统的调度系统多采用单一的容错机制，缺乏灵活性，并且浪费系统资源。

发明内容

本发明的目的是针对现有作业调度系统的不足，提供了一种适用于网格环境的基于可靠性代价的作业调度系统，该系统充分考虑了作业的QoS请求和资源可靠性，自动地为作业采用合适的容错策略，并具有效率高和通用性好的特点。

为实现上述发明目的，适用于网格环境的基于可靠性代价的作业调度系统，其特征在于：它包括作业提交接口模块和作业调度模块；

作业提交接口模块用于用户提交作业，并传送给作业调度模块；

作业调度模块用于接收作业提交接口模块提交的作业，进行调度和容错策略定制后，将作业分配到网格资源平台中相应的资源节点；它包括预调度模块、调度决策模块、作业完成时间预测模块和资源信息模块；

预调度模块通过对作业的服务质量需求进行分析，对用户作业进行分类排队；预调度模块接收作业提交模块传送来的作业，并与作业完成时间预测模块进行交互，根据作业完成时间预测模块的预测信息对作业进行分类排队；预调度模块同时作为调度决策模块的作业池，为调度决策模块提供作业；

作业完成时间预测模块用于对每个作业在各资源节点上的完成时间进行预测；作业完成时间预测模块接受预调度模块和调度决策模块的作业完成时间预测请求，在进行预测后，将预测结果分别返回至预调度模块和调度决策模块；作业完成时间预测模块与资源信息模块进行交互，作业完成时间预测模块通过资源信息模块查询各资源的性能信息；

资源信息模块负责收集网格资源节点的实时状态信息，资源信息模块接受调度决策模块和作业完成时间预测模块的资源查询请求，并将相应的查询结果返回调度决策模块和作业完成时间预测模块；资源信息模块采用定期查询和订阅/发布机制与底层网格资源中的各资源进行交互，及时更新各资源的性能信息；

调度决策模块根据资源节点未来的可用性，对用户作业进行基于可靠性代价的调度，同时也根据作业的服务质量需求和被调度资源节点的未来可用性，为每一调度作业制定容错策略；调度决策模块从预调度模块中取回待调度作业，请求作业完成时间预测模块对作业在各资源上的运行时间进行预测；然后，根据作业运行需求和作业在各资源上的运行时间，与资源信息模块进行交互，完成作业与最佳资源的匹配；最后，调度决策模块将作业调度到网格资源平台上对应的资源节点。

本系统提出作业运行时间预测模型和资源可用性预测模型，作业运行时间预测模型基于数学模型，资源可用性预测模型基于马尔科夫模型，具有较高的准确性和通用性。本系统根据作业和资源特点的不同分别采用主副本同时运行策略、主副本异步运行策略和重试策略，具有很高的灵活性和有效性。同时，本系统支持计算密集型作业和数据密集型作业，具有很好的通用性。本发明与现有的调度系统相比，具有支持更多的并发用户、提高资源的利用率、通用性好、可扩展性好、系统吞吐率高等优点。具体而言，本发明具有以下特点。

(1)预测模型的高准确性

作业运行时间预测模型基于数学模型，资源可用性预测模型基于马尔科夫模型，具有较高的准确性和通用性。

(2)提高作业运行的可靠性

本系统提出作业成功运行可靠性代价模型，该模型充分考虑了作业的QoS要求和资源未来可用性。基于此模型，进行作业可靠调度。

(3)提高系统吞吐率

本系统根据作业QoS要求，选择合适的资源，譬如为低QoS作业选择低可靠资源，从而为高QoS作业节省高可靠资源。不仅满足了作业需求，同时也节省了资源，达到了系统负载平衡，进而提高系统吞吐率。

(4)支持多种类型网格作业

本系统采用通用调度系统，不仅支持计算密集型作业，而且也支持数据密集型作业，具有较高的通用性。

附图说明

图1为适用于网格环境的基于可靠性代价的作业调度系统结构示意图；

图2为预调度模块的结构示意图；

图3为调度决策模块的结构示意图；

图4为资源信息模块的结构示意图；

图5为作业预调度流程示意图；

图6为作业调度决策流程示意图。

具体实施方式

下面结合附图对本发明作进一步详细的说明。

如图1所示，本发明提供的适用于网格环境的基于可靠性代价的作业调度系统(以下简称DGSS(Dependable Grid Scheduling System))分为二层：第一层为作业提交接口模块1，第二层为作业调度模块2。系统底层为网格资源平台7。从工作原理上说，本发明的核心为第二层的作业调度模块，它包括预调度模块3、调度决策模块4、作业完成时间预测模块5和资源信息模块6。

作业提交接口模块1用于用户提交作业，并传送给作业调度模块2中的预调度模块3。作业提交接口模块1支持多种作业提交方式，包括基于Web、命令行和JSDL的作业提交方式。

作业调度模块2接收用户提交的作业，负责对作业进行可靠性调度和有效的容错策略定制。作业调度模块2接收作业提交接口模块1提交的作业，进行过调度和容错策略定制后，将作业分配到网格资源平台7中相应的资源节点。

预调度模块3通过对作业的QoS需求进行分析，对用户作业进行分类排队；预调度模块3接收作业提交模块1传送来的作业，并与作业完成时间预测模块5进行交互，根据作业完成时间预测模块5的预测信息对作业进行分类排队。预调度模块3同时作为调度决策模块4的作业池，为调度决策模块4提供作业。

作业完成时间预测模块5对每个作业在各资源节点上的完成时间进行预测。作业完成时间预测模块5对作业i在资源节点j上的完成时间预测理论模型如下：CT_ij＝β·(Q_j/PC_j+D_in/BW_kj+Q/PC_j+D_out/BW_kj)。其中CT_ij表示作业i在资源节点j上的预期完成时间，β为修正参数，β值根据历史预测作业完成时间的准确度来确定。Q_j为资源节点j上等待处理的作业量，Q为作业i的计算量，PC_j为资源节点j的计算能力，D_in为运行作业i时需要的数据量，D_out为作业i完成后需要输出的数据量，BW_kj为存储数据的资源节点k与资源节点j之间的数据带宽。作业完成时间预测模块5接受预调度模块3和调度决策模块4的作业完成时间预测请求，在进行预测后，将预测结果分别返回至预调度模块3和调度决策模块4。作业完成时间预测模块5与资源信息模块6进行交互，作业完成时间预测模块5通过资源信息模块6查询各资源的性能信息。

资源信息模块6负责收集网格资源节点的实时状态信息，包括资源的CPU、内存利用率、硬盘空间和资源未来可用性等。资源信息模块6接受调度决策模块4和作业完成时间预测模块5的资源查询请求，并将相应的查询结果返回调度决策模块4和作业完成时间预测模块5。资源信息模块6采用定期查询和订阅/发布机制与底层网格资源7中的各资源进行交互，及时更新各资源的性能信息。

调度决策模块4根据资源节点未来的可用性，对用户作业进行基于可靠性代价的调度，同时也根据作业的QoS需求和被调度资源节点的未来可用性，为每一调度作业制定灵活的容错策略。调度决策模块4从预调度模块3中取回待调度作业，请求作业完成时间预测模块5对作业在各资源上的运行时间进行预测；然后，根据作业运行需求和作业在各资源上的运行时间，与资源信息模块6进行交互，完成作业与最佳资源的匹配；最后，调度决策模块4将作业调度到网格资源平台7上对应的资源机节点。

底层为网格资源平台7，它集合了众多资源节点。资源节点部署网格服务，用户作业最终被调度到资源节点执行。

DGSS系统根据作业QoS要求，选择合适的资源，譬如为低QoS作业选择低可靠资源，从而为高QoS作业节省高可靠资源。不仅满足了作业需求，同时也节省了资源，达到了系统负载平衡，提高了系统吞吐率。

下面举例说明作业调度模块2中各模块的一种优化的具体实现方式，本领域一般技术人员根据本发明公开的内容可以采用其它多种方式予以具体实现，本发明的保护范围并不局限于下述实例的内容。

如图2所示，预调度模块3包含作业QoS解析模块31、作业排队模块32、无QoS队列33、低QoS队列34和高QoS队列35。

作业QoS解析模块31接收用户通过作业提交接口模块1提交的作业，对作业进行解析，提取作业的QoS需求，例如：CPU、内存利用率、硬盘空间、作业完成时间限制等。经过处理后将作业及解析的信息转交与作业排队模块32。

作业排队模块32接收作业QoS解析模块31转交的作业和解析信息，并与作业完成时间预测模块5进行交互，根据作业的QoS需求和资源节点的特征确定作业的QoS等级。无完成期限要求的作业可被视为无QoS作业，完成时间期限大于作业在资源节点中最小运行时间(1+λ)倍的作业视为低QoS作业(0＜λ≤0)，反之为高QoS作业。最后，作业排队模块32将作业分类并分别提交给高QoS队列35、低QoS队列34、无QoS队列33。

无QoS队列33用于对无QoS作业进行排队，它接收作业排队模块32转交的作业，调度决策模块4中的作业提取模块41定期来无QoS队列33提取作业。

低QoS队列34用于对低QoS作业进行排队，它接收作业排队模块32转交的作业，调度决策模块4中的作业提取模块41定期来底QoS队列34提取作业。

高QoS队列35用于对高QoS作业进行排队，它接收作业排队模块32转交的作业，调度决策模块4中的作业提取模块41定期来高QoS队列35提取作业。无QoS队列33、低QoS队列34和高QoS队列35排队策略为先来先服务，优先级为无QoS队列33中的作业最低，高QoS队列35中的作业优先级最高。

如图3所示，调度决策模块4包含作业提取模块41、容错策略模块42、调度策略模块43和资源作业匹配模块44。

作业提取模块41负责从预调度模块3的无QoS队列33、低QoS队列34和高QoS队列35中提取作业，按照高低无的优先级别提取作业。并将作业转交于资源作业匹配模块44。

容错策略模块42负责为作业调度提供灵活的容错策略，为无QoS作业提供重试容错策略，即在作业运行失败后，将作业再调度到其他资源节点上运行；为低QoS作业提供主副本容错策略，另外副本有主动运行模式和被动运行模型。当副本的最晚启动时间和主本的预期完成时间重叠时，副本采用主动运行模式，反之，采用被动运行模式；为高QoS作业提供复制容错策略，就是将作业同时调度到两个以上的资源节点运行，以保障作业在用户指定的完成期限内成功完成。容错策略模块42接受资源作业匹配模块44的容错决策请求，并将相应的容错策略返回至资源作业匹配模块44。

调度策略模块43负责为作业调度提供可靠的调度策略，本发明提供基于作业运行可靠性代价的调度策略，可靠性代价即作业在该资源上的预期运行时间和该资源在作业预期运行时间内正常运行的概率之积。调度策略模块43接受资源作业匹配模块44的调度决策请求，并将相应的调度策略返回至资源作业匹配模块44。

资源作业匹配模块44接收作业提取模块41转交的作业，与作业完成时间预测模块5进行交互，预测作业的完成时间；然后根据作业特点，与资源信息模块6和调度决策模块43交互，制定作业的调度策略，选择最优的资源；并与容错策略模块42交互，制定作业的容错策略；最后，资源作业匹配模块44将作业调度于网格资源平台7对应的资源节点。

作业完成时间预测模块5负责预测作业在各个网格资源节点上的预期完成时间。它接收调度决策模块4中资源作业匹配模块4的作业信息，并从资源信息模块6中获取网格资源节点的动态性能信息，然后对作业完成时间进行预测，并将预测结果返回给资源作业匹配模块44。

如图4所示，资源信息模块6包含资源信息探测模块61、资源可用性预测模块62和数据库63。

资源信息探测模块61负责收集网格资源信息和监控网格资源的变化，它监控网格资源平台7中的各网格资源节点，将定期收集的静态和动态资源信息保存在数据库63中，同时，如果有资源加入或离开(或发生故障不能访问)，资源信息探测模块61会及时通知资源可用性预测模块62。

资源可用性预测模块62负责对资源的未来可用性进行预测，它基于马尔科夫预测模型构建资源可用性状态空间和状态转移矩阵。资源可用性预测模块62接收资源信息探测模块61的信号，并与数据库63进行交互，及时地更新资源节点的状态空间和状态转移矩阵，并将更新结果保存于数据库63。

数据库63用于保存网格资源节点的性能信息以及各资源节点的可用性状态空间和状态转移矩阵，它接收来自资源信息探测模块61和资源可用性预测模块62的信息并更新数据库，同时它也接受作业完成时间预测模块5和调度决策模块4中资源作业匹配模块44的信息查询。

下面对本发明的工作流程分别加以介绍：

(1)作业预调度流程(如图5所示)

(1.1)系统接收到用户通过作业提交接口模块1提交的作业；

(1.2)作业QoS解析模块31对作业进行解析，提取作业QoS需求信息；

(1.3)作业排队模块32判断作业QoS等级，如果属于无作业期限限制，则把作业加入无QoS队列33；

(1.4)作业排队模块32预测作业在各网格资源节点的预期完成时间；

(1.5)求作业在资源节点的平均运行时间T；

(1.6)如果Tn+(1+λ)T≥Td，作业加入高QoS对列(Tn为系统当前时间，Td为作业完成期限限制时间，0＜λ≤1)；

(1.7)否则，作业加入低QoS对列。

(2)作业调度决策流程(如图6所示)

(2.1)作业提取模块41分别从高、低、无QoS对列33、34和35中提取作业；

(2.2)资源作业匹配模块44计算作业在各资源上的可靠性代价；

(2.3)资源作业匹配模块44与调度策略模块43交互，将作业调度到可靠性代价最低的资源节点上；

(2.4)资源作业匹配模块44与容错策略模块42交互，如果作业属于高QoS作业，则对作业实施主副本同时运行策略；

(2.5)如果作业属于低QoS作业，则对作业实施主副本异步运行策略；

(2.6)如果作业属于无QoS作业，则对作业实施重试容错策略。

下面举例说明本系统实施过程中的配置情况。

为了验证本发明系统的可行性和有效性，在真实环境下配置本发明系统。在具有40个节点机的集群系统构建一个适用于网格环境的基于可靠性代价的作业调度系统。其基本配置如表1所示：

表1系统的配置例示

 CPU  内存  硬盘  网卡  操作系统  网络 2个CPU×4核  8G  74G  3C905B  Linux AS 4  100M交换机

其中，一台作为前端机，部署作业提交接口模块1，用户通过作业提交接口模块1进行作业提交。两台部署作业调度模块2，其中一台部署预调度模块3、调度决策模块4；另一台部署作业完成时间预测模块5和资源信息模块6。其余37台模拟网格资源平台7，它代表网格资源节点，每个资源节点都有不同的可靠性。

经过试验测试，可以实现以下操作：

(1)资源信息模块6能够及时地探测到底层网格资源节点的性能变化，并可以有效地预测网格资源节点未来的可用性。

(2)作业完成时间预测模块5基于数学模型构建，结合网格资源的性能信息，可以准确地预测作业的预期完成时间。

(3)基于作业的QoS需求，以及对作业完成时间的预测和网格资源节点的未来可用性预测，对作业进行基于可靠性代价调度，并为作业选择优化的容错策略。

(4)试验数据表明，本系统可以提高作业运行成功率、系统吞吐量以及负载均衡。