张艮山 刘旭宁

(石家庄学院信息技术系 河北 石家庄 050035)

0 引 言

根据需求的不同，云计算可以动态地将资源提供至用户任务，实例租用方式是即付即用的，这与传统计算模式不同，其更为灵活的特征给云计算作为处理科学工作流任务以及实施工作流调度带来了极大的便利。大规模科学工作流应用的常规建模形式是图论中的有向无环图DAG，图中顶点代表工作流中大量相互依赖或相互独立的任务集。这些任务间或存在着直接关联(执行先后有严格次序)，或无直接关联可并行执行。为了满足云工作流的服务质量，工作流调度需要在既定约束条件下搜索有效调度方案，将工作流结构中的各个任务映射和调度至云资源实例上，并优化目标函数。

云计算按需提供和即付即用的资源使用方式使得目前的任务调度算法具有以下不足：1) 实例租用价格没有利用更切合实际的商业云账单模型；2) 实例利用时间相对固定；3) 在考虑多种约束条件的工作流调度问题时，所使用的启发式算法或搜索算法时间复杂度较高，实施成本太大。针对1)，本文在设计工作流调度算法中应用Amazon EC2的实例账单价格模型，同时在已经支付的账单周期中，前一任务的空闲账单时间仍可被其他调度任务所利用，以此节省任务执行代价。针对2)，本文所考虑的场景中一旦实例空闲即可释放，资源获取更加灵活，资源利用也更加充分。针对3)，本文不仅同步考虑预算和期限的双重约束，还同步优化执行效率和代价，设计了更加高效复杂度更低的调度算法。……