时间约束下可靠性增强的网格工作流调度算法  

Reliable Scheduling Algorithm for Time-constrained Grid Workflow

作　　者：阎朝坤[1,2] 胡志刚[1] 李玺[1] 肖鹏[3] 

机构地区：[1]中南大学信息科学与工程学院,长沙410083 [2]河南大学计算机与信息工程学院,河南开封475004 [3]湖南工程学院计算机与通信系,湖南湘潭411104

出　　处：《小型微型计算机系统》2012年第7期1528-1532,共5页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(60970038)资助

摘　　要：如何在动态性极强的网格环境中有效调度工作流应用并满足用户的QoS需求是一个难题.传统的基于资源静态特征的启发式调度算法或预留策略缺乏对资源动态服务能力的有效评估而无法保证工作流应用的截止时间约束.本文采用随机服务模型建模网格资源的动态性能并考虑资源内处理单元失效的情况.利用生灭过程描述资源节点中处理单元数目的变化情况并给出了资源节点在任务截止时间内的可靠性评估方法.在此基础上,提出一种可靠性增强的网格工作流调度算法RSA_TC.实验结果表明RSA_TC算法相对于DSESAW和PFAS算法,能有效保证用户截止时间的要求,对动态网格环境有较好的自适应性.Scheduling scientific workflow which can satisfy deadline constraint is a complicated problem because of the dynamicity of Grid resource.Various strategies were proposed,including static heuristic scheduling strategies and reservation strategies.However,the existing scheduling strategies can not provide guarantee for deadline because of lacking efficient evaluation for dynamic service capacity of resource.Birth-death process was utilized to describe the change of numbers of process unit in a resource node.A novel evaluation method of resource capacity based on stochastic service model was proposed in the paper.Then,aimed at workflow scheduling with deadline constraint,a reliability enhanced scheduling algorithm was presented.The results of extensive simulation experiments show that the proposed algorithm outperforms DSESAW and PFAS,with respect to guarantee deadline and adaptability to dynamic Grid environment.

关 键 词：网格 工作流 生灭过程 随机服务模型 截止时间 失效 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]