QoS约束下基于双向分层的网格工作流调度算法  

QoS-constrained Workflow Scheduling Algorithm for Grid Computing Based on Two-way Stratified

作　　者：姚磊[1] 戴冠中[1] 张慧翔[1] 任帅[1] 

机构地区：[1]西北工业大学自动化学院,西安710072

出　　处：《计算机科学》2009年第9期24-27,共4页Computer Science

基　　金：国防基础科研项目(C2720061361)资助

摘　　要：为使网格工作流的执行满足用户QoS要求,应用有向无环图描述工作流,并分析其中的关键活动,把用户对工作流的整体QoS约束分割为对单个任务的QoS约束。以此为基础,提出了一种基于双向分层的网格工作流调度算法Q-TWS。该算法通过对工作流正向分层和逆向分层,可以方便并准确找到任务之间的并行关系。Q-TWS可最大程度放松对任务执行时间的约束,在增加调度灵活性的同时又满足用户的QoS要求。实验表明,Q-TWS算法与TL算法相比,在同样的截止时间约束下,工作流执行时间较短,且工作流执行费用较小。In order to meet user＇s QoS requirement for the implementation of grid workflow, the key tasks of the workflow were analyzed firstly, and the QoS of the whole workflow was divided into segments which are the QoS-constrained of a single task. Then, a grid workflow scheduling algorithm （Q-TWS） based on Two-Way Stratified was proposed. Through both positive layering and reverse layering, this algorithm can find the parallel relation between tasks easily and accurately. Q-TWS can relax the task execution time, increase flexibility scheduling and meet user QoS requirements. Simulation results show that Q-TWS has a shorted execution time and a less execution cost compared with BL when the two algorithms have the same deadline.

关 键 词：网格计算 工作流调度 QOS约束 双向分层 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]