论文部分内容阅读
随着社会的发展,不同领域所需计算和存储的工作流规模日益增大,计算流程也日益复杂,将数据计算和数据存储从传统PC端迁移到云端,从而获得更高的计算效率已成为普遍趋势。云计算通常采用即用即付机制,并依靠保障服务质量(Quality of Service,QoS)来满足用户需求。常见的QoS包括应用程序截止时间约束等,因此,在本文中,我们着重考虑具有截止时间约束条件的,子任务间具有相互依赖关系的实时多工作流在线调度问题。任务调度一直是云计算中的核心问题,它关系着计算资源能否被高效使用。当前云计算调度算法的研究,大多关注于如何缩减任务集或者工作流整体被处理总时间,而较少关心任务完成率以及从云环境服务提供商的角度去考虑云资源的利用率。在本文中,我们关注的调度目标是提高任务完成率和云资源的利用率,而不是传统的任务集整体被处理时间。为解决云计算环境下实时多工作流调度问题在实际环境中“难以实施”、“规模受限”、以及“缺乏有效的性能基准”等问题,本文设计了一款名叫Real Time Workflow Simulator的实时工作流模拟器,简称为RTWSim,用以支持在线多工作流调度问题的研究。该模拟器可以组建生成一组测试工作流,其包含可指定数量的任务,并且每个任务的子任务间具有相互依赖关系,每个任务具有可预设的截止时间约束。除此之外,这组测试工作流满足存在一种最优调度方案,使得任务在满足截止时间条件的前提下,具有100%的处理器资源利用率和任务完成率。一方面,本模拟器使算法研究人员可以将该工作流测试集作为调度算法的性能测试数据;另一方面,研究人员可将其调度结果与最优调度方案进行对比,从而为其调度算法的改进提供指导性方向。为验证RTWSim实时工作流调度模拟器的正确性和可用性,本文通过使用RTWSim生成的工作流测试集,测试了四种经典的传统单处理器调度算法在多处理器环境下对实时工作流的调度性能。此外,在RTWSim的辅助下,本文还提出了两种新的云计算多工作流实时调度算法,ELDF(Earliest Level-Deadline First)和 LREB(Level Relaxing and Elastic Backfilling)。ELDF算法很好的改进了经典EDF算法不适用于实时工作流的在线调度的问题。LREB算法利用可伸缩的回填机制和分层松弛机制成功提高了任务完成率和处理器资源有效利用率。