王 旖 旎

(重庆商务职业学院 重庆 401331)

0 引 言

云计算是一种革新式的应用，可以以即付即用的计算模式提供按需形式的应用、平台、基础设施[1-3]。本质上，云提供者需要部署大量的虚拟机以满足广泛分布的用户需求，同步地为云提供方和用户方降低运营代价。此外，云提供方可以根据平台负载动态地调整可用的虚拟机资源，从而进一步做到代价的节省。有赖于云计算低代价、弹性应用、高可用性的特征，云计算平台可执行的应用领域也越来越广泛[4-6]。一种描述应用过程的典型模式即为工作流，它由多数量的具有数据相关性的任务图组成，通常以有向无环图的形式描述[6-8]。对于云平台而言，该类工作流应用拥有实时性的特征，主要体现在两个方面，一是广泛分布的用户的动态发送请求，其到达时间是无法预知的；二是其需要逻辑上和临时计算上的正确性，进而确保工作流处理的时效要求。

目前，大量工作集中在云平台上的工作流调度问题上。但是，多数已有工作流集中于单一工作流调度，且无法处理实时工作流调度问题。原因在于：首先，调度实时工作流任务时，由于工作流任务间的数据依赖性导致大量虚拟机的空闲时槽无法利用；其次，若按序调度实时工作流，通过合并不同资源上的工作流任务降低空闲时槽的方法可能增加算法的复杂性。更糟的是，合并工作流任务可能延迟任务的执行时间，从而导致工作流执行的截止时间无法得到保证。……